Voir la notice de l'article provenant de la source Math-Net.Ru
@article{PDM_2023_1_a1,
author = {I. V. Martynenkov},
title = {Zero-knowledge succinct non-interactive arguments of~knowledge based on sets of polynomials},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {20--57},
publisher = {mathdoc},
number = {1},
year = {2023},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2023_1_a1/}
}
I. V. Martynenkov. Zero-knowledge succinct non-interactive arguments of~knowledge based on sets of polynomials. Prikladnaâ diskretnaâ matematika, no. 1 (2023), pp. 20-57. http://geodesic.mathdoc.fr/item/PDM_2023_1_a1/
[1] Hopwood D., Bowe S., Hornby T., and Wilcox N., Zcash Protocol Specification, Version 2021.2.16 [NU5 proposal], 2021, 213 pp. https://raw.githubusercontent.com/Zcash/zips/master/protocol/protocol.pdf
[2] Cheremushkin A. V., Cryptographic Protocols. Basic Properties and Vulnerabilities, Akademiya Publ., M., 2009, 272 pp. (in Russian)
[3] Zapechnikov S. V., “Cryptographic protection of information processing processes in an untrusted environment: achievements, problems, prospects”, Vestnik Sovremennykh Tsifrovykh Tekhnologiy, 2019, no. 1, 4–16 (in Russian)
[4] Petkus M., Why and How zk-SNARK Works, 2019, 65 pp., arXiv: 1906.07221
[5] Goldreich O., Micali S., and Wigderson A., “How to play any mental game or a completeness theorem for protocols with honest majority”, Proc. STOC'87, ACM, N.Y., 1987, 218–229
[6] Ben-Or M., Goldwasser S., and Wigderson A., “Completeness theorems for non-cryptographic fault-tolerant distributed computation”, Proc. STOC'88, ACM, N.Y., 1988, 1–10
[7] Gueron S., Lindell Y., Nof A., and Pinkas B., “Fast garbling of circuits under standard assumptions”, Proc. CCS'15, ACM, N.Y., 2015, 567–578
[8] Wang X., Ranellucci S., and Katz J., Global-scale Secure Multiparty Computation, IACR Archive, , 2017, 35 pp. https://eprint.iacr.org/2017/189.pdf
[9] Boyen X. and Waters B., “Compact group signatures without random oracles”, LNCS, 4004, 2006, 427–444 | MR
[10] Chase M., Kohlweiss M., Lysyanskaya A., and Meiklejohn S., “Malleable proof systems and applications”, LNCS, 7237, 2012, 281–300 | MR
[11] Belenkiy M., Chase M., Kohlweiss M., and Lysyanskaya A., “P-signatures and noninteractive anonymous credentials”, LNCS, 4948, 2008, 356–374 | MR
[12] Belenkiy M., Camenisch J., Chase M., et al., “Randomizable proofs and delegatable anonymous credentials”, LNCS, 5677, 2009, 108–125 | MR
[13] Katz J., Myers S., and Ostrovsky R., “Cryptographic counters and applications to electronic voting”, LNCS, 2045, 2001, 78–92 | MR
[14] Lipmaa H., Two Simple Code-Verification Voting Protocols, Cryptology Archive, Report 2011/317, , 2011 https://eprint.iacr.org/2011/317
[15] Konda C., Connor M., Westland D., et al., Nightfall, , 2019 https://raw.githubusercontent.com/EYBlockchain/nightfall/master/doc/whitepaper/nightfall-v1.pdf
[16] Diamond B., ZSL Proof of Concept, https://github.com/ConsenSys/quorum/wiki/ZSL#protocol
[17] Quorum — ZSL Integration: Proof of Concept, Technical Design Document, 23 pp. https://github.com/ConsenSys/zsl-q/blob/master/docs/ZSL-Quorum-POC_TDD_v1.3pub.pdf
[18] Welcome to zkSync, https://zksync.io/faq/
[19] Doreian B. W. and Erickson R. R., PIVX: Protected Instant Verified Transaction, , 25 pp. https://pivx.org/files/whitepapers/PIVX_Non_Technical_Whitepaper_v2.0.pdf
[20] Pertsev A., Semenov R., and Storm R., Tornado Cash Privacy Solution, Version 1.4, 2019, 3 pp. https://tornado.cash/Tornado.cash_whitepaper_v1.4.pdf
[21] Danezis G., Fournet C., Kohlweiss M., and Parno B., “Pinocchio coin: building zerocoin from a succinct pairing-based proof system”, Proc. PETShop'13, ACM, N.Y., 2013, 27–30
[22] Bitansky N., Canetti R., Chiesa A., et al., “The hunting of the SNARK”, J. Cryptology, 2016, no. 30, 989–1066 | MR
[23] Kolesnikov V., Kumaresan R., Rosulek M., and Trieu N., “Efficient batched oblivious PRF with applications to private set intersection”, Proc. CCS'2016, ACM, N.Y., 2016, 818–829
[24] Rindal P. and Rosulek M., “Malicious-secure private set intersection via dual execution”, Proc. CCS'2017, ACM, N.Y., 2017, 1229–1242
[25] Ion M., Kreuter B., Nergiz E., et al., Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions, IACR Archive, , 2017, 14 pp. https://eprint.iacr.org/2017/738
[26] Bonawitz K., Ivanov V., Kreuter B., et al., “Practical secure aggregation for federated learning on user-held data”, Proc. NIPS'2016, ACM, N.Y., 2016, 1175–1191
[27] Corrigan-Gibbs H. and Boneh D., “Prio: Private, robust, and scalable computation of aggregate statistics”, Proc. NSDI'17, USENIX Ass., 2017, 259–282
[28] Angel S., Chen H., Laine K., and Setty S., PIR with Compressed Queries and Amortized Query Processing, IACR Archive, , 2017, 18 pp. https://eprint.iacr.org/2017/1142.pdf
[29] Cheu A., Smith A., Ullman J., et al., “Distributed differential privacy via shuffling”, LNCS, 11476, 2019, 375–403 | MR
[30] Bittau A., Erlingsson Ú., Maniatis P., et al., “PROCHLO: Strong privacy for analytics in the crowd”, Proc. SOSP'17, ACM, N.Y., 2017, 441–459
[31] Groth J., “Short pairing-based non-interactive zero-knowledge arguments”, LNCS, 6477, 2010, 321–340
[32] Lipmaa H., “Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments”, LNCS, 7194, 2012, 169–189 | MR
[33] Tao T. and Vu V., Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105, Cambridge University Press, 2006, 532 pp. | MR
[34] Gennaro R., Gentry C., and Parno B., “Non-interactive verifiable computing: Outsourcing computation to untrusted workers”, LNCS, 6223, 2010, 465–482 | MR
[35] Yao A., “Protocols for secure computations”, 23rd Ann. Symp. Foundations of Computer Science, 1982, 160–164 | DOI | MR
[36] Yao A., “How to generate and exchange secrets”, 27th Ann. Symp. Foundations of Computer Science, 1986, 162–167
[37] Gennaro R., Gentry C., Parno B., and Raykova M., “Quadratic span programs and succinct NIZKs without PCPs”, LNCS, 7881, 2013, 626–645 | MR
[38] Pankova A., Succinct Non-Interactive Arguments from Quadratic Arithmetic Programs, Technical report, University of Tartu. Cybernetica AS, 2013, 28 pp. | MR
[39] Parno B., Raykova M., and Vaikuntanathan V., “How to delegate and verify in public: Verifiable computation from attribute-based encryption”, LNCS, 7194, 2012, 422–439
[40] Groth J., Ostrovsky R., and Sahai A., “Perfect non-interactive zero knowledge for NP”, LNCS, 4004, 2006, 339–358 | MR
[41] Fauzi P., Lipmaa H., and Zhang B., “Efficient modular NIZK arguments from shift and product”, LNCS, 8257, 2013, 92–121 | MR
[42] Reitwiebner C., zkSNARKs in a Nutshell, , 2017, 15 pp. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
[43] Bitansky N., Canetti R., Chiesa A., and Tromer E., Recursive Composition and Bootstrapping for Snarks and Proof-Carrying data, IACR Cryptology ePrint Archive, , 2012, 61 pp. http://eprint.iacr.org/2012/095 | MR
[44] Boneh D., Segev G., and Waters B., “Targeted malleability: homomorphic encryption for restricted computations”, Proc. ITCS'12, ACM, N.Y., 2012, 350–366 | MR
[45] Valiant P., “Incrementally verifiable computation or proofs of knowledge imply time/space efficiency”, LNCS, 4948, 2008, 1–18 | MR
[46] Paillier P., “Public-key cryptosystems based on composite degree residuosity classes”, LNCS, 1592, 1999, 223–238 | MR
[47] Los' A. B., Nesterenko A. Yu., and Rozhkov M. I., Cryptographic Methods of Information Protection, Textbook for Academic Undergraduate, Yurayt Publ., M., 2017, 473 pp. (in Russian)
[48] Chase M., Kohlweiss M., Lysyanskaya A., and Meiklejohn S., “Malleable proof systems and applications”, LNCS, 7237, 2012, 281–300 | MR
[49] Parno B., Howell J., Gentry C., and Raykova M., “Pinocchio: Nearly practical verifiable computation”, Proc. 34th IEEE Symp. Security and Privacy (Oakland, 2013), 238–252
[50] Lipmaa H., “Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes”, LNCS, 8269, 2013, 41–60
[51] Danezis G., Fournet C., Groth J., and Kohlweiss M., “Square span programs with applications to succinct NIZK arguments”, LNCS, 8873, 2014, 532–550 | MR
[52] Lipmaa H., Almost Optimal Short Adaptive Non-Interactive Zero Knowledge, Tech. Rep. 2014/396, , IACR, 2014, 20 pp. http://eprint.iacr.org/2014/396
[53] Blum M., Feldman P., and Micali S., “Non-interactive zero-knowledge and its applications”, Proc. STOC'88, ACM, N.Y., 1988, 103–112
[54] Ben-Sasson E., Chiesa A., Genkin D., et al., “SNARKs for C: Verifying program executions succinctly and in zero knowledge”, LNCS, 8043, 2013, 90–108 | MR
[55] Kosba A. E., Papadopoulos D., Papamanthou C., et al., TRUESET: Nearly practical verifiable set computations, Cryptology Archive. Report 2014/160, , 2014, 30 pp. http://eprint.iacr.org/2014/160
[56] Shoup V., “A new polynomial factorization algorithm and its implementation”, J. Symbolic Computation, 20:4 (1995), 363–397 | DOI | MR
[57] Shoup V., NTL: Number Theory Library, http://www.shoup.net/ntl/
[58] Granlund T., GMP: The GNU Multiple Precision Arithmetic Library, , 2006 http://gmplib.org/
[59] Beuchat J.-L., González-Dáz J. E., Mitsunari S., et al., “High-speed software implementation of the optimal ate pairing over Barreto — Naehrig curves”, LNCS, 6487, 2010, 21–39 | MR
[60] Kissner L. and Song D., “Privacy-preserving set operations”, LNCS, 3621, 2005, 241–257 | MR
[61] Papamanthou C., Tamassia R., and Triandopoulos N., Optimal verification of operations on dynamic sets, Cryptology Archive. Paper 2010/455, , 2010, 31 pp. https://eprint.iacr.org/2010/455 | MR
[62] Costello C., Fournet C., Howell J., et al., “Geppetto: Versatile verifiable computation”, Proc. IEEE Symp. SP'15, IEEE Computer Society, USA, 2015, 253–270
[63] Backes M., Barbosa M., Fiore D., and Reischuk R. M., “ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data”, Proc. IEEE Symp. SP'15, IEEE Computer Society, USA, 2015, 271–286
[64] Fournet C., Kohlweiss M., Danezis G., and Luo Z., “ZQL: A compiler for privacy-preserving data processing”, Proc. 22nd USENIX Conf. SEC'13, USENIX Ass., 2013, 163–178
[65] Ben-Sasson E., Chiesa A., Tromer E., and Virza M., Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture, Updated version, , 2019, 37 pp. https://eprint.iacr.org/2013/879.pdf
[66] Backes M., Fiore D., and Reischuk R. M., “Verifiable delegation of computation on outsourced data”, Proc. CCS'13, ACM, N.Y., 2013, 863–874
[67] Gennaro R. and Wichs D., “Fully homomorphic message authenticators”, LNCS, 8270, 2013, 301–320 | MR
[68] Camenisch J., Kohlweiss M., and Soriente C., “An accumulator based on bilinear maps and efficient revocation for anonymous credentials”, LNCS, 5443, 2009, 481–500 | MR
[69] Bernstein D. J., Duif N., Lange T., et al., “High-speed high-security signatures”, J. Cryptogr. Engineering, 2:2 (2012), 77–89 | DOI
[70] Supercop http://bench.cr.yp.to/supercop.html
[71] Bowe S., Gabizon A., and Green M. D., A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK, Cryptology Archive, Report 2017/602, , 2017, 25 pp. https://ia.cr/2017/602
[72] Ben-Sasson E., Chiesa A., Tromer E., and Virza M., “Succinct non-interactive zero knowledge for a von Neumann architecture”, Proc. 23rd USENIX Security Symp. (San Diego, CA, USA, 2014), 781–796
[73] Gabizon A., On the security of the BCTV Pinocchio zk-SNARK variant, Cryptology Archive, Paper 2019/119, , 2019, 9 pp. https://eprint.iacr.org/2019/119
[74] Groth J., “On the size of pairing-based non-interactive arguments”, LNCS, 9666, 2016, 305–326 | MR
[75] Galbraith S. D., Paterson K. G., and Smart N. P., “Pairings for cryptographers”, Discr. Appl. Math., 156:16 (2008), 3113–3121 | DOI | MR
[76] Bitansky N., Chiesa A., Ishai Y., et al., “Succinct non-interactive arguments via linear interactive proofs”, LNCS, 7785, 2013, 315–333
[77] Armknecht F., Boyd C., Carr C., et al., Guide to Fully Homomorphic Encryption, Cryptology Archive, , 35 pp. https://eprint.iacr.org/2015/1192.pdf
[78] Gabizon A., On the Security of the BCTV Pinocchio zk-SNARK Variant, Cryptology Archive, Report 2019/119, , 2019, 9 pp. https://ia.cr/2019/119
[79] Boneh D. and Boyen X., “Secure identity based encryption without random oracles”, LNCS, 3152, 2004, 443–459 | MR
[80] Gennaro R., “Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks”, LNCS, 3152, 2004, 220–236 | MR
[81] Ben-Sasson E., Chiesa A., Green M., et al., “Secure sampling of public parameters for succinct zero knowledge proofs”, Proc. IEEE Symp. Security and Privacy (San Jose, CA, USA, 2015), 287–304