Leakage-Resilient Key Exchange and Seed Extractors in Cryptography
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.
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
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
Key Exchange Alice Bob
Key Exchange Alice Bob . . .
Key Exchange Alice Bob Non-Interactive: Alice and Bob send one message each, non-adaptively
Key Exchange Alice Bob Non-Interactive: Alice and Bob send one message each, non-adaptively
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
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
???? 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 ??
????,?? 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 (??,??)
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)
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
Outline 1. The Symmetric Setting and Two-Seed Extractors 2. The Public Setting: Black-Box Impossibility result and limitations leading to positive results
????,?? 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!
(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?
Communication Complexity ?3 Suppose ? has 1-bit output Carol ? ?1,?2,?3? ?1 ?2 Alice Bob How many bits need to be communicated?
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)
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 ???
?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?
??,?? 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 ???(?): ? ??,??,??,????,??,????,?? ???????,????,??,????,??
Building Two-Seed Extractors (2) Not done yet: we want a strong extractor, where security holds given the seeds ??,??. We only have: ? ??,??,??,????,??,????,?? ???????,????,??,????,??
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
Outline 1. The Symmetric Setting and Two-Seed Extractors 2. The Public Setting: Black-Box Impossibility result and limitations leading to positive results
???? 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?
(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
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
Proof of Black-Box Impossibility (1) Meta-reduction technique (e.g. [Wichs 13]) : Adversary for Leakage Resilience Black-box reduction Adversary for Cryptographic Game
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
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
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) 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.
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
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
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.
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
