Dakshita Khurana: How to Achieve Non-malleability in One or Two Rounds, or, A Knowledge Extraction Technique for Two Round Protocols

Abstract: Knowledge extraction is an important technique central to several cryptographic protocols. Usually, protocols requiring knowledge extraction based on standard assumptions require at least three rounds of interaction.

 

In this talk, I will describe a new black-box knowledge extraction technique for two round protocols that only relies on sub-exponential DDH or QR or Nth residuosity. We use this extraction technique to obtain new protocols in the realm of non-malleable commitments and zero-knowledge, that were believed to be impossible so far.

- We obtain the first constructions of two-message non-malleable commitments satisfying the strong definition of non-malleability with respect to commitment.

- We also obtain one-round non-malleable commitments with respect to opening, which we use to obtain simple constructions of two round multi-party coin-tossing with simultaneous messages.

- We also construct two-message zero-knowledge with strong super-polynomial simulation. In particular, our protocol has a uniform simulator that runs in time less than the quality of zero-knowledge.

 

Joint work with Amit Sahai. Eprint: https://eprint.iacr.org/2017/291.pdf