NTRUSign Introduced

December 2001
Jeff Hoffstein, Nick Howgrave-Graham, JillPipher, Joe Silverman, William Whyte

Communications & Content Security

1

CRYPTO OVERVIEWPolynomial Ring••a( x) ∈ Ζ [ X ] / X N − 1a(X) = a0 + a1X + a2X2 + … + aN-1XN-1

a b 
c d 
Communications & Content Security

a b 
c d 

2

CRYPTO OVERVIEWNTRU Lattice

1 h 
LNTRU = 
0 q 
• h= g/f mod q• so (f, g) ∈ LNTRU– know small vector, but not entire basisCommunications & Content Security

3

NTRUSign Overview• Lattice described by public key h• Signer knows complete good basis for the lattice derived from two
short polynomials f, g• Signing:– Given message digest m, find (s, t = s h), a point in NTRU lattice veryclose to(0, m).
– Signature is s.

• Verification:– Check that (s, s h) is very close to (0, m)

Communications & Content Security

4

NTRUSign in pictures

4.6
5 (f,g) +1 (F,G)

(F,G)
1.3
(f,g)

Communications & Content Security

5

NTRUSign in pictures

(0,q)

(1,h)

(F,G)

5 (f,g)(f,g) ++1 (F,G)(F,G)-16 (0,q) + 27 (1,h)(f,g)

Communications & Content Security

6

NSS UPDATE

Keygen (1): Finding a UnimodularMatrix• Want to find a,b s.t.

fdet ag
= 1.
b

• i.e. fb – ag = 1 mod XN-1
• Solve using resultants:– α1 f + β1(XN-1) = R1
– α2 g + β2(XN-1) = R2
– u R1 + v R2 = 1– u α1 f + v α2 g = 1 mod XN-1

Communications & Content Security

7
Proprietary & Confidential – Copyright © 2001

NSS UPDATE

Keygen (2): Producing the NTRU
Latticefdet ag=1bgfdet =q
qa qbfdet FCommunications & Content Security

g
=q
G
8

Proprietary & Confidential – Copyright © 2001

NSS UPDATE

Keygen (3): Making F, G smallx

fx = (q a)= (q a)α1

1R1• For N = 251, typically ||f, g|| = 11, ||F, G|| = 45
Communications & Content Security

9Proprietary & Confidential – Copyright © 2001

NSS UPDATE

Signing & Verificationf• Use full basis Fg
1 G , inverse Gq − F• messagehash− gf (0, m)• If basis for entire lattice is B, then signing is:(s, t) = B * round (B-1 * (0, m))• Transmit s.
• Verifying:– calculate t = s*h mod q.
– make sure ||s||, ||m-t|| are small ( < NormBound)

Communications & Content Security

10Proprietary & Confidential – Copyright © 2001

Security Analysis• Direct forgery = solving appr-CVP in NTRU lattice• Transcript analysis:– No chosen message attack in RO model by definition• RO maps H(m) to {-q/2, q/2}N.

– If message was random within ball of radius NormBound, transcript
could not leak information– Transcript iss = d * f + D * F where• d, D are {-1/2, 1/2}N• d, D slightly constrained: s must have integer coefficients.

– In low dimension, leaks information about geometry of lattice; in highdimension, appears to require impractically long transcripts (> 109).
• Further details to appear in next version of preprint

Communications & Content Security11Performance of New Scheme(provisional)•NTRUSign-251 on 800Mhz Pentium III Win 2k Visual C++ (no assembler)– 2000 sigs/sec– 3300 verifications/sec•

Compare:– RSA 1024 (MIRACL, Mike Scott)• Sign: 105/sec, Verify: 2200/sec– ECC over GF (2163) (Hankerson, Hernandez, Menezes)• Random curves: 616 point multiplies/sec, ~ 616 signs/sec, ~528 verifies/sec• Koblitz curves: 1025 point multiplies/sec, ~ 1025 signs/sec, ~880 verifies/sec•

on 16 MHz 8051 without coprocessor– < 200ms for 1 signature– < 180ms for 1 verification– RSA 420 ms for signature with coprocessor; ECC 120 ms for signature withcoprocessor

Communications & Content Security

12

Further information• Preprint available from http://www.ntru.com• New Challenge problems also posted

Communications & Content Security

13