政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/153915

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/153915

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文笔数/总笔数 : 113392/144379 (79%)
造访人次 : 51207021 在线人数 : 882

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

搜寻范围

查询小技巧：

您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果

若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据

进阶搜寻

主页 ‧ 登入 ‧ 上传 ‧ 说明 ‧ 关于政大典藏 ‧ 管理

到手机版

政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 > Item 140.119/153915

请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/153915

题名:	適用於二次算術程式的見證加密方案 A Witness Encryption for Quadratic Arithmetic Programs
作者:	吳宇宸 Wu, Yu-Chen
贡献者:	左瑞麟 Tso, Raylin 吳宇宸 Wu, Yu-Chen
关键词:	見證加密見證金鑰封裝機制 zkSNARK 二次算數程式 Witness encryption Witness key encapsulation mechanism zkSNARK Quadratic arithmetic programs
日期:	2024
上传时间:	2024-10-04 10:47:24 (UTC+8)
摘要:	本文討論了見證加密（Witness Encryption，WE），這是一種在 2013 年提出的加密方案。其概念是利用 NP 語言中的陳述（Statement）進行加密，並通過見證（Witness）進行解密。例如，考慮一個驗證問題 \( y \overset{?}{=} H(x) \)。針對這一問題的見證加密方案允許加密者使用任意 \( y \) 進行加密，並且知道滿足該問題的 \( x \) 的解密者可以進行解密。見證加密可以用於構建多種密碼學原語，如非對稱加密的一般化和屬性加密（Attribute-Based Encryption）等。在近期的研究中，我們發現目前可用的見證加密方案有尚待解決的問題：在加密開始前，需要有某一方知道對應的見證，並從此見證產生其他資訊，並使加密者以此資訊進行解密。例如在前述的問題中，$x$ 需先被用於 $H(x)$ 後，方得將 $y$ 用於加密。這使得見證加密方案的可利用性受限，因為在一些驗證問題中，預先知道見證是不可行的。例如在基於時間加密中，任一方無法得知僅在未來才能得知的資訊以開始加密。在本研究中，我們設計了一種適用於二次算術程式（Quadratic Arithmetic Programs，QAP）的見證加密方案。該方案允許加密者使用 QAP 和一組陳述（公開輸入）進行加密，使得知道見證（滿足該 QAP 的一組非公開輸入）的人可以解密。這個方案的一個顯著特點是它不需要任何一方預先知道見證，因此可以應用於更多的情境中。此外，我們基於現有的開源軟體，實作了我們方案的概念驗證。我們的設計靈感來自於一個被證明安全且廣泛使用的 zkSNARK 方案，我們證明了在該 zkSNARK 是安全的假設下，我們的方案滿足安全性要求。 This paper discusses Witness Encryption (WE), a type of encryption scheme introduced in 2013. The concept involves encrypting a message using a statement from an NP language and decrypting it with a witness. For instance, consider a verification problem where $y \overset{?}{=} H(x) $. A witness encryption scheme for this problem allows an encryptor to encrypt with any $y$, and a decryptor knowing $x$ satisfying the problem can decrypt the message. Witness encryption can be used to construct various cryptographic primitives, such as a generalization of public-key encryption and Attribute-Based Encryption. Recent research has revealed limitations in existing witness encryption schemes: they require a party to know the corresponding witness before encryption begins, using this witness to generate information necessary for encryption. For example, in the aforementioned problem, $x$ must first be used to compute $H(x)$ before $y$ can be used for encryption. This restricts the applicability of witness encryption schemes, as knowing the witness in advance is not feasible in some verification problems. For instance, in time-based encryption, no party can obtain information that will only be known in the future to initiate encryption. In this work, we design a witness encryption scheme for Quadratic Arithmetic Programs (QAPs). Our scheme allows an encryptor to use a QAP and a set of statements (public input) for encryption, enabling decryption by someone who knows the witness (a set of private inputs) that satisfies the QAP. A notable feature of our scheme is that it does not require any party to know the witness in advance, making it applicable in more diverse scenarios. Besides, we implemented a proof of concept for our scheme based on existing open-source software. Our design is inspired by a proven secure and widely used zkSNARK scheme, and we demonstrate that our scheme meets security requirements under the assumption that the zkSNARK is secure.
參考文獻:	[BBH+18] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, "Scalable, transparent, and post-quantum secure computational integrity," Cryptology ePrint Archive, 2018 (cit. p. 3). [BBH+22] M. Buus, E. Bay, A. Henningsen, et al., mafintosh/blake2b-wasm. Nov. 7, 2022 (cit. p. 25). [BBS04] D. Boneh, X. Boyen, and H. Shacham, "Short group signatures," in Annual international cryptology conference, Springer, 2004, pp. 41–55 (cit. p. 11). [BCC+12] N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, "From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again," in Proceedings of the 3rd innovations in theoretical computer science conference, 2012, pp. 326–349 (cit. p. 6). [BdB+24a] J. Baylina, dependabot[bot], B. Bublitz, et al., iden3/ffjavascript. May 30, 2024 (cit. p. 25). [BdB+24b] J. Baylina, dependabot[bot], B. Bublitz, et al., iden3/snarkjs. Aug. 2, 2024 (cit. p. 25). [BDM+91] M. Blum, A. De Santis, S. Micali, and G. Persiano, "Noninteractive zero-knowledge," SIAM Journal on Computing, vol. 20, no. 6, pp. 1084–1118, 1991 (cit. p. 6). [BH15] M. Bellare and V. T. Hoang, "Adaptive witness encryption and asymmetric password-based cryptography," in Public-Key Cryptography–PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30–April 1, 2015, Proceedings 18, Springer, 2015, pp. 308–331 (cit. p. 6). [BL20] F. Benhamouda and H. Lin, "Multiparty reusable non-interactive secure computation," Cryptology ePrint Archive, 2020 (cit. p. 2). [Bon98] D. Boneh, "The decision diffie-hellman problem," in International algorithmic number theory symposium, Springer, 1998, pp. 48–63 (cit. p. 11). [CHM+20] A. Chiesa, Y. Hu, M. Maller, et al., "Marlin: Preprocessing zksnarks with universal and updatable srs," in Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I 39, Springer, 2020, pp. 738–768 (cit. p. 3). [CV21] G. Choi and S. Vaudenay, "Towards witness encryption without multilinear maps: Extractable witness encryption for multi-subset sum instances with no small solution to the homogeneous problem," in International Conference on Information Security and Cryptology, Springer, 2021, pp. 28–47 (cit. pp. 2, 6). [FHS24] N. Fleischhacker, M. Hall-Andersen, and M. Simkin, "Extractable witness encryption for kzg commitments and efficient laconic ot," Cryptology ePrint Archive, 2024 (cit. pp. 2, 4–6, 13, 21, 24, 29, 30). [FWW23] C. Freitag, B. Waters, and D. J. Wu, "How to use (plain) witness encryption: Registered abe, flexible broadcast, and more," in Annual International Cryptology Conference, Springer, 2023, pp. 498–531 (cit. p. 1). [GG17] R. Goyal and V. Goyal, "Overcoming cryptographic impossibility results using blockchains," in Theory of Cryptography Conference, Springer, 2017, pp. 529–561 (cit. p. 1). [GGH+16] S. Garg, C. Gentry, S. Halevi, et al., "Candidate indistinguishability obfuscation and functional encryption for all circuits," SIAM Journal on Computing, vol. 45, no. 3, pp. 882–929, 2016 (cit. p. 2). [GGP+13] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, "Quadratic span programs and succinct nizks without pcps," in Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32, Springer, 2013, pp. 626–645 (cit. p. 8). [GGS+13] S. Garg, C. Gentry, A. Sahai, and B. Waters, "Witness encryption and its applications," in Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 2013, pp. 467–476 (cit. pp. 1, 2, 5, 6, 29). [GHV07] S. D. Galbraith, F. Hess, and F. Vercauteren, "Aspects of pairing inversion," Cryptology ePrint Archive, 2007 (cit. p. 7). [GKP+13] S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich, "How to run turing machines on encrypted data," in Annual Cryptology Conference, Springer, 2013, pp. 536–553 (cit. pp. 3, 6). [GMR85] S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof-systems," in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, ser. STOC '85, Providence, Rhode Island, USA: Association for Computing Machinery, 1985, pp. 291–304 (cit. p. 6). [Gro16] J. Groth, "On the size of pairing-based non-interactive arguments," in Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, Springer, 2016, pp. 305–326 (cit. pp. 3, 6–10). [GS17] S. Garg and A. Srinivasan, "Garbled protocols and two-round mpc from bilinear maps," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 588–599 (cit. p. 2). [GWC19] A. Gabizon, Z. J. Williamson, and O. Ciobotaru, "Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge," Cryptology ePrint Archive, 2019 (cit. p. 3). [Kil92] J. Kilian, "A note on efficient zero-knowledge proofs and arguments," in Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, 1992, pp. 723–732 (cit. p. 6). [KL07] J. Katz and Y. Lindell, Introduction to modern cryptography: principles and protocols. Chapman and hall/CRC, 2007 (cit. p. 12). [LJK+18] J. Liu, T. Jager, S. A. Kakvi, and B. Warinschi, "How to build time-lock encryption," Designs, Codes and Cryptography, vol. 86, no. 11, pp. 2549–2586, 2018 (cit. pp. 1, 5, 29). [MBK+19] M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn, "Sonic: Zero-knowledge snarks from linear-size universal and updatable structured reference strings," in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 2111–2128 (cit. p. 3). [Mic94] S. Micali, "Cs proofs," in Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 436–453 (cit. p. 6). [PMd+24] P. Palladino, P. Miller, dependabot[bot], et al., ethereum/js-ethereum-cryptography. Jul. 1, 2024 (cit. p. 25). [RIR+24] C. Rodríguez, M. Isabel, A. Rubio, et al., iden3/circom. Jul. 30, 2024 (cit. p. 25). [ULC+21] G. Uberti, K. Luo, O. Cheng, and W. Goh, "Building usable witness encryption," arXiv preprint arXiv:2112.04581, 2021 (cit. p. 1).
描述:	碩士國立政治大學資訊科學系 110753122
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0110753122
数据类型:	thesis
显示于类别:	[資訊科學系] 學位論文

文件中的档案:

档案	描述	大小	格式	浏览次数
312201.pdf		1301Kb	Adobe PDF	0	检视/开启

在政大典藏中所有的数据项都受到原著作权保护.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - 回馈