請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21119
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 廖世偉 | |
dc.contributor.author | Ting-Yuan Cheng | en |
dc.contributor.author | 程鼎元 | zh_TW |
dc.date.accessioned | 2021-06-08T03:27:18Z | - |
dc.date.copyright | 2020-03-05 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2020-01-02 | |
dc.identifier.citation | Ajtai, M., Koml´os, J., Szemer´edi, E.: An 0 (n log n) sorting network. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. ACM (1983)
Batcher, K.E.: Sorting networks and their applications. In: Proceedings of the April 30–May 2, 1968, spring joint computer conference. pp. 307–314. ACM (1968) Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: Snarks for c: Verifying program executions succinctly and in zero knowledge. In: Annual Cryptology Conference. pp. 90–108. Springer (2013) Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: Transparent succinct arguments for r1cs. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 103–128. Springer (2019) Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. Algorithmica 79(4), 1102–1160 (2017) Benes, V.E.: Optimal rearrangeable multistage connecting networks. Bell system technical journal 43(4), 1641–1656 (1964) Bowe, S.: Bls12-381: New zk-snark elliptic curve construction. Zcash blog. March 11, 4 (2017) Daemen, J., Rijmen, V.: Aes proposal: Rijndael (1999) Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct nizks without pcps. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 626–645. Springer (2013) Groth, J.: On the size of pairing-based non-interactive arguments. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 305–326. Springer (2016) Groth, J., Maller, M.: Snarky signatures: Minimal signatures of knowledge from simulationextractable snarks. In: Annual International Cryptology Conference. pp. 581–612. Springer (2017) iden3: circomlib. https://github.com/iden3/circomlib, accessed: 2019-11-09 Kosba, A., Papamanthou, C., Shi, E.: xjsnark: a framework for efficient verifiable computation. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 944–961. IEEE (2018) Kosba, A., Zhao, Z., Miller, A., Qian, Y., Chan, H., PAPAMAN-THOU, C., Pass, R., ABHI, S., SHI, E.: c0: A framework for building composable zero-knowledge proofs. Tech. rep., Cryptology ePrint Archive, Report 2015/1093, (2015) scipr lab: libsnark. https://github.com/scipr-lab/libsnark, accessed: 2019-11-09 scipr lab: zexe. https://github.com/scipr-lab/zexe, accessed: 2019-11-09 magrady24: circuits-optimization-data. https://github.com/magrady24/circuits-optimizationdata, accessed: 2019-11-09 Sasson, E.B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: Decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy. pp. 459–474. IEEE (2014) Wahby, R.S., Setty, S.T., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient ram and control flow in verifiable outsourced computation. In: NDSS (2015) Waksman, A.: A permutation network. Journal of the ACM (JACM) 15(1), 159–163 (1968) Wood, G., et al.: Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper 151(2014), 1–32 (2014) ZoKrates: Zokrates. https://github.com/Zokrates/ZoKrates, accessed: 2019-11-09 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21119 | - |
dc.description.abstract | 區塊鏈技術可以在分散的不受信任的各方之間達成共識,而零知識證明可以增進區塊鏈上的隱私。透過零知識證明,任何人可以證明一條特定的敘述是正確的,而不會洩漏保密的資訊。但是,通常必須將該敘述轉換為特定的形式,即Rank-1約束系統,才能在已廣泛被採用的系統中使用。轉換的效率決定了公共參考字串(CRS)的大小以及證明該敘述所需的運算量。 更具體地說,為了最大程度地減少R1CS中的約束數量,我們優化了布林函式和動態陣列訪問操作,它們廣泛用於加密和可驗證計算中。本文並介紹數個建構於區塊鏈系統上之零知識應用。 | zh_TW |
dc.description.abstract | Blockchain technology can reach consensus between decentralized untrusted parties, and zero-knowledge proof can enhance the privacy on the blockchain. By zero-knowledge proof, one can prove that a particular statement is true without leaking other information. However, a general statement must be converted to a specific circuit form, Rank-1 constraint system, typically, to use in the above mechanism. The efficiency of the conversion determines the size of the common reference string (CRS) and the resources it takes to prove the statement. More specifically, to minimize the number of constraints in R1CS, we optimized boolean functions and dynamic array accessing operations, which are widely used in cryptography and computational verification. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T03:27:18Z (GMT). No. of bitstreams: 1 ntu-108-R05922098-1.pdf: 359457 bytes, checksum: 06807c5db602c662bb8a7047f0b48897 (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 摘要 iii
Abstract v 1 Introduction 1 2 Preliminaries 3 2.1 Quadratic Arithmetic Programs (QAP) [8] . . . . . . . . . . . . . . . . . 3 2.2 Rank-1 Constraint System (R1CS, Rank-1 quadratic constraint satisfaction)[3] [8] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Square Arithmetic Programs (SAP) [10] . . . . . . . . . . . . . . . . . . 4 2.4 Zero-Knowledge Proof Systems . . . . . . . . . . . . . . . . . . . . . . 4 2.5 Circuit Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Related Works 7 4 Our Contribution 9 4.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.1.1 Simple logic gate . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.1.2 By Multiplier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1.3 By Look-Up Tables . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Data Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2.1 Read-only array . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2.2 Read-write array . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Reference 25 | |
dc.language.iso | en | |
dc.title | 關於零知識證明的探討及其在區塊鏈系統上之應用 | zh_TW |
dc.title | On the Zero-Knowledge Proof and its Application in Blockchain | en |
dc.type | Thesis | |
dc.date.schoolyear | 108-1 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 鄭振牟 | |
dc.contributor.oralexamcommittee | 蕭旭君 | |
dc.subject.keyword | 密碼學,零知識證明,二次算術程式,一階約束系統,編譯器,可驗證計算,非交互式簡潔知識證明, | zh_TW |
dc.subject.keyword | Cryptography,Zero-knowledge proof,Quadratic arithmetic programs,Rank-1 constraint system,Compiler,Verifiable computation,SNARKs, | en |
dc.relation.page | 27 | |
dc.identifier.doi | 10.6342/NTU201904438 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2020-01-02 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 351.03 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。