Efficient zero-knowledge range arguments and privacy-preserving applications

Abstract

This thesis primarily explores efficient zero-knowledge range arguments as first part and privacy-preserving applications within distributed systems as second part.

The first part focuses on zero-knowledge range arguments, a fundamental cryptographic primitive that enables a prover to convince a verifier that a secret value lies within a predefined range without disclosing any unnecessary information. However, deploying range arguments in practice faces significant challenges due to high gas costs and computational overhead. This part contributes to optimizing the {\em verification efficiency} of range arguments to reduce deployment costs on blockchains and other decentralized platforms. We introduce four new zero-knowledge range arguments in the discrete logarithm setting that require only $c \sqrt{\tfrac{N}{\log N}}$ group exponentiations in verification, where $N$ is the number of bits to represent a range and $c$ is a small constant. These improvements make the arguments concretely efficient for blockchain deployment with minimal gas costs.

The second part proposes two privacy-enhancing secure distributed systems and applications. First, we introduce a novel paradigm for decentralized privacy-preserving group purchasing for energy plans. Leveraging privacy-preserving blockchain technology and secure multi-party computation, this approach enables users to form coalitions for coordinated switch decisions in a decentralized manner without relying on a trusted third party. We develop an effective solution to support decentralized privacy-preserving group purchasing, which includes a competitive online algorithm for decision-making, secure multi-party computation for enhancing privacy, and zero-knowledge proofs on the blockchain for verifying the private input data used in our online algorithm. Second, we propose a novel scheme zk-qrcode based on anonymous credentials and zk-SNARK. Our scheme leverages the following features: Blockchain-based credential issuance, we eliminate the need for credential issuers to hold signing keys by allowing them to issue credentials to a smart contract on the blockchain; Flexible and composable identity statements, enables users to prove complex statements about their credentials without revealing unnecessary information; QR code based verification: enables user interaction with service providers through QR codes displayed or scanned on mobile phones, incorporating identity proof and access control requests. We implement and evaluate our zk-qrcode scheme in practical use cases for entering bar anonymously. Our results demonstrate that the scheme is efficient and practical, with access control proof generation and verification taking less than 650 milliseconds.