Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits Based on Isogenies
 
conference paper

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

Chen, Mingjie
•
Lai, Yi Fu
•
Laval, Abel
Show more
Chattopadhyay, Anupam
•
Bhasin, Shivam
Show more
2024
Progress in Cryptology – INDOCRYPT 2023 - 24th International Conference on Cryptology in India, 2023, Proceedings
24th International Conference on Progress in Cryptology

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-031-56232-7_11
Scopus ID

2-s2.0-85190704657

Author(s)
Chen, Mingjie

University of Birmingham

Lai, Yi Fu

The University of Auckland

Laval, Abel

Université Libre de Bruxelles

Marco, Laurane  

École Polytechnique Fédérale de Lausanne

Petit, Christophe

University of Birmingham

Editors
Chattopadhyay, Anupam
•
Bhasin, Shivam
•
Picek, Stjepan
•
Rebeiro, Chester
Date Issued

2024

Publisher

Springer Science and Business Media Deutschland GmbH

Published in
Progress in Cryptology – INDOCRYPT 2023 - 24th International Conference on Cryptology in India, 2023, Proceedings
Series title/Series vol.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 14459 LNCS

ISSN (of the series)

1611-3349

0302-9743

Start page

221

End page

243

Subjects

commitments

•

generic zero-knowledge proof of knowledge

•

group action

•

isogeny-based cryptography

•

post-quantum cryptography

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LASEC  
Event nameEvent acronymEvent placeEvent date
24th International Conference on Progress in Cryptology

Goa, India

2023-12-10 - 2023-12-13

FunderFunding(s)Grant NumberGrant URL

Ministry for Business and Employment

EPSRC

EP/V011324/1

Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/245067
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés