Transcript Parameters-1363-2004

Choosing
NTRUEncrypt
Parameters
William Whyte
NTRU Cryptosystems
March 2004
PROPRIETARY AND CONFIDENTIAL
Agenda
 Parameter Generation
– How to pick parameters to obtain a given security level?
 We present a recipe for parameter generation
 Will 1363.1use this recipe, or simply the constraints that come
out of it?
– Multiple parameter forms
 Standard form, product form
– Possible bandwidth savings – NTRU-KEM
 Key validation
 But first…
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
2
Review: NTRU parameters
 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.
– For 80-bit security, N = 251.
 Increases roughly linearly with k for k-bit security
 q, “big” modulus
– All coefficients in polynomial are reduced mod q
– For 80-bit security, q = 239.
 Increases roughly linearly with k for k-bit security
 p, “small” modulus
– Reduce mod p during decryption
– p = 2, 2+X or 3 for all security levels.
 Sizes:
– Public key, ciphertext size = N log2 q = 2004 bits for 80-bit security
– message size (bits) = N log2 ||p|| = 251 bits for 80-bit security
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
3
Review: NTRUEncrypt Operations
 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.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
4
Review: Why Decryption Works
 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 (usually) 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).
 Current parameter sets for 280 security include means for choosing
this range. Choice of range fails on validly encrypted message one
time in 2104.
– “Decryption failures”
– Attatcker gains information from decryption failures: wants to choose
funky r, m.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
5
Review: SVES-3 encryption
b
mLen
00…
m
ID
Hash
r
XOR
r*h
Hash
m’
r*h + m’
e
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
6
Parameter Generation
 Input: k, the desired level of security
 Process:
– Choose N
 Set N to give necessary bandwidth
– Choose form of f, g, r
 Ensure combinatorial security
– Choose q, p
 Set q to prevent decryption failures
– Ensure that these parameters give appropriate lattice security
 There are many different ways of making these choices.
– These are the proposed ones for X9.98
 Note: extremely provisional and may change as the analysis
proceeds
– Currently writing up a paper to formalize them
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
7
Choose N
– With binary messages, N is the number of bits that can be
transported
– For k bits of security for key transport, want to transport 2k bits of
material
 Prevent birthday-like attacks based on future use of material
– For SVES-3, want to use at least k bits of random padding
 Gives security against enumeration attacks if encryption
scheme is used to transport low-entropy messages
– Set N to be the first prime greater than 3k.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
8
Choose form of f, g, r
 Our choice:
– Take f = 1+pF
 Speeds up decryption: f-1 mod p= 1, so we eliminate a
convolution
– Take F, g, r to be binary with df, dg, dr 1s respectively.
 Number of additions necessary for convolution is df*N.
 Alternatives:
– Take f not to be of form 1+pF
 Slows down decryption but reduces q (see next choice)
– Take f (or F), g, r to be of the form (e.g.) f = f1 * f2 + f3.
 “Product form”:
 Number of additions necessary for convolution is (f1 + f2 +
f3)*N.
– Performance benefit
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
9
Binary F, g, r: Combinatorial
Security
 F, g, r have df, dg, dr 1s respectively
 Brute force-like search on F, g, r can be speeded up by meetin-the-middle 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 = dg.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
10
df, dg, dr for different security levels
 N and df, using the above criteria:
k
N
df
80
251
49
112
337
66
128
389
74
160
487
92
192
577
110
256
769
142
 df ~= 0.185 N.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
11
Pick q, p
 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
 Alternatives:
– Take p = 2+X or 3, q = first power of 2 greater than p(1).min(dr, dg) + 1 +
p(1).min(df, N/2)
 Taking q to be power of 2 speeds up reductions
 Larger value of p leads to larger q and worse lattice security
– Take p = 2, q = largest prime less than first power of 2 greater than
p(1).min(dr, dg) + 1 + p(1).min(df, N/2)
 Speeds up reductions at expense of lattice security
– Allow a non-zero chance of decryption failures, if it can be determined to
be less than 2-k.
 Reduces q, improves bandwidth and lattice security
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
12
df, q for different security levels
 N, df, q, using the above criteria:
k
N
df
q
80
251
49
199
112
337
66
269
128
389
74
307
160
487
92
373
192
577
110
443
256
769
142
571
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
13
Check Lattice Strength
 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.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
14
Lattice Strength
 Based on the above experiments:
k
N
df
q
c
Lattice
bitstrength
80
251
49
199
2.60
88
112
337
66
269
2.60
120
128
389
74
307
2.58
139
160
487
92
373
2.61
174
192
577
110
443
2.62
207
256
769
142
571
2.63
277
 Neglecting zero-forcing; also neglecting fact that the lattices under
consideration are stronger than the ones experimented on.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
15
More Notes on Parameter
Generation
 Note how df affects lattice strength:
– For these parameters, q ~= 2p df, ||f|| ~= df, c ~= ||f||/q
 c is ~independent of df!
 More precisely: ||f|| >= (df/2). Run expts for c = (pe / p) = 2.066?
 Rounding q up to next prime reduces min(c) slightly, not much.
 If we use the number of additions, not multiplications, as measure of
combinatorial security, we can reduce df by typically 10-25%
– Gain decreases as N increases
– Reducing df reduces q  potentially improves bandwidth
 Using product form (f = f1 * f2 + f3) improves efficiency but increases q
– Increased bandwidth, but typically only by one bit
 Using trinary (f, g) gives greater combinatorial security
 So many appealing choices…
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
16
Product Form
 Interested in meet-in-the-middle attacks on product form
– df1 = df2 = df3
 Standard search, described in Tech Note 4, takes on (f1*f2) and (f3)
– Could also remove a 1 from f2, add df 1s to f3
 df =~ 0.032 N for N = 251, 0.028 N for N = 769
N
df1
251
8
337 11
389 12
487 15
577 17
769 22
PROPRIETARY AND CONFIDENTIAL
f1
search
41.98
60.57
67.76
86.94
100.8
134
f1*f2
83.97
121.1
135.5
173.9
201.6
268.1
f3
search
48.31
66.87
74.16
93.35
107.3
140.5
f1* most
(f2)
78.8804
116.115
130.416
168.811
196.404
262.885
f3 + f2
search
82.59
113.79
126.4
158.81
182.64
239.22
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
17
Product Form Speedups, Keygen,
Lattice Consideration
k
N
standard
df
product speedup
df
factor
effective
df
q
c
80
251
49
8
2.04
72
241
2.52
112
337
66
11
2
132
397
2.37
128
389
74
12
2.06
156
461
2.35
160
487
92
15
2.04
240
673
2.19
192
577
110
17
2.16
306 = 271
769
2.24
256
769
142
22
2.15
506 = 263
811
2.44
 Speed up typically factor of 2 over standard form
 Keygen will get slow for larger N -- haven’t done calculations
 For even larger N, guessing zeroes becomes better than guessing f
 Increased df doesn’t affect lattice strength (much)
– c = 2.05 experiments would still be fine
 Bandwidth increases only for k=160 and 192, by 1 bit per coeff
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
18
NTRU-KEM?
ID
b
Hash1
r
XOR
Hash2
r*h
m’
r*h + m’
e
Hash3
PROPRIETARY AND CONFIDENTIAL
K
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
19
Parameters for NTRU-KEM
 Still taking p = 2.
 Now, only have to transmit about 2k bits, so can save
bandwidth
 For k-bit security:
– Pick N = 2k
–
–
–
–
–
Pick df = N/2
Increase N until combinatorial security is > 2k.
Take df, dr, dg, to be the same
Take f=1+pF
Set q as before
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
20
Parameter Sets
 This gives the following (note: c >= 2.05, so we omit it).
 In some cases, slightly increasing N decreases log2(q); we’ve
done this where it helps. Note: q needs rounding up.
k
N
df
q
Number
of adds
SVES-3
adds
bwdth
SVES-3
bwdth
RSA
bwdth
80
176
80
321
14080
12299
1584
2008
1024
112
240
120
481
28800
22242
2160
3033
~2048
128
272
134
537
36448
28786
2720
3501
3072
128
274
124
501
33976
28786
2466
3501
3072
160
338
168
673
56784
44804
3380
4383
4096
192
400
200
801
80000
63470
4000
5193
7680
256
532
255
1021
135660
109198
5320
7690
15360
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
21
Speeding up?
 The parameters above successfully reduce bandwidth
 Can we improve speeds?
 Taking small polynomials to be {-1, 0, 1} improves
combinatorial security
– Taking them to be {-2, -1, 0, 1, 2} would do even better, but…
– The wider the polynomials are, the wider2 their products are
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
22
Trinary polynomials
 Take p to be 3.
 f, g, r, m could be trinary
 Two different forms:
– Balanced: Equal +1s and –1s
– Biased: Minimum possible number of –1s
 Set N/2 1s, N/2 0s
 If this doesn’t give enough combinatorial security, set some of the 0s
to –1s.
 Once there is adequate combinatorial security, see if we can reduce
the number of 1s
 End with dg+ 1s, dg- -1s
 Combinatorial security estimated as sqrt ((N pick dg+)(N pick dg-)) /
N
– This needs to be made more precise
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
23
Polynomial width
 Consider a*b:
–
–
–
–
–
a has da+ +1s, da- -1s
b has db+ +1s, db- -1s
Maximum value if all +1s line up, all –1s line up.
Minimum value if all +1s line up with –1s.
Maximum width is Min(da+, db+) + Min(da-, db-) + Min(da+, db-) +
Min(da-, db+)
 Advantage of having one balanced, one biased is we reduce this width
compared to two balanced or two biased.
 Take f, r to be balanced trinary
– Gives lowest Hamming weight
 Take g to be biased trinary
 Consider m on next slide
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
24
Choosing N and encoding m
 Say we choose N to be ~2k
– Then biased polynomials have very few –1s.
 Want to transmit k bits of entropy
– Attacker can meet-in-the-middle on m’
 Could draw m’ from a space of 3N polynomials
– But this might be tiresome
– Open question: exactly how tiresome? Certainly tiresome in that
output of Hash2 needs to be encoded as random trinary vector,
involving repeated mod 3 divides of big integer
 Suggestion: Take b, output of Hash2, m’ to be binary
– Once m’ is generated, flip some terms (only 1s or only 0s) to –1s
to obtain combinatorial security
– If more than (say) 4 need to be flipped, generate another b.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
25
Recipe
 Choose N to be first prime > 2k
 Choose F, r to be balanced trinary
– (Actually, choose dr+ = dr- +1 for invertibility)
 Choose g to be biased trinary
 Choose f = 1+pF
– f(1) should not be 0 mod 2
 Say m’ will have no more than 4 –1s
 Maximum width is df + dr + dg- + 4
 Set q = the first power of 2 greater than this width
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
26
Parameter Sets
 This gives the following (note: c >= 2.11, so we omit it)
 df ~= 0.115 N, compared to 0.185 for SVES-3; time = N2.
k
N
df
dg+ dg-
q
adds
SVES3
adds
bwdth
SVES3
bwdth
RSA
bwdth
80
163
20
66
2
256
6520
12299
1304
2008
1024
112
227
28
94
2
256
12712
22242
1816
3033
~2048
128
257
31
112
2
256
15934
28786
2056
3501
3072
160
331
38
126
2
256
25156
44804
2648
4383
4096
192
389
46
164
2
512
35788
63470
3501
5193
7680
256
521
60
220
2
512
62520
109198
4689
7690
15360
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
27
Notes:
 We gain a speedup of a factor of about 2 over standard SVES-3
– Comparable to (though slightly worse than) speedup from move to
product form
– Could consider product form here too, but there seem to be few
advantages
 Bandwidth is about 0.65 of SVES-3 bandwidth
– Bandwidth is between 16 k and 18.3 k for security k
– Goes slightly worse than k, slightly better than k ln k.
 Lattice strength is a BIG question here
– Not clear that you can get 80 bits of lattice strength at N=163
– Equally, not 100% clear that you can’t….
– Can increase lattice strength by beefing up dg+, but this only goes so far
 Requires an additional SHA at the end
– But on fewer SHA compression blocks
– End up with about 2*0.65 = 1.3 as many SHA calls
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
28
Parameter Generation: Summary
 Outlined a possible parameter generation routine for NTRU
– Put in k, turn the handle, out come the parameters
– Parameters can be validated by third parties
 Specific parameter generation routine may change, but basic
method remains the same:
–
–
–
–
Choose N
Choose form of f, g, r, m
Choose q
Check lattice strength; if too low, increase N to next prime and try
again.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
29
Open Questions
 How many parameter sets do we want?
– Optimize speed
– Optimize bandwidth
– Optimize for 8-bit processors?
 Can be done by increasing N  decreasing q < 256 (or 128)
 Do we ever want to allow decryption failures for k > 80?
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
30
Open Research Questions
 Is it okay to use SHA-160 as the core hash function for k > 80?
– I think yes, but this needs discussion
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
31
Key Validation
 What can go wrong with an NTRUEncrypt public key h? Should
be random mod q.
– Might be all zeroes
 Reveals message immediately
– If q is composite and gcd(hi, q) != 1 for all hi, might be possible to
recover message from ciphertext by simple modular reduction.
– If h is too thin, such that r*h will have very few mod q reductions
(< 2k effort to guess reduction locations), can recover message
from ciphertext by linear algebra.
 Possible simple key validation procedure:
– Check that keys are not all the same value
– Check that sufficient number of hi have gcd(hi, q) = 1
– Check that width of h > c. q/df, c > 1 some parameter set
dependent constant.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
32
Key Validation (2)
 More sophisticated:
– Measure how “random” h looks. For example:
 Chance that a given mod q value does not occur anywhere in
h=
(1-1/q)N
 Find value l such that for random h the probability that l
distinct values do not occur anywhere in h is less than 2-k.
– A different bound may be appropriate
 Count the number of distinct values that do not occur in h and
reject if greater than l.
 Next draft will contain suggested text.
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
33
Issue: Forward Secrecy (1)
 NTRU key generation is efficient
– Can generate ephemeral keypairs easily
 This + next slide propose three ways of getting perfect forward
secrecy using this fact
– Do these actually give forward secrecy?
– Do they give mutual authentication?
– Should they be included in the standard?
 (1) Say Alice has static keypairs (as, As).
– Bob generates ephemeral keypair (be, Be), sends Alice EAs(Be).
 This may have to be signed
– Alice uses Be as the public key for key transport or key agreement
– Afterwards, Bob disposes of (be, Be).
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
34
Issue: Forward Secrecy (2)
 (2) Say Alice and Bob have static, certified keypairs (as, As), (bs, Bs).
– Bob generates ephemeral keypair (be, Be), sends Alice EAs(Be).
– Alice uses both Bs and Be in two runs of a key transport or key agreement
mechanism, combines the two transported keys to get a single shared
key.
– Afterwards, Bob disposes of (be, Be).
 (3) Say Alice and Bob have static, certified keypairs (as, As), (bs, Bs).
–
–
–
–
–
Bob generates ephemeral keypair (be, Be), sends Alice EAs(Be).
Alice generates ephemeral keypair (ae, Ae), sends Bob EBs(Ae).
Alice uses Be to transport secret k1 to Bob
Bob uses Ae to transport secret k2 to Alice
Bob and Alice combine k1, k2 to get shared secret k.
 Note: need to define encryption carefully above: will probably be
symmetric+public-key operation
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
35
That’s it!
 Questions?
PROPRIETARY AND CONFIDENTIAL
NTRU CRYPTOSYSTEMS, INC. COPYRIGHT © 2004
36