Cryptology ePrint Archive: Report 2006/363

A Weakness in Some Oblivious Transfer and Zero-Knowledge Protocols

Ventzislav Nikov and Svetla Nikova and Bart Preneel

Abstract: We consider oblivious transfer protocols and their applications that use underneath semantically secure homomorphic encryption scheme (e.g. Paillier's). We show that some oblivious transfer protocols and their derivatives such as private matching, oblivious polynomial evaluation and private shared scalar product could be subject to an attack. The same attack can be applied to some non-interactive zero-knowledge arguments which use homomorphic encryption schemes underneath. The roots of our attack lie in the additional property that some semantically secure encryption schemes possess, namely, the decryption also reveals the random coin used for the encryption, and that the (sender's or prover's) inputs may belong to a space, that is very small compared to the plaintext space. In this case it appears that even a semi-honest chooser (verifier) can derive from the random coin bounds for all or some of the sender's (prover's) private inputs with non-negligible probability. We propose a fix which precludes the attacks.

Category / Keywords: cryptographic protocols / Oblivious Transfer, Homomorphic Semantically Secure Cryptosystems, Paillier's Public-Key Cryptosystem, Non-Interactive Zero-Knowledge Arguments

Publication Info: Full version of a paper from AsiaCrypt 2006

Date: received 25 Oct 2006, withdrawn 28 Nov 2006

Contact author: svetla nikova at esat kuleuven be

Available formats: (-- withdrawn --)

Note: The attack does not work! Details can be found at http://homes.esat.kuleuven.be/~snikova/svb_ac06.pdf (Added on 2 Jan 2007)

Version: 20070110:135558 (All versions of this report)

Discussion forum: Show discussion | Start new discussion