NTRUSign

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.

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 2³⁰ 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.

References

^ 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.
^ 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.
^ ^a ^b http://www.szydlo.com/ntru-revised-full02.pdf^{[bare URL PDF]}
^ ^a ^b P. Nguyen and O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures", available from https://cims.nyu.edu/~regev/papers/gghattack.pdf
^ "NIST Post Quantum Crypto Submission". OnBoard Security. Archived from the original on 2017-12-29. Retrieved 2018-03-20.
^ 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.
^ 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.

External links

Public-key cryptography

Algorithms

Integer factorization	Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Naccache–Stern Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa
Discrete logarithm	BLS Cramer–Shoup DH DSA ECDH X25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS
Lattice/SVP/CVP/LWE/SIS	Kyber NTRUEncrypt NTRUSign RLWE-KEX RLWE-SIG BLISS NewHope
Others	AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern knapsack cryptosystem Three-pass protocol XTR

Theory

Standardization

Topics

v t e Cryptography
General	History of cryptography Outline of cryptography Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network
Mathematics	Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography
Category

This page was last edited on 28 December 2022, at 20:29

From Wikipedia, the free encyclopedia

Security

References

External links