Randomized Verification in Signature Schemes and Identity-Based Encryption
Explore the world of signature schemes, randomized verification, public key signatures, and identity-based encryption with key insights on security, attacker challenges, and Naor's transformation. Unveil the significance of weakening EUFCMA, the Naor transformation theorem, and the amplification of weak security to standard.
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
Signature Schemes with Randomized Verification Cody Freitag, Rishab Goyal, Susan Hohenberger, Venkata Koppula, Eysa Lee, Tatsuaki Okamoto and Brent Waters
Public Key Signatures Basic building blocks Could be randomized!
Identity-Based Encryption [Shamir84 ...] Authority MSK PP SKBob m m
Naors Transformation: IBE Signatures Interpreted as identity . For IBE encryption.
EUFCMA Security Attacker Challenger vk m1 m1 mQ mQ m*, ?* Adv = | | Pr[Verify(vk, m*, ?*) = = 1] | |
Naors Transformation: Proving Security Reduction Attacker on Signatures IBE Challenger PP m skm Chooses d0, d1 randomly m*, ?* (d0, d1), m* ct* Decrypts ct* using ?* Guess
Weakening EUFCMA Successful Verification Probability (?-????) Measures fraction of random coins that accept signature ? on ? with key ?? Formally, # of accepting coins Total # of random coins
?-EUFCMA Security Attacker Challenger vk m1 m1 mQ mQ m*, ?* EUFCMA Adv = | | Pr[Verify(vk, m*, ?*) = = 1] | | ?-EUFCMA Adv = | | Pr[V-Prob(vk, m*, ?*) > > ? + negl] | |
Rest of the talk: Outline Naor s transformation gives weak security Amplifying soundness (weak to standard) Derandomizing in the ROM Derandomizing in standard model
Naors Transformation Naor s transformation gives weak security Theorem. If IBE scheme with message space is secure, then the Naor transformed scheme is ?-EUFCMA secure with ? = 1 .
Naors Transformation: Proving Security Reduction Attacker on Signatures IBE Challenger PP m skm Chooses d0, d1 randomly m*, ?* (d0, d1), m* ct* Decrypts ct* using ?* Problem is to use ?* directly! Guess Doesn t work
Naors Transformation: Proving Security Solution Estimates quality of forgery (/secret key) by counting Artificial Abort-type step [Waters05] Reduction runs verification sufficiently many times # of successful verifications <threshold Abort & Guess # of successful verifications threshold Decrypt & Test Worse than random guessing ? + ?/2 ? 0 ? + ? 1 Bad Good Mid ?-????(? ,? )
Amplifying soundness Theorem. If ?-EUFCMA secure signature scheme with ? = 1 then signature scheme that is ?- EUFCMA secure with ? = 0. 1 ???? , Idea.Direct product amplification. Run Verify sufficiently many times with fresh randomness.
Derandomization: ROM Assume starting scheme (0-)EUFCMA secure Randomness generated by hashing message- signature pair Proof Idea Adversary makes poly RO queries Each response is uniformly random Union bound
Derandomization: Standard Model Sufficiently many random coins generated at Setup Verify accepts iff successful on all coins
Derandomization: Standard Model Verification Key Standard reduction 2 cases Forgery is valid Forgery is invalid, but gets verified on r1, , rn Set ? log( | |) Note. Starting scheme is (0-)EUFCMA secure, and message and signature space is bounded. Set of random coins
Conclusions Introduced a weaker security notion for signature schemes with randomized verification Proved security of Naor transformed scheme Generic soundness amplification Generic derandomization of verification Both in ROM and standard model
