Foundations of Cryptography: Lecture 12 - Digital Signatures and Collision-Resistant Hash Functions
The lecture covers the construction of collision-resistant hash functions from discrete log, the security behind it, and the implications for digital signature schemes. It delves into the theoretical foundations of cryptography, showcasing the interplay between one-way functions, hash functions, and signature schemes.
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
MIT 6.875 Foundations of Cryptography Lecture 12
Digital Signatures We showed: Theorem: Assuming the existence of one-way functions and collision-resistant hash function families, there are digital signature schemes.
Collision-Resistant Hash Functions A compressing family of functions ? = {h: 0,1? 0,1?} (where ? > ?) for which it is computationally hard to find collisions. Def: is collision-resistant if for every PPT algorithm A, there is a negligible function ? s.t. Pr ? 1?, = ?,? :? ?, ? = ? = ?(?)
Construction of CRHF from Discrete Log ? = 2? + 1is a safe prime. = {h:( ?)2 ???} Each function ?1 ,?2 is parameterized by two generators ?1 and ?2 of ??? (a group of order q). ?1?2 ?2 mod p. ?1 ,?2?1,?2 = ?1 This compresses 2 log q bits into log p log q + 1 bits.
Construction of CRHF from Discrete Log ? = 2? + 1is a safe prime. = {h:( ?)2 ???} Each function ?1 ,?2 is parameterized by two generators ?1 and ?2 of ??? (a group of order q). ?1?2 ?2 mod p. ?1 ,?2?1,?2 = ?1 Why is this collision-resistant? Suppose there is an adversary that finds a collision ?1,?2 and ?1,?2
Construction of CRHF from Discrete Log ?1?2 ?2 mod p. ?1 ,?2?1,?2 = ?1 Why is this collision-resistant? Suppose there is an adversary that finds a collision ?1,?2 and ?1,?2 ?1?2 ?2 = ?1 ?1?2 ?2 mod p. ?1 ?1 ?1= ?2 ?2 ?2 mod p. ?1 (assume wlog ?1 ?1 0 ??? ?) (?2 ?2)(?1 ?1) 1 mod p. ?????2(?1)! ?1= ?2
Digital Signatures Theorem: Assuming the hardness of the discrete logarithm problem, there are digital signature schemes.
Other Constructions of CRHFs From the hardness of factoring, lattice problems etc. Not known to follow from the existence of one-way functions or even one-way permutations Black-box separations : Certain ways of constructing CRHF from OWF/OWP cannot work. Finding collisions on a one-way street , Daniel Simon, Eurocrypt 1998. Nevertheless, big open problem: OWF/OWP ? CRHF?
Digital Signatures It turns out that collision-resistant hashing is not necessary; something weaker called universal one-way hashing (UOWHF) suffices. Furthermore, UOWHFs can be constructed from one-way functions alone. Theorem: Digital Signature schemes exist if and only if one-way functions exist.
Worlds in Crypto Cryptomania: Public-key encryption Minicrypt: Zero- Knowledge proofs PRP Digital Signatures Bit Commitment Secret-key encryption PRF PRG CRHF UOWHF OWF OWF
Direct Constructions Hash-and-Sign : Secure in the random oracle model.
Vanilla RSA Signatures Start with any trapdoor permutation, e.g. RSA. Gen(1?): Pick primes ?,? and let ? = ??. Pick ? relatively prime to ? ? and let ? = ? 1 (mod? ? ). SK = ?,? and VK = ?,? Sign(??,?): Output signature ? = ??mod ? . Verify(V?,?,?): Check if ??= ? mod ? . Problem: Existentially forgeable!
Vanilla RSA Signatures Sign(??,?): Output signature ? = ??mod ? . Verify(V?,?,?): Check if ??= ? mod ? . Problem: Existentially forgeable! Attack: Pick a random ? and output (? = ??, ?) as the forgery. Problem: Malleable! Attack: Given a signature of ?, you can produce a signature of 2?,3?, ,?2,?3,
Vanilla RSA Signatures Sign(??,?): Output signature ? = ??mod ? . Verify(V?,?,?): Check if ??= ? mod ? . Fundamental Issues: 1. Can reverse-engineer the message starting from the signature (Attack 1) 2. Algebraic structure allows malleability (Attack 2)
How to Fix Vanilla RSA Start with any trapdoor permutation, e.g. RSA. Gen(1?): Pick primes ?,? and let ? = ??. Pick ? relatively prime to ? ? and let ? = ? 1 (mod? ? ). SK = ?,? and VK = ?,?,? Sign(??,?): Output signature ? = ?(?)?mod ? . Verify(V?,?,?): Check if ??= ?(?) mod ? . So, what is H? Some very complicated hash function.
How to Fix Vanilla RSA Start with any trapdoor permutation, e.g. RSA. Gen(1?): Pick primes ?,? and let ? = ??. Pick ? relatively prime to ? ? and let ? = ? 1 (mod? ? ). SK = ?,? and VK = ?,?,? Sign(??,?): Output signature ? = ?(?)?mod ? . Verify(V?,?,?): Check if ??= ?(?) mod ? . H should be at least one-way to prevent Attack #1.
How to Fix Vanilla RSA Start with any trapdoor permutation, e.g. RSA. Gen(1?): Pick primes ?,? and let ? = ??. Pick ? relatively prime to ? ? and let ? = ? 1 (mod? ? ). SK = ?,? and VK = ?,?,? Sign(??,?): Output signature ? = ?(?)?mod ? . Verify(V?,?,?): Check if ??= ?(?) mod ? . Hard to algebraically manipulate H(m) into H(related m ). (to prevent Attack #2.)
How to Fix Vanilla RSA Start with any trapdoor permutation, e.g. RSA. Gen(1?): Pick primes ?,? and let ? = ??. Pick ? relatively prime to ? ? and let ? = ? 1 (mod? ? ). SK = ?,? and VK = ?,?,? Sign(??,?): Output signature ? = ?(?)?mod ? . Verify(V?,?,?): Check if ??= ?(?) mod ? . Collision-resistance does not seem to be enough. (Given a CRHF h(m), you may be able to produce h(m ) for related m .)
The Random Oracle Heuristic Want: A public H that is non-malleable . Given H(m), it is hard to produce H(m ) for any non- trivially related m . For every PPT adv ? and every non-trivial relation ?, Pr ? ? = ? :? ?,? = 1 = negl(?) How about the relation ? where ? ?,? = 1 if and only if ? = H x ?
The Random Oracle Heuristic Proxy: A public H that behaves like a random function (A PRF also behaves like a random function, but ???? is not publicly computable.) Reality: Random Oracle Heuristic: H ?( ? ) (1?) H The only way to compute H H is virtually a black box. is by calling the oracle.
Proof Assume there is a PPT adversary ? that breaks the EUF- CMA security of hashed RSA in the random oracle model. ?? Give me H(m) ? Give me a signature of m Then, there is an algorithm that solves the RSA problem. (? ,? )
Proof Assume there is a (?-query) PPT adversary ? that breaks the EUF-CMA security of hashed RSA in the random oracle model. ?? = (?,?) (?,?,?) Hash Query: m ? trap ? ? = ? Pick random ? o.w., ? ? = ?? normal Sign Query: m ? = ??!abort! o.w., ? = ? Forgery: ? ,?
Proof Claim: To produce a successful forgery, ? must have queried the hash oracle on ? . W.p. 1/?, ? is the trap. ?? = (?,?) (?,?,?) Hash Query: m ? ? ? = ? o.w., ? ? = ?? Sign Query: m ? = ??!abort! o.w., ? = ? Forgery: ? ,? ?1/? trap If ? = ?, yay!
Bottomline: Hashed RSA (PKCS Standard, used everywhere) In practice, we let ? be the SHA-3 hash function. and believe that SHA-3 acts like a random function . That s the heuristic. On the one hand, it doesn t make any sense, but on the other, it has served us well so far. No attacks against RSA + SHA-3, for example.
Many Variants of Signatures (on the board) Aggregate Signatures: Compressing many signatures into one Ring Signatures: Protection for Whistleblowers Threshold Signatures: Protecting against loss of secret key
