{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:07Z","timestamp":1750309507049,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T00:00:00Z","timestamp":1756080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,8,25]]},"DOI":"10.1145\/3709015.3728673","type":"proceedings-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T18:31:14Z","timestamp":1749234674000},"page":"34-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["More Efficient Lattice-Based Zero-Knowledge Proofs with Straight-Line Extractability"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8240-6167","authenticated-orcid":false,"given":"Ngoc Khanh","family":"Nguyen","sequence":"first","affiliation":[{"name":"King's College London, London, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3459-561X","authenticated-orcid":false,"given":"George","family":"O'Rourke","sequence":"additional","affiliation":[{"name":"King's College London, London, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2025,8,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1515\/jmc-2015-0016"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Sven Argo Tim G\u00fcneysu Corentin Jeudy Georg Land Adeline Roux-Langlois and Olivier Sanders. 2024. Practical Post-Quantum Signatures for Privacy. In CCS. ACM 1523\u20131537.","DOI":"10.1145\/3658644.3670297"},{"volume-title":"CRYPTO (2) (Lecture Notes in Computer Science","author":"Attema Thomas","key":"e_1_3_2_1_3_1","unstructured":"Thomas Attema, Vadim Lyubashevsky, and Gregor Seiler. 2020. Practical Product Proofs for Lattice Commitments. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 12171). Springer, 470\u2013499."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01445125"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Carsten Baum Ivan Damg\u00e5rd Vadim Lyubashevsky Sabine Oechsner and Chris Peikert. 2018. More Efficient Commitments from Structured Lattice Assumptions. In SCN. 368\u2013385.","DOI":"10.1007\/978-3-319-98113-0_20"},{"key":"e_1_3_2_1_6_1","volume-title":"Ngoc Khanh Nguyen, and Gregor Seiler","author":"Beullens Ward","year":"2023","unstructured":"Ward Beullens, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler. 2023. Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal. In CCS. ACM, 16\u201329."},{"volume-title":"CRYPTO (5) (Lecture Notes in Computer Science","author":"Beullens Ward","key":"e_1_3_2_1_7_1","unstructured":"Ward Beullens and Gregor Seiler. 2023. LaBRADOR: Compact Proofs for R1CS from Module-SIS. In CRYPTO (5) (Lecture Notes in Computer Science, Vol. 14085). Springer, 518\u2013548."},{"key":"e_1_3_2_1_8_1","volume-title":"Ngoc Khanh Nguyen, and Alessandro Sorniotti","author":"Bootle Jonathan","year":"2023","unstructured":"Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Alessandro Sorniotti. 2023. A Framework for Practical Anonymous Credentials from Lattices. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 14082). Springer, 384\u2013417."},{"key":"e_1_3_2_1_9_1","unstructured":"Megan Chen Pousali Dey Chaya Ganesh Pratyay Mukherjee Pratik Sarkar and Swagata Sasmal. 2024. Universally Composable Non-Interactive Zero-Knowledge from Sigma Protocols via a New Straight-line Compiler. Cryptology ePrint Archive Paper 2024\/1713. https:\/\/eprint.iacr.org\/2024\/1713"},{"key":"e_1_3_2_1_10_1","volume-title":"Ngoc Khanh Nguyen, and Hoeteck Wee","author":"Cini Valerio","year":"2024","unstructured":"Valerio Cini, Giulio Malavolta, Ngoc Khanh Nguyen, and Hoeteck Wee. 2024. Polynomial Commitments from Lattices: Post-quantum Security, Fast Verification and Transparent Setup. In CRYPTO (10) (Lecture Notes in Computer Science, Vol. 14929). Springer, 207\u2013242."},{"volume-title":"Public Key Cryptography (1) (Lecture Notes in Computer Science","author":"Damg\u00e5rd Ivan","key":"e_1_3_2_1_11_1","unstructured":"Ivan Damg\u00e5rd, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. 2021. Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices. In Public Key Cryptography (1) (Lecture Notes in Computer Science, Vol. 12710). Springer, 99\u2013130."},{"volume-title":"CRYPTO (2) (Lecture Notes in Computer Science","author":"del Pino Rafa\u00ebl","key":"e_1_3_2_1_12_1","unstructured":"Rafa\u00ebl del Pino and Shuichi Katsumata. 2022. A New Framework for More Efficient Round-Optimal Lattice-Based (Partially) Blind Signature via Trapdoor Sampling. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 13508). Springer, 306\u2013336."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"L\u00e9o Ducas Alain Durmus Tancr\u00e8de Lepoint and Vadim Lyubashevsky. 2013. Lattice Signatures and Bimodal Gaussians. In CRYPTO (1). 40\u201356.","DOI":"10.1007\/978-3-642-40041-4_3"},{"key":"e_1_3_2_1_14_1","volume-title":"Ngoc Khanh Nguyen, and Gregor Seiler","author":"Esgin Muhammed F.","year":"2020","unstructured":"Muhammed F. Esgin, Ngoc Khanh Nguyen, and Gregor Seiler. 2020. Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings. In ASIACRYPT (2). 259\u2013288."},{"key":"e_1_3_2_1_15_1","unstructured":"Giacomo Fenzi Hossein Moghaddas and Ngoc Khanh Nguyen. 2023. Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency. Cryptology ePrint Archive Paper 2023\/846. https:\/\/eprint.iacr.org\/2023\/846 https:\/\/eprint.iacr.org\/2023\/846."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_10"},{"volume-title":"EUROCRYPT (1) (Lecture Notes in Computer Science","author":"Gentry Craig","key":"e_1_3_2_1_17_1","unstructured":"Craig Gentry, Shai Halevi, and Vadim Lyubashevsky. 2022. Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties. In EUROCRYPT (1) (Lecture Notes in Computer Science, Vol. 13275). Springer, 458\u2013487."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser Silvio Micali and Charles Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In STOC. ACM 291\u2013304.","DOI":"10.1145\/22145.22178"},{"volume-title":"Application to Anonymous Credentials. In CRYPTO (2) (Lecture Notes in Computer Science","author":"Jeudy Corentin","key":"e_1_3_2_1_19_1","unstructured":"Corentin Jeudy, Adeline Roux-Langlois, and Olivier Sanders. 2023. Lattice Signature with Efficient Protocols, Application to Anonymous Credentials. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 14082). Springer, 351\u2013383."},{"volume-title":"CRYPTO (2) (Lecture Notes in Computer Science","author":"Katsumata Shuichi","key":"e_1_3_2_1_20_1","unstructured":"Shuichi Katsumata. 2021. A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 12826). Springer, 580\u2013610."},{"key":"e_1_3_2_1_21_1","volume-title":"Ngoc Khanh Nguyen, and Micha\u0142 Osadnik","author":"Kloo\u00df Michael","year":"2024","unstructured":"Michael Kloo\u00df, Russell W. F. Lai, Ngoc Khanh Nguyen, and Micha\u0142 Osadnik. 2024. RoK, Paper, SISsors - Toolkit for Lattice-based Succinct Arguments. Cryptology ePrint Archive, Paper 2024\/1972. https:\/\/eprint.iacr.org\/2024\/1972"},{"key":"e_1_3_2_1_22_1","unstructured":"Qiqi Lai Feng-Hao Liu Anna Lysyanskaya and Zhedong Wang. 2023. Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials. IACR Cryptol. ePrint Arch. (2023) 766."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-014-9938-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky. 2009. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In ASIACRYPT. 598\u2013616.","DOI":"10.1007\/978-3-642-10366-7_35"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky. 2012. Lattice Signatures Without Trapdoors. In EUROCRYPT. 738\u2013755.","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"e_1_3_2_1_26_1","volume-title":"Ngoc Khanh Nguyen, and Maxime Plan\u00e7on","author":"Lyubashevsky Vadim","year":"2022","unstructured":"Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Maxime Plan\u00e7on. 2022. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. In CRYPTO (2) (Lecture Notes in Computer Science, Vol. 13508). Springer, 71\u2013101."},{"key":"e_1_3_2_1_27_1","volume-title":"Maxime Plan\u00e7on, and Gregor Seiler.","author":"Lyubashevsky Vadim","year":"2021","unstructured":"Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plan\u00e7on, and Gregor Seiler. 2021. Shorter Lattice-Based Group Signatures via \"Almost Free\" Encryption and Other Optimizations. In ASIACRYPT (4). Springer, 218\u2013248."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky Gregor Seiler and Patrick Steuer. 2024. The LaZer Library: Lattice-Based Zero Knowledge and Succinct Proofs for Quantum-Safe Privacy. In CCS. ACM 3125\u20133137.","DOI":"10.1145\/3658644.3690330"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0234-9"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_19"},{"key":"e_1_3_2_1_31_1","unstructured":"Lior Rotem and Stefano Tessaro. 2024. Straight-Line Knowledge Extraction for Multi-Round Protocols. Cryptology ePrint Archive Paper 2024\/1724. https:\/\/eprint.iacr.org\/2024\/1724"},{"volume-title":"EUROCRYPT (2) (Lecture Notes in Computer Science","author":"Unruh Dominique","key":"e_1_3_2_1_32_1","unstructured":"Dominique Unruh. 2015. Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model. In EUROCRYPT (2) (Lecture Notes in Computer Science, Vol. 9057). Springer, 755\u2013784."}],"event":{"name":"APKC '25: 12th ACM ASIA Public-Key Cryptography Workshop","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"],"location":"Meli\u00e1 Hanoi Hanoi Vietnam","acronym":"APKC '25"},"container-title":["Proceedings of the 12th ACM ASIA Public-Key Cryptography Workshop"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709015.3728673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:55Z","timestamp":1750295875000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709015.3728673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,25]]},"references-count":32,"alternative-id":["10.1145\/3709015.3728673","10.1145\/3709015"],"URL":"https:\/\/doi.org\/10.1145\/3709015.3728673","relation":{},"subject":[],"published":{"date-parts":[[2025,8,25]]},"assertion":[{"value":"2025-08-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}