NTRUSign

Last updated

NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99. [1] The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. [2] The 2003 publication included parameter recommendations for 80-bit security. A subsequent 2005 publication revised the parameter recommendations for 80-bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm.

Contents

NTRUSign involves mapping a message to a random point in 2N-dimensional space, where N is one of the NTRUSign parameters, and solving the closest vector problem in a lattice closely related to the NTRUEncrypt lattice. NTRUSign is claimed to be faster than those algorithms at low security levels, and considerably faster at high security levels. However, analysis had shown that original scheme is insecure and would leak knowledge of private key. [3] [4]

A redesigned pqNTRUSign had been submitted to the NIST Post-Quantum Cryptography Standardization competition. [5] It is based on "hash-and-sign" (contrasting Fiat–Shamir transformation) methodology, and claims to achieve smaller signature size.

NTRUSign is under consideration for standardization by the IEEE P1363 working group.[ citation needed ]

Security

It was demonstrated in 2000 by Wu, Bao, Ye and Deng that the signature of PASS, the original version of NTRUSign, can be forged easily without knowing the private key. [6] NTRUSign is not a zero-knowledge signature scheme and a transcript of signatures leaks information about the private key, as first observed by Gentry and Szydlo. [3] Nguyen and Regev demonstrated in 2006 that for the original unperturbed NTRUSign parameter sets an attacker can recover the private key with as few as 400 signatures. [4]

The current proposals use perturbations to increase the transcript length required to recover the private key: the signer displaces the point representing the message by a small secret amount before the signature itself is calculated. NTRU claimed that at least 230 signatures are needed, and probably considerably more, before a transcript of perturbed signatures enabled any useful attack. In 2012 an attack on the scheme with perturbations was presented that required a few thousand signatures for standard security parameters. [7]

The pqNTRUSign claims a 128-bit classical and quantum security for their given parameter set.

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

Articles related to cryptography include:

The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice-based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice.

In cryptography, LOKI89 and LOKI91 are symmetric-key block ciphers designed as possible replacements for the Data Encryption Standard (DES). The ciphers were developed based on a body of work analysing DES, and are very similar to DES in structure. The LOKI algorithms were named for Loki, the god of mischief in Norse mythology.

<span class="mw-page-title-main">CrypTool</span>

CrypTool is an open-source project that is a free e-learning software for illustrating cryptographic and cryptanalytic concepts. According to "Hakin9", CrypTool is worldwide the most widespread e-learning software in the field of cryptology.

The Goldreich-Goldwasser-Halevi (GGH) signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem (CVP) in a lattice. The signer demonstrates knowledge of a good basis for the lattice by using it to solve CVP on a point representing the message; the verifier uses a bad basis for the same lattice to verify that the signature under consideration is actually a lattice point and is sufficiently close to the message point.

Neural cryptography is a branch of cryptography dedicated to analyzing the application of stochastic algorithms, especially artificial neural network algorithms, for use in encryption and cryptanalysis.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems—which could, theoretically, be defeated using Shor's algorithm on a quantum computer—some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme.

The following outline is provided as an overview of and topical guide to cryptography:

In cryptography, post-quantum cryptography refers to cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

Digital signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use will become completely insecure if scientists are ever able to build a moderately sized quantum computer. Post quantum cryptography is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used RSA and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as Ring learning with errors. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes

In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. Public-key cryptography relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database.

In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.

Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.

Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.

Oded Regev is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University. He is best known for his work in lattice-based cryptography, and in particular for introducing the learning with errors problem.

In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.

Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It has been designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte and Zhenfei Zhang. It relies on the hash-and-sign technique over the Gentry, Peikert and Vaikuntanathan framework over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.

References

  1. ↑ Hoffstein, Jeffrey; Lieman, Daniel; Silverman, Joseph H. (1999). "Polynomial Rings and Efficient Public Key Authentication" (PDF). International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC'99). City University of Hong Kong Press.
  2. ↑ Hoffstein, Jeffrey; Howgrave-Graham, Nick; Pipher, Jill; Silverman, Joseph H.; Whyte, William (2003). "NTRUSign: Digital Signatures Using the NTRU Lattice" (PDF). Topics in Cryptology — CT-RSA 2003. LNCS. Vol. 2612. Springer. pp. 122–140.
  3. 1 2 http://www.szydlo.com/ntru-revised-full02.pdf [ bare URL PDF ]
  4. 1 2 P. Nguyen and O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures", available from https://cims.nyu.edu/~regev/papers/gghattack.pdf
  5. ↑ "NIST Post Quantum Crypto Submission". OnBoard Security. Archived from the original on 2017-12-29. Retrieved 2018-03-20.
  6. ↑ Wu, Hongjun; Bao, Feng; Ye, Dingfeng; Deng, Robert H. (2000). "Cryptanalysis of Polynomial Authentication and Signature Scheme" (PDF). ACISP 2000. LNCS. Vol. 1841. Springer. pp. 278–288.
  7. ↑ Ducas, Léo; Nguyen, Phong (2012). "Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures" (PDF). ASIACRYPT 2012. LNCS. Vol. 7658. Springer. pp. 433–450. doi: 10.1007/978-3-642-34961-4_27 . Retrieved 2013-03-07.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.