Prior art

Prior Art Analysis for US Patent 7,020,281

This analysis details the most relevant prior art cited in US patent 7,020,281. The central innovation of the patent is a method to perform cryptographic operations in a way that is resistant to timing attacks, where an attacker analyzes the time taken for computations to deduce parts of the secret key. The patent's claims focus on two main approaches: ensuring each bit of a secret key is processed using similar, constant-time operations (Claim 1), and recoding the key into a signed-digit format to regularize the process (Claim 6).

The foundational concept of timing attacks was introduced in a 1996 paper by Paul C. Kocher, which is cited as a non-patent reference. Kocher's work identified the vulnerability in common cryptographic implementations, such as the square-and-multiply algorithm, where operations for a '1' bit take a different amount of time than for a '0' bit. This paper established the problem that US 7,020,281 and much of the cited prior art aim to solve.

Below are the most relevant patent citations and their potential impact on the claims of US 7,020,281.

---

1. US Patent 6,298,442 B1: "Secure modular exponentiation with leak minimization for smartcards and other cryptosystems"

• Full Citation: US Patent 6,298,442 B1. Assignee: Cryptography Research, Inc. Publication Date: Oct. 2, 2001. Filing Date: Jun. 3, 1998.
• Brief Description: This patent, by inventor Paul C. Kocher, describes methods to protect cryptographic systems from side-channel attacks, including timing and power analysis. A key technique disclosed is "blinding," where the input message is multiplied by a random number before the exponentiation and the result is later corrected by dividing out the effect of the random number. This makes the relationship between the computation time and the secret key statistically insignificant to an attacker. It also suggests ensuring that the sequence of operations (e.g., squares and multiplies) is independent of the key's bit values.
• Potential Anticipation:
  • Claim 1 & 6: While the '442 patent's primary method of blinding is different from the specific state-based, inverse-operation method of Claim 1 or the signed-digit recoding of Claim 6, it directly addresses the same problem with the same goal. The '442 patent's disclosure of making the sequence of operations independent of the key's bits could be interpreted as anticipating the core principle of performing "similar operations" for each bit. For example, it teaches performing a multiplication for every bit, using the real intermediate value if the bit is '1' and a dummy value if the bit is '0', which results in a constant execution flow. This directly anticipates the motivation and general method of making operations uniform, which is the foundation of Claim 1.

2. US Patent 5,991,415 A: "Method and apparatus for protecting public key schemes from timing and fault attacks"

• Full Citation: US Patent 5,991,415 A. Assignee: Yeda Research And Development Co. Ltd. Publication Date: Nov. 23, 1999. Filing Date: May 12, 1997.
• Brief Description: This patent discloses methods to thwart timing and fault attacks on cryptographic systems like RSA. One of its key teachings is to make the exponentiation process uniform. It describes performing a modular multiplication at each step of the square-and-multiply loop, regardless of whether the corresponding key bit is a zero or a one. This ensures that the execution time is not correlated with the key's bit values.
• Potential Anticipation:
  • Claim 1: The method described in the '415 patent appears to anticipate the core inventive concept of Claim 1. Claim 1 requires that "each of said predetermined bits... is processed with similar operations, thereby inhibiting disclosure." The '415 patent teaches always performing a square and a multiplication, which constitutes "similar operations" for each bit to achieve the same goal. While the specific state-machine logic of Claim 1 in US 7,020,281 (using an inverse element for '0' bits) differs in implementation, the fundamental principle of a constant-time, uniform sequence of operations for every bit is clearly disclosed in the '415 patent.

3. US Patent 6,175,850 B1: "Scheme for carrying out modular calculations based on redundant binary calculation"

• Full Citation: US Patent 6,175,850 B1. Assignee: Nippon Telegraph And Telephone Corporation. Publication Date: Jan. 16, 2001. Filing Date: Feb. 3, 1997.
• Brief Description: This patent describes a method for modular exponentiation using a "redundant binary representation" for the exponent. In this representation, digits can be {-1, 0, 1}. This recoding allows for a more uniform calculation process. The algorithm processes the exponent from the most significant digit and performs operations based on whether the digit is 1, 0, or -1. Using -1 allows subtractions, which can reduce the number of operations and regularize the calculation flow.
• Potential Anticipation:
  • Claim 6: This patent appears highly relevant and potentially anticipates Claim 6. Claim 6 explicitly requires "recoding said binary vector to produce a signed digit representation of plus one and minus one digits" and then performing addition or subtraction based on that representation. The '850 patent teaches the use of a redundant binary representation (which includes +1 and -1) for the exponent to perform modular calculations. This is the central feature of Claim 6.

4. US Patent 6,366,673 B1: "Method and device for executing a decrypting mechanism through calculating a standardized modular exponentiation for thwarting timing attacks"

• Full Citation: US Patent 6,366,673 B1. Assignee: U.S. Philips Corporation. Publication Date: Apr. 2, 2002. Filing Date: Sep. 16, 1997.
• Brief Description: This patent focuses on preventing timing attacks by making the modular exponentiation algorithm execute in a fixed amount of time. It explicitly teaches performing a squaring operation followed by a multiplication operation for each bit of the exponent, regardless of the bit's value. This ensures a constant execution path and time.
• Potential Anticipation:
  • Claim 1: Similar to the '415 patent, the '673 patent discloses the core idea of making the cryptographic loop constant-time by performing uniform operations for every bit. It anticipates the fundamental concept of Claim 1, which is to process each bit with "similar operations" to prevent timing analysis. The specific implementation in US 7,020,281 (using states and inverse elements) is a variation on this established theme of constant-time execution paths.