Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies

Mingjie Chen; Yi-Fu Lai; Abel Laval; Laurane Marco; Christophe Petit

doi:10.1007/978-3-031-56232-7_11

Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies

Mingjie Chen, Yi-Fu Lai, Abel Laval^*, Laurane Marco, Christophe Petit

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Downloads (Pure)

Abstract

Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments.

In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt’22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs.

Original language	English
Title of host publication	Progress in Cryptology – INDOCRYPT 2023
Subtitle of host publication	24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I
Editors	Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, Chester Rebeiro
Publisher	Springer
Pages	221–243
Number of pages	23
Edition	1
ISBN (Electronic)	9783031562327
ISBN (Print)	9783031562310
DOIs	https://doi.org/10.1007/978-3-031-56232-7_11
Publication status	Published - 29 Mar 2024
Event	24th International Conference on Cryptology in India - BITS Pilani Goa Campus, Goa, India Duration: 10 Dec 2023 → 13 Dec 2023

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14459
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Cryptology in India
Abbreviated title	INDOCRYPT 2023
Country/Territory	India
City	Goa
Period	10/12/23 → 13/12/23

Bibliographical note

Acknowledgments:
Mingjie Chen and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1. Yi-Fu Lai thanks the New Zealand Ministry for Business and Employment for financial support.

Keywords

group action
isogeny-based cryptography
commitments
generic zero-knowledge proof of knowledge
post-quantum cryptography

Access to Document

10.1007/978-3-031-56232-7_11

Embargoed Document

ChenM2023Malleable
Accepted author manuscript, 490 KB
Licence: Other (please specify with Rights Statement)
Embargo ends: 28/03/25

Post-Quantum Cryptography: a Cryptanalysis Approach
Petit, C.
Engineering & Physical Science Research Council
1/10/21 → 30/09/26
Project: Research Councils

Cite this

Chen, M., Lai, Y.-F., Laval, A., Marco, L., & Petit, C. (2024). Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies. In A. Chattopadhyay, S. Bhasin, S. Picek, & C. Rebeiro (Eds.), Progress in Cryptology – INDOCRYPT 2023: 24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I (1 ed., pp. 221–243). (Lecture Notes in Computer Science; Vol. 14459). Springer. https://doi.org/10.1007/978-3-031-56232-7_11

Chen, Mingjie ; Lai, Yi-Fu ; Laval, Abel et al. / Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies. Progress in Cryptology – INDOCRYPT 2023: 24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I. editor / Anupam Chattopadhyay ; Shivam Bhasin ; Stjepan Picek ; Chester Rebeiro. 1. ed. Springer, 2024. pp. 221–243 (Lecture Notes in Computer Science).

@inproceedings{189ee9dc49da41f1bbe5cca3c7b21264,

title = "Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies",

abstract = "Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments.In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt{\textquoteright}22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs.",

keywords = "group action, isogeny-based cryptography, commitments, generic zero-knowledge proof of knowledge, post-quantum cryptography",

author = "Mingjie Chen and Yi-Fu Lai and Abel Laval and Laurane Marco and Christophe Petit",

note = "Acknowledgments: Mingjie Chen and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1. Yi-Fu Lai thanks the New Zealand Ministry for Business and Employment for financial support.; 24th International Conference on Cryptology in India, INDOCRYPT 2023 ; Conference date: 10-12-2023 Through 13-12-2023",

year = "2024",

month = mar,

day = "29",

doi = "10.1007/978-3-031-56232-7_11",

language = "English",

isbn = "9783031562310",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "221–243",

editor = "Anupam Chattopadhyay and Shivam Bhasin and Stjepan Picek and Chester Rebeiro",

booktitle = "Progress in Cryptology – INDOCRYPT 2023",

edition = "1",

}

Chen, M, Lai, Y-F, Laval, A, Marco, L & Petit, C 2024, Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies. in A Chattopadhyay, S Bhasin, S Picek & C Rebeiro (eds), Progress in Cryptology – INDOCRYPT 2023: 24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I. 1 edn, Lecture Notes in Computer Science, vol. 14459, Springer, pp. 221–243, 24th International Conference on Cryptology in India, Goa, India, 10/12/23. https://doi.org/10.1007/978-3-031-56232-7_11

Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies. / Chen, Mingjie; Lai, Yi-Fu; Laval, Abel et al.
Progress in Cryptology – INDOCRYPT 2023: 24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I. ed. / Anupam Chattopadhyay; Shivam Bhasin; Stjepan Picek; Chester Rebeiro. 1. ed. Springer, 2024. p. 221–243 (Lecture Notes in Computer Science; Vol. 14459).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies

AU - Chen, Mingjie

AU - Lai, Yi-Fu

AU - Laval, Abel

AU - Marco, Laurane

AU - Petit, Christophe

N1 - Acknowledgments: Mingjie Chen and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1. Yi-Fu Lai thanks the New Zealand Ministry for Business and Employment for financial support.

PY - 2024/3/29

Y1 - 2024/3/29

N2 - Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments.In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt’22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs.

AB - Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments.In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt’22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs.

KW - group action

KW - isogeny-based cryptography

KW - commitments

KW - generic zero-knowledge proof of knowledge

KW - post-quantum cryptography

UR - https://crsind.in/indocrypt2023/

U2 - 10.1007/978-3-031-56232-7_11

DO - 10.1007/978-3-031-56232-7_11

M3 - Conference contribution

SN - 9783031562310

T3 - Lecture Notes in Computer Science

SP - 221

EP - 243

BT - Progress in Cryptology – INDOCRYPT 2023

A2 - Chattopadhyay, Anupam

A2 - Bhasin, Shivam

A2 - Picek, Stjepan

A2 - Rebeiro, Chester

PB - Springer

T2 - 24th International Conference on Cryptology in India

Y2 - 10 December 2023 through 13 December 2023

ER -

Chen M, Lai YF, Laval A, Marco L, Petit C. Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies. In Chattopadhyay A, Bhasin S, Picek S, Rebeiro C, editors, Progress in Cryptology – INDOCRYPT 2023: 24th International Conference on Cryptology in India, Goa, India, December 10–13, 2023, Proceedings, Part I. 1 ed. Springer. 2024. p. 221–243. (Lecture Notes in Computer Science). Epub 2024 Mar 28. doi: 10.1007/978-3-031-56232-7_11

Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Embargoed Document

Fingerprint

Projects

Post-Quantum Cryptography: a Cryptanalysis Approach

Cite this