Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 03/11/2025 has been considered by the examiner.
Drawings
The drawing submitted on 03/11/2025 has been accepted.
Specification
The specification submitted on 03/11/2025 has been accepted.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-4, 6-18 and 20-22 are rejected under 35 U.S.C. 103 as being unpatentable over DE HOOGH US 20220182218 A1 in view of Golic US 20090052657 A1.
As pe claim 1: DE HOOGH discloses a method to perform a cryptographic operation, the method comprising:
identifying, by a processing device, a polynomial associated with a ciphertext input into the cryptographic operation ([0043] The above computation which works for linear operators does not work for non-linear operators, in particular substitutions boxes, such as the S-box of AES. Interestingly, any non-linear operation on a data element may be represented as a polynomial. For example, a non-linear transformation f on bytes is a polynomial on the finite field F.sub.256 . [0083] Furthermore, a convolution computes simultaneously the point-wise product of all the Fourier Coefficients, as opposed to the linear transformation, where one has the freedom to specify what happens which each separate Fourier Coefficient. Each linear operation can be hidden in this matrix. In fact, any two non-linear functions can be written as polynomials and can be evaluated in parallel in different Fourier Coefficients. Indeed, using a convolution network all relevant powers of the inputs can be computed in parallel, while the inner-product with the polynomial coefficients (the only difference between the polynomials) is linear and, hence, can be computed in parallel by a matrix product);
obtaining, by the processing device, a discrete transform (DT) of the polynomial for a plurality of elements of a finite field, wherein obtaining the DT of the polynomial ([0041] Embodiments make use of the discrete Fourier transform in the finite field. For example, in case data-elements are bytes the finite field may be F.sub.256 the finite field with 256 elements. In an embodiment, the data-elements are binary words comprising multiple bits; in this case, a finite field with characteristic 2 is appropriate and size 2 to the power of the number of bits. This is not necessary though. One could construct a block cipher operating on words of, e.g., ternary bits, in which case the finite field may have characteristic 3, etc. Below computing with sets of shares is introduced and it is explained how they relate to the Fourier transform ([0092-0093] In box 330, discrete Fourier transforms of the share sets in 320 are shown. Shown are sets of Fourier coefficients 331, 332 and 333. For example, set of Fourier coefficients 331 may be obtained by applying a discrete Fourier transform in a finite field to share set 321. The sets of Fourier coefficients in box 330 are not encoded either, and cannot be stored in a memory in this way either in a white-box implementation. Box 340 shows the internal state represented as sets of encoded shares. The data in box 340 may be obtained from box 320 by encoding each share in each set separately. For example, by encoding the first share in set 321 one may obtain the first share in set 341, etc. In an embodiment, only the data shown in box 340 may be directly visible, e.g., may be physically stored in the memory); comprises:
randomizing a set of basis vectors for the finite field to obtain a first randomized set of basis vectors ([0149] If multiple Fourier coefficients together represent an input data element (e.g. as the sum), all but one of the Fourier coefficient may be selected at random, and the last one may be computed from the input data element and the selected random Fourier coefficients. For the remaining protective Fourier coefficients, random choices may be made satisfying the relationship. A random Fourier coefficient may be selected by applying a random operator to the input data. In white-box implementations it is often inadvisable to use a separate random number generator. For a grey-box implementation only, the random Fourier coefficients could be selected by a random number generator. [0151] an inverse Fourier transform, and [0152] an encoding operation, e.g., to encode each of the shares. The encodings may be chosen linear. There may be multiple different encodings. For example, for each one of the shares a different encoding may be used);
obtaining, using the first randomized set of basis vectors, a first reduced set of basis vectors ([0112] Relationships can also be defined between Fourier coefficients within the same set of Fourier coefficients. This may reduce the number of valid representations of an internal state as a set of shares, but this may be acceptable. For example, the number of valid representation may still be large enough, in particular the number of valid representation may still be large enough to represent all entropy of the input data to the cryptographic operation, e.g., in case the entire internal state is represented in the set of Fourier coefficients. For example, a good choice is to pick Fourier coefficients with consecutive indices as protective elements, and set the values of said Fourier coefficients to predetermined, fixed values. It can mathematically be shown that in order to create a different set of Fourier coefficients with the predetermined values in, say, b consecutive Fourier coefficients, an attacker must change at least b+1 bytes of the set of shares. The predetermined, fixed values may be chosen randomly at compile time);
identifying, based on the polynomial, a first polynomial and second polynomial ([0162] For the additive transformations AddRoundKey, ShiftRows and MixColumns this can be achieved by a suitable choice of the transformation on the Fourier coefficients, as will is detailed herein, while for the SubBytes operation this property can be guaranteed since the Fourier transform is compatible with polynomials acting on share sets. In this embodiment, one particular choice for the relationship is made. Moreover, the zeroth Fourier coefficient is used to represent a data element of internal state); and
computing the DT of the polynomial using the first reduced set of basis vectors, the DT of the first polynomial, and the DT of the second polynomial ([0112] Relationships can also be defined between Fourier coefficients within the same set of Fourier coefficients. This may reduce the number of valid representations of an internal state as a set of shares, but this may be acceptable. For example, the number of valid representation may still be large enough, in particular the number of valid representation may still be large enough to represent all entropy of the input data to the cryptographic operation, e.g., in case the entire internal state is represented in the set of Fourier coefficients); and
computing, by the processing device, a plaintext output corresponding to the ciphertext input using the DT of the polynomial ([0161] a cryptographic primitive implemented in a cryptographic device or method according to the invention. The chosen cryptographic primitive is the AES block cipher, chosen as an illustration. The decryption operation follows straightforward. The embodiments shown in detail below use a single representing Fourier coefficient for each set of Fourier coefficients. In total 16*17 bytes of encoding for the internal states are used).
DE HOOGH does not explicitly disclose the first polynomial and the second polynomial are a first auxiliary polynomial and a second auxiliary polynomial. Golic, in analogous art however, discloses the first polynomial and the second polynomial are a first auxiliary polynomial and a second auxiliary polynomial ([0074] A functional block adapted to implement (in hardware or software or a mix of the two) the double-and-add algorithm receives in input the base point P and the scalar k, and, at the end of the computation, returns the desired result of the scalar multiplication as a resulting point Q, which is also used as an auxiliary variable during the computations. The base point P and the resulting point Q are both represented in affine coordinates. For example, the left-to-right implementation of the double-and-add algorithm, where the intermediate point (auxiliary variable) Q is represented in affine coordinates is given as follows. In case neither of the two conditions above are satisfied, the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q is added (adder 105) to the initial value x.sub.2.sup.(1) of the coordinate x.sub.2 of the point P, to obtain a first value u.sup.(1) for the auxiliary variable u. Then, the first value u.sup.(1) for the auxiliary variable u is inverted (inverter 107) to obtain a second value u.sup.(2) for the auxiliary variable u. Afterwards, the initial value y.sub.1.sup.(1) of the coordinate y.sub.1 of the point Q is added (adder 109) to the initial value y.sub.2.sup.(1) of the coordinate y.sub.2 of the point P, to obtain a first value v.sup.(1) for the auxiliary variable v. Then, the second value u.sup.(2) for the auxiliary variable u is multiplied (multiplier 111) by the first value v.sup.(1) for the auxiliary variable v, to obtain a third value u.sup.(3) for the auxiliary variable u. The third value u.sup.(3) for the auxiliary variable u is then added (adder 113) to the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q, to obtain a second value v.sup.(2) for the auxiliary variable v. The third value u.sup.(3) for the auxiliary variable u is then multiplied by itself (multiplier 115) to obtain a third value v.sup.(3) for the auxiliary variable v. The third value v.sup.(3) for the auxiliary variable v is then added (adder 117) to the third value u.sup.(3) for the auxiliary variable u to obtain a fourth value v.sup.(4) for the auxiliary variable v. Then, the fourth value v.sup.(4) for the auxiliary variable v is added (adder 119) to the value x.sub.2.sup.(1) of the coordinate x.sub.2 of the point P, to obtain a fifth value v.sup.(5) for the auxiliary variable v. The fifth value v.sup.(5) for the auxiliary variable v is then added (adder 121) to the constant a, i.e., the elliptic curve parameter, to obtain a sixth value v.sup.(6) for the auxiliary variable v. The sixth value v.sup.(6) for the auxiliary variable v is then added (adder 123) to the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q, to obtain an updated, second value x.sub.1.sup.(2) of the coordinate x.sub.1 of the point Q. The third value u.sup.(3) for the auxiliary variable u is then multiplied (multiplier 125) by the sixth value v.sup.(6) for the auxiliary variable v, to obtain a fourth value u.sup.(4) for the auxiliary variable u. The fourth value u.sup.(4) for the auxiliary variable u is then added (adder 127) to the second value x.sub.1.sup.(2) of the coordinate x.sub.1 of the point Q to obtain a fifth value u.sup.(5) for the auxiliary variable u. Finally, the fifth value u.sup.(5) for the auxiliary variable u is added (adder 129) to the initial value y.sub.1.sup.(1) of the coordinate y.sub.1 of the point Q, to obtain an updated, second value y.sub.1.sup.(2) of the coordinate y.sub.1 of the point Q). Therefore, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the claimed limitations of the first polynomial and the second polynomial disclosed by DE HOOGH are a first auxiliary polynomial and a second auxiliary polynomial. This modification would have been obvious because a person having ordinary skill in the art would have been motivated by the desire to apply elliptic-curve cryptography more safely against side-channel attacks. It focuses on the main ECC operation called scalar multiplication, where a secret number is used to multiply a point on an elliptic curve. to make less revealing by using a balanced Extended Euclidean Algorithm; and randomize the scalar by adding a random multiple of the point order and reduce leakage from timing, power consumption, and similar measurements as suggested by Golic ([0047-0051]).
As per claim 2:. DE HOOGH in view of Golic disclose the method of claim 1, wherein the DT comprises Additive Fast Fourier Transform (DE HOOGH [0051] The inventors had the insight that a white-box device could hide cryptographic data in Fourier coefficients. The device would still act on a set of shares, or on multiple sets of shares, but the relevant data would be coded in the set or sets of Fourier coefficients that correspond to the set of shares. This has several consequences. The sets of Fourier coefficients themselves are not directly stored in the device. The Fourier coefficients only become available by computing them from a set of shares. However, since the Fourier transform is linear, the Fourier transform can be hidden efficiently by combining it with the affine operations in the cryptographic algorithm and the encoding of the shares).
As per claim 3:. DE HOOGH in view of Golic disclose the method of claim 1, wherein randomizing the set of basis vectors comprises multiplying the set of basis vectors by a randomization matrix comprising one or more random elements (DE HOOGH [0126] The input to the linear operation may be, e.g., a vector with as elements the shares of two or more sets of shares. For example, in so-far a linear operator acts on Fourier coefficients that represent the data value, they can perform the linear operation needed for the cryptographic primitive, e.g., as desired by a standard; but in so-far the one or more linear operators act only on Fourier coefficients that do not represent the data value, they can perform any linear operation, e.g., a random linear operation, so long as the relationship is preserved).
As per claim 4:. DE HOOGH in view of Golic disclose method of claim 1, wherein randomizing the set of basis vectors comprises permuting two or more vectors of the set of basis vectors (DE HOOGH [0096] FIG. 3b shows an example, in which one of the Fourier coefficients has been randomly chosen at compile time as the representing coefficient. In fact, which Fourier coefficient represents the data value may even vary per round, e.g., per update of the internal state. For example, after the next update, in set 331 it may be the Fourier coefficient of index 2, while in set 332 it is the Fourier coefficient of index 3, etc. For example, the Fourier coefficients may be permuted in an affine part of the round function).
As per claim 6:. DE HOOGH in view of Golic disclose method of claim 1, wherein the polynomial is obtained by combining an input polynomial with a masking polynomial, and wherein computing the plaintext output comprises: obtaining the DT of the input polynomial using the DT of the polynomial (DE HOOGH [0147] As noted, some of the operations may be keyed. For example, in an operation a round key may be added to all or part of the internal state. The key may be stored in device 100 in an encoded form. Preferably, the keys use the same type encoding as the internal state does, e.g., as set of (encoded) shares with restrictions imposed on the Fourier coefficients of the sets. For example, the key may be represented in a memory of device 100 as a corresponding set of shares, the set of shares satisfying the predetermined relationship between the Fourier coefficients corresponding to the set of shares of the key according to the discrete Fourier transform in the finite field); and
computing the plaintext output using the DT of the input polynomial (DE HOOGH [0139] For example, one may select a fixed constant as input for coefficients IV, in which case the same input should occur on the output. One could also use the same input coefficients IV as for coefficients I, so that the original input is present at the output. The latter may be used by producing not the regular output, but the regular output plus (say xor) the input. To obtain the regular output one would have to subtract (say xor) the input).
As per claim 7:. DE HOOGH in view of Golic disclose method of claim 6, wherein the masking polynomial is one of a first-degree polynomial or a second-degree polynomial (Golic [0011] A binary polynomial field F.sub.2.sub.m, i.e., a finite field of characteristic 2, is a finite field with 2.sup.m elements, where m is a positive integer, which represents the dimension or the bit size of the field F.sub.2.sub.m. It is composed of a set of polynomials over the binary field F.sub.2 whose degree is at most m-1, together with the operations of addition and multiplication defined as addition and multiplication of polynomials modulo an irreducible polynomial of degree m over F.sub.2, respectively. By irreducible polynomial over F.sub.2 there is meant a polynomial that cannot be written as a product of two polynomials over F.sub.2 having degrees of at least 1. In other words, the elements of the field F.sub.2.sub.m, are binary polynomials of degree less than m, and, given an irreducible polynomial f(z) of degree m, called "reduction polynomial", the sum of two elements a(z) and b(z), also denoted as a+b, is defined as (a(z)+b(z)) mod f(z)=a(z)+b(z), that is, the coefficients are simply bitwise added, which is an operation also denoted as a a.sym.b, and the product of the two elements a(z) and b(z), also denoted as ab, is defined as (a(z)b(z)) mod f(z), that is, as the remainder obtained after dividing the product a(z) b(z) by f (z)).
As per claim 8:. DE HOOGH in view of Golic disclose method of claim 1, wherein the finite field comprises a GF(2m) field, wherein m is an integer number (Golic [0011] A binary polynomial field F.sub.2.sub.m, i.e., a finite field of characteristic 2, is a finite field with 2.sup.m elements, where m is a positive integer, which represents the dimension or the bit size of the field F.sub.2.sub.m. It is composed of a set of polynomials over the binary field F.sub.2 whose degree is at most m-1, together with the operations of addition and multiplication defined as addition and multiplication of polynomials modulo an irreducible polynomial of degree m over F.sub.2, respectively. By irreducible polynomial over F.sub.2 there is meant a polynomial that cannot be written as a product of two polynomials over F.sub.2 having degrees of at least 1).
As per claim 9:. DE HOOGH in view of Golic disclose method of claim 1, wherein the polynomial is representative of a locator polynomial of an error correction code, and wherein computing the plaintext output comprises identifying one or more roots of the locator polynomial using the DT of the polynomial (DE HOOGH [0064] An embodiment, using a single representing element for each set of Fourier coefficients may be described in summary as follows. Suppose we have n shares x=x.sub.0, . . . ,x.sub.n−1 representing a secret x over some finite field [AltContent: rect] of order q. Let α ϵ [AltContent: rect] be a primitive n-th root, e.g., n ϵ [AltContent: rect] is the smallest power such that α.sup.n≡1. Recall that n should divide q−1. The Fourier Transform of x is defined as {circumflex over (x)}, where {circumflex over (x)}.sub.i=Σ.sub.j=0.sup.n−1α.sup.i*jx.sub.j).
As per claim 10: DE HOOGH discloses a method to perform a cryptographic operation, the method comprising:
identifying, by a processing device, a polynomial associated with a ciphertext input into the cryptographic operation ([0043] The above computation which works for linear operators does not work for non-linear operators, in particular substitutions boxes, such as the S-box of AES. Interestingly, any non-linear operation on a data element may be represented as a polynomial. For example, a non-linear transformation f on bytes is a polynomial on the finite field F.sub.256 . [0083] Furthermore, a convolution computes simultaneously the point-wise product of all the Fourier Coefficients, as opposed to the linear transformation, where one has the freedom to specify what happens which each separate Fourier Coefficient. Each linear operation can be hidden in this matrix. In fact, any two non-linear functions can be written as polynomials and can be evaluated in parallel in different Fourier Coefficients. Indeed, using a convolution network all relevant powers of the inputs can be computed in parallel, while the inner-product with the polynomial coefficients (the only difference between the polynomials) is linear and, hence, can be computed in parallel by a matrix product);
combining, by the processing device, the polynomial with a masking polynomial to obtain a masked polynomial ([0037] A countermeasure to defend against the latter type of attacks is the masking of variables by using multiple shares to represent them. For example, a variable x can be additively represented by n shares x.sub.0, . . . ,x.sub.n−1, where n≥2 and x.sub.0 ⊕ x.sub.1 ⊕ . . . ⊕ x.sub.n−1=x. Here addition is the XOR operation. For example, in hardware implementations, one may choose n−1 of the shares randomly and calculate the remaining one such that the n shares represent the variable x. Then a simultaneous collision on any set of k shares, where k<n, does not reveal any information about whether a collision occurs on variable x; only if a simultaneous collision occurs on all n shares, the attacker can infer that a collision occurs on x. An n-th order DPA attack is thus needed to extract the key.
obtaining, by the processing device, a discrete transform (DT) of the masked polynomial for a plurality of elements of a finite field, wherein obtaining the DT of the masked polynomial ([0041] Embodiments make use of the discrete Fourier transform in the finite field. For example, in case data-elements are bytes the finite field may be F.sub.256 the finite field with 256 elements. In an embodiment, the data-elements are binary words comprising multiple bits; in this case, a finite field with characteristic 2 is appropriate and size 2 to the power of the number of bits. This is not necessary though. One could construct a block cipher operating on words of, e.g., ternary bits, in which case the finite field may have characteristic 3, etc. Below computing with sets of shares is introduced and it is explained how they relate to the Fourier transform ([0092-0093] In box 330, discrete Fourier transforms of the share sets in 320 are shown. Shown are sets of Fourier coefficients 331, 332 and 333. For example, set of Fourier coefficients 331 may be obtained by applying a discrete Fourier transform in a finite field to share set 321. The sets of Fourier coefficients in box 330 are not encoded either, and cannot be stored in a memory in this way either in a white-box implementation. Box 340 shows the internal state represented as sets of encoded shares. The data in box 340 may be obtained from box 320 by encoding each share in each set separately. For example, by encoding the first share in set 321 one may obtain the first share in set 341, etc. In an embodiment, only the data shown in box 340 may be directly visible, e.g., may be physically stored in the memory); comprises:
identifying, based on the masked polynomial, a first polynomial and a second polynomial ([0112] Relationships can also be defined between Fourier coefficients within the same set of Fourier coefficients. This may reduce the number of valid representations of an internal state as a set of shares, but this may be acceptable. For example, the number of valid representation may still be large enough, in particular the number of valid representation may still be large enough to represent all entropy of the input data to the cryptographic operation, e.g., in case the entire internal state is represented in the set of Fourier coefficients. For example, a good choice is to pick Fourier coefficients with consecutive indices as protective elements, and set the values of said Fourier coefficients to predetermined, fixed values. It can mathematically be shown that in order to create a different set of Fourier coefficients with the predetermined values in, say, b consecutive Fourier coefficients, an attacker must change at least b+1 bytes of the set of shares. The predetermined, fixed values may be chosen randomly at compile time); and
computing the DT of the masked polynomial using a set of basis vectors for the finite field, the first polynomial, and the DT of the second polynomial ([0112] Relationships can also be defined between Fourier coefficients within the same set of Fourier coefficients. This may reduce the number of valid representations of an internal state as a set of shares, but this may be acceptable. For example, the number of valid representation may still be large enough, in particular the number of valid representation may still be large enough to represent all entropy of the input data to the cryptographic operation, e.g., in case the entire internal state is represented in the set of Fourier coefficients);
computing, by the processing device and using the DT of the masked polynomial, the DT of the polynomial ([0037] A countermeasure to defend against the latter type of attacks is the masking of variables by using multiple shares to represent them. For example, a variable x can be additively represented by n shares x.sub.0, . . . ,x.sub.n−1, where n≥2 and x.sub.0 ⊕ x.sub.1 ⊕ . . . ⊕ x.sub.n−1=x. Here addition is the XOR operation. For example, in hardware implementations, one may choose n−1 of the shares randomly and calculate the remaining one such that the n shares represent the variable x. Then a simultaneous collision on any set of k shares, where k<n, does not reveal any information about whether a collision occurs on variable x; only if a simultaneous collision occurs on all n shares, the attacker can infer that a collision occurs on x. An n-th order DPA attack is thus needed to extract the key); and
obtaining, by the processing device, a plaintext output corresponding to the ciphertext input using the DT of the polynomial ([0161] a cryptographic primitive implemented in a cryptographic device or method according to the invention. The chosen cryptographic primitive is the AES block cipher, chosen as an illustration. The decryption operation follows straightforward. The embodiments shown in detail below use a single representing Fourier coefficient for each set of Fourier coefficients. In total 16*17 bytes of encoding for the internal states are used).
DE HOOGH does not explicitly disclose the first polynomial and the second polynomial are a first auxiliary polynomial and a second auxiliary polynomial. Golic, in analogous art however, discloses the first polynomial and the second polynomial are a first auxiliary polynomial and a second auxiliary polynomial ([0074] A functional block adapted to implement (in hardware or software or a mix of the two) the double-and-add algorithm receives in input the base point P and the scalar k, and, at the end of the computation, returns the desired result of the scalar multiplication as a resulting point Q, which is also used as an auxiliary variable during the computations. The base point P and the resulting point Q are both represented in affine coordinates. For example, the left-to-right implementation of the double-and-add algorithm, where the intermediate point (auxiliary variable) Q is represented in affine coordinates is given as follows. In case neither of the two conditions above are satisfied, the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q is added (adder 105) to the initial value x.sub.2.sup.(1) of the coordinate x.sub.2 of the point P, to obtain a first value u.sup.(1) for the auxiliary variable u. Then, the first value u.sup.(1) for the auxiliary variable u is inverted (inverter 107) to obtain a second value u.sup.(2) for the auxiliary variable u. Afterwards, the initial value y.sub.1.sup.(1) of the coordinate y.sub.1 of the point Q is added (adder 109) to the initial value y.sub.2.sup.(1) of the coordinate y.sub.2 of the point P, to obtain a first value v.sup.(1) for the auxiliary variable v. Then, the second value u.sup.(2) for the auxiliary variable u is multiplied (multiplier 111) by the first value v.sup.(1) for the auxiliary variable v, to obtain a third value u.sup.(3) for the auxiliary variable u. The third value u.sup.(3) for the auxiliary variable u is then added (adder 113) to the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q, to obtain a second value v.sup.(2) for the auxiliary variable v. The third value u.sup.(3) for the auxiliary variable u is then multiplied by itself (multiplier 115) to obtain a third value v.sup.(3) for the auxiliary variable v. The third value v.sup.(3) for the auxiliary variable v is then added (adder 117) to the third value u.sup.(3) for the auxiliary variable u to obtain a fourth value v.sup.(4) for the auxiliary variable v. Then, the fourth value v.sup.(4) for the auxiliary variable v is added (adder 119) to the value x.sub.2.sup.(1) of the coordinate x.sub.2 of the point P, to obtain a fifth value v.sup.(5) for the auxiliary variable v. The fifth value v.sup.(5) for the auxiliary variable v is then added (adder 121) to the constant a, i.e., the elliptic curve parameter, to obtain a sixth value v.sup.(6) for the auxiliary variable v. The sixth value v.sup.(6) for the auxiliary variable v is then added (adder 123) to the initial value x.sub.1.sup.(1) of the coordinate x.sub.1 of the point Q, to obtain an updated, second value x.sub.1.sup.(2) of the coordinate x.sub.1 of the point Q. The third value u.sup.(3) for the auxiliary variable u is then multiplied (multiplier 125) by the sixth value v.sup.(6) for the auxiliary variable v, to obtain a fourth value u.sup.(4) for the auxiliary variable u. The fourth value u.sup.(4) for the auxiliary variable u is then added (adder 127) to the second value x.sub.1.sup.(2) of the coordinate x.sub.1 of the point Q to obtain a fifth value u.sup.(5) for the auxiliary variable u. Finally, the fifth value u.sup.(5) for the auxiliary variable u is added (adder 129) to the initial value y.sub.1.sup.(1) of the coordinate y.sub.1 of the point Q, to obtain an updated, second value y.sub.1.sup.(2) of the coordinate y.sub.1 of the point Q). Therefore, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the claimed limitations of the first polynomial and the second polynomial disclosed by DE HOOGH are a first auxiliary polynomial and a second auxiliary polynomial. This modification would have been obvious because a person having ordinary skill in the art would have been motivated by the desire to apply elliptic-curve cryptography more safely against side-channel attacks. It focuses on the main ECC operation called scalar multiplication, where a secret number is used to multiply a point on an elliptic curve. to make less revealing by using a balanced Extended Euclidean Algorithm; and randomize the scalar by adding a random multiple of the point order and reduce leakage from timing, power consumption, and similar measurements as suggested by Golic ([0047-0051]).
As per claim 11:. DE HOOGH in view of Golic disclose the method of claim 10, wherein the set of basis vectors is obtained by randomizing a stored set of basis vectors (DE HOOGH FIG. 3b shows an example, in which one of the Fourier coefficients has been randomly chosen at compile time as the representing coefficient. In fact, which Fourier coefficient represents the data value may even vary per round, e.g., per update of the internal state. For example, after the next update, in set 331 it may be the Fourier coefficient of index 2, while in set 332 it is the Fourier coefficient of index 3, etc. For example, the Fourier coefficients may be permuted in an affine part of the round function).
As per claim 12:. DE HOOGH in view of Golic disclose the method of claim 11, wherein randomizing the stored set of basis vectors comprises: multiplying the stored set of basis vectors by an invertible randomization matrix comprising one or more random elements (DE HOOGH [0126] The input to the linear operation may be, e.g., a vector with as elements the shares of two or more sets of shares. For example, in so-far a linear operator acts on Fourier coefficients that represent the data value, they can perform the linear operation needed for the cryptographic primitive, e.g., as desired by a standard; but in so-far the one or more linear operators act only on Fourier coefficients that do not represent the data value, they can perform any linear operation, e.g., a random linear operation, so long as the relationship is preserved).
As per claim 13:. DE HOOGH in view of Golic disclose the method of claim 11, wherein randomizing the stored set of basis vectors comprises permuting two or more vectors of the stored set of basis vectors ((DE HOOGH [0096] FIG. 3b shows an example, in which one of the Fourier coefficients has been randomly chosen at compile time as the representing coefficient. In fact, which Fourier coefficient represents the data value may even vary per round, e.g., per update of the internal state. For example, after the next update, in set 331 it may be the Fourier coefficient of index 2, while in set 332 it is the Fourier coefficient of index 3, etc. For example, the Fourier coefficients may be permuted in an affine part of the round function).
As per claim 14:.. DE HOOGH in view of Golic disclose the method of claim 10, wherein combining the polynomial comprises adding the polynomial to the masking polynomial to obtain the masked polynomial (DE HOOGH [0147] As noted, some of the operations may be keyed. For example, in an operation a round key may be added to all or part of the internal state. The key may be stored in device 100 in an encoded form. Preferably, the keys use the same type encoding as the internal state does, e.g., as set of (encoded) shares with restrictions imposed on the Fourier coefficients of the sets. For example, the key may be represented in a memory of device 100 as a corresponding set of shares, the set of shares satisfying the predetermined relationship between the Fourier coefficients corresponding to the set of shares of the key according to the discrete Fourier transform in the finite field).
As per claim 15:.. DE HOOGH in view of Golic disclose the method of claim 10, wherein combining the polynomial comprises multiplying the polynomial by the masking polynomial to obtain the masked polynomial, the method further comprising: identifying roots of the masked polynomial that are not roots of the masking polynomial (DE HOOGH [0064] An embodiment, using a single representing element for each set of Fourier coefficients may be described in summary as follows. Suppose we have n shares x=x.sub.0, . . . ,x.sub.n−1 representing a secret x over some finite field of order q. Let α ϵbe a primitive n-th root, e.g., n ϵ is the smallest power such that α.sup.n≡1. Recall that n should divide q−1. The Fourier Transform of x is defined as {circumflex over (x)}, where {circumflex over (x)}.sub.i=Σ.sub.j=0.sup.n−1α.sup.i*jx.sub.j).
As per claims 16-18 and 20-22:
Claims 16-18 and 20-22 are directed to system to perform a cryptographic operation, the system comprising: a memory device; and a processing device communicatively coupled to the memory device, the processing device of claims 16-18 and 20-22 having substantially similar corresponding limitations of claims 1, 3-4, 6-7 and 9 respectively and therefore claims 16-18 and 20-22 are rejected with the same rationale given above to reject limitation of corresponding limitations of claims 1, 3-4, 6-7 and 9 respectively
Allowable Subject Matter
Claims 5 and 19 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
As per claims 5 and 19:. wherein the DT of the first auxiliary polynomial is obtained using operations that comprise: randomizing the first reduced set of basis vectors to obtain a second randomized set of basis vectors; obtaining, using the second randomized set of basis vectors, a second reduced set of basis vectors; identifying, based on the first auxiliary polynomial, a third auxiliary polynomial and a fourth auxiliary polynomial; and computing the DT of the first auxiliary polynomial using the second reduced set of basis vectors, the DT of the third auxiliary polynomial, and the DT of the fourth auxiliary polynomial.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
POEPPELMANN US 20200082738 A1 describes a way to generate and use random polynomial values more efficiently in cryptographic systems, especially lattice-based cryptography. Instead of separately sampling many random coefficients, the system samples one polynomial normally and a second polynomial that has only a small number of nonzero coefficients. The two polynomials are multiplied, and the product is then used as part of the cryptographic operation. Because the second polynomial is sparse, the multiplication can be done more efficiently than a full dense multiplication. The approach can reduce the amount of randomness needed to create secret or error values. The disclosure emphasizes that this can be useful for public-key encryption, key generation, signatures, and related operations. It also describes use on secure hardware such as smartcards, HSMs, and crypto modules. A major stated goal is improving resistance to side-channel attacks. The specification also discusses using shared computation or randomized masking to protect intermediate values. Example code and figures illustrate the sampling distribution and integration into lattice-based schemes like LPR10/NewHope-style operations.
Satpathy et al US 20210182437 A1 describes a chip-based encryption system designed to make side-channel attacks harder. The system is built into devices such as a head-mounted display or a peripheral device in an artificial reality setup. It uses one engine that can both encrypt outgoing data and decrypt incoming data. Rather than running all encryption rounds and all decryption rounds separately, the chip mixes them together on a round-by-round basis. The encryption rounds use one polynomial, and the decryption rounds use a different polynomial. By switching between these different round types, the device changes its power usage pattern in a less predictable way. That makes it harder for an attacker to learn secret keys by measuring power traces or other leakage. The security processor controls this mixing through selection inputs to a multiplexer. The disclosure also describes exploring different polynomial pairings to find combinations with different power profiles. In some examples, the design uses finite-field arithmetic to reduce area and improve efficiency while preserving AES-style compatibility.
Contact Information
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TECHANE GERGISO whose telephone number is (571)272-3784. The examiner can normally be reached 9:30am to 6:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, LINGLAN EDWARDS can be reached at (571) 270-5440. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/TECHANE GERGISO/ Primary Examiner, Art Unit 2408
