Loading...
|
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: | [資訊科學系] 學位論文
|
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.
|
