Digital Signatures for Message Authentication and Non-Repudiation
In the realm of cryptography, digital signatures play a vital role in ensuring message authenticity and integrity between communicating parties. They provide a way for users to verify the source of a message and detect any potential tampering during transmission. This description explores the distinction between digital signatures and message authentication codes, highlighting their respective functions and applications. Additionally, it delves into the concept of non-repudiation and the security measures digital signatures offer against potential adversaries.
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
MIT 6.875 Foundations of Cryptography Lecture 11
Message Authentication Codes m ?,? = ???(??,?) sk sk Verify(??,?,?) Authenticity: Bob wants to ensure that the message came from Alice. Needs Bob and Alice to share a secret key beforehand.
Alice vk Digital Signatures: Public-key Analog of MACs m ?, Sign(??,?) sk Verify(??,?, ) (Public) verification keys are stored in a directory . Only Alice can produce signatures; but Bob (or indeed, anyone else) can verify them.
Digital Signatures vs. MACs Signatures MACs ? users require ?2keys ? users require ? key-pairs Publicly Verifiable Privately Verifiable Transferable Not Transferable Provides Non-Repudiation (is this a good thing or a bad thing?) Does not provide Non-Rep.
Alice pk,vk Other Applications 1. Certificates, or a public-key directory in practice: Trusted Certificate Authority, e.g. Verisign, Let s Encrypt. When Alice (=www.google.com) wants to register her public (encryption and signing) keys ?? and ??, first check that she is Alice. Issue a certificate ? ????(??????????,?????| ?? |??) Alice can later produce this certificate to prove that she owns ?? and ??. Browsers store ?????????? and check the certificate.
Other Applications 2. Bitcoin and other cryptocurrencies: I am identified by my verification key ??. When I pay you (= ?? ), I sign $x paid to ?? with my ??.
Digital Signatures: Definition A triple of PPT algorithms (???,????,??????) s.t. ??,?? ??? 1?. PPT Key generation algorithm generates a public-private key pair. (possibly probabilistic) Signing algorithm uses the secret signing key to produce a signature ?. ? ???? ??,? . Verification algorithm uses the public verification key to check the signature ? against a message ?. A??(1)/???(0) ?????? ??,?,? . Correctness: For all vk, sk, m: ?????? ??,?,???? ??,? = accept.
Digital Signatures: Security The adversary after seeing signatures of many msgs, should not be able to produce a signature of any new msg. 1. What are the adversary s powers? Request for, and obtain, signatures of (poly many) messages ?1,?2, Chosen-message attack 2. What is her goal? She wins if she produces a signature of any message ? {?1,?2, }. Existential Forgery
EUF-CMA Security (Existentially Unforgeable against a Chosen Message Attack) Challenger ??,?? ??? 1? Eve ?? ?? poly many times ?? ?? ????(??,??) ? ,? Eve wins if Verify(??,? ,? )= 1 and ? {?1,?2, }. The signature scheme is EUF-CMA-secure if no PPT Eve can win with probability better than negl(?).
Strong EUF-CMA Security (Existentially Unforgeable against a Chosen Message Attack) Challenger ??,?? ??? 1? Eve ?? ?? poly many times ?? ?? ????(??,??) ? ,? Eve wins if Verify(??,? ,? )= 1 and (? ,? ) (??,??,(??,??), }. The signature scheme is EUF-CMA-secure if no PPT Eve can win with probability better than negl(?).
Lamport (One-time) Signatures How to sign a bit Signing Key ??: [?0,?1] Verification Key ??: [?0= ?(?0),?1= ?(?1)] Signing a bit b: The signature is ? = ?? ? Verifying (b,?): Check if ? ? = ?? Claim: Assuming ? is a OWF, no PPT adversary can produce a signature of ? given a signature of ?.
Lamport (One-time) Signatures How to sign n bits ??,0 ??,1 ?1,0 ?1,1 ?2,0 ?2,1 ?1,0 ?1,1 Signing Key ??: ??,0 ??,1 ?2,0 ?2,1 Verification Key ??: where ??,?= ?(??,?). Signing an n-bit message (?1, ,??): The signature is ?1,?1, ,??,??. ? Verifying (?, ?): Check if ?:? ?? = ??,??
