Ntru Cryptosystems, Inc.

Onboard Security, Inc.

Security Innovation Inc.

Ntru Cryptosystmes, Inc.

Jill C Pipher

Jeffrey Hoffstein

Joseph H Silverman

William Whyte

Zhenfei Zhang

Nicholas A Howgrave-Graham

John M Schanck

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

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 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 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.

Growing community of inventors

Pawtucket, RI, United States of America

Jill C Pipher