### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# NTRU, Quantum Resistance

No description
by

## Peter Matkovski

on 19 June 2014

Report abuse

#### Transcript of NTRU, Quantum Resistance

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

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:
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)