Facebook Inc v. BlackBerry Ltd

1. Case Identification

• Case #: IPR2019-00923
• Patent #: 7,372,961
• Filed: April 3, 2019
• Petitioner(s): Facebook, Inc., Instagram, LLC, and WhatsApp Inc.
• Patent Owner(s): BlackBerry Limited
• Challenged Claims: 1, 2, 5, 15, 16, 19, 23, 24, and 27

2. Patent Overview

• Title: Method of Public Key Generation
• Brief Description: The ’961 patent discloses a method for generating a cryptographic key for use in the Digital Signature Algorithm (DSA). The method purports to remedy "modulo bias," a known issue where using a standard modular reduction operation can cause smaller key values to be generated more frequently, by instead using a rejection sampling technique.

3. Grounds for Unpatentability

Ground 1: Obviousness of Claims 1, 2, 5, 15, 16, and 19 over DSS in view of Schneier and Rose

• Prior Art Relied Upon: DSS (Federal Information Processing Publication 186, 1994), Schneier (Applied Cryptography, 2d ed. 1996), and Rose (a 1993 USENET article).
• Core Argument for this Ground:
  • Prior Art Mapping: Petitioner argued that the Digital Signature Standard (DSS) discloses all steps of the claimed method except for the specific technique used to avoid modulo bias. DSS teaches generating a key by creating a seed value, hashing it to produce an integer, and then performing a modular reduction (mod q) to ensure the final key k is within a desired range. This modular reduction, however, introduces the very bias the ’961 patent addresses. Rose, a USENET article, explicitly identifies the modulo bias problem and teaches the exact solution claimed in the ’961 patent: generate a number, check if it is "too big" (i.e., outside the desired range), and if so, "throw away any result... and try again." This is the claimed rejection sampling method. Schneier was cited to support the use of "true" random numbers for key generation, as taught in DSS.
  • Motivation to Combine: A POSITA implementing the key generation algorithm in DSS would have recognized the potential for modulo bias, an issue the ’961 patent admits was known. Rose directly addresses this exact problem and provides a simple, explicit solution. Therefore, Petitioner asserted a POSITA would combine Rose's rejection sampling technique with the DSS algorithm to improve key strength by ensuring a uniform distribution of random numbers, thereby avoiding the known bias.
  • Expectation of Success: Petitioner contended that combining the teachings would have been straightforward. Rose provides a simple, generic technique with sample source code that could be readily applied to any random number generation process, including the one in DSS, with a predictable result.

Ground 2: Obviousness of Claims 1, 2, 5, 15, 16, and 19 over DSS in view of Schneier and Menezes

• Prior Art Relied Upon: DSS (Federal Information Processing Publication 186, 1994), Schneier (Applied Cryptography, 2d ed. 1996), and Menezes (Handbook of Applied Cryptography, 1997).

• Core Argument for this Ground:

  • Prior Art Mapping: This ground presented a similar argument to Ground 1, but substituted the Rose reference with Menezes. Menezes, a widely known cryptography textbook co-authored by two of the ’961 patent’s inventors, also teaches the claimed rejection sampling method. Menezes explains that to obtain a random integer within a specific interval [0, n], one can generate a random bit sequence; "if the resulting integer exceeds n, one option is to discard it and generate a new random bit sequence." This directly teaches the core steps of determining if a generated number is outside the desired range and, if so, rejecting it and repeating the process.
  • Motivation to Combine: Similar to the motivation for combining Rose, a POSITA would combine Menezes with DSS to solve the known modulo bias problem and generate stronger, uniformly distributed cryptographic keys. Menezes expressly states its technique generates "uniformly distributed" numbers, which was known to be preferable for cryptographic security. The motivation was to improve the existing DSS standard with a well-known, alternative technique for constraining a random number to a desired range.
  • Expectation of Success: The combination was argued to be simple and predictable. Menezes presents rejection sampling as a standard option for generating random numbers in a specific range, suggesting its implementation would be routine for a POSITA.

• Additional Grounds: Petitioner asserted additional obviousness challenges (Grounds 3 and 4) against claims 23, 24, and 27. These grounds mirrored Grounds 1 and 2, respectively, but added Rao (a 1974 textbook) and Floyd (a 1987 textbook) to demonstrate that the claimed "arithmetic processor" was a fundamental, ubiquitous component of general-purpose computers and thus obvious to use for performing the claimed method steps.

4. Key Claim Construction Positions

• Petitioner argued that the disputed term “reducing mod q” should be construed as simply "determining the remainder of dividing a number by q." Petitioner asserted that this construction is consistent with the term's plain meaning in the art and does not require that the operation always result in a numerically lower value (e.g., 5 mod 10 = 5). This construction was important because it supported the argument that Rose's method satisfies the claim limitation of performing the determination step "prior to reducing mod q," as the final mod operation in Rose occurs only after the rejection loop is complete.

5. Arguments Regarding Discretionary Denial

• Petitioner argued that discretionary denial under §325(d) would be inappropriate because the petition did not present the "same or substantially the same prior art or arguments" previously presented to the Office. Although the examiner considered eight pages of the Schneier textbook during prosecution, those pages related to a general description of the DSA. Petitioner, in contrast, relied on different, earlier sections of Schneier concerning the generation of "true" random numbers. Furthermore, the primary references teaching the claimed rejection sampling method, Rose and Menezes, were never considered by the examiner.

6. Relief Requested

• Petitioner requested institution of an inter partes review and cancellation of claims 1, 2, 5, 15, 16, 19, 23, 24, and 27 of the ’961 patent as unpatentable.