Trapdoors for Lattices:
Simpler, Tighter, Faster, Smaller
Daniele Micciancio1

Chris Peikert2

1 UC San Diego
2 Georgia Tech

CRYPTO Rump Session
16 Aug 2011

1/5

Lattice-Based One-Way Functionshi$
I Public key · · · A · · · ←Zn×m
for q = poly(n), m = O(n log q)q

2/5

Lattice-Based One-Way Functionshi$
I Public key · · · A · · · ←Zn×m
for q = poly(n), m = O(n log q)
qfA (x) = Ax mod q

gA (s, e) = st A + et mod q(surjective)(injective)

OWF if SIS hard [Ajtai’96]

OWF if LWE hard [Regev’05]

2/5

Lattice-Based One-Way Functionshi$
I Public key · · · A · · · ←Zn×mfor q = poly(n), m = O(n log q)
qfA (x) = Ax mod q

gA (s, e) = st A + et mod q(surjective)(injective)

OWF if SIS hard [Ajtai’96]

OWF if LWE hard [Regev’05]

I fA , gA in forward direction yields CRHFs, IND-CPA encryption(. . . and not much else)

2/5Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .

3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert bt = gA (s, e) = st A + et :find the unique preimage s, e

3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert u = fA (x) = Ax:

Invert bt = gA (s, e) = st A + et :sample Gaussian x ← fA−1 (u)find the unique preimage s, e

3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert u = fA (x) = Ax:

Invert bt = gA (s, e) = st A + et :sample Gaussian x ← fA−1 (u)find the unique preimage s, e

I How? Use a “strong trapdoor” for A: a short basis[Babai’86,GGH’97,Klein’01,GPV’08,P’10]

3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert u = fA (x) = Ax:

Invert bt = gA (s, e) = st A + et :sample Gaussian x ← fA−1 (u)find the unique preimage s, e

I How? Use a “strong trapdoor” for A: a short basis[Babai’86,GGH’97,Klein’01,GPV’08,P’10]

I Crypto applications: [GPV’08, PW’08, PV’08, PVW’08, P’09, CHKP’10,R’10, ABB’10a, GHV’10, B’10, ABB’10b, GKV’10, BF’11a, BF’11b, OPW’11, . . . ]3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert u = fA (x) = Ax:

Invert bt = gA (s, e) = st A + et :sample Gaussian x ← fA−1 (u)find the unique preimage s, eI How? Use a “strong trapdoor” for A: a short basis[Babai’86,GGH’97,Klein’01,GPV’08,P’10]

I Crypto applications: [GPV’08, PW’08, PV’08, PVW’08, P’09, CHKP’10,R’10, ABB’10a, GHV’10, B’10, ABB’10b, GKV’10, BF’11a, BF’11b, OPW’11, . . . ]Some Practical Drawbacks. . .
7 Generating A with short basis is complicated & slow [Ajtai’99,AP’09]

3/5

Trapdoor Inversion
I Many cryptographic applications need to invert fA and/or gA .
Invert u = fA (x) = Ax:

Invert bt = gA (s, e) = st A + et :sample Gaussian x ← fA−1 (u)find the unique preimage s, e

I How? Use a “strong trapdoor” for A: a short basis[Babai’86,GGH’97,Klein’01,GPV’08,P’10]

I Crypto applications: [GPV’08, PW’08, PV’08, PVW’08, P’09, CHKP’10,R’10, ABB’10a, GHV’10, B’10, ABB’10b, GKV’10, BF’11a, BF’11b, OPW’11, . . . ]Some Practical Drawbacks. . .
7 Generating A with short basis is complicated & slow [Ajtai’99,AP’09]
7 Inversion algorithms either are sequential & need bigints, or arefor suboptimal dimension m and preimage “quality.”
3/5

Our Contributions
New trapdoor generation and inversion algorithms:

4/5

Our Contributions
New trapdoor generation and inversion algorithms:
4 Much, much simpler & faster
FTo generate: one matrix mult.

F

To invert fA , gA : efficient, highly parallel, & mostly offline

4/5

Our Contributions
New trapdoor generation and inversion algorithms:
4 Much, much simpler & fasterF

To generate: one matrix mult.

F

To invert fA , gA : efficient, highly parallel, & mostly offline

4 Tighter, more secure parametersF

Asymptotically optimal with small constant factors

FImprovements: 8x in dim m, 112x in “quality” ⇒ 50x in keysize

4/5

Our Contributions
New trapdoor generation and inversion algorithms:
4 Much, much simpler & fasterF

To generate: one matrix mult.

F

To invert fA , gA : efficient, highly parallel, & mostly offline

4 Tighter, more secure parametersF

Asymptotically optimal with small constant factors

F

Improvements: 8x in dim m, 112x in “quality” ⇒ 50x in keysize

4 New trapdoor notion (not a basis!): 4x smaller, easier delegation

4/5

Our Contributions
New trapdoor generation and inversion algorithms:
4 Much, much simpler & faster
FTo generate: one matrix mult.

FTo invert fA , gA : efficient, highly parallel, & mostly offline

4 Tighter, more secure parametersF

Asymptotically optimal with small constant factors

FImprovements: 8x in dim m, 112x in “quality” ⇒ 50x in keysize

4 New trapdoor notion (not a basis!): 4x smaller, easier delegation
4 More efficient applications beyond “black box” improvements:
FCCA encryption with smaller keys

(subsumes [PW’08,P’09,ABB’10a])F

Short, standard-model signatures(improves [CHKP’10,R’10,B’10])

4/5

Trapdoor Generation and Algorithms
1

Start from a special (fixed, public) lattice defined by G.
F

Give very fast, parallel, offline algorithms for fG−1 , g−1
GFConcretely,
1 2 · · · 2q
G = In ⊗ [1, 2, 4, . . . , q2 ] = 


1 2 ···q2..

.
1 2 · · · 2q




5/5

Trapdoor Generation and Algorithms
1

Start from a special (fixed, public) lattice defined by G.
F

Give very fast, parallel, offline algorithms for fG−1 , g−1
GFConcretely,
1 2 · · · 2q
G = In ⊗ [1, 2, 4, . . . , q2 ] = 2
1 2 ···

q2..

.
1 2 · · · 2q






Randomize G ↔ A with a “nice” unimodular transformation:

I R
A = [Ā | G]
= [Ā | G + ĀR]
I

5/5

Trapdoor Generation and Algorithms
1Start from a special (fixed, public) lattice defined by G.
F

Give very fast, parallel, offline algorithms for fG−1 , g−1
GFConcretely,
1 2 · · · 2q
G = In ⊗ [1, 2, 4, . . . , q2 ] = 23
1 2 ···q2..

.
1 2 · · · 2q






Randomize G ↔ A with a “nice” unimodular transformation:

I R
A = [Ā | G]
= [Ā | G + ĀR]
I
Efficiently reduce fA−1 , g−1
to fG−1 , g−1
A
G with pre-/post-processing

5/5Trapdoor Generation and Algorithms
1Start from a special (fixed, public) lattice defined by G.
F

Give very fast, parallel, offline algorithms for fG−1 , g−1
GFConcretely,
1 2 · · · 2q
G = In ⊗ [1, 2, 4, . . . , q2 ] = 23


1 2 ···q
2..

.
1 2 · · · 2q






Randomize G ↔ A with a “nice” unimodular transformation:

I R
A = [Ā | G]
= [Ā | G + ĀR]
I
Efficiently reduce fA−1 , g−1
to fG−1 , g−1
A
G with pre-/post-processing

Coming very soon to an eprint near you. . .
5/5