Efficient Non-Interactive Zero-Knowledge Proofs for Privacy Applications

Abstract

Non-interactive zero-knowledge (NIZK) proofs can be an extremely powerful tool, allowing one to prove a statement in a single message without revealing any information besides the truth of the statement. Blum et al. showed that NIZK proof systems exist for all languages in NP. However, in practice, NIZK proofs are rarely used, because existing protocols are extremely inefficient. Here we examine some useful languages for which we can give efficient proof system. We define two useful building blocks: one for proving that a message has been signed, and a second for proving that a value has been chosen according to a pseudorandom function. We give applications of these building blocks to anonymous credential systems, to electronic cash, and to the design of other efficient NIZK proofs systems.