請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66851完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳君明(Jiun-Ming Chen) | |
| dc.contributor.author | Er-Cheng Tang | en |
| dc.contributor.author | 唐爾晨 | zh_TW |
| dc.date.accessioned | 2021-06-17T01:09:33Z | - |
| dc.date.available | 2020-02-04 | |
| dc.date.copyright | 2020-02-04 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-01-17 | |
| dc.identifier.citation | [1] E. BenSasson, I. Bentov, Y. Horesh, and M. Riabzev. Fast reedsolomon interactive oracle proofs of proximity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss DagstuhlLeibnizZentrumfuer Informatik, 2018.
[2] E. BenSasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward. Aurora: Transparent succinct arguments for r1cs. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 103–128. Springer, 2019. [3] E. BenSasson, A. Chiesa, and N. Spooner. Interactive oracle proofs. In Theory of Cryptography Conference, pages 31–60. Springer, 2016. [4] F. Benhamouda, J. Camenisch, S. Krenn, V. Lyubashevsky, and G. Neven. Better zeroknowledge proofs for lattice encryption and their application to group signatures. In International Conference on the Theory and Application of Cryptology and Information Security, pages 551–572. Springer, 2014. [5] D. Boneh, B. Bünz, and B. Fisch. Batching techniques for accumulators with applications to iops and stateless blockchains. In Annual International Cryptology Conference, pages 561–586. Springer, 2019. [6] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Efficient zeroknowledge arguments for arithmetic circuits in the discrete log setting. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 327–357. Springer, 2016. [7] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy (SP), pages 315–334. IEEE, 2018. [8] B. Bünz, B. Fisch, and A. Szepieniec. Transparent snarks from dark compilers. Technical report, Cryptology ePrint Archive, Report 2019/1229, 2019, https://eprint.iacr.org, 2019. [9] R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct nizks without pcps. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 626–645. Springer, 2013. [10] I. Giacomelli, J. Madsen, and C. Orlandi. Zkboo: Faster zeroknowledge for boolean circuits. In 25th {USENIX} Security Symposium ({USENIX} Security 16), pages 1069–1083, 2016. [11] J. Groth. Short pairingbased noninteractive zeroknowledge arguments. In International Conference on the Theory and Application of Cryptology and Information Security, pages 321–340. Springer, 2010. [12] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Zeroknowledge from secure multiparty computation. In Proceedings of the thirtyninth annual ACM symposiumon Theory of computing, pages 21–30. ACM, 2007. [13] A. Kate, G. M. Zaverucha, and I. Goldberg. Constantsize commitments to polynomials and their applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 177–194. Springer, 2010. [14] J. Katz, V. Kolesnikov, and X. Wang. Improved noninteractive zero knowledge with applications to postquantum signatures. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 525–537. ACM, 2018. [15] R. W. Lai and G. Malavolta. Subvector commitments with application to succinct arguments. In Annual International Cryptology Conference, pages 530–560. Springer, 2019. [16] V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In International Colloquium on Automata, Languages, and Programming, pages 144–155. Springer, 2006. [17] B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238–252. IEEE, 2013. [18] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 459–474. IEEE, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66851 | - |
| dc.description.abstract | 近年來，針對NP完備問題的零知識證明 (zero knowledge argument of knowledge) 有了更實際的構造，並在現實應用中發揮作用。然而，這樣的零知識證明大多需要由公正第三方來進行初始化，因此不適合在區塊鏈 (blockchain) 等去中心化的場域中使用。本篇論文鎖定於透明的證明 (transparent argument)，即初始過程不包含祕密資訊的證明。這有賴於使用透明的承諾系統 (commitment scheme)，而承諾系統的額外功能也能用以降低實際成本。本篇論文採納前人工作 [6,7]，將其轉化成基於離散對數難題 (discrete logarithm problem) 的透明多階段子向量承諾系統 (transparent multistage subvector commitment scheme)，使得在事先承諾的諸多訊息之中，可以揭露任意數量而不影響所產生的證明大小。本論文將其應用於近年來的互動預言機證明 (interactive oracle proof) 模型下的零知識證明，結果顯示在 2^16 個運算閘的計算問題上得以減少 58.7% 的證明大小。本論文也延伸此承諾系統，使其基於目前公認為後量子安全 (post-quantum secure) 的具結構的晶格 (structured lattice) 上的短向量難題假設。 | zh_TW |
| dc.description.abstract | In recent years, practical zero knowledge arguments of knowledge for NP-complete problems have been proposed and used in real-world applications. However, many of them require a trusted setup, which is unsuitable for decentralized areas like blockchain. We therefore focus only on transparent arguments, which do not involve any secret in the setup procedure. This is highly related to using commitment schemes that are transparent, but one also needs commitment schemes with nice features to reduce concrete costs. In this work, we modify the works [6,7] that are based on the hardness of the discrete logarithm problem, and turn them into a transparent multi-stage subvector commitment scheme. Such commitment schemes can open to an arbitrary number of committed messages without affecting the opening proof size. We then apply our multi-stage subvector commitment scheme to a recent IOP-based zero knowledge argument, obtaining arguments with a 58.7% reduction on proof size for circuits with 2^16 gates. We also extend our scheme to one that is alternatively based on structured lattice assumptions, which are currently believed to be post-quantum secure. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T01:09:33Z (GMT). No. of bitstreams: 1 ntu-109-R06221006-1.pdf: 2149630 bytes, checksum: 6ca7cba66bf19ba3791b3e9acbe1d607 (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 1 Introduction (1)
1.1 Early Constructions of Zero Knowledge Arguments (1) 1.2 Efficiency and Transparency (2) 1.3 Commitment Scheme (3) 1.4 Contribution of This Paper (3) 1.5 Arrangement (4) 2 Preliminaries (5) 2.1 Notations (5) 2.2 Lattice (6) 2.3 Hardness Assumptions (7) 3 Zero Knowledge Argument of Knowledge (9) 3.1 Security Goal (9) 3.2 Subvector Commitment Scheme (11) 3.3 An IOPbased Construction (15) 3.3.1 Arithmetization (15) 3.3.2 Batching Techniques (15) 3.3.3 Low Degree Test (17) 3.4 Compilation into zk-SNARK (18) 4 Building Subvector Commitments (21) 4.1 Previous Approaches (21) 4.2 Building Blocks (22) 4.3 Latticebased Variants of The Building Blocks (27) 4.4 Our Subvector Commitment Scheme (28) 4.5 Our MultiStage Subvector Commitment Scheme (29) 5 Performance (33) 6 Conclusion (37) A Lattice-based Building Blocks (39) A.1 Family of Somewhat Homomorphic Collision Resistant Functions (39) A.2 Relaxed Argument for Batch Opening (40) Bibliography (43) | |
| dc.language.iso | en | |
| dc.subject | 離散對數問題 | zh_TW |
| dc.subject | 子向量承諾系統 | zh_TW |
| dc.subject | 透明初始設定 | zh_TW |
| dc.subject | 零知識證明 | zh_TW |
| dc.subject | 近似最短多項式問題 | zh_TW |
| dc.subject | Zero knowledge | en |
| dc.subject | Argument of knowledge | en |
| dc.subject | Transparent setup | en |
| dc.subject | Interactive oracle proof | en |
| dc.subject | Subvector commitment scheme | en |
| dc.subject | Discrete logarithm problem | en |
| dc.subject | Approximate shortest polynomial problem | en |
| dc.title | 由子向量承諾系統所生之簡短零知識證明 | zh_TW |
| dc.title | Compact Zero Knowledge Argument from Subvector Commitment Scheme | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳君朋(Jiun-Peng Chen),鐘楷閔(Kai-Min Chung),謝致仁(Jyh-Ren Shieh),薛智文(Chih-Wen Hsueh) | |
| dc.subject.keyword | 零知識證明,透明初始設定,子向量承諾系統,離散對數問題,近似最短多項式問題, | zh_TW |
| dc.subject.keyword | Zero knowledge,Argument of knowledge,Transparent setup,Interactive oracle proof,Subvector commitment scheme,Discrete logarithm problem,Approximate shortest polynomial problem, | en |
| dc.relation.page | 45 | |
| dc.identifier.doi | 10.6342/NTU202000163 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-01-17 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-109-1.pdf 未授權公開取用 | 2.1 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。