Рассматриваются принципы построения и основные виды кратких неинтерактивных аргументов с нѵлевым разглашением для выполнимости булевых функций с исполвзованием различных полиномиальных наборов, в том числе и для аутентифицированных данных. Приведены различные алгоритмы формирования публичных параметров, доказательств достоверности вычислений и их верификации. Представлены необходимые криптографические преобразования и некоторые примеры многосторонних верифицируемых вычислений.
Скачать электронную версию публикации
Загружен, раз: 16
- Title Краткие неинтерактивные аргѵменты с нулевым разглашением на основе наборов полиномов
- Headline Краткие неинтерактивные аргѵменты с нулевым разглашением на основе наборов полиномов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 59
- Date:
- DOI 10.17223/20710410/59/2
Ключевые слова
краткие неинтерактивные аргументы, нулевое разглашение, достоверность вычислений, доказательство знанияАвторы
Ссылки
Ben-Sasson E., Chiesa A., Green M., et al. Secure sampling of public parameters for succinct zero knowledge proofs // Proc. IEEE Svmp. Security and Privacy, San Jose, CA, USA, 2015. P. 287-304.
Gennaro R. Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks // LNCS. 2004. V.3152. P.220-236.
Boneh D. and Boyen X. Secure identity based encryption without random oracles // LNCS. 2004. V. 3152. P. 443-459.
Gabizon A. On the Security of the BCTV Pinocchio zk-SNARK Variant. Cryptology ePrint Archive. Report 2019/119. 2019. 9p. https://ia.cr/2019/119.
Armknecht F., Boyd С., Carr С., et al. Guide to Fully Homomorphic Encryption. Cryptology ePrint Archive. 35p. https://eprint.iacr.org/2015/1192.pdf.
Bitansky N., Chiesa A., Ishai Y., et al. Succinct non-interactive arguments via linear interactive proofs // LNCS. 2013. V.7785. P.315-333.
Galbraith S. D., Paterson K. G., and Smart N. P. Pairings for cryptographers // Discr. Appl. Math. 2008. V. 156. Iss. 16. P. 3113-3121.
Groth J. On the size of pairing-based non-interactive arguments // LNCS. 2016. V. 9666. P.305-326.
Gabizon A. On the security of the BCTV Pinocchio zk-SNARK variant. Cryptology ePrint Archive. Paper 2019/119. 2019. 9p. https://eprint.iacr.org/2019/119.
Ben-Sasson E., Chiesa A., Tromer E., and Virza M. Succinct non-interactive zero knowledge for a von Neumann architecture // Proc. 23rd USENIX Security Svmp. San Diego, CA, USA, 2014. P.781-796.
Bowe S., Gabizon A., and Green M. D. A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. Cryptology ePrint Archive. Report 2017/602. 2017. 25p. https://ia.cr/2017/602.
Supercop. http://bench.cr.yp.to/supercop.html.
Bernstein D. J., Duif N., Lange T., et al. High-speed high-securitv signatures //j. Crvptogr. Engineering. 2012. V.2. No.2. P.77-89.
Camenisch J., Kohlweiss M., and Soriente C. An accumulator based on bilinear maps and efficient revocation for anonymous credentials // LNCS. 2009. V.5443. P.481-500.
Gennaro R. and Wichs D. Fully homomorphic message authenticators // LNCS. 2013. V.8270. P.301-320.
Backes M., Fiore D., and Reischuk R. M. Verifiable delegation of computation on outsourced data // Proc. CCS'13. N.Y.: ACM, 2013. P.863-874.
Ben-Sasson E., Chiesa A., Tromer E., and Virza M. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Updated version, 2019. 37 p. https: //eprint. iacr.org/2013/879.pdf.
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. P. 163-178.
Baches M., Barbosa M., Fiore D., and Reischuk R. M. ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data // Proc. IEEE Svmp. SP'15. IEEE Computer Society, USA, 2015. P.271-286.
Costello C., Fournet C., Plowell J., et al. Geppetto: Versatile verifiable computation // Proc. IEEE Svmp. SR 15. IEEE Computer Society, USA, 2015. P.253-270.
Kissner L. and Song D. Privacy-preserving set operations // LNCS. 2005. V. 3621. P. 241-257.
Papamanthou G., Tamassia R., and Triandopoulos N. Optimal verification of operations on dynamic sets. Cryptology ePrint Archive. Paper 2010/455. 2010. 31 p. https://eprint.iacr.org/2010/455.
Beuchat J.-L., Gonzalez-Daz J. E., Mitsunari S., et al. High-speed software implementation of the optimal ate pairing over Barreto - Naehrig curves // LNCS. 2010. V. 6487. P. 21-39.
Granlund T. CMP: The GNU Multiple Precision Arithmetic Library. 2006. http://gmplib.org/.
Shoup V. NTL: Number Theory Library, http://www.shoup.net/ntl/.
Shoup V. A new polynomial factorization algorithm and its implementation //j. Symbolic Computation. 1995. V. 20. No. 4. R 363-397.
Kosba А. Е., Papadopoulos D., Papamanthou С., et al. TRUESET: Nearly practical verifiable set computations. Cryptology ePrint Archive. Report 2014/160. 2014. 30p. http://epri.nt.iacr.org/2014/160.
Ben-Sasson E., Chiesa A., Genkin D., et al. SNARKs for C: Verifying program executions succinctly and in zero knowledge // LNCS. 2013. V. 8043. P. 90-108.
Blum M., Feldman P., and Micali S. Non-interactive zero-knowledge and its applications // Proc. STOCKS. N.Y.: ACM, 1988. P.103-112.
Lipmaa H. Almost Optimal Short Adaptive Non-interactive Zero Knowledge. Tech. Rep. 2014/396. IACR, 2014. 20p. http://eprint.iacr.org/2014/396.
Danezis G., Fournet G., Groth J., and Kohlweiss M. Square span programs with applications to succinct NIZK arguments // LNCS. 2014. V.8873. P.532-550.
Lipmaa H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes // LNCS. 2013. V.8269. P.41-60.
Parno B., Howell J., Gentry C., and Raykova M. Pinocchio: Nearly practical verifiable computation // Proc. 34th IEEE Svmp. Security and Privacy. Oakland, 2013. P. 238-252.
Chase М., Kohlweiss М., Lysyanskaya A., and Meiklejohn S. Malleable proof systems and applications // LNCS. 2012. V. 7237. P. 281-300.
Лось A. Б., Нестеренко А. Ю., Рожков М.И. Криптографические методы защиты информации: учеб, для академического бакалавриата. 2-е изд. М.: Юрайт, 2017. 473 с.
Paillier P. Public-key cryptosystems based on composite degree residuositv classes // LNCS. 1999. V. 1592. P.223-238.
Valiant P. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency // LNCS. 2008. V. 19 IS. P. 1-18.
Boneh D., Segev G., and Waters B. Targeted malleability: homomorphic encryption for restricted computations // Proc. ITCS'12. N.Y.: ACM, 2012. P.350-366.
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 p. http://eprint.iacr.org/2012/095.
Reitwiebner C. zkSNARKs in a Nutshell. 2017. 15 p. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/.
Fauzi P., Lipmaa H., and Zhang В. Efficient modular NIZK arguments from shift and product // LNCS. 2013. V. 8257. P.92-121.
Groth J., Ostrovsky R., and Sahai A. Perfect non-interactive zero knowledge for NP // LNCS. 2006. V.4004. P.339-358.
Parno B., Raykova M., and Vaikuntanathan V. How to delegate and verify in public: Verifiable computation from attribute-based encryption // LNCS. 2012. V.7194. P.422-439.
Pankova A. Succinct Non-interactive Arguments from Quadratic Arithmetic Programs. Technical report. University of Tartu. Cybernetica AS, 2013. 28 p.
Gennaro R., Gentry G., Parno B., and Raykova M. Quadratic span programs and succinct NIZKs without PCPs // LNCS. 2013. V.7881. P.626-645.
Yao A. How to generate and exchange secrets // 27th Ann. Svmp. Foundations of Computer Science. 1986. P. 162-167.
Gennaro R., Gentry C., and Parno B. Non-interactive verifiable computing: Outsourcing computation to untrusted workers // LNCS. 2010. Y. 6223. P.465-482.
Yao A. Protocols for secure computations // 23rd Ann. Svmp. Foundations of Computer Science. 1982. P. 160-164.
Tao T. and Vu V. Additive Combinatorics. Cambridge Studies in Advanced Mathematics. No. 105. Cambridge University Press, 2006. 532 p.
Lipmaa Н. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments // LNCS. 2012. V.7194. P.169-189.
Groth J. Short pairing-based non-interactive zero-knowledge arguments // LNCS. 2010. V.6477. P.321-340.
Bittau A., Erlingsson U., Maniatis P., et al. PROCHLO: Strong privacy for analytics in the crowd // Proc. SOSP'17. N.Y.: ACM, 2017. P.441-459.
Cheu A., Smith A., Ullman J., et al. Distributed differential privacy via shuffling // LNCS. 2019. V. 11476. P.375-403.
Angel S., Chen H., Laine K., and Setty S. PIR with Compressed Queries and Amortized Query Processing. IACR eprint Archive. 2017. 18p. https://eprint.iacr.org/2017/1142.pdf.
Corrigan-Gibbs H. and Boneh D. Prio: Private, robust, and scalable computation of aggregate statistics // Proc. NSDI'17. USENIX Ass., 2017. P.259-282.
Bonawitz K., Ivanov V., Kreuter B., et al. Practical secure aggregation for federated learning on user-held data // Proc. NIPS'2016. N.Y.: ACM, 2016. P.1175-1191.
Ion M., Kreuter B., Nergiz E., et al. Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions. IACR eprint Archive. 2017. 14 p. https: //eprint. iacr.org/2017/738.
Rindal P. and Rosulek M. Malicious-secure private set intersection via dual execution // Proc. CCS'2017. N.Y.: ACM, 2017. P. 1229-1242.
Bitansky N., Canetti R., Chiesa A., et al. The hunting of the SNARK //j. Cryptology. 2016. No. 30. P.989-1066.
Kolesnikov V., Kumaresan R., Rosulek M., and Trieu N. Efficient batched oblivious PRF with applications to private set intersection // Proc. CCS'2016. N.Y.: ACM, 2016. P.818-829.
Danezis G., Fournet G., Kohlweiss M., and Parno B. Pinocchio coin: building zerocoin from a succinct pairing-based proof system j j Proc. PETShop'13. N.Y.: ACM, 2013. P.27-30.
Pertsev A., Semenov R., and Storm R. Tornado Cash Privacy Solution. Version 1.4. 2019. 3 p. https://tornado.cash/Tornado.cash_whitepaper_vl.4.pdf.
Doreian B. W. and Erickson R. R. PIVX: Protected Instant Verified Transaction. 25 p. https: //pivx.org/files/whitepapers/PIVX_Non_Technical_Whitepaper_v2.0.pdf.
Diamond В. ZSL Proof of Concept. https://github.eom/ConsenSys/quorum/wiki/ZSL# protocol.
Quorum - ZSL Integration: Proof of Concept. Technical Design Document. 23p. https: //github.com/ConsenSys/zsl-q/blob/master/docs/ZSL-Quorum-POC_TDD_vl.3pub.pdf.
Welcome to zkSvnc. https://zksync.io/faq.
Konda C., Connor M., Westland D., et al. Nightfall, https://raw.githubusercontent.com/EYBlockchain/nightfall/master/doc/whitepaper/nightfall-vl.pdf. 2019.
Lipmaa H. Two Simple Code-Verification Voting Protocols. Cryptology ePrint Archive. Report 2011/317. 2011. https://eprint.iacr.org/2011/317.
Katz J., Myers S., and Ostrovsky R. Cryptographic counters and applications to electronic voting // LNCS. 2001. V.2045. P.78-92.
Belenkiy M., Chase M., Kohlweiss M., and Lysyanskaya A. P-signatures and noninteractive anonymous credentials // LNCS. 2008. V.4948. P.356-374.
Belenkiy M., Camenisch J., Chase M., et al. Randomizable proofs and delegatable anonymous credentials // LNCS. 2009. V. 5677. P. 108-125.
Chase M., Kohlweiss M., Lysyanskaya A., and Meiklejohn S Malleable proof systems and applications // LNCS. 2012. V.7237. P. 281-300.
Воуеп X. and Waters В.Compact group signatures without random oracles // LNCS. 2006. V. 4004. P. 427-444.
Wang X., Ranellucci S., and Katz J. Global-scale Secure Multiparty Computation. IACR eprint Archive. 2017. 35p. https://eprint.iacr.org/2017/189.pdf.
Ben-Or M., Goldwasser S., and Wigderson A.Completeness theorems for non-crvptographic fault-tolerant distributed computation // Proc. STOC'88. N.Y.: ACM, 1988. P. 1-10.
Gueron S., Lindell Y., Nof A., and Pinkas B. Fast garbling of circuits under standard assumptions // Proc. CCS'16. N.Y.: ACM, 2015. P.567-578.
Petkus M. Why and How zk-SNARK Works. ArXiv, abs/1906.07221. 2019. 65p. https://arxiv.org/pdf/1906.07221.pdf.
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. N.Y.: ACM, 1987. P.218-229.
Запечпиков С. В. Криптографическая защита процессов обработки информации в недоверенной среде: достижения, проблемы, перспективы // Вестник современных цифровых технологий. 2019. №1. С. 4-16.
Черемушкин А. В. Криптографические протоколы. Основные свойства и уязвимости. М.: Изд. центр "Академия", 2009. 272 с.
Hopwood D., Bowe S., Hornby Т., and Wilcox N. Zcash Protocol Specification. Version 2021.2.16 [NU5 proposal], 2021. 213p. https://raw.githubusercontent.com/Zcash/zips/master/protocol/protocol.pdf.
Краткие неинтерактивные аргѵменты с нулевым разглашением на основе наборов полиномов | Прикладная дискретная математика. 2023. № 59. DOI: 10.17223/20710410/59/2
Скачать полнотекстовую версию
Загружен, раз: 533