Idealized Model for Cryptographic Primitives and Indifferentiability Framework
Explore new notions and constructions in public key crypto-systems, leakage resilience, related-key attack PKE, and idealized models for cryptographic primitives such as hash functions, random oracles, and more. Learn about the concept of Ideal NIKE and the Indifferentiability Framework in the context of secure cryptographic design.
Uploaded on | 0 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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Indifferentiability for Public Key Crypto-systems Cong Zhang Rutgers University Joint work with Mark Zhandry (Princeton University) 1
When designing a crypto-primitive CCA [Cramer-Shoup, CRYPTO 98] Leakage-Resilient [Alwen-Dodis-Wichs, CRYPTO 09] Related-key attack PKE [Bellare-Cash, CRYPTO 10] What s the magic scheme that rules them all? 2
Idealized model for Cryptographic Primitives Construction Idealized Model Hash Function Random Oracle [Bellare-Rogaway, CCS 93] Block Cipher Random Keyed Permutation [Black, FSE 06] Cryptographic Groups Generic Group Model [Shoup, Eurocrypt 97] (Secret Key) Encryption Random Keyed Injection [Barbosa-Farshim, CRYPTO 18] Public Key Encryption ?
This work: New Notions and Constructions NIKE PKE Digital Signature Ideal NIKE Ideal PKE Ideal Signature What s Ideal NIKE? It should be an idealized model for NIKE
What is Ideal NIKE? An idealized model for NIKE ???? = (??????,?????????) ??????(??) = ?? ?????????(???,???) = ?????????(???,???) Inspired by [Barbosa-Farshim, CRYPTO 18] ???? = (??????,?????????) ???? a random tuple of functions (???,???)?,?,? ??????(??) random injection ??? is an injection such that ? ? ?????????(???,???) random function ??? is a function such that ? ? ? ?????????(???,???) = ?????????(???,???) ???(?1,???(?2)) = ???(?2,???(?1))
Indifferentiability Framework [Maurer-Renner-Holenstein, TCC 04] ??) is as good as ideal NIKE (???,???). ??,?2 ???= (?1 Real World Ideal World ??) ??,?2 ???= (?1 (???,???) . ?(???,???) ?? everything is under controlled by adversary.
Why Indifferentiability? Theorem: If ??? is indifferentiable from ideal NIKE, then ??? is secure in many adversarial environment in the random oracle model. [Maurer-Renner-Holenstein, TCC 04] Unpredicted shared key against active attacker Leakage resilience KDM-security RKA-security Combined Security Unknown-yet Security Single stage game
Main Challenges: Random oracle itself can never be sufficient ! [Impagliazzo-Rudich, STOC 89] Random oracle oracle oracle Random Random Standard-model NIKE Indifferentiable NIKE Assumptions always associated with some structure; while Ideal NIKE has no such structure
Contributions of Our Work 1: We propose the notions of ideal NIKE, ideal PKE and ideal Digital Signature. 2: We build an indifferentiable NIKE from random oracles + doubly-strong CDH assumption. 3: We build an indifferentiable PKE from ideal NIKE + random oracles. 4: We build an indifferentiable Signature from random oracles + BDDH assumption
Outline 1. Construction 2. Intuition of the Simulator 3. Conclusion
Outline 1. Construction 2. Intuition of the Simulator 3. Conclusion
Making KEYGEN indifferentiable Strategy is: combining random oracles and standard-model NIKE into an indifferentiable NIKE (???,???) . Let (??????,?????????) be an NIKE scheme. ???(??) = ?(??????(??)) ???(??) = ?1(??????(?0(??))) ???(??) = ?(??????(?0(??))) [Holenstein-K nzler-Tessaro, STOC 11] ?? ?(??????(?? )) ?1(??????(?0(?? )) ?0(?? ) ?? ???(?? ) Once hash ??????, we destroy the group structure. 12
Making SHAREDKEY indifferentiable ???(??) = ?(??????(?0(??))) ???(???,???) = ?(?????????(?0(???),? 1(???))) = ?1(???,???,?????????(?0(???),? 1(???))) ???(???,???) ??? ??? ? 1(???(???)) ??? ?(?????????(???,???)) ??? ?(??????(???)) ??? ??? ????(???,???) test: ??? = In the second step, it knows nothing of (???,???,???,???) Enforce the adversary to hand it ??? before hashing by adding ??? into hash.
Outline 1. Construction 2. Intuition of the Simulator 3. Conclusion
Simulators Goal Goal: Simulator needs to simulates ?0,?,? 1,?1 properly. The response of ?0 and ?1 query is random string; The response of ? and ? 1 query is random permutation; ???(??) = ?(??????(?0(??))); ???(???,???) = ?1(???,???(???),?????????(? 1(???),?0(???)))
Simulators states Simulator keeps four tables: (??,??,??,??) ?0-table ?-table (??, ,??,??) ? 1-table ( ,??,??,??) ?1-table (???,???,???,???)
Simulators Responses ? 1-table ( ,??,??,??) For ?0 query: ?0(??) checks ?0 table (if ?? ?0, then responds with ??); checks ? 1 table (if ???(??) ? 1, then responds with ??); samples ??, and inserts (??,??,??????(??),???(??)) into ?0-table. For ? 1 query: ? 1(??) checks ? and ? 1 table (if ?? ? ? 1, then responds with ??) checks ?0 table (if ?? ?0, then responds with ??) samples ??, and inserts ( ,??,??????(??),???(??)) into ? 1-table pseudo random public key
Simulators Responses For ? query: ?(??) checks ? ? 1 table (if ?? ? ? 1, then responds with ??); checks ?0 table (if ?? ?0, then responds with ??); samples ??, and inserts (??, ,??,???(??)) into ?-table. Why not a random string? Adversary might choose ?? and would induce to an attack: ??? ??? ?(??????(??1)) ? 1(???(???)) ??? ?1(???,???,?????????(???,???)) ???,??? ???(???,???) ????(???,???) =
Simulators Responses For ?1 query: ?1(???,???,???) checks ?1 table (if ???,???,??? ?1, then responds with ???); tests the validity of ??? using ?0,?,? 1 tables; samples ???, and inserts (???,???,???,???) into ?1-table. Example: ??? ?0;??? ? ??????????(???,???) If passes, then responds with ???(???,???); Else, a random string. test: ??? = the shared key is unpredictable against active attacker
Conclusion New notions for ideal public key systems: ideal NIKE/PKE/Signature. Construct an indifferentiable NIKE in random oracle model. Construct an indifferentiable PKE in ideal NIKE model. Construct an indifferentiable Signature in random oracle model. Hope more indifferentiable works in public key setting coming soon! Thanks!
