Efficient Set Membership Proofs using MPC-in-the-Head

Aarushi Goel, Matthew Green, Mathias Nørup Hall-Andersen, Gabriel Kaptchuk

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskning

25 Downloads (Pure)

Abstract

Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. R(w, x) = 1 and is a member of a public set {x1, ..., xl}. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies.

In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC'07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS'18]. We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.
OriginalsprogEngelsk
TidsskriftProceedings on Privacy Enhancing Technologies
Vol/bind2022
Nummer2
Sider (fra-til)304-324
Antal sider20
DOI
StatusUdgivet - 2022
Begivenhed22nd Privacy Enhancing Technologies Symposium (PETS 2022) - Sydney, Australien
Varighed: 11 jul. 202215 jul. 2022

Konference

Konference22nd Privacy Enhancing Technologies Symposium (PETS 2022)
Land/OmrådeAustralien
BySydney
Periode11/07/202215/07/2022

Fingeraftryk

Dyk ned i forskningsemnerne om 'Efficient Set Membership Proofs using MPC-in-the-Head'. Sammen danner de et unikt fingeraftryk.

Citationsformater