We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field. Our system does not suffer from these limitations.The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values in this setting. We then adapt the approach from Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using 25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is range proof. To prove that each plaintext in 200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.

This article presents two dynamic symmetric searchable encryption schemes for geometric range search. Our constructions are the first to provide forward/backward security in the context of SSE-based schemes supporting geometric range search. Besides, we define a security notion called content privacy. This security notion captures the leakages that are critical in the context of geometric range search but not considered by forward/backward security. Content privacy eliminates the leakage on the updated points of the database during both search and update. Due to the inherent leakages associated with range queries, none of the existing related works can support content privacy, whereas the design of our constructions avoids such leakages. When compared to the state-of-the-art schemes, our constructions provide a higher level of security and practical efficiency supported by our experimental results.

An escrow protocol for Bitcoin allows fair trading using bitcoins. To ensure fairness, the existing proposals made various trade-offs between trust, privacy, and efficiency. In this work, we evaluate the existing escrow protocols for cryptocurrency and propose a practical escrow protocol for Bitcoin that is: (a) computationally efficient; (b) round efficient; and (c) privacy-preserving. The core component of our escrow protocol for Bitcoin is a new verifiably encrypted ECDSA scheme, which may be of independent interest. Furthermore, we implement the escrow protocol for Bitcoin in Bitcoin mainnet, demonstrating the feasibility of our protocol.