publications

2023

1. Updatable Privacy-Preserving Blueprints

   Bernardo David, Felix Engelmann, Tore Frederiksen, Markulf Kohlweiss, Elena Pagnin, and Mikhail Volkhov

   In Cryptology ePrint Archive, 2023

   Abstract eprint

   Privacy-preserving blueprints enable users to create escrows using the auditor’s public key. An escrow encrypts the evaluation of a function P(t,x), where t is a secret input used to generate the auditor’s key and x is the user’s private input to escrow generation. Nothing but P(t,x) is revealed even to a fully corrupted auditor. The original definition and construction (Kohlweiss et al., EUROCRYPT’23) only support the evaluation of functions on an input x provided by a single user.
   We address this limitation by introducing updatable privacy-preserving blueprint schemes (UPPB), which enhance the original notion with the ability for multiple parties to non-interactively update the private value x in a blueprint. Moreover, a UPPB scheme allows for verifying that a blueprint is the result of a sequence of valid updates while revealing nothing else.
   We present uBlu, an efficient instantiation of UPPB for computing a comparison between private user values and a private threshold t set by the auditor, where the current value x is the cumulative sum of private inputs, which enables applications such as privacy-preserving anti-money laundering and location tracking. Additionally, we show the feasibility of the notion generically for all value update functions and (binary) predicates from FHE and NIZKs.
   Our main technical contribution is a technique to keep the size of primary blueprint components independent of the number of updates and reasonable for practical applications. This is achieved by elegantly extending an algebraic NIZK by Couteau and Hartmann (CRYPTO’20) with an update function and making it compatible with our additive updates. This result is of independent interest and may find additional applications thanks to the concise size of our proofs.

2. Zero-Knowledge Arguments for Subverted RSA Groups

   Dimitris Kolonelos, Mary Maller, and Mikhail Volkhov

   In IACR International Conference on Public-Key Cryptography, 2023

   Abstract eprint Talk

   This work investigates zero-knowledge protocols in subverted RSA groups where the prover can choose the modulus and where the verifier does not know the group order. We introduce a novel technique for extracting the witness from a general homomorphism over a group of unknown order that does not require parallel repetitions. We present a NIZK range proof for general homomorphisms such as Paillier encryptions in the designated verifier model that works under a subverted setup. The key ingredient of our proof is a constant sized NIZK proof of knowledge for a plaintext. Security is proven in the ROM assuming an IND-CPA additively homomorphic encryption scheme. The verifier’s public key is reusable, can be maliciously generated and is linear in the number of proofs to be verified.

2022

1. Zswap: zk-SNARK Based Non-Interactive Multi-Asset Swaps

   Felix Engelmann, Thomas Kerber, Markulf Kohlweiss, and Mikhail Volkhov

   In Proceedings on Privacy Enhancing Technologies, 2022

   Abstract eprint Talk

   Privacy-oriented cryptocurrencies, like Zcash or Monero, provide fair transaction anonymity and confidentiality but lack important features compared to fully public systems, like Ethereum. Specifically, supporting assets of multiple types and providing a mechanism to atomically exchange them, which is critical for e.g. decentralized finance (DeFi), is challenging in the private setting. By combining insights and security properties from Zcash and SwapCT (PETS 21, an atomic swap system for Monero), we present a simple zk-SNARKs-based transaction scheme, called Zswap, which is carefully malleable to allow the merging of transactions, while preserving anonymity. Our protocol enables multiple assets and atomic exchanges by making use of sparse homomorphic commitments with aggregated open randomness, together with Zcash-friendly simulation-extractable non-interactive zero-knowledge (NIZK) proofs. This results in a provably secure privacy-preserving transaction protocol, with efficient swaps, and overall performance close to that of existing deployed private cryptocurrencies. It is similar to Zcash Sapling and benefits from existing code bases and implementation expertise.

2021

1. Snarky Ceremonies

   Markulf Kohlweiss, Mary Maller, Janno Siim, and Mikhail Volkhov

   In Advances in Cryptology – ASIACRYPT, 2021

   Abstract eprint Talk

   Succinct non-interactive arguments of knowledge (SNARKs) have found numerous applications in the blockchain setting and elsewhere. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). Our contributions are two-fold:
   1. We give a security framework for non-interactive zero-knowledge arguments with a ceremony protocol.
   2. We revisit the ceremony protocol of Groth’s SNARK [Bowe et al., 2017]. We show that the original construction can be simplified and optimized, and then prove its security in our new framework. Importantly, our construction avoids the random beacon model used in the original work.

2020

1. Another Look at Extraction and Randomization of Groth’s zk-SNARK

   Karim Baghery, Markulf Kohlweiss, Janno Siim, and Mikhail Volkhov

   In Financial Cryptography and Data Security, 2020

   Abstract eprint Talk

   Due to the simplicity and performance of zk-SNARKs they are widely used in real-world cryptographic protocols, including blockchain and smart contract systems. Simulation Extractability (SE) is a necessary security property for a NIZK argument to achieve Universal Composability (UC), a common requirement for such protocols. Most of the works that investigated SE focus on its strong variant which implies proof non-malleability. In this work we investigate a relaxed weaker notion, that allows proof randomization, while guaranteeing statement non-malleability, which we argue to be a more natural security property. First, we show that it is already achievable by Groth16, arguably the most efficient and widely deployed SNARK nowadays. Second, we show that because of this, Groth16 can be efficiently transformed into a black-box weakly SE NIZK, which is sufficient for UC protocols.
   To support the second claim, we present and compare two practical constructions, both of which strike different performance trade-offs:
   * Int-Groth16 makes use of a known transformation that encrypts the witness inside the SNARK circuit. We instantiate this transformation with an efficient SNARK-friendly encryption scheme.
   * Ext-Groth16 is based on the SAVER encryption scheme (Lee et al.) that plugs the encrypted witness directly into the verification equation, externally to the circuit. We prove that Ext-Groth16 is black-box weakly SE and, contrary to Int-Groth16, that its proofs are fully randomizable.

2019

1. Techniques, Software, and Applications for Packed Partially Homomorphic Encryption

   Mikhail Volkhov

   Master’s thesis at INRIA Paris/MPRI, 2019

   Abstract PDF

   Secure Machine Learning analyses different ML solutions trying to answer the question of how to make these algorithms conform nowadays security and privacy requirements. Most of the solutions fall into the category of either secure training, or secure inference (classification or regression). The active research on fully homomorphic encryption (FHE) that started right after Gentry’s [Gen09] proposal together with the latest improvements in protocol design produced a lot of different secure computation models that allow to easily adapt existing ML methods, like classifiers, to meet the common security goals. One of the popular targets to apply these techniques to are Convolutional Neural Network classifiers, and recently it was shown that it is possible and practical to execute CNN linear layers using modern FHEs [JVC18]. On the other hand, a number of different techniques that make use of simpler classifiers, like SVM, can achieve comparable classification accuracy, using much simpler cryptographic primitives [MRSV19]. Different combinations of multiparty protocols, homomorphic encryption, and classifiers present many open problems related to the performance, accuracy, and security. Verification is another concern — many solutions are implemented only as prototypes and do not take the systematic verified approach that is possible to introduce with software verification techniques.