Privacy in Signatures: Exploring Security Measures
Delve into the world of privacy-preserving signatures, encryption schemes, and digital authentication. Understand the importance of distinguishing good content from bad, ensuring message authenticity, and preventing repudiation. Explore the structures and functionalities of signature schemes, hash methods, and the misconceptions surrounding public-key encryption. Uncover the complexities of ring and group signatures, as well as the significance of non-repudiation in digital communication.
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
Privacy in signatures. Hiding in rings, hiding in groups Rennes, 24/10/2014 Cristina Onete CIDRE/ INRIA
Message authenticity Am lie Baptiste Message authenticity Baptiste is waiting for a message from Am lie How can he make sure it s really from her? Cristina Onete || 24/10/2014 || 2
Why sign Baptiste More importantly: Telling good content from bad Updates vs. malware and trojans Message should be sent by authorized party Cristina Onete || 24/10/2014 || 3
So far: MACs Shared Am lie Baptiste Message authentication codes Usually implemented as a keyed hash function MSCheme = (KGen, MAC, Vf) ?? KGen 1?; ??? MAC ??,? ; 0,1 Vf(??,?,???) Repudiation: anyone with sk can generate a tag (at least two people) Cristina Onete || 24/10/2014 || 4
Now: PK digital signatures A Am lie Baptiste SScheme = (KGen, Sign, Vf) (??,??) KGen 1?; ? Sign ??,? ; 0,1 Vf(??,?,?) Anyone can verify the signature! Non-repudiation: signer can never deny generating a real signature Cristina Onete || 24/10/2014 || 5
Contents Signatures vs. PK Encryption A common misconception Signature Scheme security The Hash and Sign method Privacy-preserving signatures Ring signatures Rings vs. Groups Group signatures
Common misconception Public-Key Encryption B B Am lie Baptiste Inverse mechanisms? Digital Signatures A Am lie Baptiste Cristina Onete || 24/10/2014 || 7
Common misconception Can we build signatures from encryption? Completely different functionality and goals! Property Encryption schemes Signatures schemes Message integrity Message confidentiality Non-repudiation Sender authentication Single receiver Using one primitive to get the other is dangerous! Cristina Onete || 24/10/2014 || 8
Digital Signatures Structure SSchemes = (KGen, Sign, Verify) Security parameter: determines key size KGen(1?) Everyone A ?? ?? Sign(s?,?) ?,? Vf(??,?,?) ? Cristina Onete || 24/10/2014 || 9
Signature Security Functionality correctness: KGen(1?) Sign( , ) B Verify( , ) A Security: unforgeability Verify A Cristina Onete || 24/10/2014 || 10
Inverse mechanisms? PK Encryption Signatures Key Generation: Key Generation: ?? ?? ?? ?? Encrypt Sign ? = ?????(?) = ?????(?) Decrypt: Verify: ? ? = ?????(?) ? = ?????( ) Exercise: Find a forgery ( ?, ?) given only ?? (no signatures) Cristina Onete || 24/10/2014 || 11
Abuse encryption step Input: ?? Choose random signature: ? Find the message: encrypt signature ? = ?????( ?) Output:( ?, ?) Now verify: ????? ? = ? Note: this message is random , it doesn t mean we can forge a signature for ANY message ? Cristina Onete || 24/10/2014 || 12
Inverse mechanisms? PK Encryption Signatures Key Generation: Key Generation: ?? ?? ?? ?? Encrypt Sign ? = ?????(?) = ?????(?) Decrypt: Verify: ? ? = ?????(?) ? = ?????( ) Suppose: ??????? ??????? = ????????? for any ??,?? Exercise: You are answered two signature queries for any two messages you want. Forge a signature for any ? Cristina Onete || 24/10/2014 || 13
Choosing messages well Input: ?,?? Choose random message: ??. Get signature ??= ?????(??) Second message is: ??= ???. Get signature ??= ?????(??) Output forgery: ? = ???? Now verify: ????????? = ??????????(??)?????(??) = ??????????(??) ?????(?????(??))= ? ?? = ????= ?? = ? ??????? ??????? = ????????? How likely is it to get signatures ?1,?2? Cristina Onete || 24/10/2014 || 14
Attacks against Signatures Security depends on what the attacker knows The more knows, the harder it is to get security Random-message attack: Lots of users all around Their messages are random Adv. gets (m, signa- ture) pairs Forge signature on new message! Cristina Onete || 24/10/2014 || 15
Attacks against Signatures Security depends on what the attacker knows The more knows, the harder it is to get security Known-message attack: Lots of users all around Knows messages in advance, before re- ceiving any signature Adv. gets (m, signa- ture) pairs Forge signature on new message! Hi, how are you? I m fine, thanks. How are you? I m very well, thank you Cristina Onete || 24/10/2014 || 16
Attacks against Signatures Security depends on what the attacker knows The more knows, the harder it is to get security Chosen-message attack: ?1 Lots of users all around Can choose messages that will be signed Adv. gets (m, signa- ture) pairs Forge signature on new message! ?? Cristina Onete || 24/10/2014 || 17
Attacks against Signatures Power of Strong Not strong/ Not weak Weak Attack Unf-RMA Unf-KMA Unf-CMA Cristina Onete || 24/10/2014 || 18
Hash and Sign in general Use the same thing in general Signature scheme (???????,????,??) Hash function(????,?) Key generation: Run (?????,?????) ???????and ? ???? Signing: = ????(??,??(?)) Verifying: Compute: ? = ??(?) Return ??(??, ?,?) Cristina Onete || 24/10/2014 || 19
Contents Signatures vs. PK Encryption A common misconception Signature Scheme security The Hash and Sign method Privacy-preserving signatures Ring signatures Rings vs. Groups Group signatures
So far: integrity & authenticity A Each ?? corresponds to its owner Successful verification means identifying signer! Cristina Onete || 24/10/2014 || 21
Ring Signatures Cristina Onete || 24/10/2014 || 22
Ring Signatures Regular Signatures: (??,??) KGen 1?; ? Sign ??,? ; 0,1 Vf(??,?,?) Ring Signatures: ??,?? KGen 1?; ? Sign ?,??; ?,? ; with ? = ??1, ,??? and ??,??? KGen 1?; 0,1 Vf(?,?,?) Cristina Onete || 24/10/2014 || 23
Ring Signature Properties Anonymity: ???? ??? Flavours of anonymity depend on how much we let the adver- sary control the ring and the keys in it. Cristina Onete || 24/10/2014 || 24
Ring Signature Properties Unforgeability: ???? 0 Could do this for a fixed ring, a chosen subring, or even allo- wing insider corruptions (the adversary learns secret keys) Cristina Onete || 24/10/2014 || 25
Aside: pairings Two groups: G1,G2,G?, all of prime order ? Generators: ?1of G1, ?2of G2 Pairing: a map e: G1 G2 G?which is: Bilinear: ?,?2 ?= ?(?1,?2)?? ?,? ??: ? ?1 Non-degenerate: ? ?1,?2 1 Computable: ? should be efficiently computable Pairings exist for many groups. Not all are efficiently computable! Cristina Onete || 24/10/2014 || 26
Ring Signature 2-Ring Three groups: G = G1= G2,G?, all of prime order ? Generator: ? of G Key generation: Choose ?? ??. Set ?? = ???. Signature on m ??, given ??, ??, ?? = ??? : Choose ? ??, set ? = ??. Output ? = (?,(?? )?,???(?? )? ?? ?) Signature on m ??, given ?? , ?? , ?? = ???: Choose ? ??, set ? = ??. Output ? = (?,??? ,???+ ? ?? ?) Verification of ? = (?,?,?) on message ? Output 1 iff. ? ?,?? = ?(?,?) AND ? ??,? ?(??,?)?= ?(?,?) Cristina Onete || 24/10/2014 || 27
Ring vs. Group Ring Signatures: Signer needs to get ? 1 other ??s Other ring members independent of signer, unaware of him Signer remains completely untraceable, even if he misbehaves No accountability Group signatures Signer registers into a group of arbitrarily many signers Sign on behalf of a group (with just one ??) Optional anonymity revocation : can extract signer if needed Cristina Onete || 24/10/2014 || 28
Ring Signatures Cristina Onete || 24/10/2014 || 29
Group Signatures G Cristina Onete || 24/10/2014 || 30
Optional Anonymity Revocation G Cristina Onete || 24/10/2014 || 31
Group Signatures Syntax ??? = {???1, ,????},???,???? KGen 1?,1?; ? GSign ????; ? ; 0,1 GVf(???,?,?) {?,????} Open(????, ?,?) Sometimes ???? = ???,??? Revocation key Registration key Cristina Onete || 24/10/2014 || 32
Group Signature Properties Full-anonymity: ???? G ??? Cristina Onete || 24/10/2014 || 33
Group Signature Properties Full-traceability: ???? G Cristina Onete || 24/10/2014 || 34
General strategy Public key is a function of all the keys Traceability: use a ZK proof of knowledge then use extractability to trace Further Reading: [BMW03] Bellare, Micciancio, Warinschi: Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions , CRYPTO 2003 [BMW04] Boneh, Boyen, Shacham: Short Group Signatures , CRYPTO 2004 Cristina Onete || 24/10/2014 || 35
Thanks! CIDRE
