New and Improved Key-Homomorphic Pseudorandom Functions

Document technical information

Format pdf
Size 407.6 kB
First found Nov 13, 2015

Document content analysis

Category Also themed
Language
English
Type
not defined
Concepts
no text concepts found

Persons

Seth MacFarlane
Seth MacFarlane

wikipedia, lookup

Organizations

Transcript

New and Improved
Key-Homomorphic Pseudorandom Functions
Abhishek Banerjee1
1 Georgia
Chris Peikert1
Institute of Technology
CRYPTO ’14
19 August 2014
Outline
1
Introduction
2
Construction, Parameters and Efficiency
3
Proof of Security (Idea)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
1 / 11
Outline
1
Introduction
2
Construction, Parameters and Efficiency
3
Proof of Security (Idea)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
1 / 11
Pseudorandom Functions
[GGM’84]
A family of functions F = {Fs : {0, 1}k → B} such that, given
adaptive query access,
Fs ← F
6
c
≈
?
xi Fs (xi )
Random U
6
xi
?
U (xi )
??
Lots of applications in symmetric key cryptography: encryption,
message authentication, friend or foe identification, . . .
(Thanks to Seth MacFarlane for the adversary)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
2 / 11
Cooking a (Provably Secure) PRF
1
Goldreich-Goldwasser-Micali [GGM’84]
Based on any (doubling) PRG: Fs (x1 , . . . , xk ) = Gxk (· · · (Gx1 (s)) · · · )
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
3 / 11
Cooking a (Provably Secure) PRF
1
Goldreich-Goldwasser-Micali [GGM’84]
Based on any (doubling) PRG: Fs (x1 , . . . , xk ) = Gxk (· · · (Gx1 (s)) · · · )
2
Number-theoretic direct constructions [NR’97, NRR’00]
Framework: exponentiate to a product of (secret) exponents
Security from number-theoretic assumptions (DDH, factoring, . . . )
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
3 / 11
Cooking a (Provably Secure) PRF
1
Goldreich-Goldwasser-Micali [GGM’84]
Based on any (doubling) PRG: Fs (x1 , . . . , xk ) = Gxk (· · · (Gx1 (s)) · · · )
2
Number-theoretic direct constructions [NR’97, NRR’00]
Framework: exponentiate to a product of (secret) exponents
Security from number-theoretic assumptions (DDH, factoring, . . . )
3
Lattice-based direct constructions [BPR’12]
Framework: round a product of (secret) matrices/ring elements
Security from lattice assumptions (LWE, worst-case lattice problems)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
3 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications:
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications: distribute the operation of a Key Distribution Center,
1
DDH-based construction [NPR’99]
Security in the random oracle model
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications: distribute the operation of a Key Distribution Center,
symmetric-key proxy re-encryption, updatable encryption, and PRFs
secure against related-key attacks [BC’10,LMR’14]
1
DDH-based construction [NPR’99]
Security in the random oracle model
2
Lattice-based construction [BLMR’13]
Security in the standard model; construction and proof similar to
[BPR’12] rounded-subset-product construction
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications: distribute the operation of a Key Distribution Center,
symmetric-key proxy re-encryption, updatable encryption, and PRFs
secure against related-key attacks [BC’10,LMR’14]
1
DDH-based construction [NPR’99]
Security in the random oracle model
2
Lattice-based construction [BLMR’13]
Security in the standard model; construction and proof similar to
[BPR’12] rounded-subset-product construction
Main drawback: has huge parameters, keys, and runtimes
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications: distribute the operation of a Key Distribution Center,
symmetric-key proxy re-encryption, updatable encryption, and PRFs
secure against related-key attacks [BC’10,LMR’14]
1
DDH-based construction [NPR’99]
Security in the random oracle model
2
Lattice-based construction [BLMR’13]
Security in the standard model; construction and proof similar to
[BPR’12] rounded-subset-product construction
Main drawback: has huge parameters, keys, and runtimes
also gives (non-KH) PRFs having much better parameters,
with slightly worse (still polylog) depth
[BPR’12]
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Key-Homomorphic Pseudorandom Functions
Key Homomorphism
Can efficiently compute Fs+t (x) from Fs (x) and Ft (x)
Applications: distribute the operation of a Key Distribution Center,
symmetric-key proxy re-encryption, updatable encryption, and PRFs
secure against related-key attacks [BC’10,LMR’14]
1
DDH-based construction [NPR’99]
Security in the random oracle model
2
Lattice-based construction [BLMR’13]
Security in the standard model; construction and proof similar to
[BPR’12] rounded-subset-product construction
Main drawback: has huge parameters, keys, and runtimes
also gives (non-KH) PRFs having much better parameters,
with slightly worse (still polylog) depth
[BPR’12]
Can we obtain similar tradeoffs for KH-PRFs?
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
4 / 11
Our Results
? New KH-PRFs (from lattices):
˜
Polylog O(1)
depth (still)
˜
Quasi-optimal O(λ)
key sizes
˜
First sublinear-depth PRFs (KH or otherwise) with O(λ)
key size!
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
5 / 11
Our Results
? New KH-PRFs (from lattices):
˜
Polylog O(1)
depth (still)
˜
Quasi-optimal O(λ)
key sizes
˜
First sublinear-depth PRFs (KH or otherwise) with O(λ)
key size!
Reference
Key
Pub Params
Time/Bit
[BLMR’13]
λ3 [λ3 ]
λ6 [λ4 ]
λ5 [λ3 ]
This work
λ [λ]
λ2 [λ]
λω [λ]
Figure : For input length λ with 2λ security under standard assumptions.
Log factors omitted. Ring-based constructions appear in [brackets].
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
5 / 11
Our Results
? New KH-PRFs (from lattices):
˜
Polylog O(1)
depth (still)
˜
Quasi-optimal O(λ)
key sizes
˜
First sublinear-depth PRFs (KH or otherwise) with O(λ)
key size!
Reference
Key
Pub Params
Time/Bit
[BLMR’13]
λ3 [λ3 ]
λ6 [λ4 ]
λ5 [λ3 ]
This work
λ [λ]
λ2 [λ]
λω [λ]
Figure : For input length λ with 2λ security under standard assumptions.
Log factors omitted. Ring-based constructions appear in [brackets].
? New proof technique that may be useful elsewhere
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
5 / 11
Our Results
? New KH-PRFs (from lattices):
˜
Polylog O(1)
depth (still)
˜
Quasi-optimal O(λ)
key sizes
˜
First sublinear-depth PRFs (KH or otherwise) with O(λ)
key size!
Reference
Key
Pub Params
Time/Bit
[BLMR’13]
λ3 [λ3 ]
λ6 [λ4 ]
λ5 [λ3 ]
This work
λ [λ]
λ2 [λ]
λω [λ]
Figure : For input length λ with 2λ security under standard assumptions.
Log factors omitted. Ring-based constructions appear in [brackets].
? New proof technique that may be useful elsewhere
Full version: http://eprint.iacr.org/2014/074
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
5 / 11
Outline
1
Introduction
2
Construction, Parameters and Efficiency
3
Proof of Security (Idea)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
5 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
Banerjee and Peikert (Georgia Tech)
'
Bxi
p
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
1
'
Bxi
0
p
2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
1
'
Bxi
0
p
2
“Somewhat key-homomorphic:” Fs (x) + Ft (x) ∈ Fs+t (x) + {0, ±1}n
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
1
'
Bxi
0
p
2
“Somewhat key-homomorphic:” Fs (x) + Ft (x) ∈ Fs+t (x) + {0, ±1}n
Proof strategy: introduce “short” error which “rounds away”



$
'
t
k
k

Y
Y
s 

q q xk
Bxi ≈ (sBx1 + ex1 ) ·
Fs (x) = s ·
Bxi 
q
tx
|
{z
}

i=1
i=2

p
3
sx
1
t
p
x2
tx
1
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
1
'
Bxi
0
p
2
“Somewhat key-homomorphic:” Fs (x) + Ft (x) ∈ Fs+t (x) + {0, ±1}n
Proof strategy: introduce “short” error which “rounds away”



$
'
t
k
k

Y
Y
s 

q q xk
Bxi ≈ (sBx1 + ex1 ) ·
Fs (x) = s ·
Bxi 
q
tx
|
{z
}

i=1
i=2

p
3
sx1
p
t
$
'
x2
k
Y
c
c
c
≈ s x1 ·
Bxi ≈ . . . ≈ bsx ep = U (x)
i=2
Banerjee and Peikert (Georgia Tech)
p
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Boneh et al. KH-PRF Construction
[BLMR’13]
Secret key s ∈ Znq , pub params B0 , B1 ∈ {0, 1}n×n , input x ∈ {0, 1}k
$
Fs (x) = s ·
k
Y
i=1
1
'
Bxi
0
p
2
“Somewhat key-homomorphic:” Fs (x) + Ft (x) ∈ Fs+t (x) + {0, ±1}n
Proof strategy: introduce “short” error which “rounds away”



$
'
t
k
k

Y
Y
s 

q q xk
Bxi ≈ (sBx1 + ex1 ) ·
Fs (x) = s ·
Bxi 
q
tx
|
{z
}

i=1
i=2

p
3
sx1
p
t
$
'
x2
k
Y
c
c
c
≈ s x1 ·
Bxi ≈ . . . ≈ bsx ep = U (x)
i=2
p
7 LWE approx factor grows exponentially in input length k.
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
6 / 11
Gadget and Bit-Decomposition
“Gadget” Zq -matrix G [MP’12]:
A
=
G
Any
Zq -matrix
Banerjee and Peikert (Georgia Tech)
q
G−1 (A)
Square
{0, 1}-matrix
New and Improved KH-PRFs
CRYPTO ’14
7 / 11
Gadget and Bit-Decomposition
“Gadget” Zq -matrix G [MP’12]:
A
=
G
Any
Zq -matrix
q
G−1 (A)
Square
{0, 1}-matrix
A ubiquitous tool in lattice cryptography: FHE [BV’11,GSW’13,AP’14],
CCA/IBE/ABE/FHS [MP’12,BGG+ ’14,GVW’14]
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
7 / 11
Our Construction
For matrices A0 , A1 , full binary tree T and x ∈ {0, 1}|T | , define AT (x):
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
8 / 11
Our Construction
For matrices A0 , A1 , full binary tree T and x ∈ {0, 1}|T | , define AT (x):
T d
x
Banerjee and Peikert (Georgia Tech)
AT (x) := Ax
New and Improved KH-PRFs
for |T | = 1
CRYPTO ’14
8 / 11
Our Construction
For matrices A0 , A1 , full binary tree T and x ∈ {0, 1}|T | , define AT (x):
T d
x
T dH
A
A
T.l A
xl
AT (x) := Ax
HH
A
A
A
T.r A
for |T | = 1
AT (xl kxr ) := AT.l (xl ) · G−1 (AT.r (xr ))
xr
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
8 / 11
Our Construction
For matrices A0 , A1 , full binary tree T and x ∈ {0, 1}|T | , define AT (x):
T d
x
T dH
A
A
T.l A
xl
AT (x) := Ax
HH
A
A
A
T.r A
for |T | = 1
AT (xl kxr ) := AT.l (xl ) · G−1 (AT.r (xr ))
xr
New KH-PRF Construction
Public parameters: matrices A0 , A1 , full binary tree T
Function Fs on |T |-bit input x defined as
Fs (x) = bs · AT (x)ep
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
8 / 11
Our Construction
For matrices A0 , A1 , full binary tree T and x ∈ {0, 1}|T | , define AT (x):
T d
x
T dH
A
A
T.l A
xl
AT (x) := Ax
HH
A
A
A
T.r A
for |T | = 1
AT (xl kxr ) := AT.l (xl ) · G−1 (AT.r (xr ))
xr
New KH-PRF Construction
Public parameters: matrices A0 , A1 , full binary tree T
Function Fs on |T |-bit input x defined as
Fs (x) = bs · AT (x)ep
Somewhat KH just as in [BLMR’13]. Same applications!
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
8 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
t
##cc
t#
ct
C
S
t Ct
t St
S
t
St
s=2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
t
##cc
t#
ct
C
S
t Ct
t St
S
t
St
e=2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
Banerjee and Peikert (Georgia Tech)
e+s
s
New and Improved KH-PRFs
t
##cc
t
#
ct
C
S
t Ct
t St
S
t
St
s = 2, e = 2
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
Banerjee and Peikert (Georgia Tech)
e+s
s
New and Improved KH-PRFs
t
##cc
t
#
ct
C
S
t Ct
t St
S
S
t
St t St
s = 2, e = 2
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
e+s
s
Instantiations
t
##cc
t
ct
#
C
S
t Ct
t St
S
S
t
St t St
s = 2, e = 2
“Left Spine”
e(T )
s(T )
Key
Params
λ−1
1
λ3
λ6
qt
qq A
t At
A xλ
t At
A x3
t At
x1 x2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
e+s
s
t
##cc
t
ct
#
C
S
t Ct
t St
S
S
t
St t St
s = 2, e = 2
[BLMR’13]
Instantiations
Construction!
e(T )
s(T )
Key
Params
λ−1
1
λ3
λ6
qt
qq A
t At
A xλ
t At
A x3
t At
x1 x2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
e+s
s
Instantiations
t
##cc
t
ct
#
C
S
t Ct
t St
S
S
t
St t St
s = 2, e = 2
“Right Spine”
e(T )
s(T )
Key
Params
λ−1
1
λ3
λ6
1
λ−1
λ
λ2
t
A
t At
x1 A
t At
x2 q q q
t t
x3 xλ
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Parameters and Parallelism
Sequentiality s(T ): the “right depth” of T
Circuit depth of PRF is proportional to s(T )
Expansion e(T ): the “left depth” of T
LWE approx factor is exponential in e(T )
Max input length = max # leaves =
e+s
s
t
##cc
t
ct
#
C
S
t Ct
t St
S
S
t
St t St
s = 2, e = 2
Instantiations
6
e(T )
s(T )
Key
Params
λ−1
1
λ3
λ6
1
λ−1
λ
λ2
≈ log4 (λ)
≈ log4 (λ)
λ
λ2
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Outline
1
Introduction
2
Construction, Parameters and Efficiency
3
Proof of Security (Idea)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
9 / 11
Proof Idea
t
qA
q
q
t
A
A
A
t
A TdA
→
A
A −
x
d
T
A 2A
−
→
A x2
T1A
T
t
x0
−
→
x
1
Banerjee and Peikert (Georgia Tech)
→)) · · ·
Fs (x) = s · Ax0 · G−1 (AT1 (−
x
1
p




s 
→)) · · ·
≈ (s · Ax0 + ex0 ) ·G−1 (AT1 (−
x

1
|
{z
}


ux0
p
c −
→
−1
≈ ux0 · G (AT1 (x1 )) · · · p
New and Improved KH-PRFs
CRYPTO ’14
10 / 11
Proof Idea
3 New Idea: u = s · G + v for uniform, independent s and v ∈ P(G).
t
qA
q
q
t
A
A
A
t
A TdA
→
A
A −
x
d
T
A 2A
−
→
A x2
T1A
T
t
x0
−
→
x
1
Banerjee and Peikert (Georgia Tech)
→)) · · ·
Fs (x) = s · Ax0 · G−1 (AT1 (−
x
1
p




s 
→)) · · ·
≈ (s · Ax0 + ex0 ) ·G−1 (AT1 (−
x

1
|
{z
}


ux0
p
c −
→
−1
≈ ux0 · G (AT1 (x1 )) · · · p
New and Improved KH-PRFs
CRYPTO ’14
10 / 11
Proof Idea
3 New Idea: u = s · G + v for uniform, independent s and v ∈ P(G).
t
qA
q
q
t
A
A
A
t
A TdA
→
A
A −
x
d
T
A 2A
−
→
A x2
T1A
T
t
x0
−
→
x
1
→)) · · ·
Fs (x) = s · Ax0 · G−1 (AT1 (−
x
1
p




s 
→)) · · ·
≈ (s · Ax0 + ex0 ) ·G−1 (AT1 (−
x

1
|
{z
}


ux0
p
c −
→
−1
≈ ux0 · G (AT1 (x1 )) · · · p
→) · G−1 (A (−
→
−
→
−1
= sx0 · AT1 (−
x
1
T2 x2 )) · · · + vx0 · G (AT1 (x1 )) · · · p
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
10 / 11
Proof Idea
3 New Idea: u = s · G + v for uniform, independent s and v ∈ P(G).
t
qA
q
q
t
A
A
A
A TdA
→
A
x
A −
d
T
T
1A 2A
T0
−
→
x
1
−
→
x
2
→)) · · ·
Fs (x) = s · Ax0 · G−1 (AT1 (−
x
1
p




s 
→)) · · ·
≈ (s · Ax0 + ex0 ) ·G−1 (AT1 (−
x

1
|
{z
}


ux0
p
c −
→
−1
≈ ux0 · G (AT1 (x1 )) · · · p
→) · G−1 (A (−
→
−
→
−1
= sx0 · AT1 (−
x
1
T2 x2 )) · · · + vx0 · G (AT1 (x1 )) · · · p
→k · · · k−
→) + v · G−1 (A (−
→
= sx0 · AT 0 (−
x
x
1
x0
T1 x1 )) · · · p
d
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
10 / 11
Proof Idea
3 New Idea: u = s · G + v for uniform, independent s and v ∈ P(G).
t
qA
q
q
t
A
A
A
A TdA
→
A
x
A −
d
T
T
1A 2A
T0
−
→
x
1
−
→
x
2
→)) · · ·
Fs (x) = s · Ax0 · G−1 (AT1 (−
x
1
p




s 
→)) · · ·
≈ (s · Ax0 + ex0 ) ·G−1 (AT1 (−
x

1
|
{z
}


ux0
p
c −
→
−1
≈ ux0 · G (AT1 (x1 )) · · · p
→) · G−1 (A (−
→
−
→
−1
= sx0 · AT1 (−
x
1
T2 x2 )) · · · + vx0 · G (AT1 (x1 )) · · · p
→k · · · k−
→) + v · G−1 (A (−
→
= sx0 · AT 0 (−
x
x
1
x0
T1 x1 )) · · · p
d
c s
→)) · · · + other v terms ≈
· · · ≈ sx + vx0 G−1 (AT1 (−
x
U (x).
1
p
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
10 / 11
Conclusions
Our main contributions
New KH-PRFs from lattices: quasi-optimal key sizes, polylog depth
New proof technique
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
11 / 11
Conclusions
Our main contributions
New KH-PRFs from lattices: quasi-optimal key sizes, polylog depth
New proof technique
The Last Word [Mun’07]
(Image source: http://xkcd.com/221/)
Banerjee and Peikert (Georgia Tech)
New and Improved KH-PRFs
CRYPTO ’14
11 / 11

Similar documents

×

Report this document