Foundations of Cryptography: Digital Signatures and Collision-Resistant Hash Functions
Foundations of Cryptography explores the construction of digital signature schemes and collision-resistant hash function families using one-way functions and safe primes. The content delves into the concept of collision-resistant hash functions and their construction from the discrete logarithm problem, highlighting their importance in securing cryptographic systems. Additionally, it addresses techniques for compressing more data efficiently and presents theorems related to digital signature schemes based on the hardness of the discrete logarithm problem.
Uploaded on Oct 02, 2024 | 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. 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 13
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
What if I want to compress more? Solution 1: Modify the Discrete Log construction ?3 mod p. ?1?2 ?2?3 ?1 ,?2,?3?1,?2,?3 = ?1 Solution 2: Domain-extension Theorems. If there exist hash functions compressing ? + 1 bits to ? bits, then there are hash functions that compress any poly(?) bits into ? bits.
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. 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 ? CRHF?
Digital Signatures It turns out that collision-resistant hashing is not necessary. Theorem: Digital Signature schemes exist if and only if one-way functions exist.
Worlds in Crypto Cryptomania: Public-key encryption Minicrypt: Zero- Knowledge proofs MAC Digital Signatures Bit Commitment Secret-key encryption PRF PRG CRHF OWF OWF
Digital Signature Construction Start from ??.???,??.????,??.??? , a one-time signature scheme that can sign arbitrarily long messages. (Lamport + collision-resistant hashing) Build a (virtual) tree of depth ? = security param. Let ? be a PRF key, ??= ???(?,?) for ? 0,1 ?, and ???,??? ??.???(1?;??).
Digital Signature Construction Signature keys: ?? = ? and ?? = ?????. Signing Algorithm: Pick a random leaf r 0,1?, Generate the authentication path ??, ??1,??2, ,?? & ? ?? ??.???? ???,???0||???1 ? ??.???? ???,? The signature is (r,??, ??1,??2, ,??,? ).
Digital Signature Construction Historically regarded as inefficient; therefore, never used in practice. However, this signature scheme (or variants thereof) are now called hash-based signatures and seeing a re-emergence as a candidate post-quantum secure signature scheme. E.g. https://sphincs.org/
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.
An Application: Authenticated Key Exchange ?? ??
An Application: Authenticated Key Exchange ??? Bob Alice ??? ??, Sign(???,??) ??, Sign(???,??)
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
