Note : Following the convention in Theoretical Computer Science, the list of authors in the publications below is sorted alphabetically.
Publications
Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs
Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Nitin Singh
ASIACRYPT 2024 | [ePrint]
Summary: While the notion of secure multiparty computation (MPC) allows multiple participants to compute a function over their private inputs in a way that preserves the privacy of the inputs and ensures the correctness of the output, it does not prevent the participants from influencing the protocol by choosing incorrect inputs (input poisoning). We designed a compiler which transforms any linear secret-sharing based honest-majority MPC protocol to include input authentication with negligible overhead. For certain corruption thresholds, our compiler additionally preserves the stronger identifiable abort security of the underlying MPC protocol.
In order to achieve this, we propose a new notion of distributed proofs of knowledge - where prover distributes the proof generation to a set of workers by secret-sharing its witness - and show its concrete instantiations for discrete-log relation and popular digital signatures like BBS+ and PS. Additionally, we define a new notion of robust completeness, which preserves security even in the presence of dishonest usage of shares by some of the workers.
Batching-Efficient RAM using Updatable Lookup Arguments
Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Shubh Prakash, Nitin Singh
Summary: RAM (random access memory) is an important primitive in verifiable computation. In this work, we achieve RAM with efficient batching property, i.e, proving a batch of m updates on a RAM of size N while incurring a cost that is sub-linear in N, where m is significantly smaller than N. Our techniques offers significant improvement over existing works on batching-efficient accumulators/RAMs, with a substantially reduced resource barrier. In order to achieve this, we improve upon the state-of-the-art proofs for sub-vector relation - known as lookup arguments - by enabling them to be efficient in presence of updates to the table.
Succinct Verification of Compressed Sigma Protocols in the Updatable SRS setting
Moumita Dutta, Chaya Ganesh, Neha Jawalkar
PKC 2024 | [ePrint]
Summary: Sigma protocols are well-understood primitive in the literature of zero-knowledge proofs which has attractive real-world applications (eg. in blockchain) and have linear proof size and verification complexity. The work of Attema and Cramer provides compressed sigma protocols with logarithmic proof size, but still incur linear verification. To achieve efficient verification, we construct a compressed sigma protocol that has both logarithmic proof size and logarithmic verification complexity. This is achieved by moving from transparent setup to updatable setup, which only requires one honest update during the setup phase to guarantee security against malicious prover strategies.