@inproceedings {27574,
title = {Somewhere Statistically Binding Commitment Schemes with Applications},
journal = {FC 2021: Financial Cryptography and Data Security},
year = {2021},
abstract = {We define a new primitive that we call a somewhere statistically binding (SSB) commitment scheme, which is a generalization of dual-mode commitments but has similarities with SSB hash functions (Hubacek and Wichs, ITCS 2015) without local opening. In (existing) SSB hash functions, one can compute a hash of a vector v that is statistically binding in one coordinate of v. Meanwhile, in SSB commitment schemes, a commitment of a vector v is statistically binding in some coordinates of v and is statistically hiding in the other coordinates. The set of indices where binding holds is predetermined but known only to the commitment key generator. We show that the primitive can be instantiated by generalizing the succinct Extended Multi-Pedersen commitment scheme (Gonz{\'a}lez et al., Asiacrypt 2015). We further introduce the notion of functional SSB commitment schemes and, importantly, use it to get an efficient quasi-adaptive NIZK for arithmetic circuits and efficient oblivious database queries.},
keywords = {Commitment scheme, oblivious transfer, QA-NIZK, SSB},
author = {Fauzi, Prastudy and Lipmaa, Helger and Pindado, Zaira and Siim, Janno}
}
@inproceedings {27144,
title = {A Non-Interactive Shuffle Argument With Low Trust Assumptions},
journal = {Cryptographers{\textquoteright} Track at the RSA Conference (CT-RSA 2020)},
year = {2020},
month = {02/2020},
pages = {667-692},
publisher = {Springer, Cham},
abstract = {A shuffle argument is a cryptographic primitive for proving correct behaviour of mix-networks without leaking any private information. Several recent constructions of non-interactive shuffle arguments avoid the random oracle model but require the public key to be trusted.We augment the most efficient argument by Fauzi et al. [Asiacrypt 2017] with a distributed key generation protocol that assures soundness of the argument if at least one party in the protocol is honest and additionally provide a key verification algorithm which guarantees zero-knowledge even if all the parties are malicious. Furthermore, we simplify their construction and improve security by using weaker assumptions while retaining roughly the same level of efficiency. We also provide an implementation to the distributed key generation protocol and the shuffle argument.},
keywords = {Non-interactive zero-knowledge, Secure multi-party computation, Shuffle, Subversion security},
doi = {https://doi.org/10.1007/978-3-030-40186-3_28},
url = {https://eprint.iacr.org/2019/1420},
author = {Aggelakis, Antonis and Fauzi, Prastudy and Korfiatis, Georgios and Louridas, Panos and Mergoupis-Anagnou, Foteinos and Siim, Janno and Zaj{\k a}c, Micha{\l}},
editor = {Jarecki, Stanislaw}
}
@inproceedings {27143,
title = {Quisquis: A New Design for Anonymous Cryptocurrencies},
journal = {Advances in Cryptology {\textendash} ASIACRYPT 2019},
volume = {11921},
year = {2019},
pages = {649 - 678},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {Despite their usage of pseudonyms rather than persistent identifiers, most existing cryptocurrencies do not provide users with any meaningful levels of privacy. This has prompted the creation of privacy-enhanced cryptocurrencies such as Monero and Zcash, which are specifically designed to counteract the tracking analysis possible in currencies like Bitcoin. These cryptocurrencies, however, also suffer from some drawbacks: in both Monero and Zcash, the set of potential unspent coins is always growing, which means users cannot store a concise representation of the blockchain. Additionally, Zcash requires a common reference string and the fact that addresses are reused multiple times in Monero has led to attacks to its anonymity.In this paper we propose a new design for anonymous cryptocurrencies, Quisquis, that achieves provably secure notions of anonymity. Quisquis stores a relatively small amount of data, does not require trusted setup, and in Quisquis each address appears on the blockchain at most twice: once when it is generated as output of a transaction, and once when it is spent as input to a transaction. Our result is achieved by combining a DDH-based tool (that we call updatable keys) with efficient zero-knowledge arguments.},
keywords = {cryptocurrencies, cryptographic protocols / anonymity, Zero knowledge},
isbn = {978-3-030-34577-8},
issn = {0302-9743},
doi = {10.1007/978-3-030-34578-5_23},
url = {https://link.springer.com/chapter/10.1007\%2F978-3-030-34578-5_23},
author = {Fauzi, Prastudy and Meiklejohn, Sarah and Mercer, Rebekah and Orlandi, Claudio},
editor = {Steven D. {Galbraith} and Moriai, Shiho}
}
@inproceedings {26618,
title = {An Efficient Pairing-Based Shuffle Argument},
journal = {International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2017)},
volume = {1062524311562359528427},
year = {2017},
pages = {97 - 127},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument:1. A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee,\ 2. A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zaj{\k a}c,\ 3. A (simplified) consistency argument of Groth and Lu.We prove the knowledge-soundness of the first two subarguments in the generic bilinear group model, and the culpable soundness of the third subargument under a KerMDH assumption. This proves the soundness of the shuffle argument. We also discuss our partially optimized implementation that allows one to prove a shuffle of\ 100000100000\ ciphertexts in less than a minute and verify it in less than 1.5\ min.},
keywords = {Common Reference String, Generic group model, Mix-net, Shuffle argument, Zero knowledge},
isbn = {978-3-319-70696-2},
issn = {0302-9743},
doi = {10.1007/978-3-319-70697-910.1007/978-3-319-70697-9_4},
url = {http://link.springer.com/10.1007/978-3-319-70697-9_4},
author = {Fauzi, Prastudy and Lipmaa, Helger and Zaj{\k a}c, Micha{\l} and Siim, Janno},
editor = {Takagi, Tsuyoshi and Peyrin, Thomas}
}
@inproceedings {26620,
title = {Efficient Culpably Sound NIZK Shuffle Argument Without Random Oracles},
journal = {Cryptographers{\textquoteright} Track at the RSA Conference (CT-RSA 2016)},
volume = {96103188{\textendash}A235921},
year = {2016},
month = {03/2016},
pages = {200 - 216},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {One way to guarantee security against malicious voting servers is to use NIZK shuffle arguments. Up to now, only two NIZK shuffle arguments in the CRS model have been proposed. Both arguments are relatively inefficient compared to known random oracle based arguments. We propose a new, more efficient, shuffle argument in the CRS model. Importantly, its online prover{\textquoteright}s computational complexity is dominated by only two\ (n+1)-wide multi-exponentiations, where\ n\ is the number of ciphertexts. Compared to the previously fastest argument by Lipmaa and Zhang, it satisfies a stronger notion of soundness.\ },
keywords = {Bilinear pairings, CRS model, Mix-net, Non-interactive zero knowledge, Shuffle argument},
isbn = {978-3-319-29484-1},
issn = {0302-9743},
doi = {10.1007/978-3-319-29485-810.1007/978-3-319-29485-8_12},
url = {http://link.springer.com/10.1007/978-3-319-29485-8_12},
author = {Fauzi, Prastudy and Lipmaa, Helger},
editor = {Sako, Kazue}
}
@inproceedings {26617,
title = {A Shuffle Argument Secure in the Generic Model},
journal = {International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)},
volume = {1003223592127},
year = {2016},
month = {12/2016},
pages = {841 - 872},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
abstract = {We propose a new random oracle-less NIZK shuffle argument. It has a simple structure, where the first verification equation ascertains that the prover has committed to a permutation matrix, the second verification equation ascertains that the same permutation was used to permute the ciphertexts, and the third verification equation ascertains that input ciphertexts were {\textquotedblleft}correctly{\textquotedblright} formed. The new argument has 3.5 times more efficient verification than the up-to-now most efficient shuffle argument by Fauzi and Lipmaa (CT-RSA 2016). Compared to the Fauzi-Lipmaa shuffle argument, we (i) remove the use of knowledge assumptions and prove our scheme is sound in the generic bilinear group model, and (ii) prove standard soundness, instead of culpable soundness.},
isbn = {978-3-662-53889-0},
issn = {0302-9743},
doi = {10.1007/978-3-662-53890-610.1007/978-3-662-53890-6_28},
url = {http://link.springer.com/10.1007/978-3-662-53890-6_28},
author = {Fauzi, Prastudy and Lipmaa, Helger and Zaj{\k a}c, Micha{\l}},
editor = {Jung Hee {Cheon} and Takagi, Tsuyoshi}
}
@inproceedings {26619,
title = {Efficient Non-Interactive Zero Knowledge Arguments for Set Operations},
journal = {FC 2014: Financial Cryptography and Data Security},
volume = {8437261970},
year = {2014},
pages = {216 - 233},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
abstract = {We propose a non-interactive zero knowledge\ pairwise multiset sum equality test (PMSET)argument of knowledge in the common reference string (CRS) model that allows a prover to show that the given committed multisets\ Aj for\ j∈{1,2,3,4} satisfy\ A1⊎A2=A3⊎A4, i.e., every element is contained in\ A1 and\ A2 exactly as many times as in\ A3 and\ A4. As a corollary to the\ PMSET argument, we present arguments that enable to efficiently verify the correctness of various (multi)set operations, for example, that one committed set is the intersection or union of two other committed sets. The new arguments have constant communication and verification complexity (in group elements and group operations, respectively), whereas the CRS length and the prover{\textquoteright}s computational complexity are both proportional to the cardinality of the (multi)sets. We show that one can shorten the CRS length at the cost of a small increase of the communication and the verifier{\textquoteright}s computation.},
isbn = {978-3-662-45471-8},
issn = {0302-9743},
doi = {10.1007/978-3-662-45472-510.1007/978-3-662-45472-5_14},
url = {https://link.springer.com/chapter/10.1007/978-3-662-45472-5_14},
author = {Fauzi, Prastudy and Lipmaa, Helger and Zhang, Bingsheng},
editor = {Christin, Nicolas and Safavi-Naini, Reihaneh}
}
@inproceedings {26616,
title = {Efficient Modular NIZK Arguments from Shift and Product},
journal = {Cryptology and Network Security (CANS 2013)},
volume = {8257371918411522619174},
year = {2013},
pages = {92 - 121},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {We propose a non-interactive product argument, that is more efficient than the one by Groth and Lipmaa, and a novel shift argument. We then use them to design several novel non-interactive zero-knowledge (NIZK) arguments. We obtain the first range proof with constant communication and subquadratic prover{\textquoteright}s computation. We construct NIZK arguments for\ NP-complete languages,\ Set-Partition,\ Subset-Sum\ and\ Decision-Knapsack, with constant communication, subquadratic prover{\textquoteright}s computation and linear verifier{\textquoteright}s computation.},
isbn = {978-3-319-02936-8},
issn = {0302-9743},
doi = {10.1007/978-3-319-02937-510.1007/978-3-319-02937-5_6},
url = {https://link.springer.com/chapter/10.1007/978-3-319-02937-5_6},
author = {Fauzi, Prastudy and Lipmaa, Helger and Zhang, Bingsheng},
editor = {Hutchison, David and Kanade, Takeo and Kittler, Josef and Jon M. {Kleinberg} and Mattern, Friedemann and John C. {Mitchell} and Naor, Moni and Nierstrasz, Oscar and Rangan, Pandu and Steffen, Bernhard and Sudan, Madhu and Terzopoulos, Demetri and Tygar, Doug and Moshe Y. {Vardi} and Weikum, Gerhard and Abdalla, Michel and Nita-Rotaru, Cristina and Dahab, Ricardo}
}