Pseudorandom Functions and Lattices
Abhishek Banerjee1

Chris Peikert1

Alon Rosen2

1 Georgia Tech
2 IDC Herzliya

CRYPTO 2011 Rump Session
16 Aug 2011

1/6

Pseudorandom Functionsc

I A family F = {F : {0, 1}k → {0, 1}} s.t. (F ← F) ≈ rand function.
Oodles of applications in symmetric cryptography.

2/6Pseudorandom Functionsc

I A family F = {F : {0, 1}k → {0, 1}} s.t. (F ← F) ≈ rand function.
Oodles of applications in symmetric cryptography.
1Goldreich-Goldwasser-Micali [GGM’84]
4 Based on any PRG

2/6

Pseudorandom Functions
cI A family F = {F : {0, 1}k → {0, 1}} s.t. (F ← F) ≈ rand function.
Oodles of applications in symmetric cryptography.
1Goldreich-Goldwasser-Micali [GGM’84]
4 Based on any PRG
7 Inherently sequential, depth ≥ k for k-bit inputs

2/6

Pseudorandom Functionsc

I A family F = {F : {0, 1}k → {0, 1}} s.t. (F ← F) ≈ rand function.
Oodles of applications in symmetric cryptography.
1Goldreich-Goldwasser-Micali [GGM’84]
4 Based on any PRG
7 Inherently sequential, depth ≥ k for k-bit inputs

2

Naor-Reingold/Naor-Reingold-Rosen [NR’95,NR’97,NRR’00]
4 Based on “synthesizers” or number theory (DDH, factoring)
4 Low-depth: NC2 , NC1 or even TC02/6

Pseudorandom Functions
cI A family F = {F : {0, 1}k → {0, 1}} s.t. (F ← F) ≈ rand function.
Oodles of applications in symmetric cryptography.
1Goldreich-Goldwasser-Micali [GGM’84]
4 Based on any PRG
7 Inherently sequential, depth ≥ k for k-bit inputs

2

Naor-Reingold/Naor-Reingold-Rosen [NR’95,NR’97,NRR’00]
4 Based on “synthesizers” or number theory (DDH, factoring)
4 Low-depth: NC2 , NC1 or even TC0
7 Huge circuits that need mucho preprocessing
7 No “post-quantum” construction under standard assumptions

2/6

Our Results1

Low-depth, (relatively) small-circuit PRFs from (ring-)LWE

3/6

Our Results1

Low-depth, (relatively) small-circuit PRFs from (ring-)LWE
F

Synthesizer-based PRF in NC2 (or TC1 ) a la [NR’95]

FDirect construction in NC1 (or TC0 ) analogous to [NR’97,NRR’00]

3/6

Our Results

12

Low-depth, (relatively) small-circuit PRFs from (ring-)LWE
F

Synthesizer-based PRF in NC2 (or TC1 ) a la [NR’95]

FDirect construction in NC1 (or TC0 ) analogous to [NR’97,NRR’00]

Main technique: “derandomization” of LWE: deterministic errors

3/6

“Learning With Rounding” (LWR)
Learning With Errors (LWE)[Regev’05]

I Distinguish pairs (ai , bi = hai , si + ei ) ∈ Znq × Zq from uniform
I Interpretation: errors ei “wipe out” lsb’s of the inner products

4/6

“Learning With Rounding” (LWR)
Learning With Errors (LWE)[Regev’05]

I Distinguish pairs (ai , bi = hai , si + ei ) ∈ Znq × Zq from uniform
I Interpretation: errors ei “wipe out” lsb’s of the inner products
Learning With Rounding (LWR)[This work]
87654

9I Let q > p and define bxep = b(p/q) · xe mod p.

11

13
14
15

2

0

1112(Common in decryption to “remove noise.”)

31002321617 18 192022214/6

“Learning With Rounding” (LWR)
Learning With Errors (LWE)[Regev’05]

I Distinguish pairs (ai , bi = hai , si + ei ) ∈ Znq × Zq from uniform
I Interpretation: errors ei “wipe out” lsb’s of the inner products
Learning With Rounding (LWR)[This work]
87654

9I Let q > p and define bxep = b(p/q) · xe mod p.

I LWR: distinguish pairs
ai , bi = bhai , siep ∈ Znq × Zp
1

1013
14
15

20

1112

(Common in decryption to “remove noise.”)31023

21617 18 1920

2221

from uniform

Interpretation: “throw out” lsb’s of the inner products

4/6

“Learning With Rounding” (LWR)
Learning With Errors (LWE)[Regev’05]

I Distinguish pairs (ai , bi = hai , si + ei ) ∈ Znq × Zq from uniform
I Interpretation: errors ei “wipe out” lsb’s of the inner products
Learning With Rounding (LWR)[This work]
87

6

54

9I Let q > p and define bxep = b(p/q) · xe mod p.

I LWR: distinguish pairs
ai , bi = bhai , siep ∈ Znq × Zp
1

10131415

201112(Common in decryption to “remove noise.”)31023

21617 18 19

2022
21

from uniform

Interpretation: “throw out” lsb’s of the inner products
I We prove LWE ≤ LWR for appropriate parameters
4/6

Synthesizer-Based PRF (a la [NR’95])
Synthesizer from LWR
I For random a1 , a2 , . . . and s1 , s2 , . . . (mod q),bhai , sj iepc

i, j≈ uniform mod p

5/6

Synthesizer-Based PRF (a la [NR’95])
Synthesizer from LWR
I For random a1 , a2 , . . . and s1 , s2 , . . . (mod q),bhai , sj iepc

i, j≈ uniform mod pd

PRF on Domain {0, 1}k=2 (e.g. d = 7)
I (Public) moduli qd > qd−1 > · · · > q0 .
I Secret key is 2k square matrices Si,b ∈ Zn×nfor i ∈ [k], b ∈ {0, 1}.
qd(Or ring elements si,b using ring-LWR [LPR’10].)

5/6

Synthesizer-Based PRF (a la [NR’95])
Synthesizer from LWR
I For random a1 , a2 , . . . and s1 , s2 , . . . (mod q),bhai , sj iepc

i, j≈ uniform mod pd

PRF on Domain {0, 1}k=2 (e.g. d = 7)
I (Public) moduli qd > qd−1 > · · · > q0 .
I Secret key is 2k square matrices Si,b ∈ Zn×n
for i ∈ [k], b ∈ {0, 1}.
qd(Or ring elements si,b using ring-LWR [LPR’10].)I Depth d = lg k tree of LWR synthesizers:F(x1 · · · x8 ) =jm jm bS1,x1 · S2,x2 eq2· bS3,x3 · S4,x4 eq2 · bS5,x5 · S6,x6 eq2· bS7,x7 · S8,x8 eq2
q1

q1 q05/6

Shallower: A Direct Construction
I Public moduli q > p.
I Secret key is ring elements a, s1 , . . . , sk modulo q

6/6

Shallower: A Direct Construction
I Public moduli q > p.
I Secret key is ring elements a, s1 , . . . , sk modulo q
I “Rounded subset-product” function:$'kY
F(x1 · · · xk ) = a ·sxi i mod q .
i=1p

I Very efficient evaluation in TC0 , by reduction to subset-sum

6/6

Shallower: A Direct Construction
I Public moduli q > p.
I Secret key is ring elements a, s1 , . . . , sk modulo q
I “Rounded subset-product” function:$'kY
F(x1 · · · xk ) = a ·sxi i mod q .
i=1p

I Very efficient evaluation in TC0 , by reduction to subset-sum

Details: ePrint report #2011/401
6/6