Shorter ZK-SNARKs from square span programs over ideal lattices
Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation an...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2024-03-01
|
| Series: | Cybersecurity |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s42400-024-00215-x |
| _version_ | 1797247193817546752 |
|---|---|
| author | Xi Lin Heyang Cao Feng-Hao Liu Zhedong Wang Mingsheng Wang |
| author_facet | Xi Lin Heyang Cao Feng-Hao Liu Zhedong Wang Mingsheng Wang |
| author_sort | Xi Lin |
| collection | DOAJ |
| description | Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around $$23.3\%$$ 23.3 % smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212–234, 2021), and the CRS length is $$3.6\times$$ 3.6 × smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556–573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way. |
| first_indexed | 2024-04-24T19:54:48Z |
| format | Article |
| id | doaj.art-4cdecb24492f492bb50539c837221925 |
| institution | Directory Open Access Journal |
| issn | 2523-3246 |
| language | English |
| last_indexed | 2024-04-24T19:54:48Z |
| publishDate | 2024-03-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Cybersecurity |
| spelling | doaj.art-4cdecb24492f492bb50539c8372219252024-03-24T12:24:25ZengSpringerOpenCybersecurity2523-32462024-03-017111910.1186/s42400-024-00215-xShorter ZK-SNARKs from square span programs over ideal latticesXi Lin0Heyang Cao1Feng-Hao Liu2Zhedong Wang3Mingsheng Wang4Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesKey Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesSchool of Electrical Engineering & Computer Science, Washington State UniversitySchool of Cyber Science and Engineering, Shanghai Jiaotong UniversityKey Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesAbstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around $$23.3\%$$ 23.3 % smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212–234, 2021), and the CRS length is $$3.6\times$$ 3.6 × smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556–573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.https://doi.org/10.1186/s42400-024-00215-xZk-SNARKsPost-quantumSuccinct argument |
| spellingShingle | Xi Lin Heyang Cao Feng-Hao Liu Zhedong Wang Mingsheng Wang Shorter ZK-SNARKs from square span programs over ideal lattices Cybersecurity Zk-SNARKs Post-quantum Succinct argument |
| title | Shorter ZK-SNARKs from square span programs over ideal lattices |
| title_full | Shorter ZK-SNARKs from square span programs over ideal lattices |
| title_fullStr | Shorter ZK-SNARKs from square span programs over ideal lattices |
| title_full_unstemmed | Shorter ZK-SNARKs from square span programs over ideal lattices |
| title_short | Shorter ZK-SNARKs from square span programs over ideal lattices |
| title_sort | shorter zk snarks from square span programs over ideal lattices |
| topic | Zk-SNARKs Post-quantum Succinct argument |
| url | https://doi.org/10.1186/s42400-024-00215-x |
| work_keys_str_mv | AT xilin shorterzksnarksfromsquarespanprogramsoverideallattices AT heyangcao shorterzksnarksfromsquarespanprogramsoverideallattices AT fenghaoliu shorterzksnarksfromsquarespanprogramsoverideallattices AT zhedongwang shorterzksnarksfromsquarespanprogramsoverideallattices AT mingshengwang shorterzksnarksfromsquarespanprogramsoverideallattices |