An Efficient Encryption Framework for Zero-Knowledge Proof Systems

Abstract

In privacy-sensitive applications, there often exists a conflict between privacy and reliability; transparent data may guarantee the reliability but harm the privacy, while encrypted data may protect the privacy but obscure the reliability. For a typical example, in a blockchain system, sharing original data harms the privacy but encrypting them causes a doubt on whether the ciphertext is based on legitimate data. The zero-knowledge proof system is a cryptographic primitive where one can prove a statement of data without revealing secret information, which can be a suitable solution for the conflict between privacy and reliability. Among zero-knowledge proofs, the pairing-based zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) is a useful candidate that achieves a constant proof size regardless of the input function. However, pairing-based zk-SNARKs suffer from two limitations which prevent them from being deployed in practical applications; one is that an adversary can modify an existing proof to pass the verification without the knowledge of witnesses, and the other one is that proving time and parameter size becomes heavily inefficient when the input function includes complex operations such as encryption. In this dissertation, we overcome the limitation of malleability by proposing an efficient simulation-extractable zk-SNARK (SE-SNARK) with a single verification. The SE-SNARK is a notion of non-malleable zk-SNARK, and it requires an additional check in verification and sacrifices either proof size or input function size to gain non-malleability. We propose an SE-SNARK construction comparable to the original zk-SNARK which does not require any additional check or sacrifice of efficiency. This dissertation then overcomes the limitation of practicality by proposing an efficient encryption framework for zero-knowledge proof systems. There often exists a requirement for the proof system to be combined with encryption, but including encryption in the proof circuit causes impractical proving time and parameter size. By introducing an idea of detaching the encryption from proof circuit, we propose an efficient encryption framework called SNARK-friendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization (SAVER) that achieves practical performance when combined with zero-knowledge proof systems. For the representative application, we also propose a Vote-SAVER based on SAVER, which is a novel voting system where voter's secret key lies only with the voter himself. The Vote-SAVER satisfies receipt-freeness (which implies ballot privacy), individual verifiability (which implies non-repudiation), vote verifiability, tally uniqueness, and voter anonymity. The experimental results show that our SAVER with respect to the Vote-SAVER relation yields 0.7s for zk-SNARK proving time and 10ms for encryption, with the parameter size of 16MB.