[Cryptography] Is Non-interactive Zero Knowledge Proof an oxymoron?

Allen allen at credacash.com
Sat Mar 12 10:04:42 EST 2016


> This is really a question about terminology. I've been trying to come up
> with a definition of a Zero Knowledge Proof.

In general, I think the term "Zero Knowledge Proof" is best understood  
as abbreviation for the more complete name "Zero Knowledge Proof of  
Knowledge".  See
https://www.google.com/#q=%22zero+knowledge+proof+of+knowledge%22

Here's how we describe it in the documentation for our CredaCash  
cryptocurrency (paraphrasing somewhat):

A zero knowledge proof of knowledge verifies a prover knows a set of  
hidden inputs that satisfy a set of conditions given a set of public  
inputs.  In order to create a zero knowledge proof, the prover must  
provide a set of hidden inputs that, when combined with a set of  
public inputs, satisfy the conditions determined in the construction  
of the proof system.  Using only the public inputs and the proof, a  
verifier can verify that the prover was able to satisfy the  
conditions, but is unable to determine any information about the  
prover's hidden inputs, other than the fact that they satisfy the  
conditions.  In general, this is most useful when the prover is  
required to provide inputs that correspond to the publicly-known  
outputs of a cryptographic hash function, since this proves knowledge  
of values (the hash inputs) that cannot be determined from the  
publicly-known values (the hash outputs).  The zero knowledge proof  
verifies the prover knows these hash inputs without revealing the  
inputs themselves.

For example, the condition could be that public_input =  
hash(hidden_input).  The prover generates a secret value A, computes B  
= hash(A), and then publishes B, making it a public value.  To prove  
it knows the A that satisfies B = hash(A), the prover computes a proof  
C.  The prover then sends B and C to a verifier, and the verifier is  
able to verify that the prover does in fact know an A that satisfies B  
= hash(A), but does not gain any other information about the specific  
A used to create the proof.  This can be used in the same way as a  
digital signature, however, depending on the zero knowledge proof  
system, the conditions can be much more complex and include one or  
more hash outputs, each with one or more inputs, and the hash inputs  
and outputs can be cascaded and combined using addition, subtraction,  
multiplication, division, bitwise and, or, exclusive-or, one’s  
complement, etc., and the outputs can be tested using comparison  
operations such as equality, less than, greater than, etc.

In the CredaCash cryptocurrency, a zero knowledge proof is used to  
verify that the sum of a transaction's input values equals the sum of  
the transaction's output values, while keeping the transaction values  
themselves private.  See https://credacash.com/

The "non-interactive" part means that the prover can generate the  
proof without any input or interaction with the verifier, and the  
verifier needs no additional information to verify the proof, other  
than the proof itself and the public inputs.  This is important for  
example in a cryptocurrency to allow many users to verify a  
transaction without requiring any interaction with the user who  
created the transaction.  Most digital signing schemes are also  
non-interactive, i.e., a signature can be created without interacting  
with the verifier, and can then be verified without interacting with  
the signer.




More information about the cryptography mailing list