CN-122003834-A - Cryptographic system involving masked inversion of polynomial ring elements

Abstract

A method of performing cryptographic operations is described, the method comprising performing masked inversion on a ring element f ε R q , where R q is a commutative ring, and the ring element f is composed of multiple shares And (3) representing. Inverting the mask by computing a plurality of shares Performing a number-theory transformation to generate a corresponding plurality of shares of the polynomial function a Wherein each coefficient And i e n, determining a set of coefficients, the set of coefficients and the plurality of shares Corresponding to the product of n coefficients of a plurality of shares An inverse of a set of coefficients corresponding to the product of n coefficients of (2) generating a plurality of shares Is a set of coefficients c i of the plurality of shares Corresponding to the inverse of the polynomial function a, wherein a plurality of shares Is by the ith coefficient from the multiple shares The value obtained by multiplying the inverse of the product of n coefficients by multiple shares Calculated for a plurality of shares corresponding to the inverse of the polynomial function a Performing an inverse number theory transformation to generate a plurality of shares corresponding to the inverse of the ring element f . By applying the NTT transform to the masking ring element and then determining the inverse of the set of coefficients corresponding to the product of the masking transform coefficients, the processing cost of the inversion of the masking ring element may be reduced.

Inventors

• THOMAS PREST
• Thomas. Epietau
• Jiyang Neo

Assignees

• PQ盾牌有限公司

Dates

Publication Date

20260508

Application Date

20241007

Priority Date

20231006

Claims (12)

1. 1. A method of performing a cryptographic operation, wherein the method comprises performing a masked inversion of a ring element f e R q , wherein R q is a swap ring, and the ring element f is composed of multiple shares The expression is as follows: for the plurality of shares Performing a number-theory transformation to generate a corresponding plurality of shares of the polynomial function a Wherein each coefficient And i e [ n ]; for the multiple shares of the polynomial function a For n=0 to N-1, iteratively determining the plurality of shares To generate a set of products, the set of products includes the plurality of shares Is a product of the n coefficients; Determining the plurality of shares An inverse of said product of said n coefficients; for multiple shares Generating a set of coefficients c i , the plurality of shares The inverse element corresponding to the polynomial function a, wherein a plurality of shares Is by the factor (i) from the plurality of shares The value resulting from the inverse of the product of the n coefficients is multiplied by the contributions from the plurality of contributions Calculated from the values obtained from other coefficients of (a) and For the plurality of shares corresponding to the inverse of the polynomial function a Performing an inverse number theory transformation to generate a plurality of shares corresponding to the inverse of the ring element f 。
2. 2. The method of claim 1, further comprising for the share of the polynomial function a The inverse of the product of the n coefficients and the product of the n coefficients is calculated to generate data indicating whether the ring element f is invertible.
3. 3. The method of claim 1 or claim 2, calculating the ith coefficient c i comprising at least one of i) refreshing the plurality of shares The value of the product of the n coefficients for each share in (a); and ii) refreshing the plurality of shares Is used for the value of the coefficient of (c).
4. 4. A method as claimed in any preceding claim, wherein the determination of the inverse of the product of the n coefficients is performed using the euler theorem.
5. 5. The method of claim 4, wherein the exponential operation of the euler theorem is performed using a sum-of-square multiplication algorithm.
6. 6. A method as claimed in any preceding claim, wherein the cryptographic function is a key generation function.
7. 7. The method of claim 6, further comprising encrypting a message using a cryptographic key generated by the key generation function.
8. 8. The method of claim 6 or claim 7, further comprising decrypting a message using a cryptographic key generated by the key generation function.
9. 9. The method of any of claims 6 to 8, further comprising generating a digital signature of a message using a cryptographic key generated by the key generation function.
10. 10. The method of any of claims 6 to 9, further comprising verifying a digital signature of a message using a cryptographic key generated by the key generation function.
11. 11. A computer program comprising instructions for performing the method of any preceding claim.
12. 12. An apparatus comprising processing circuitry and a memory, wherein the memory stores instructions that, when executed by the processing circuitry, perform the method of any of claims 1 to 10.

Description

Cryptographic system involving masked inversion of polynomial ring elements Technical Field The invention relates to a method for generating a new element f EAn efficient method of masking pseudo-inversions is performed and is particularly applicable to loops used in lattice-based cryptography, but is not limited thereto. Background Dot matrix based cryptographic schemes such as those based on fault tolerant Learning (LWE) and Short Integer Solution (SIS) problems are of interest because dot matrix based cryptographic schemes are presumed to be resistant to attack by attackers that can access large scale quantum computers. Thus, lattice-based cryptography schemes are generally considered as a subset of post quantum cryptography. However, lattice-based cryptographic schemes can be vulnerable to side channel attacks, where adversaries learn side channel information about the physical execution of the algorithm. Side channel information may be derived from many sources such as run time, electromagnetic emissions, energy consumption, and acoustic emissions. For example, various studies have shown that side channel information regarding the execution of lattice-based signature algorithms may allow a adversary to recover the used signing key sk. The countermeasure against side channel attacks that has been proposed is masking, which relies on techniques in the field of secret sharing and multiparty computing (MPC). Given a sensitivity value x epsilonMasking x includes representing x as tuple (x 1, . . . , xd) ∈Where d is the number of shares (also called the number of shares), and in the context of masking, d-1 is often called the number of masks, such that (i)And (ii) any subset of t < d distinct x i appears to be uniformly random. When d is clear in context, the tuple can be markedTo represent. The principle of masking is that an attacker with the ability to learn the values of t < d variables x i will not learn anything about x. Increasing the value of d strengthens countermeasures against side channel attacks, but the challenging aspect of masking is that increasing the value of d generally results in an increase in computational complexity with secondary (or higher) overhead. Several post quantum cryptography systems need to determine the inverse of the ring element f e R q, where R q eAnd∈ Is the first polynomial. Among the family of lattice-based cryptosystems, examples of such cryptosystems include NTRU-type lattice-based schemes. In NTRU based systems, the ring elements f, g e R q are secret and the ring element h=f/g is public. Thus, determining the ring elements f, g, and h involves inverting the ring elements. While algorithms for performing masked inversion have been proposed in many publications, such as, for example, the number of times R q, the complexity of these algorithms is at least on the order of d 2 multiplications. Since the known method for multiplying two elements in R q involves processing costs of at least O (d 2 nlogn), a more efficient method of computing the masked inversion of the ring elements is desirable. Disclosure of Invention According to a first aspect of the present invention there is provided a method of performing a cryptographic operation, the method comprising performing a masked inversion of a ring element f e R q, wherein R q is a commutative ring, and the ring element f is composed of a plurality of sharesAnd (3) representing. Inverting the mask by computing a plurality of sharesPerforming a number-theory transformation to generate a corresponding plurality of shares of the polynomial function aWherein each coefficientAnd i e n, determining a set of coefficients, the set of coefficients and the plurality of sharesCorresponding to the product of n coefficients of a plurality of sharesAn inverse of a set of coefficients corresponding to the product of n coefficients of (2) generating a plurality of sharesIs a set of coefficients c i of the plurality of sharesCorresponding to the inverse of the polynomial function a, wherein a plurality of sharesIs by the ith coefficient from the multiple sharesThe value derived from the inverse of the product of n coefficients of (2) is multiplied by the value derived from the multiple sharesCalculated for a plurality of shares corresponding to the inverse of the polynomial function aPerforming an inverse number theory transformation to generate a plurality of shares corresponding to the inverse of the ring element f. By applying the NTT transform to the masking ring element and then determining the inverse of the set of coefficients corresponding to the product of the masking transform coefficients, the processing cost of the inversion of the masking ring element may be reduced. Not all ring elements are reversible. In an example, while determining the inverse of the masked ring element f, the method may involve calculating the share of the polynomial function aA product of n coefficients, and an inverse of the product of n coefficien