Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
  • 幫助
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 電機資訊學院
  3. 資訊工程學系
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21119
完整後設資料紀錄
DC 欄位值語言
dc.contributor.advisor廖世偉
dc.contributor.authorTing-Yuan Chengen
dc.contributor.author程鼎元zh_TW
dc.date.accessioned2021-06-08T03:27:18Z-
dc.date.copyright2020-03-05
dc.date.issued2019
dc.date.submitted2020-01-02
dc.identifier.citationAjtai, 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.urihttp://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21119-
dc.description.abstract區塊鏈技術可以在分散的不受信任的各方之間達成共識,而零知識證明可以增進區塊鏈上的隱私。透過零知識證明,任何人可以證明一條特定的敘述是正確的,而不會洩漏保密的資訊。但是,通常必須將該敘述轉換為特定的形式,即Rank-1約束系統,才能在已廣泛被採用的系統中使用。轉換的效率決定了公共參考字串(CRS)的大小以及證明該敘述所需的運算量。 更具體地說,為了最大程度地減少R1CS中的約束數量,我們優化了布林函式和動態陣列訪問操作,它們廣泛用於加密和可驗證計算中。本文並介紹數個建構於區塊鏈系統上之零知識應用。zh_TW
dc.description.abstractBlockchain 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.provenanceMade 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.isoen
dc.title關於零知識證明的探討及其在區塊鏈系統上之應用zh_TW
dc.titleOn the Zero-Knowledge Proof and its Application in Blockchainen
dc.typeThesis
dc.date.schoolyear108-1
dc.description.degree碩士
dc.contributor.coadvisor鄭振牟
dc.contributor.oralexamcommittee蕭旭君
dc.subject.keyword密碼學,零知識證明,二次算術程式,一階約束系統,編譯器,可驗證計算,非交互式簡潔知識證明,zh_TW
dc.subject.keywordCryptography,Zero-knowledge proof,Quadratic arithmetic programs,Rank-1 constraint system,Compiler,Verifiable computation,SNARKs,en
dc.relation.page27
dc.identifier.doi10.6342/NTU201904438
dc.rights.note未授權
dc.date.accepted2020-01-02
dc.contributor.author-college電機資訊學院zh_TW
dc.contributor.author-dept資訊工程學研究所zh_TW
顯示於系所單位:資訊工程學系

文件中的檔案:
檔案 大小格式 
ntu-108-1.pdf
  目前未授權公開取用
351.03 kBAdobe PDF
顯示文件簡單紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved