Movatterモバイル変換

[0]ホーム

Jump to content

NTRUEncrypt

Edit links

From Wikipedia, the free encyclopedia

Lattice-based public key cryptosystem

This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(April 2013) (Learn how and when to remove this message)

TheNTRUEncryptpublic key cryptosystem, also known as theNTRU encryption algorithm, is anNTRU lattice-based alternative toRSA andelliptic curve cryptography (ECC) and is based on theshortest vector problem in a lattice (which is not known to be breakable usingquantum computers).

It relies on the presumed difficulty offactoring certain polynomials in a truncatedpolynomial ring into a quotient of two polynomials having very small coefficients. Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem oflattice reduction in certainlattices. Careful choice of parameters is necessary to thwart some published attacks.

Since both encryption and decryption use only simple polynomial multiplication, these operations are very fast compared to other asymmetric encryption schemes, such as RSA,ElGamal andelliptic curve cryptography. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis in deployed form.

A related algorithm is theNTRUSign digital signature algorithm.

Specifically, NTRU operations are based on objects in a truncated polynomial ring $\ R=\mathbb {Z} [X]/(X^{N}-1)$ with convolution multiplication and all polynomials in the ring haveinteger coefficients and degree at mostN-1:

{\textbf {a}}=a_{0}+a_{1}X+a_{2}X^{2}+\cdots +a_{N-2}X^{N-2}+a_{N-1}X^{N-1}

That $X^{N}=1$ in this ring has the effect that multiplying a polynomial by $X {\displaystyle X}$ rotates the coefficients of the polynomial. A map of the form $f\mapsto fg$ for a fixed $g\in R$ thus produces a new polynomial $f g {\displaystyle fg}$ where every coefficient depends on as many coefficients from $f {\displaystyle f}$ as there are nonzero coefficients in $g {\displaystyle g}$ .

NTRU has three integer parameters (N,p,q), whereN is the polynomial degree bound,p is called the small modulus, andq is called the large modulus; it is assumed thatN isprime,q is always (much) larger thanp, andp andq arecoprime.Plaintext messages are polynomials modulop butciphertext messages are polynomials moduloq. Concretely the ciphertext consists of the plaintext message plus a randomly chosen multiple of the public key, but the public key may itself be regarded as a multiple of the small modulusp, which allows the holder of the private key to extract the plaintext from the ciphertext.

History

[edit]

The NTRUEncrypt Public Key Cryptosystem is a relatively new cryptosystem.The first version of the system, which was simply called NTRU, was developed around 1996 by three mathematicians (Jeffrey Hoffstein,Jill Pipher, andJoseph H. Silverman). In 1996 these mathematicians together withDaniel Lieman founded the NTRU Cryptosystems, Inc. and were given a patent^[1] (now expired) on the cryptosystem.

During the last ten years people have been working on improving the cryptosystem. Since the first presentation of the cryptosystem, some changes were made to improve both the performance of the system and its security. Most performance improvements were focused on speeding up the process.^{[further explanation needed]} Up till 2005 literature can be found that describes the decryption failures of the NTRUEncrypt.^{[citation needed]} As for security, since the first version of the NTRUEncrypt, new parameters have been introduced^{[citation needed]} that seem secure^{[clarification needed]} for all currently^[specify] known attacks and reasonable increase in computation power.^{[clarification needed]}

Now the system is fully accepted to IEEE P1363 standards under the specifications for lattice-based public-key cryptography (IEEE P1363.1).Because of the speed of the NTRUEncrypt Public Key Cryptosystem (seehttp://bench.cr.yp.to for benchmarking results) and its low memory use (seebelow)^{[dubious –discuss]}, it can be used in applications such as mobile devices andSmart-cards.In April 2011, NTRUEncrypt was accepted as a X9.98 Standard, for use in the financial services industry.^[2]

Public key generation

[edit]

Sending a secret message from Alice to Bob requires the generation of a public and a private key. The public key is known by both Alice and Bob and the private key is only known by Bob. To generate the key pair two polynomialsf andg, with degree at most $\ N-1$ and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo $\ X^{N}-1$ inR. The polynomial ${\textbf {f}}\in L_{f}$ must satisfy the additional requirement that the inverses moduloq and modulop (computed using theEuclidean algorithm) exist, which means that $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ and $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ must hold.So when the chosenf is not invertible, Bob has to go back and try anotherf.

Bothf and $\ \mathbf {f} _{p}$ (and $\mathbf {g}$ ) are Bob's private key. The public keyh is generated computing the quantity

{\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {q}}.

Example:In this example the parameters (N,p,q) will have the valuesN = 11,p = 3 andq = 32 and therefore the polynomialsf andg are of degree at most 10. The system parameters (N,p,q) are known to everybody. The polynomials are randomly chosen, so suppose they are represented by

{\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}

{\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}

Using the Euclidean algorithm the inverse off modulop and moduloq, respectively, is computed

{\textbf {f}}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod {3}}

{\textbf {f}}_{q}=5+9X+6X^{2}+16X^{3}+4X^{4}+15X^{5}+16X^{6}+22X^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}

Which creates the public keyh (known to both Alice and Bob) computing the product

{\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {32}}=8-7X-10X^{2}-12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}

Encryption

[edit]

Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomialm with coefficients in $[-p/2,p/2]$ . In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation.After creating the message polynomial, Alice randomly chooses a polynomialr with small coefficients (not restricted to the set {-1,0,1}), that is meant to obscure the message.

With Bob's public keyh the encrypted messagee is computed:

{\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}

This ciphertext hides Alice's messages and can be sent safely to Bob.

Example:Assume that Alice wants to send a message that can be written as polynomial

{\textbf {m}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}

and that the randomly chosen ‘blinding value’ can be expressed as

{\textbf {r}}=-1+X^{2}+X^{3}+X^{4}-X^{5}-X^{7}

The ciphertexte that represents her encrypted message to Bob will look like

{\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {32}}=14+11X+26X^{2}+24X^{3}+14X^{4}+16X^{5}+30X^{6}+7X^{7}+25X^{8}+6X^{9}+19X^{10}{\pmod {32}}

Decryption

[edit]

Anybody knowingr could compute the messagem by evaluatinge -rh; sor must not be revealed by Alice. In addition to the publicly available information, Bob knows his own private key. Here is how he can obtainm: First he multiplies the encrypted messagee and part of his private keyf

{\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}

By rewriting the polynomials, this equation is actually representing the following computation:

{\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}

{\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\pmod {q}}

{\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\pmod {q}}

{\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\pmod {q}}

Instead of choosing the coefficients ofa between 0 andq – 1 they are chosen in the interval [-q/2,q/2] to prevent that the original message may not be properly recovered since Alice chooses the coordinates of her messagem in the interval [-p/2,p/2]. This implies that all coefficients of $\ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}$ already lie within the interval [-q/2,q/2] because the polynomialsr,g,f andm and primep all have coefficients that are small compared toq. This means that all coefficients are left unchanged during reducing moduloq and that the original message may be recovered properly.

The next step will be to calculatea modulop:

{\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}

because $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ .

Knowingb Bob can use the other part of his private key $\ \left({\textbf {f}}_{p}\right)$ to recover Alice's message by multiplication ofb and $\ {\textbf {f}}_{p}$

{\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}

{\textbf {c}}={\textbf {m}}{\pmod {p}}

because the property $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ was required for $\ {\textbf {f}}_{p}$ .

Example: The encrypted messagee from Alice to Bob is multiplied with polynomialf

{\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {32}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}},

where Bob uses the interval [-q/2,q/2] instead of the interval [0,q – 1] for the coefficients of polynomiala to prevent that the original message may not be recovered correctly.

Reducing the coefficients ofa modp results in

{\textbf {b}}={\textbf {a}}{\pmod {3}}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod {3}}

which equals $\ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}$ .

In the last step the result is multiplied with $\ {\textbf {f}}_{p}$ from Bob's private key to end up with the original messagem

{\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}

{\textbf {c}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}

Which indeed is the original message Alice has sent to Bob!

Attacks

[edit]

Since the proposal of NTRU several attacks on the NTRUEncrypt public key cryptosystem have been introduced. Most attacks are focused on making a total break by finding the secret keyf instead of just recovering the messagem.Iff is known to have very few non-zero coefficients Eve can successfully mount abrute force attack by trying all values forf. When Eve wants to know whetherf´ is the secret key, she simply calculates $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ . If it has small coefficients it might be the secret keyf, and Eve can test iff´ is the secret key by using it to decrypt a message she encrypted herself.Eve could also try values ofg and test if $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ has small values.

It is possible to mount ameet-in-the-middle attack which is more powerful. It can cut the search time by square root. The attack is based on the property that $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ .

Eve wants to find $\ {\textbf {f}}_{1}$ and $\ {\textbf {f}}_{2}$ such that $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ holds and such that they have the property

\left({\textbf {f}}_{1}+{\textbf {f}}_{2}\right)\cdot {\textbf {h}}={\textbf {g}}{\pmod {q}}

{\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}

Iff hasd one's andN-d zero's, then Eve creates all possible $\ {\textbf {f}}_{1}$ and $\ {\textbf {f}}_{2}$ in which they both have length $\ {\frac {1}{2}}N$ (e.g. $\ {\textbf {f}}_{1}$ covers the $\ {\frac {1}{2}}N$ lowest coefficients off and $\ {\textbf {f}}_{2}$ the highest)withd/2 one's. Then she computes ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ for all $\ {\textbf {f}}_{1}$ and orders them in bins based on the first k coordinates. After that she computes all $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ and orders them in bins not only based on the first k coordinates, but also based on what happens if you add 1 to the first k coordinates. Then you check the bins that contain both $\ {\textbf {f}}_{1}$ and $\ {\textbf {f}}_{2}$ and see if the property $\ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ holds.

The lattice reduction attack is one of the best known and one of the most practical methods to break the NTRUEncrypt. In a way it can be compared to the factorization of the modulus in RSA. The most used algorithm for the lattice reduction attack is theLenstra-Lenstra-Lovász algorithm.Because the public keyh contains bothf andg one can try to obtain them fromh. It is however too hard to find the secret key when the NTRUEncrypt parameters are chosen secure enough. The lattice reduction attack becomes harder if the dimension of the lattice gets bigger and the shortest vector gets longer.

Thechosen ciphertext attack is also a method which recovers the secret keyf and thereby results in a total break. In this attack Eve tries to obtain her own message from the ciphertext and thereby tries to obtain the secret key. In this attack Eve doesn't have any interaction with Bob.

How it works:

First Eve creates a ciphertext $\ {\textbf {e}}=c{\textbf {h}}+c$ such that $\ c=0{\pmod {p}},c<{\frac {q}{2}}$ and $\ 2c>{\frac {q}{2}}$ .When Eve writes down the steps to decipher e (without actually calculating the values since she does not know f) she finds $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ :

{\textbf {a}}={\textbf {f}}\left(c{\textbf {h}}+c\right){\pmod {q}}

{\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}

{\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK

In which $\ K=\sum k_{i}x^{i}$ such that

k_{i}={\begin{cases}1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1,\\-1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1,\\0&{\text{otherwise.}}\end{cases}}

Example:

{\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}

{\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}

ThenK becomes $\ K=-1+X^{2}-X^{10}$ .

Reducing the coefficients ofa modp really reduces the coefficients of $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ . After multiplication with $\ {\textbf {f}}_{p}$ , Eve finds:

{\textbf {m}}=c{\textbf {f}}_{p}\cdot {\textbf {g}}+c{\textbf {f}}_{p}\cdot {\textbf {f}}-q{\textbf {f}}_{p}\cdot K{\pmod {p}}

{\textbf {m}}=c{\textbf {h}}+c-q{\textbf {f}}_{p}\cdot K{\pmod {p}}

Because c was chosen to be a multiple ofp,m can be written as

{\textbf {m}}=-q{\textbf {f}}_{p}\cdot K{\pmod {p}}

Which means that $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ .

Now iff andg have few coefficients which are the same at the same factors,K has few non zero coefficients and is thereby small. By trying different values ofK the attacker can recoverf.

By encrypting and decrypting a message according to the NTRUEncrypt the attacker can check whether the functionf is the correct secret key or not.

Security and performance improvements

[edit]

Using the latest suggested parameters (seebelow) the NTRUEncrypt public key cryptosystem is secure to most attacks. There continues however to be a struggle between performance and security. It is hard to improve the security without slowing down the speed, and vice versa.

One way to speed up the process without damaging the effectiveness of the algorithm, is to make some changes in the secret keyf.First, constructf such that $\ {\textbf {f}}=1+p{\textbf {F}}$ , in whichF is a small polynomial (i.e. coefficients {-1,0, 1}). By constructingf this way,f is invertible modp. In fact $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ , which means that Bob does not have to actually calculate the inverse and that Bob does not have to conduct the second step of decryption. Therefore, constructingf this way saves a lot of time but it does not affect the security of the NTRUEncrypt because it is only easier to find $\ {\textbf {f}}_{p}$ butf is still hard to recover.In this casef has coefficients different from -1, 0 or 1, because of the multiplication byp. But because Bob multiplies byp to generate the public keyh, and later on reduces the ciphertext modulop, this will not have an effect on the encryption method.

Second,f can be written as the product of multiple polynomials, such that the polynomials have many zero coefficients. This way fewer calculations have to be conducted.

According to the 2020 NTRU NIST submission^[3] the following parameters are considered secure:

Table 1: Parameters

[edit]

	N	q	p
128 bit security margin (NTRU-HPS)	509	2048	3
192 bit security margin (NTRU-HPS)	677	2048	3
256 bit security margin (NTRU-HPS)	821	4096	3
256 bit security margin (NTRU-HRSS)	701	8192	3

References

[edit]

^"US Patent 6081597 – Public key cryptosystem method and apparatus" – viaGoogle Patents.
^"Security Innovation's NTRUEncrypt Adopted as X9 Standard for Data Protection" (Press release). April 11, 2011.
^"NIST-PQ-Submission-NTRU-20201016.tar.gz".

Jaulmes, E. and Joux, A. A Chosen-Ciphertext Attack against NTRU. Lecture Notes in Computer Science; Vol 1880. Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptography. pp. 20–35, 2000.
Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman.NTRU: A Ring Based Public Key Cryptosystem. In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267–288.
Howgrave-Graham, N., Silverman, J.H. & Whyte, W.,Meet-In-The-Middle Attack on a NTRU Private Key.
J. Hoffstein, J. Silverman.Optimizations for NTRU. Public-Key Cryptography and Computational Number Theory (Warsaw, September 11–15, 2000), DeGruyter, to appear.
A. C. Atici, L. Batina, J. Fan & I. Verbauwhede.Low-cost implementations of NTRU for pervasive security.

External links

[edit]

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	BLISS Kyber NewHope NTRUEncrypt NTRUSign RLWE-KEX RLWE-SIG
Others	AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern knapsack cryptosystem Three-pass protocol XTR SQIsign SPHINCS⁺

Theory

Standardization

Topics

v t e Cryptography
General	History of cryptography Outline of cryptography Classical cipher Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Secure Hash Algorithms Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Machines 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

Retrieved from "https://en.wikipedia.org/w/index.php?title=NTRUEncrypt&oldid=1323971191"

Categories:

Hidden categories:

[8]ページ先頭