Adaptive Proofs of Knowledge in the Random Oracle Model
Dive into the world of adaptive proofs of knowledge in the random oracle model, exploring topics such as interactive proofs, non-interactive proofs, and extraction challenges. Discover the intricacies of simulation-sound adaptive zero-knowledge proofs and the importance of adversaries and extractors in cryptographic security.
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
Adaptive Proofs of Knowledge in the Random Oracle Model 21. PKC 2015 Marc Fischlin joint work with David Bernhard, Bogdan Warinschi 13. Oktober 2010 | Dr.Marc Fischlin | Kryptosicherheit | 1
(Interactive) Proofs of Knowledge theorem interactive proof extractor (malicious) prover witness extraction usually through rewinding April 1st, 2015 | Marc Fischlin | PKC 2015 | 2
[Fiat-Shamir] Non-interactive Proofs of Knowledge in the Random Oracle (RO) Model RO * RO non-interactive extractor (malicious) prover still require rewinding for extraction April 1st, 2015 | Marc Fischlin | PKC 2015 | 3
Extraction is easy in the RO model [Pointcheval-Stern] Example: Fiat-Shamir-Schnorr signatures RO RO* April 1st, 2015 | Marc Fischlin | PKC 2015 | 4
Extraction is easy in the RO model or is it? April 1st, 2015 | Marc Fischlin | PKC 2015 | 5
adaptive zero-knowledge proofs of knowledge in random oracle model (ROM) [Shoup-Gennaro] adversary RO RO RO April 1st, 2015 | Marc Fischlin | PKC 2015 | 6
simulation-sound adaptive zero-knowledge proofs of knowledge in the ROM ? needs to program RO needs to program RO RO extractor ZK simulator April 1st, 2015 | Marc Fischlin | PKC 2015 | 7
This work here: Model for simulation-sound adaptive ZK PoKs in ROM Show that one can work with it Show that one can achieve it Discuss that some approaches fail April 1st, 2015 | Marc Fischlin | PKC 2015 | 8
main execution (non-rewinding) RO list of queries RO same coins local branches adversary wins if extractor at some point fails to compute witness PPT adversaries extractor: Pr [ adversary wins ] is negligible April 1st, 2015 | Marc Fischlin | PKC 2015 | 9
Result #1 (applicability): CPA-secure encryption + simulation-sound adaptive zero-knowledge proof of knowledge in ROM I know message and randomness encrypted under CPA scheme CCA-secure encryption in ROM so far: common reference string model [Groth, Chase-Lysanskaya, Dodis et al.] April 1st, 2015 | Marc Fischlin | PKC 2015 | 10
Result #2 (feasibility): Fischlin s transformation with straightline extractor for protocols with special soundness is simulation-sound adaptive zero-knowledge proof of knowledge in the ROM so far: only shown for adaptive scenario in [Fischlin] April 1st, 2015 | Marc Fischlin | PKC 2015 | 11
RO RO Idea: straightline extractor in Fischlin s scheme only needs hash queries of adversary April 1st, 2015 | Marc Fischlin | PKC 2015 | 12
Result #3 (limitations): Fiat-Shamir-Schnorr transformation is not adaptive proof of knowledge under one-more DL assumption (for black-box extractors). so far: certain extractor strategy fails [Shoup-Gennaro] here: any efficient extractor strategy fails April 1st, 2015 | Marc Fischlin | PKC 2015 | 13
[Bellare et al.] One-More-DL Problem Ch A DL output more solutions to challenges than DL queries April 1st, 2015 | Marc Fischlin | PKC 2015 | 14
RO Ch RO DL Metareduction output more solutions to challenges than DL queries April 1st, 2015 | Marc Fischlin | PKC 2015 | 15
RO Ch RO DL use [Shoup-Gennaro] adversary here Metareduction output more solutions to challenges than DL queries April 1st, 2015 | Marc Fischlin | PKC 2015 | 16
Ch RO DL make at most 2 calls to DL for each use [Shoup-Gennaro] adversary here Metareduction if extractor requires less than 2 executions to extract output more solutions to challenges than DL queries for some , then metareduction solves OMDL problem April 1st, 2015 | Marc Fischlin | PKC 2015 | 17
Final step in the proof (not here): If extractor requires 2 executions to extract for each then Shoup-Gennaro adversary forces exponential number of executions combinatorial, via execution tree April 1st, 2015 | Marc Fischlin | PKC 2015 | 18
Take-home Message April 1st, 2015 | Marc Fischlin | PKC 2015 | 19
RO RO CPA + ss-adaptive PoK CCA in ROM Fischlin s transformation is an example for ss-adaptive PoK Fiat-Shamir transformation in general is (presumably) not 1. 2. 3. April 1st, 2015 | Marc Fischlin | PKC 2015 | 20
