Leakage-Resilient Key Exchange and Seed Extractors in Cryptography

 
L
e
a
k
a
g
e
-
R
e
s
i
l
i
e
n
t
 
K
e
y
 
E
x
c
h
a
n
g
e
a
n
d
 
T
w
o
-
S
e
e
d
 
E
x
t
r
a
c
t
o
r
s
 
Fermi Ma
Princeton
& NTT Research
 
Willy Quach
Northeastern
 
Daniel Wichs
Northeastern
& NTT Research
 
Xin Li
JHU
 
CRYPTO 2020
Key Exchange
 
Bob
Alice
Key Exchange
 
Bob
Alice
.
.
.
 
Key Exchange
 
 
 
 
 
 
 
Non-Interactive: 
Alice and Bob send one message each, non-adaptively
 
Bob
 
Alice
 
Key Exchange
 
 
 
 
 
 
 
Non-Interactive: 
Alice and Bob send one message each, non-adaptively
 
Bob
 
Alice
 
Key Exchange
 
 
 
 
 
 
 
Non-Interactive: 
Alice and Bob send one message each, non-adaptively
Passive Adversaries:
 Final key looks uniform to eavesdroppers
 
Bob
 
Alice
 
Eve
NIKE
Leakage Resilience
 
 
 
 
 
What if the randomness is 
unreliable
?
Eve could get some information about      directly
Perfect randomness not necessarily available or expensive
Here: 
bounded 
leakage
 
Standard solution: privacy amplification via 
leak-free randomness
Bob
Alice
Eve
random coins
random coins
 
Key Exchange
 
Bob
 
Alice
 
Eve
Leakage-Resilient NIKE
Symmetric-Key Setting
Bob
Alice
Eve
Symmetric-key
Leakage-Resilient NIKE
Our Contributions (1)
Our Contributions (2)
Includes most common cryptographic
assumptions (RSA, DDH, LWE, iO…)
 
Outline
 
 
1.
The Symmetric Setting and Two-Seed Extractors
 
2.
The Public Setting: Black-Box Impossibility result
… and limitations leading to positive results
The Symmetric Setting
Bob
Alice
 
Source
 
Source
 
Seed
 
Seed
(Strong) Two-Seed Extractors
 
Seeds
 
Leakage
 
Secret key
 
Alice’s
randomness
 
Bob’s
randomness
Source is jointly
correlated with the
seeds
Communication Complexity
 
 
 
 
 
 
How many bits need to be communicated?
Bob
Alice
Carol
Communication Complexity
The Number on Forehead (NOF) Model
Bob
Alice
Carol
Communication Complexity
The Number on Forehead (NOF) Model
Bob
Alice
Carol
Building Two-Seed Extractors (1)
Bob
Alice
Carol
Building Two-Seed Extractors (1)
Bob
Alice
Carol
 
Building Two-Seed Extractors (2)
Building Two-Seed Extractors (2)
 
Outline
 
 
1.
The Symmetric Setting and Two-Seed Extractors
 
2.
The Public Setting: Black-Box Impossibility result
… and limitations leading to 
positive results
Key Exchange
Bob
Alice
Eve
(Single-Stage) Cryptographic Games
 
 
 
 
 
 
 
Captures all common cryptographic assumptions: RSA, QR, DDH, LWE, iO…
 
Leakage resilience (with black-box leakage) is a 
two-stage game
 
.
.
.
 
Adversary
 
Challenger
 
Win/Lose
Efficient
Potentially
inefficient
A Black-Box Impossibility Result
Theorem
: 
There are no 
black-box reductions
 from the leakage
resilience of NIKE to 
any single-stage cryptographic games.
 
treats the adversary as a black-box
Proof of Black-Box Impossibility (1)
Meta-reduction technique (e.g. [Wichs’13])
 
Black-box
reduction
 
Adversary for
Leakage Resilience
 
Adversary for
Cryptographic Game
Proof of Black-Box Impossibility (1)
Meta-reduction technique (e.g. [Wichs’13])
 
Inefficient
Adversary for
Leakage Resilience
 
Inefficient
Adversary for
Cryptographic Game
 
Efficient
 
Efficient
(Efficient)
Black-box
reduction
 
Generic adversary
for the
Cryptographic game
 
Not admissible
 
Admissible
 
Admissible
 
Admissible
Proof of Black-Box Impossibility (2)
An inefficient adversary
A inadmissible efficient adversary
 
Program random oracle, and 
records queries
Leakage:
 
Distinguisher:
Breaks leakage resilience
if 
perfectly correct
 
Sampled fresh
as needed
 
Circumventing the Impossibility Result (1)
 
Impossibility 
for 
black-box reductions
 for LR-NIKEs with
perfect correctness
 and 
super-log leakage 
to 
cryptographic games
Circumventing the Impossibility Result (1)
 
Impossibility 
for 
black-box reductions
 for LR-NIKEs with
perfect correctness
 and 
super-log leakage
 
to cryptographic games
Theorem
: 
Any standard NIKE remains secure with
logarithmically-sized leakage.
Open question:
Use statistical
correctness?
Open question:
Non-black-box?
Circumventing the Impossibility Result (2)
 
Using 
Setups
:
1.
Common reference string
: a trusted third party generates a global
reference string
 
2.
Leak-free preprocessing
 
 
 
 
 
 
The random coins needed to generate the preprocessed state are 
leak-free
But the parties 
do not need
 
those coins to execute the protocol: they can discard it
 
Bob
 
Alice
 
Preprocessed
state
 
Preprocessed
state
Circumventing the Impossibility Result (3)
 
Positive results with 
linear leakage
: (see paper)
 
 
 
Techniques heavily inspired by 
dual-system encryption
 
What about CRS or preprocessing alone?
 
 
Theorem
: 
Assuming pairings (DLIN) + symmetric-key LR-NIKE,
there exists a LR-NIKE using 
both
 a CRS and preprocessing
Theorem
: 
Assuming iO (and lossy functions), there exists a
leakage-resilient NIKE using 
either
 a CRS or preprocessing
 
Circumventing the Impossibility Result
 
Impossibility 
for 
black-box reductions
 for LR- NIKEs with 
no setups
perfect correctness
 and 
super-log leakage
Theorem
: 
Any standard NIKE remains secure with
logarithmically-sized leakage.
Open question:
Use statistical
correctness?
Open question:
Non-black-box?
Theorem
: 
Assuming pairings and symmetric-key NIKE,
there exists a leakage-resilient NIKE with setup
Summary
 
We initiate a study of 
leakage-resilient, non-interactive key exchange
that does 
not
 rely on leak-free randomness
 
In the 
symmetric-key setting
, this is closely related to 
two-seed
extractors
, that we build using 
communication complexity lower bounds
in the NOF model
 
In the 
public-key setting
, we show a broad 
black-box impossibility result,
  
 and several ways to circumvent it, giving 
positive results
:
   in the 
small-leakage setting
, in the 
CRS 
and/or 
preprocessing
 models
 
Thank you!
 
https://eprint.iacr.org/2020/771.pdf
Slide Note
Embed
Share

This content discusses the concepts of leakage-resilient key exchange and seed extractors in cryptography, focusing on scenarios involving Alice, Bob, and Eve. It covers non-interactive key exchanges, passive adversaries, perfect randomness challenges, and leakage-resilient settings in symmetric-key scenarios. The contributions include information-theoretic constructions and extractor connections to communication complexity lower bounds.


Uploaded on Sep 09, 2024 | 6 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Leakage Leakage- -Resilient Key Exchange Resilient Key Exchange and Two and Two- -Seed Extractors Seed Extractors Xin Li JHU Willy Quach Northeastern Daniel Wichs Northeastern & NTT Research Fermi Ma Princeton & NTT Research CRYPTO 2020

  2. Key Exchange Alice Bob

  3. Key Exchange Alice Bob . . .

  4. Key Exchange Alice Bob Non-Interactive: Alice and Bob send one message each, non-adaptively

  5. Key Exchange Alice Bob Non-Interactive: Alice and Bob send one message each, non-adaptively

  6. Eve Key Exchange Alice Bob NIKE Non-Interactive: Alice and Bob send one message each, non-adaptively Passive Adversaries: Final key looks uniform to eavesdroppers

  7. Eve Leakage Resilience Alice Bob random coins random coins What if the randomness is unreliable? Eve could get some information about directly Perfect randomness not necessarily available or expensive Here: bounded leakage Standard solution: privacy amplification via leak-free randomness

  8. ???? 0,1 Eve Key Exchange ???? 0,1 2 ??+ ?? Alice Bob ?? ?? Leakage-Resilient NIKE Non-Interactive: Alice and Bob send one message each, non-adaptively Passive Adversaries: Final key looks uniform to eavesdroppers Leakage Resilient: Eve gets some (independent) leakage on ??and ??

  9. ????,?? 0,1 Eve Symmetric-Key Setting ????,?? 0,1 Alice Bob ?? ?? ?? ?? Symmetric-key Leakage-Resilient NIKE Key update after leakage Easier problem: can hope for information theoretic constructions Leakage Resilient: Eve gets (independent) leakage on (??,??) and (??,??)

  10. Our Contributions (1) Symmetric-Key Setting: Related notion of extractor: two-seed extractors Connection with communication complexity lower bounds Information theoretic constructions (not possible in public-key setting)

  11. Our Contributions (2) Public-Key Setting: Is Diffie-Hellman key-exchange leakage-resilient? Does DDH hold with high-entropic exponents? A broad black-box impossibility result Rules out any black-box reduction for leakage-resilient NIKE with large leakage under any single-stage cryptographic game Includes most common cryptographic assumptions (RSA, DDH, LWE, iO ) Positive results in alternate settings Small Leakage Leak-free preprocessing: parties preprocess Common Reference String (CRS) before execution

  12. Outline 1. The Symmetric Setting and Two-Seed Extractors 2. The Public Setting: Black-Box Impossibility result and limitations leading to positive results

  13. ????,?? 0,1 The Symmetric Setting ????,?? 0,1 ?? Alice Bob ?? ?? ?? ?? ?? Source Seed Source Seed ? = ?(??,??,??) Security: ? looks uniform given ??,??and leakages ????,?? , ????,?? ? is a special type of extractor!

  14. (Strong) Two-Seed Extractors Alice s randomness Bob s Secret key randomness Ext:?????? ????1 ????2 ? ?? ?? ?? Security: For all (potentially inefficient) ??,??with -bit outputs: Source is jointly correlated with the seeds Ext ??,??,??,??,??,????,??,????,?? ???????,??,??,????,??,????,?? Seeds Leakage How to build such extractors?

  15. Communication Complexity ?3 Suppose ? has 1-bit output Carol ? ?1,?2,?3? ?1 ?2 Alice Bob How many bits need to be communicated?

  16. Communication Complexity The Number on Forehead (NOF) Model ?1,?2 ?3 Suppose ? has 1-bit output Carol ? ?1,?2,?3? ?2,?3 ?1,?3 ?1 ?2 Alice Bob ???(?) size of transcript needed to compute ? with good probability (over random ?1,?2,?3)

  17. Communication Complexity The Number on Forehead (NOF) Model ?1,?2 ?3 Suppose ? has 1-bit output Carol ? ?1,?2,?3? ?2,?3 ?1,?3 ?1 ?2 Alice Bob ???(?) size of transcript needed to distinguish output from random ? is a NOF extractor : output uniform even given small NOF transcript Also observed in [Babai-Nisan-Szegedy 92, Kumar-Meka-Sahai 19] Theorem [Chung 90, BNS 92]: There exists explicit efficient ? with high ???

  18. ?1,?2 Building Two-Seed Extractors (1) ?3 Carol ?2,?3 ?1,?3 ?1 ?2 Claim: Suppose ? is a NOF extractor. Then ? is a (weak) two-seed extractor. Bob Alice ? ?1,?2,?3?

  19. ??,?? Building Two-Seed Extractors (1) ?? Carol ??,?? ??,?? ?? ?? Claim: Suppose ? is a NOF extractor. Then ? is a (weak) two-seed extractor. Bob Alice ? ??,?A,??? Idea: Leakages ????,??,??(??,??) = valid NOF transcript! (where only Alice and Bob speak) If ??and ??have combined output smaller than ???(?): ? ??,??,??,????,??,????,?? ???????,????,??,????,??

  20. Building Two-Seed Extractors (2) Not done yet: we want a strong extractor, where security holds given the seeds ??,??. We only have: ? ??,??,??,????,??,????,?? ???????,????,??,????,??

  21. Building Two-Seed Extractors (2) Not done yet: we want a strong extractor, where security holds given the seeds ??,??. We would like: ? ??,??,??,??,??,????,??,????,?? ???????,??,??,????,??,????,?? Two-seed extractors built from CC lower bounds are strong (with some loss in parameters) Intuition: the output of a distinguisher for the strong version can be seen as an extra transcript component for the weak version

  22. Outline 1. The Symmetric Setting and Two-Seed Extractors 2. The Public Setting: Black-Box Impossibility result and limitations leading to positive results

  23. ???? 0,1 Eve Key Exchange ???? 0,1 = ?? ?? Alice Bob = ?? ?? ?? ?? = ? ? = ? ? Diffie-Hellman is a secure (standard) NIKE from standard assumptions What about leakage resilience? Can we get leakage resilient NIKE from standard assumptions? Is Diffie-Hellman secure with leakage on the exponents? to what extent does DDH hold with (independent) entropic exponents?

  24. (Single-Stage) Cryptographic Games Adversary Challenger . . . Potentially inefficient Efficient Win/Lose Pr wins negl Captures all common cryptographic assumptions: RSA, QR, DDH, LWE, iO Leakage resilience (with black-box leakage) is a two-stage game

  25. A Black-Box Impossibility Result treats the adversary as a black-box Theorem: There are no black-box reductions from the leakage resilience of NIKE to any single-stage cryptographic games. Quite broad impossibility result Covers leaky-DDH : ??,??,??? ?(??,??,??) given leakage on ?,? But some limitations! positive results

  26. Proof of Black-Box Impossibility (1) Meta-reduction technique (e.g. [Wichs 13]) : Adversary for Leakage Resilience Black-box reduction Adversary for Cryptographic Game

  27. Proof of Black-Box Impossibility (1) Meta-reduction technique (e.g. [Wichs 13]) : Admissible Admissible Inefficient Adversary for Leakage Resilience (Efficient) Black-box reduction Inefficient Adversary for Cryptographic Game Generic adversary for the Cryptographic game : Efficient Not admissible Efficient Admissible

  28. Proof of Black-Box Impossibility (2) A inadmissible efficient adversary Program random oracle, and records queries Leakage: ? An inefficient adversary A hard-coded random oracle ? Leakage: ? ?(?) ?(?) ? Sampled fresh as needed where ? is message computed using ? Distinguisher: ?,?(?) Distinguisher: ?,?(?) ? ? ? Brute-forces ? if leakage matches transcript Recovers ? by looking at the queries, deduces ? Simulates ? is long enough as long as Breaks leakage resilience if perfectly correct

  29. Circumventing the Impossibility Result (1) Impossibility for black-box reductions for LR-NIKEs with perfect correctness and super-log leakage to cryptographic games

  30. Circumventing the Impossibility Result (1) Open question: Non-black-box? Impossibility for black-box reductions for LR-NIKEs with perfect correctness and super-log leakage to cryptographic games Open question: Use statistical correctness? Theorem: Any standard NIKE remains secure with logarithmically-sized leakage.

  31. Circumventing the Impossibility Result (2) Using Setups: 1. Common reference string: a trusted third party generates a global reference string 2. Leak-free preprocessing Alice Bob Preprocessed state Preprocessed state The random coins needed to generate the preprocessed state are leak-free But the parties do not need those coins to execute the protocol: they can discard it

  32. Circumventing the Impossibility Result (3) Positive results with linear leakage: (see paper) Theorem: Assuming pairings (DLIN) + symmetric-key LR-NIKE, there exists a LR-NIKE using both a CRS and preprocessing Techniques heavily inspired by dual-system encryption What about CRS or preprocessing alone? Theorem: Assuming iO (and lossy functions), there exists a leakage-resilient NIKE using either a CRS or preprocessing

  33. Circumventing the Impossibility Result Open question: Non-black-box? Theorem: Assuming pairings and symmetric-key NIKE, there exists a leakage-resilient NIKE with setup Impossibility for black-box reductions for LR- NIKEs with no setups perfect correctness and super-log leakage Open question: Use statistical correctness? Theorem: Any standard NIKE remains secure with logarithmically-sized leakage.

  34. Summary We initiate a study of leakage-resilient, non-interactive key exchange that does not rely on leak-free randomness In the symmetric-key setting, this is closely related to two-seed extractors, that we build using communication complexity lower bounds in the NOF model In the public-key setting, we show a broad black-box impossibility result, and several ways to circumvent it, giving positive results: in the small-leakage setting, in the CRS and/or preprocessing models

  35. Thank you! https://eprint.iacr.org/2020/771.pdf

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#