**NTRU, Quantum Resistance**

RSA

Bit vs. Qubit

And now what?

•We need time to improve the efficiency of post-quantum cryptography.

•We need time to build confidence in post-quantum cryptography.

•We need time to improve the usability of post-quantum cryptography.

NTRU

**Peter Matkovski**

Designers Ron Rivest, Adi Shamir, and Leonard Adleman

First published 1977

Certification PKCS#1, ANSI X9.31, IEEE 1363

Key sizes 1,024 to 4,096 bit typical

Choose two distinct prime numbers p and q.

Compute n = pq.

Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1)

Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1

Determine d as d ≡ e−1 (mod φ(n))

Encryption

Decryption

Shor's algorithm

quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor.

First, find a number that has no factors in common with 15 other than 1.

Suppose we pick 11.

Then:

Divide 11 by 15 to get 0 with a remainder of 11.

Square the remainder, getting 121.

Divide 121 by 15 to get 8 with a remainder of 1.

Cube 11 to get 1331.

Divide 1331 by 15, to get 88 with a remainder of 11.

If we proceed this way, raising 11 to higher powers, we will notice a curious thing about the remainder when we divide by 15: it will alternately either be 11 or 1. Thus, we say the period of 11 with respect to being divided by 15 is 2.

But how is this useful to factorise 15? Raise 11 to the power given by its period, which is 2, the answer is 121. Now take the square root to get 11. The next step involves adding 1 to 11 and subtracting 1 from 11 to get a pair of numbers, 10 and 12. Find the greatest common denominator of 10 and 15 and 12 and 15. The former is 5 and the latter is 3, which are also the factors of 15.

There are many important classes of cryptographic systems beyond RSA and DSA and ECDSA:

•Hash-based cryptography.

The classic example is Merkle’s hash-tree public-key signature system (1979), building upon a one-message-signature idea of Lamport and Diffie.

•Code-based cryptography.

The classic example is McEliece’s hidden-Goppa-code public-key encryption system (1978).

•Lattice-based cryptography.

The example that has perhaps attracted the most interest, not the first example historically, is the Hoffstein–Pipher–Silverman “NTRU” public-key-encryption system (1998).

• Multivariate-quadratic-equations cryptography.

One of many interesting examples is Patarin’s “ HFE v − ” public-key-signature system (1996), generalizing a proposal by Matsumoto and Imai.

• Secret-key cryptography.

The leading example is the Daemen–Rijmen “Rijndael” cipher (1998), subsequently renamed “AES,” the Advanced Encryption Standard.

The National Institute of Standards and Technology wrote in a 2009 survey that "[there] are viable alternatives for both public key encryption and signatures that are not vulnerable to Shor’s Algorithm” and “[of] the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical"

NTRU – Nth Degree Truncated Polynomial Ring Units (or R=Z[X]/(X^N-1))

NTRU is the first public key cryptosystem not based on factorization or discrete logarithmic problems. NTRU is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice.

References:

http://media.ccc.de/browse/congress/2013/30C3_-_5339_-_en_-_saal_1_-_201312281830_-_the_year_in_crypto_-_nadia_heninger_-_djb_-_tanja_lange.html

https://www.securityinnovation.com/products/encryption-libraries/ntru-crypto/ntru-faqs.html#ntru1

http://www.quantiki.org/wiki/Shor's_factoring_algorithm

http://www.wisdom.weizmann.ac.il/~yaakovh/PKC2007/PrivatePapers/ntru-tutorial-slides.pdf

Is NTRU vulnerable to attacks based on quantum computing?

There is no known quantum computing algorithm which speeds up attacks on NTRU.

In general, there are two quantum computing algorithms of great significance to cryptanalysis: Shor's algorithm and Grover's algorithm.

Shor's algorithm

uses the fact that quantum computing methods can calculate the period of a periodic function very quickly. This can be used to massively speed up attacks on RSA, Discrete Log based cryptosystems such as DSA and Diffie-Hellman, and Elliptic Curve Discrete Log systems such as ECDSA, ECMQV, and so on. (Note that in the case of RSA the period of the function essentially is the private key). Shor's algorithm has no obvious application to NTRU: NTRU has no similar periodic function to exploit.

Grover's algorithm

speeds up unsorted database and brute force searches: using Grover's algorithm, it is possible to search a list of N items in sqrt(N) time. This effectively halves the keylength of symmetric ciphers. However, there is no obvious application to NTRU, as in the case of NTRU the brute force attack is not the most efficient, even if sped up by Grover's algorithm. (Note that there is a known meet-in-the-middle attack on NTRU private keys which also speeds up a brute force search by a square-root factor; there is no known way to compose this speed-up with a quantum computing speed-up).

Lattice problem

Heisenberg

all in one time ,most P = right solution, ideal for DB search, factoring

Public key cryptography, like RSA, works because it is so difficult to figure out which two large numbers (keys) were multiplied to a specific result (encoded message).

A classical computer may never solve the factors of, say, a 400-digit number used in RSA.

Each factor is a 200-digit number, which means each contains more possible integer values than there are known elementary particles in the universe (1090)

Speed,factoring exponential/quadratic

How RSA works