Commitment like a note placed in a combination safe

Commitment like a note placed in a combination safe

• Commitment like a note placed in a combination safe

• Two properties: hiding and binding

• Electronic equivalent of such a safe

Introduced in the seminal work of Dolev, Dwork and Naor [DDN91]

• Introduced in the seminal work of Dolev, Dwork and Naor [DDN91]

• Plan for the rest of the talk

• Problem statement + Definition
• An informal idea of our new technique
• Some formal details
• Results / Prior works

• A central concept in the formal analysis of crypto protocols

• To prove adversary knows a string s

• just run the adversary many times from different points (called rewinding the adversary machine)
• observe protocol messages
• compute string s and output

This construction

• This construction

• Only works for identities coming from a logarithmic domain (need to find a collision)
• Assumes that the adversary always gives correct answers

• The ideas presented here don’t directly extend to the general case

• Final construction:

• Gives constant round non-malleable commitments for general adversaries
• relies on a fair bit of probability/combinatorial analysis

Long line of prior works on non-malleable commitments [Dolev-Dwork-Naor’91, Barak’02, Pass-Rosen’05,…., Wee’10]

• Long line of prior works on non-malleable commitments [Dolev-Dwork-Naor’91, Barak’02, Pass-Rosen’05,…., Wee’10]

• All previous constructions either:

• very inefficient (used heavy PCP machinery), or,
• Non-standard assumptions

• This work: avoids PCP machinery + uses only OWF

Techniques in this work allow us to solve several other connected open problems

• Techniques in this work allow us to solve several other connected open problems

• Constant round oblivious transfer -> constant round secure multi-party computation
• Black-box constant round non-malleable zero-knowledge

• Follow up works using / improving our construction in various direction [Jain-Pandey’12, Goyal-Lee-Ostrovsky-Visconti’12, Garg-Goyal-Jain-Sahai’12]