Transcript ppt

P1363.1 D5 Overview
STRONG security that fits everywhere.
William Whyte
NTRU Cryptosystems
December 2005
Agenda
STRONG security that fits everywhere.
 Document walkthrough
 Timetable
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Document Structure
STRONG security that fits everywhere.
1. Overview
2. References
3. Definitions
4. Types of Crytographic Technique
5. Mathematical Conventions
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Document Structure (2)
STRONG security that fits everywhere.
6. The SV Family

Algorithm specification conventions
7. Data types and conversions
8. Mathematical Foundation

Ring operations; fast multiplication techniques; inversion
9. Supporting Algorithms
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Document Structure (3)
STRONG security that fits everywhere.
10. Encryption Scheme





Components
Primitives
Encoding Methods
Scheme Overview
Scheme Operations
11. Signature Scheme





Components
Primitives
Encoding Methods
Scheme Overview
Scheme Operations
12. Security Considerations
13. Bibliography
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Document Structure: Annexes
STRONG security that fits everywhere.

Editorial: Annexes listed in ToC by accident and will be
removed.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Conversion Primitives
STRONG security that fits everywhere.
 Integer to/from octet string, bit string
 Ring element to/from octet string, bit string
 Binary ring element to/from octet string, bit string
 Octet string to/from bit string
– BS2OSP in other standards pads on the left (designed for bit
strings < 1 byte or integers). X9.98 converts to “right-padded octet
string”.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Review: NTRU parameters
STRONG security that fits everywhere.
 N, dimension of polynomial ring
– NTRU works on polynomials of degree N-1
– Polynomial multiplication is convolution multiplication: terms of degree > N
are reduced mod N.
– Increases roughly linearly with k for k-bit security
 For 80-bit security, N = 251.
 q, “big” modulus
– All coefficients in polynomial are reduced mod q
– For 80-bit security, q = 197.
 Increases roughly linearly with k for k-bit security
 p, “small” modulus (Used only in NTRUEncrypt)
– Reduce mod p during decryption
– p = 2 for all security levels.
 Sizes:
– Public key, ciphertext size = N log2 q
– message size (bits) = N log2 ||p||
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Review: NTRUEncrypt Operations
STRONG security that fits everywhere.
 Key Generation
– Generate f, g, “small” polynomials in Zq[X]/(XN-1).
– Public key h = p*f-1*g mod q; private key = (f, fp = f-1 mod p).
 Encrypt (Raw operation)
– Encode message as “small” polynomial m.
– Generate “small” random polynomial r
– Ciphertext e = r*h + m mod q.
 Decrypt (Raw operation)
– Set a = f*e mod q.
 “mod q” = in range [A, A+q-1].
– Set m = fp * a mod p.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Review: Why Decryption Works
STRONG security that fits everywhere.
 a
= f * e (mod q)
= f * (r*h + m) (mod q)
= f * (r*p*g*Fq + m)
(mod q)
= p*r*g + f*m (mod q)
since f*Fq = 1 (mod q)
 All of the polynomials r, g, f, m are small, so coefficients of
p*r*g + f*m
will all lie within q of each other.
 If its coefficients are reduced into the right range, the
polynomial a(x) is exactly equal to p*r*g + f*m. Then
fp * a = p*r*g*fp (mod p) + fp*f*m (mod p) = m (mod p).
 For speed, we take f = 1+pF; then f-1 mod p = 1.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Review: SVES-3 encryption
STRONG security that fits everywhere.
b
mLen
00…
m
ID
Hash
r
XOR
r*h
Hash
m’
r*h + m’
e
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Parameter sets
STRONG security that fits everywhere.
 N, q, p
 Form of f, g
 How to produce M: Length of b, means of encoding message
length
 How to produce r: ID, PRBG algorithm, means of converting
output to polynomial (Blinding Value Generation Method)
 How to produce m’: PRBG algorithm, minimum Hamming
weight of m’
 How to decrypt: lower bound on the mod q range, called A
(always 0 in this standard)
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Subcategorization
STRONG security that fits everywhere.
 Parameters – fixed inputs
 Primitives – raw keygen, encrypt, decrypt
– Included by analogy with 1363; since there is only one scheme in
the document, should the primitives just be combined into the
schemes?
 Encoding methods – BVGM
 Supporting algorithms – Hash, PRNG, MGF
– Are these two categories logically distinct?
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Different parameter sets
STRONG security that fits everywhere.
 F, r are binary polynomials, or “product-form” (p1*p2 + p3), with
p1, p2, p3 binary
– One set of each type at each security level
– Product-form polynomial multiplications are faster: if p is productform, p*a can be calculated as p1*(p2*a) + p3*a.
 Parameter sets give number of 1s in each component
polynomial – dF and dr or df1, df2, df3, dr1, dr2, dr3
– Fixed, optimal number of 1s: more would make operations slower,
fewer would be insecure.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Key Pair Validation
STRONG security that fits everywhere.
 Key pair: check F (or f1, f2, f3) and g = fh/p have right form
according to parameter set.
 Public key plausibility test: check that a significant amount of
reduction mod q is likely to occur in calculating r*h.
 No full public key validation.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
NTRUSign
STRONG security that fits everywhere.
 Lattice-based signature scheme
 Pick two short polynomials (f, g) in ring R = Z[X]/(XN-1)
 Find (F, G) s. t. f*G – g*F = q, q an integer (power of 2)
f

F
g

G  is an R-module / lattice with det q and a basis
 Then
vectors of length N1/2, N: private key
LNTRU
1 h 


0
q

, h = g/f mod q, is an R-module / lattice with a
 And
basis of vectors of length N3/2: public key
 Signing: message is point, solve CVP for this point using good basis.
 Verification: check signature is in lattice (using bad basis) and close to
message point.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Signing & Verification
STRONG security that fits everywhere.
f
 Use full basis B = 
g
 message
F
1 G
-1
 , inverse B = 
q  g
G
hash
F

f 
(0, m)
– more efficient than (m1, m2), no security risk
 Sign with a single public basis:
(s, t) = B * Round (B-1 * (0, m))
 Transmit s.
 Verifying:
– calculate t = s*h mod q.
– make sure ||s||, ||m-t|| are small ( < N)
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Supporting Techniques
STRONG security that fits everywhere.
 Message Representative Generation
 1 – Hash message into [0, q-1]^N
 2 – Form message representative as product of small
polynomials
– Has efficiency advantages, but only in case with no perturbations
 1363.1 parameter sets only use method 1.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Security Considerations!
STRONG security that fits everywhere.
 Lattice
 All other
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Check Lattice Strength
STRONG security that fits everywhere.
 We characterize the lattice by two variables:
– c = (2N) . (2)||f||/s. = 2||f||(pe / q)
 Length of shortest vector [ (2)||f|| ]…
 Divided by expected length of shortest vector for lattice of the
same determinant [ = (N q/p e) ]…
 Scaled by (2N) .
– a = N/q.
 Experimentally, breaking time is very sensitive to c, somewhat
sensitive to a.
 Experimentally, for fixed c, a, breaking time is exponential in N.
 For all the parameter sets given in the previous slide, we have
a >= 1.25, c >= 2.58.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Lattice Strength
STRONG security that fits everywhere.
 The lower a and c, the faster
reduction algorithms run.
 Run experiments at a and c much
lower than those obtained for our
parameter sets.
– a = 0.535, c = 1.73;
– Breaking time goes as
10 .1095N - 12.6 MIPS-years.
 N = 251 ==> 1.37*1013 MIPS-years,
taking “zero-forcing” into account.
– 80-bit security: ~1012 MIPS-years
 Trend is concave upwards, and
actual NTRU lattice is stronger than
this: estimate is quite conservative.
 Paper available on X9 website
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Binary F, g, r: Combinatorial
Security
STRONG security that fits everywhere.
 F, g, r have df, dg, dr 1s respectively
 Brute force-like search on F, g, r can be speeded up by meet-in-themiddle techniques.
 Using these techniques, number of binary convolution multiplications
needed to break f is
 N / 2


 df / 2 
N
– Each multiplication requires df.N additions
 … perhaps divided by 2-8 if we use wordsize cleverly
 In general, use number of multiplications as security measure
 Attacker will go for easiest of (f, g), (r, m); pick df = dr.
 Take g = N/2: larger = greater security
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Pick q, p
STRONG security that fits everywhere.
 Our choice:
– Pick p = 2, q to be the first prime greater than
p.min(dr, dg) + 1 + p.min(df, N/2)
with large order mod N.
 This gives zero chance of decryption failures
 Minimum q to do so consistent with choice of p, df.
– Best lattice security
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Other considerations
STRONG security that fits everywhere.
 Keys (and random component b) must be generated with sufficient
entropy
– Added section B.3.1 stating that RNG should be seeded with k+64 bits
 R*h must result in a reasonable amount of reduction mod q
– Otherwise an attacker can recover r by linear algebra
 N must be prime; if it is divisible by l, can form lattice of dimension
2N/l.
 E(1) = r(1)h(1) +m’(1), and r(1) and h(1) are known; therefore, the
ciphertext leaks m’(1)
– Require m’ to be blinded.
 q must have large order mod N: similar attack to above might
otherwise leak value of m’(X) in larger fields. The chance of this
happening is qorder(q mod N).
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Other considerations (2)
STRONG security that fits everywhere.
 p and q must be relatively prime
 Need to prevent adaptive chosen ciphertext attacks with appropriate
scheme
– For k-bit security, length of random component b = k bits
– Consistent with standard security proofs.
 If q is too small relative to f, r, g, m, decryption failures can occur
– This will not happen for any of the given parameter sets
 ID is included to ensure that sender and receiver are using same
parameter set
 The blinding value r is generated as a series of indices < N
– Mechanisms in standard guarantee that these are uniformly distributed.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Security Levels: Encryption
STRONG security that fits everywhere.
 Provided parameter sets for each security level k={80, 112,
128, 160, 192, 256}.
– Do we need 160?
 2 parameter sets at each level
– “Binary”: lower bandwidth, less RAM
– “Product-form”: faster
 Standard table of strengths
– Note that SHA-160 is suitable as core of RNG up to 128-bit
security; 80-bit limit in table is for direct use as a hash function
– Captured in text, not in table.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Binary Parameter Sets
STRONG security that fits everywhere.
Parameter set
k
N
d
dm0
q
O(q)
c (F, g)
c (r, m)
T(L)
r
Tzf(L)
adds
size (bits)
ees251ep6
80
251
48
70
197
125
2.93
2.77
103.1
29
97.98
12048
2008
ees347ep2
112
347
66
108
269
173
2.94
2.83
143.9
31
138.26
22902
3033
ees397ep1
128
397
74
128
307
198
2.93
2.84
165.1
33
159.17
29378
3501
ees491ep1
160
491
91
167
367
490
2.98
2.90
205.0
35
198.75
44681
4383
ees587ep1
192
587
108
208
439
293
2.97
2.91
245.7
37
239.21
63396
5193
ees787ep1
256
787
140
294
587
393
2.95
2.91
330.6
41
323.45
110180
7690
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Product-form Parameter Sets
STRONG security that fits everywhere.
Parameter set
k
N
d
dm0
q
O(q)
c (F, g)
c (r, m)
T(L)
r
Tzf(L)
adds
size (bits)
ees251ep7
80
251
8
70
293
250
2.57
2.43
87.2
20
80.1
6024
2259
ees347ep3
112
347
11
108
541
173
2.31
2.22
117.8
16
118.7
11451
3370
ees397ep2
128
397
12
128
659
396
2.24
2.17
138.3
17
136.6
14292
3890
ees491ep2
160
491
14
167
967
490
2.08
2.02
171.3
16
170.1
22095
4870
ees587ep2
192
587
17
208
1229
293
2.02
1.97
203.3
14
204.6
29937
6347
ees787ep2
256
787
21
294
2027
393
1.78
1.73
278.1
14
276.7
51942
8459
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Signing Security Considerations
STRONG security that fits everywhere.
 To be filled in.
 Four main attacks
– Brute force search on keyspace (square-rooted by combinatorial
methods)
– Lattice reduction attack on public key to recover private key (SVP)
– Brute force search on possible signature space to find signature
(also square-rootable)
– Lattice reduction attack on public key and message to generate
signature (CVP)
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Improved Lattice Security Allows
Smaller N than for NTRUEncrypt
STRONG security that fits everywhere.
 In standard lattice ((f g) (F G)), (f g) is short vector of length
O(√N).
 In transpose lattice, (f F) is short vector of length O(N).
– Improved c by factor of √N?
 Attacker can “balance” lattice so f & F are of same length, but
changes determinant
– Improves ctranspose by factor of N1/4 compared to cstandard.
 Increase N, hold d/N constant 
– combinatorial security increases exponentially
– lattice security increases superexponentially
 Note: LHS of signature is smaller than RHS; balance with
balancing factor β.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
CVP
STRONG security that fits everywhere.
 Difficulty of solving signature by lattice reduction linked to
constant γ.
– γ = N/(σ * √(2N)).
 Norm bound …
 Divided by expected length of shortest vector…
 Scaled by 1/(√2N).
 In this case, smaller γ = required to solve CVP “better” = harder
lattice problem
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Signature Parameter Generation
STRONG security that fits everywhere.
 Want to pick (N, d, q, beta, NB) s. t.
– strength against all attacks is greater than k bits
– performance is optimized
 smallest public keys/bandwith
 fastest operations
 Paper presents iterative process:
– Loop through N, d, q
– Calculate expected size of signature
– Set NB = ρ * size of signature (ρ typically 1.1 – 1.25 – affects
chance of having to re-sign, essentially negligible for specified
parameter sets)
– Check strength against specified attacks
– Store all acceptable parameter sets: output one with best
performance using chosen metric.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Transcript Analysis
STRONG security that fits everywhere.
 If message was random within
ball of radius NormBound,
transcript could not leak
information
 Transcript is
s=d*f+D*F
– d, D are {-1/2, 1/2}N
– d, D slightly constrained: s
must have integer coefficients.
 Leaks information about
geometry of lattice
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Signing with Perturbations
STRONG security that fits everywhere.
 Message is (0, m); public basis is B0; b private bases B1 … Bb.
– Set (sb+1, tb+1) = (0, m).
 For each private basis i in turn, i = b, b-1, … 1:
– Input point is (sb+1, tb+1)
– (si, ti) = result of solving appr-CVP in basis Bi on point (si+1, ti+1).
 Signature is appr-CVP on (s1, t1) in B0.
 Can implement this such that each private basis operation
requires:
– 2 multiplies by (fi, Fi) (or (fi, gi) in transpose lattice)
– One multiply by hi.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Transcript Analysis
STRONG security that fits everywhere.
 s=d*f+D*F
– d, D are {-1/2, 1/2}N
 First moment: s averages to 0
– Subtranscripts don’t appear to help.
 Second moment: Can find quantities that behave like norms (don’t
average to 0)
– Define prev(X) = p(X-1) for any polynomial p
 if p = [f0, f1, f2, …], then prev = [f0, fN-1, fN-2, …]
– Constant coordinate of p * prev = p ¢ p = squared norm of p  0
 Other coordinates are p dotted with its rotations
– s * srev will average to non-zero result.
 Notation:
– denote average of x by
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
NTRUSign with Perturbations
STRONG security that fits everywhere.
(s, t-m) -- without
perturbations
(s, t-m) -- with
perturbations
(F,G)
(F,G)
(f,g)
(F1,G1)
(f1,g1)
(f,g)
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Security Claim for Perturbations
STRONG security that fits everywhere.
 Number of signatures required to recover private key = number
required to converge on 6th moment
– = O(29d6)
– Highly conservative
 Could be that 8th moment is actually required
 Big-O constant is considerably more than 1.
 In paper, take a single perturbation at each security level
– Required transcript is > 109.
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Improved Parameter Sets
STRONG security that fits everywhere.
 k: security level; d: f consists of d+1 +1s, d -1s, and (N-2d-1)
0s; \beta: signature normalization factor; Norm: how close you
have to be for a signature to pass
 \tau: attacker requires >> 2\tau signatures to recover private key.
k
80
112
128
160
192
256
N
157
197
223
263
313
349
d
29
28
32
45
50
75
q
256
256
256
512
512
512
\beta
0.384
0.514
0.655
0.315
0.406
0.185
Norm
150.02
206.91
277.52
276.53
384.41
368.62
\tau
31.9
32.2
31.2
34.9
35.6
38.9
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005
Timetable
STRONG security that fits everywhere.
 End of December: Complete Editorial Review and NTRUSign
Security Considerations
 January: Present to working group and request written
comments
 March: First WG vote, hopefully with comments resolved.
 May?: Go into Sponsor Ballot
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2005