What is the conceptual difference between the definition of correctness and completeness in verifiable cryptographic protocols? They justify that if a statement is correct then the verification should always successfully verifies. Is their any difference in the definitions? Or the one can substitute correctly the other?

It seems like authors prefer the term correctness for verifiable computations and the term completeness for zero-knowledge proofs


In context of interactive proof systems (including zero-knowledge proofs) completeness means the same as the term correctness as used for many other (interactive) cryptographic schemes or protocols. I guess that's mainly due to historical reasons (there are even some people that use correctness instead of completeness in context of zero-knowledge proofs).

Basically, both things say that if everything happens honestly, then it works out as it is supposed to be. Note that completeness as well as correctness may not be perfect. For instance, zero-knowledge proofs may have a completeness error, i.e., even if the statement to be proven is true and both - the prover and the verifier - behave honest, the verification may only work with some probability (close to one). Similarly, for public key encryption schemes the correctness may also only hold with a probability close to one, i.e., that decrypting a ciphertext for a message may lead to some different message (even under some honestly generated keys).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.