Report

Foundations of Privacy Formal Lecture Zero-Knowledge and Deniable Authentication Lecturer: Moni Naor Giving talks Advice on giving Academic Talks • • • • • Giving an Academic Talk by Jonathan Shewchuk Oral Presentation Advice by Mark D. Hill Pointers on giving a talk by David Messerschmitt How to give a good talk by Hany Farid Giving Talks by Tom Cormen Authentication and Non-Repudiation • Key idea of modern cryptography [Diffie-Hellman]: can make authentication (signatures) transferable to third party - Non-repudiation. – Essential to contract signing, e-commerce… • Digital Signatures: last 25 years major effort in – Research • Notions of security • Computationally efficient constructions – Technology, Infrastructure (PKI), Commerce, Legal Is non-repudiation always desirable? Not necessarily so: • Privacy of conversation, no (verifiable) record. – Do you want everything you ever said to be held against you? • If Bob pays for the authentication, shouldn't be able to transfer it for free • Perhaps can gain efficiency Alternative: (Plausible) Deniability If the recipient (or any recipient) could have generated the conversation himself or an indistinguishable one Deniable Authentication Setting: • Sender has a public key known to receiver • Want to an authentication scheme such that the receiver keeps no receipt of conversation. This means: • Any receiver could have generated the conversation itself. – There is a simulator that for any message m and verifier V* generates an indistinguishable conversation. – Exactly as in Zero-Knowledge! – An example where zero-knowledge is the ends, not the means! Proof of security consists of Unforgeability and Deniability ciphertext Encryption Plaintext • Assume a public key encryption scheme E • Public key Pk – knowing Pk can encrypt message m – Compute Y=E(Pk, m) • With corresponding secret key Ps, given y can retrieve m m=D(Ps, E(Pk, m)) • Process is probabilistic: to actually encrypt choose random string and compute Y=E(PK, x, ). Deniable Authentication Completeness for any good sender and receiver possible to complete the authentication on any message Unforgeability Existential unforgeable against adaptive chosen message attack – Adversary can ask to authenticate any sequence m1, m2, … – Has to succeed in making V accept a message m not previously authenticated – Has complete control over the channels Deniability – For any(?) verifier, there is simulator that can generate computationally indistinguishable conversations. Interactive Authentication P wants to convince V that he is approving message m P has a public key Pk and a secret key Ps of encryption scheme E. To authenticate a message m: • V P: Choose x 2R {0,1}n. Send c=E(PK, m ° x) • P V: Receiving c Decrypt c using Ps Verify that prefix of plaintext is m. If yes - send x. V is satisfied if he receives the same x he chose Is it Safe? Want: Existential unforgeability against adaptive chosen message attack – Adversary can ask to authenticate any sequence m1, m2, … – Has to succeed in making V accept a message m not authenticated – Has complete control over the channels • Intuition of security: if E does not leak information about plaintext – Nothing is leaked about x Unforgeability: depends on the strength of E • Sensitive to malleability: – if given E(PK, m°x, ) can generate E(PK, m’°x’, ’) where m’ is related to m and x’ is related to x then can forge. Security of the scheme Unforgeability: depends on the strength of E • Sensitive to malleability: – if given E(PK, m°r, ) can generate E(PK, m’°r’, ’) where m’ is related to m and r’ is related to x then can forge. • The protocol allows a chosen ciphertext attack on E. – Even of the post-processing kind! • Can prove that any strategy for existential forgery can be translated into a CCA strategy on E • Works even against concurrent executions. There are encryption schemes satisfying the desired requirements Deniability: does V retain a receipt?? – It does not retain one for an honest V – Need to prove knowledge of r No receipts • Can the verifier convince third party that the prover approved a certain message? Simulator for honest receiver Choose x R {0,1}n. Output: hY=E(PK, m°x, ), x, i Has exactly the same distribution as a real conversation when the verifier is following the protocol Statistical indistinguishability Verifier might cheat by checking whether certain ciphertext have as a prefix m No known concrete way of doing harm this way Commitment Schemes Commit Phase Sender s X Receiver – Hiding: A computationally bounded receiver learns nothing about X. Reveal Phase Sender v X X – Binding: s can only be “opened” to the value X. Receiver s, v, X Reveal Verification Algorithm yes/no Encryption as Commitment When the public key PK is fixed and known Y=E(PK, x, ) can be seen as commitment to x To open x: reveal , the random bits used to create Y Perfect binding: from unique decryption For any Y there are no two different x and x’ and and ’ s.t. Y=E(PK, x, ) =E(PK, x’, ’) Secrecy: no information about x is leaked to those not knowing private key PS Deniable Protocol P has a public key PK of an encryption scheme E. To authenticate message m: P commits to the value x. n • V P: Choose xR{0,1} . Does not reveal it yet Send Y=E(PK, m°x, ) • P V: Decrypt Y=E(PKj, m°x, ), Send E(PK, x, ) • V P: Send x and - opening Y=E(PK, m°x, ) • P V: Verify consistency and open E(PK, x, ) by sending . Security of the scheme Unforgeability: as before - depends on the strength of E can simulate previous scheme (with access to D(PK , . )) Important property: E(PK, x, ) is a non-malleable commitment (wrt the encryption) to x. In Step 2. Instead of E(PK, x, ) Deniability: can run simulator: • Extract x by running with E(PK, garbage, ) and rewinding – Expected polynomial time • Need the semantic security of E - acts as a commitment scheme Complexity of the scheme Sender: single decryption, single encryption and singe encryption verification Receiver: same Communication Complexity: O(1) public-key encryptions Ring Signatures and Authentication Want to keep the sender anonymous by proving that the signer is a member of an ad hoc set – Other members do not cooperate – Use their `regular’ public-keys – Should be indistinguishable which member of the set is actually doing the authentication Bob Alice? Eve Ring Authentication Setting • A ring is an arbitrary set of participants including the authenticator • Each member i of the ring has a public encryption key PKi – Only i knows the corresponding secret key PSi • To run a ring authentication protocol both sides need to know PK1, PK2, …, PKn the public keys of the ring members ... Deniable Ring Authentication Completeness for any good sender and receiver possible to complete the authentication on any message Unforgeability Existential unforgeable against adaptive chosen message attack Deniability – For any verifier, for any arbitrary set of keys, some good some bad, there is simulator that can generate computationally indistinguishable conversations. Source Hiding: – For any verifier, for any arbitrary set of keys, some good some bad, the source is computationally indistinguishable among the good keys Source Hiding and Deniability – incomparable An almost Good Ring Authentication Protocol Ring has public keys PK1, PK2, …, PKn of encryption scheme E To authenticate message m with jth decryption key PSj: V P: Choose x {0,1}n. Send E(PK1, m°x, 1), E(PK2, m°x, 2), …, E(PKn, m°x, n) P V: Decrypt E(PKj, m°x, j), using PSj and Send E(PK1, x, 1), E(PK2, x, 2), …, E(PKn, x, n) V P: open all the E(PKi, m°x, i)’s by Send x and 1, 2 ,…, n P V: Verify consistency and open all E(PKi, x, i) by Send x and 1, 2 ,… n Problem: what if not all suffixes (x‘s) are equal And the adversary knows one the keys! The Ring Authentication Protocol Ring has public keys PK1, PK2, …, PKn of encryption scheme E To authenticate message m with jth decryption key PSj: V P: Choose x {0,1}n. Send E(PK1, m°x, 1), E(PK2, m°x, 2), …, E(PKn, m°x, n) P V: Decrypt E(PKj, m°x, j), using PSj and Send E(PK1, x1, 1), E(PK2, x2, 2), …, E(PKn, xn, n) Where x=x1+x2 + xn V P: open all the E(PKj, m°x, j)’s, by Send x and 1, 2 ,…, n P V: Verify consistency and open all E(PKi, x, i) by Send x1, x2, …, xn and 1, 2 ,… n Complexity of the scheme Sender: single decryption, n encryptions and n encryption verifications Receiver: n encryptions and n encryption verifications Communication Complexity: O(n) public-key encryptions Security of the scheme Unforgeability: as before (assuming all keys are well chosen) since E(PK1, x1, t1), E(PK2, x2, t2),…,E(PK1, xn, tn) where x=x1+x2 + xn is a non-malleable commitment to x Source Hiding: which key was used (among well chosen keys) is – Computationally indistinguishable during protocol – Statistically indistinguishable after protocol • If ends successfully Deniability: Can run simulator `as before’ Properties of the Scheme • Works with any good encryption scheme - members of the ring are unwilling participants. • Fairly efficient scheme: – Need n encryptions n verifications and one decryption • Can extend the scheme so that convince a verifier that At least k members confirm the message. Extended Protocol Ring has public keys PK1, PK2, …, PKn of encryption scheme E To authenticate message m with subset T of decryption keys: : To authenticate message m with subset T of decryption keys: • V P: Choose r {0,1}n. and split into shares x1, x2, … xn Send E(PK1, m°x1, r1), E(PK2, m°x2, r2), …, E(PK1, m°xn, rn) • P V: For each jT decrypt E(PKj, m°xj, rj) using PSj and reconstruct r Send E(PK1, x’1, 1), E(PK2, x’2, 2), …, E(PKn, x’n, n) Where r=x’1+x’2 + x’n • V P: open all the E(PKi, m°xj, ri) by Send x1, x2, … xn and r1, r2 ,… rn • P V: Verify consistency and open all E(PKi, x, ti) by Send t1, t2 ,… tn and x’1, x’2 ,…, x’n Ring Signatures [RST] Rivest, Shamir and Tauman proposed Ring Signatures: • Signature on message m by a member of an ad hoc set of participants – Using existing Infrastructure for signatures • For a generated signature the source is (statistically) indistinguishable • Non-repudiation - recipient can convince a third party of the authenticity of a signature • Non-interactive - single round • Efficient - if underlying signature is low exponent RSA/Rabin – Need Ideal Cipher for combining function • What are the social implications of the existence of ring authentication and signatures? Related Notions Deniability and anonymity can have many meanings…, long history in Crypto • Deniable Encryption • Undeniable signatures – • Chameleon signatures (Krawczyk and Rabin 98). Group signatures The signature is intended for ultimate adjudication by a third party (judge). – Not deniable if secret keys are revealed! • Designated verifier proofs Coming Lectures • • • • Randomized Response – Stanley L. Warner, Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias, – Moran and Naor, Polling with Physical Envelopes: A Rigorous Analysis of a HumanCentric Protocol, More Randomized Response – Evfimievski, Gehrke, and Srikant. Limiting Privacy Breaches in Privacy Preserving Data Mining. (PODS 2003). – Nina Mishra and Mark Sandler, Privacy via Pseudorandom Sketches, PODS 2006 K- Anonymity and Linkability – Latanya Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570. – A. Narayanan, V. Shmatikov. How To Break Anonymity of the Netflix Prize Dataset. – Machanavajjhala, Gehrke, Kifer, and M. Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity. In Proc. 22nd Int Conf. Data Eng. (ICDE), page 24, 2006. – Ninghui Li, Tiancheng Li, Suresh Venkatasubramanian. t-closeness: Privacy Beyond kAnonymity and l-Diversity ICDE 2007. Auditing – J. Kleinberg, C. Papadimitriou, P. Raghavan, Auditing Boolean Attributes, PODS 2000. – Krishnaram Kenthapadi, Nina Mishra, Kobbi Nissim, Simulatable Auditing, PODS 2005. Coming Lectures – Irit Dinur and Kobbi Nissim, Revealing information while preserving privacy. PODS, 2003. – Cynthia Dwork, Frank McSherry and Kunal Talwar, The price of privacy and the limits of LP decoding. STOC 2007, • Differntial Privacy – Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith: Calibrating Noise to Sensitivity in Private Data Analysis. TCC 2006, – A. Blum, C. Dwork, F. McSherry, and K. Nissim, Practical Privacy: The SuLQ Framework, PODS, 2005. • Contingency Tables – Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry and Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release. PODS 2007: 273-282 – Lars Backstrom, Cynthia Dwork and Jon M. Kleinberg: Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography. WWW 2007 • Application of Differential Privacy – Kunal Talwar and Frank McSherry, Mechanism Design via Differential Privacy. FOCS, 2007. – Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. Smooth Sensitivity and Sampling in Private Data Analysis , STOC 2007, Extras • Fuzzy Extractors • RFIDs, – Yossi Oren and Adi Shamir, Power Analysis of RFID Tags – Stephen A. Weis Security of HB+ • Face\Vision Crowd – Enabling Video Privacy through Computer Vision – E. Newton, L. Sweeney, and B. Malin. Preserving Privacy by Deidentifying Facial Images