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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113318/144297 (79%)
Visitors : 51054524 Online Users : 926

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

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/153915

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/153915

Title:	適用於二次算術程式的見證加密方案 A Witness Encryption for Quadratic Arithmetic Programs
Authors:	吳宇宸 Wu, Yu-Chen
Contributors:	左瑞麟 Tso, Raylin 吳宇宸 Wu, Yu-Chen
Keywords:	見證加密見證金鑰封裝機制 zkSNARK 二次算數程式 Witness encryption Witness key encapsulation mechanism zkSNARK Quadratic arithmetic programs
Date:	2024
Issue Date:	2024-10-04 10:47:24 (UTC+8)
Abstract:	本文討論了見證加密（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.
Reference:	[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).
Description:	碩士國立政治大學資訊科學系 110753122
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0110753122
Data Type:	thesis
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

File	Description	Size	Format
312201.pdf		1301Kb	Adobe PDF	0	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 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 © - Feedback