1985 Reports

A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems

Galil, Zvi; Haber, Stuart; Yung, Moti

We introduce a new two-party protocol with the following properties: 1. The protocol gives a proof of the value, 0 or 1, of a particular Boolean predicate which is (assumed to be) hard to compute. This extends the 'interactive proof systems' of (7), which are only used to prove that a certain predicate has value 1. 2. The protocol is provably minimum-knowledge ill the sense that it communicates no additional knowledge (besides the value of the predicate) that might be used, for example, to compromise the private key of a user of a public-key cryptosystem. 3. The protocol is result-indistinguishable: an eavesdropper, overhearing an execution of the protocol, does not know the value of the predicate that was proved. This bit is cryptographically secure. The protocol achieves this without the use of encryption functions, all messages being sent in the clear. These properties enable us to define a minimum-knowledge cryptosystem, in which each user receives exactly the knowledge he is supposed to receive and nothing more. In particular, the system is provably secure against both chosen-message and chosen-ciphertext attack. Moreover, extending the Diffie-Hellman model, it allows a user to encode messages to other users with his own public key. This enables a symmetric use of public-key encryption.