Ntru Cryptosystems, Inc.

Onboard Security, Inc.

Security Innovation Inc.

Brown University

Rsa Security Inc.

Ntru Cryptosystmes, Inc.

Jeffrey Hoffstein

Joseph H Silverman

Jill C Pipher

William Whyte

John M Schanck

Zhenfei Zhang

Nicholas A Howgrave-Graham

Burton S Kaliski, Jr

Yiqun Lisa Yin

Matthew John Robshaw

Daniel Lieman

Daniel Bennett Lieman

A method is set forth for signing and subsequently verifying a plurality of digital messages, including the following steps implemented using at least one processor-based subsystem: selecting parameters including an integer q, a relatively smaller integer p that is coprime with q, and a Gaussian function parameter; generating random polynomial f relating to p and random polynomial g relating to q; producing a public key that includes h, where h is equal to a product that can be derived using g and the inverse of f mod q; producing a private key from which f and g can be derived; storing the private key and publishing the public key; producing a plurality of message digests by hashing each of the digital messages with the public key; for each message digest, producing a digital signature using the message digest, the private key, and a Gaussian noise polynomial related to the Gaussian function parameter; and performing a batch verification procedure utilizing the plurality of digital signatures and the public key to determine whether the digital signatures are valid.

Digital signature technique

Systems, methods, and computer-readable storage devices storing instructions for homomorphic encryption via finite ring isomorphisms are provided. An example method includes selecting a polynomial f(x) of exact degree n with small coefficients in a ring F[x] and selecting a polynomial h(y) of exact degree n in a ring F[y]. The method includes constructing an isomorphism from the ring F[x]/(f(x)) to the ring F[y]/(h(y)) and constructing an inverse isomorphism from the ring F[y]/(h(y)) to the ring F[x]/(f(x)). The method includes encrypting a message using said isomorphism from the ring F[x]/(f(x)) to the ring F[y]/(h(y)) and transmitting the encrypted message to a remote computer. The method also includes receiving one or more encrypted response messages from the remote computer based at least in part on the transmitted message and decrypting the one or more encrypted response messages.

Homomorphic encryption

A method for signing and subsequently verifying a digital message, including the following steps: generating an irreducible monic polynomial f(x) of degree n in a ring F[x]; generating an irreducible monic polynomial F(y) of degree n in a ring F[y]; producing first and second finite fields as F[x]/(f(x)) and F[y]/(F(y)), respectively; producing a secret isomorphism from the first finite field to the second finite field; producing and publishing a public key that depends on F(y); producing a private key that depends on the secret isomorphism; producing a message digest by applying a hash function to the digital message and the public key; producing a digital signature using the message digest and the private key; and performing a verification procedure utilizing the digital signature and the public key.

Digital signature method and apparatus

A method for signing and subsequently verifying a digital message, including the following steps implemented using at least one processor-based subsystem: selecting parameters including an integer q and a relatively smaller integer p that is coprime with q; generating random polynomial f relating to p and random polynomial g relating to q; producing a public key that includes h, where h is equal to a product that can be derived using g and the inverse of f mod q; producing a private key from which f and g can be derived; storing the private key and publishing the public key; producing a message digest by applying a hash function to the digital message; producing a digital signature using the message digest and the private key; and performing a verification procedure utilizing the digital signature and the public key to determine whether the signature is valid.

Digital signature method

A method for signing a digital message, including the following steps: selecting parameters that include first and second primes, a ring of polynomials related to the primes, and at least one range-defining integer; deriving private and public keys respectively related to a random polynomial private key of the ring of polynomials, and to evaluations of roots of unity of the random polynomial to obtain a public key set of integers; storing the private key and publishing the public key; signing the digital message by: (A) generating a noise polynomial, (B) deriving a candidate signature by obtaining a hash of the digital message and the public key evaluated at the noise polynomial, and determining the candidate signature using the private key, a polynomial derived from the hash, and the noise polynomial, (C) determining whether the coefficients of the candidate signature are in a predetermined range dependent on the at least one range-defining integer, and (D) repeating steps (A) through (C) until the criterion of step (C) is satisfied, and outputting the resultant candidate signature as an encoded signed message.

A signing technique of a disclosed identification/digital signature method hereof uses a mixing system based on multiplication in a ring and reduction modulo an ideal q in that ring, while a disclosed verification technique uses special properties of products of elements whose validity depends on elementary probability theory. The security of the identification/digital signature scheme comes from the interaction of reduction modulo q and the difficulty of forming products with special properties. In an embodiment of the identification/digital signature scheme hereof that employs a quotient ring of polynomials, the security also relies on the experimentally observed fact that for most lattices, it is very difficult to find a vector whose length is only a little bit longer than the shortest vector, and it is also difficult to find a lattice vector that is quite close to a randomly chosen nonlattice vector.

Digital signature and authentication method and apparatus

A method, system and apparatus for performing user identification, digital signatures and other secure communication functions in which keys are chosen essentially at random from a large set of vectors and key lengths are comparable to the key lengths in other common identification and digital signature schemes at comparable security levels. The signing technique of an embodiment of the identification/digital signature scheme hereof uses a mixing system based on multiplication in a ring and reduction modulo an ideal q in that ring; while the verification technique uses special properties of products of elements whose validity depends on elementary probability theory. The security of the identification/digital signature scheme comes from the interaction of reduction modulo q and the difficulty of forming products with special properties.

A method for performing a cryptographic operation involving transforming digital information is described. A digital operator is provided that has a component selected from a large set of elements. The component is expanded into a plurality of factors, each factor having a low Hamming weight. Digital information is transformed using the digital operator. Computer readable medium embody instructions for the method.

Speed enhanced cryptographic method and apparatus

A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, includes the steps: selection by the first user of a private key f in a ring R and a public key that includes &#x3c6;(f) in a ring B that is mapped from f using the ring homomorphism &#x3c6;: R&#x2192;B, and publication by the first user of the public key; generation of the challenge communication by the second user that includes selection of a challenge c in the ring R; generation of the response communication by the first user that includes computation of a response comprising h in the ring R, where h is a function of c and f; and performing of a verification by the second user that includes determination of &#x3c6;(c) from c, &#x3c6;(h) from h, and an evaluation that depends on &#x3c6;(h), &#x3c6;(c) and &#x3c6;(f).

Secure user identification based on ring homomorphisms

A method of communicating information between users of a communications system includes the following steps: generating a ring R, ideals P and Q in R, a set of coset representatives C,for the ring R modulo the ideal Q, and a set of coset representatives C,for the ring R modulo the ideal P; generating at least one public key element h,, . . . , h,in the ring R as a function of at least two private key elements &fnof;,, . . . &fnof;,in R and the ideal Q of the first user; and transmitting from a first user to a second user a description of the ring R, the ideal Q, the ideal P, and the elements h,, . . . , h,in R; generating an element e in R as a function of the ideals P and Q, the public key elements h,, . . . , h,, a private message element m in R, and at least one private random element &oslash;,, . . . , &oslash;,of the second user; and transmitting the element e from the second user to the first user, such that the first user can determine the message element m by computing a result A in R of evaluating a function F of e, &fnof;,, . . . , &fnof;,, computing a coset representative a of A in the set of coset representatives C,, computing a result B of evaluating a function G of a, &fnof;,, . . . , &fnof;,, computing a coset representative b of B in the set of coset representatives C,, and computing a result c in the set of coset representatives C,of evaluating a function H of b, &fnof;,, . . . , &fnof;,.

Ring-based public key cryptosystem method

The public key encryption system of the present invention has short and easily created encryption keys and wherein the encoding and decoding processes are performed extremely rapidly, and has low memory requirements. The encoding and decoding processes use both the addition and multiplication operations in a ring modulo with two different ideals. The cryptosystem of the present invention allows encryption keys to be chosen essentially at random from a large set of binary vectors, for which key lengths are comparable to the key lengths of the most widely used prior art cryptosystems. The present invention features an appropriate security level (.about.2.sup.80), with encoding and decoding processes ranging from approximately one to two orders of magnitude faster than the prior art, particularly the exponentiation cryptosystems.

Public key cryptosystem method and apparatus

Methods and apparatus for providing secure user identification or digital signatures based on evaluation of constrained polynomials. In an exemplary user identification technique, a prover sends a verifier a commitment signal representative of a first polynomial satisfying a first set of constraints. The verifier sends the prover a challenge signal representative of a second polynomial satisfying a second set of constraints. The prover generates a response signal as a function of (i) information used to generate the commitment signal, (ii) a challenge signal, and (iii) a private key polynomial of the prover, such that the response signal is representative of a third polynomial satisfying a third set of constraints. The verifier receives the response signal from the prover, and authenticates the identity of the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover. In a digital signature technique, the challenge signal may be generated by the prover applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and the prover sends the message to the verifier. The verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover. The constraints on the polynomials are selected such that an attacker will find it very difficult to recover the private key polynomial from the partial information sent between the prover and verifier.

Growing community of inventors

Providence, RI, United States of America

Jeffrey Hoffstein