Re-Randomize and Extract: A Novel Commitment Construction Framework Based on Group Actions

Kaijie Jiang; Anyu Wang; Hengyi Luo; Guoxiao Liu; Tang Gang; Yanbin Pan; Xiaoyun Wang

Paper 2025/400

Re-Randomize and Extract: A Novel Commitment Construction Framework Based on Group Actions

Kaijie Jiang, Tsinghua University

Anyu Wang, Tsinghua University

Hengyi Luo, University of Chinese Academy of Sciences

Guoxiao Liu, Tsinghua University

Tang Gang, University of Birmingham

Yanbin Pan, University of Chinese Academy of Sciences

Xiaoyun Wang, Tsinghua University

Abstract

Cryptographic group actions have attracted growing attention as a useful tool for constructing cryptographic schemes. Among their applications, commitment schemes are particularly interesting as fundamental primitives, playing a crucial role in protocols such as zero-knowledge proofs, multi-party computation, and more. In this paper, we introduce a novel framework to construct commitment schemes based on cryptographic group actions. Specifically, we propose two key techniques for general group actions: re-randomization and randomness extraction. Roughly speaking, a re-randomization algorithm introduces randomness within an orbit for any input element, while a randomness extractor maps this randomness to uniformity over the message space. We demonstrate that these techniques can significantly facilitate the construction of commitment schemes, providing a flexible framework for constructing either perfectly hiding or perfectly binding commitments, depending on the type of extractor involved. Moreover, we extend our framework to support the construction of commitments with additional desirable properties beyond hiding and binding, such as dual-mode commitments and enhanced linkable commitments. These extensions are achieved by further adapting the extractor to satisfy trapdoor or homomorphic properties. Finally, we instantiate all our proposed commitment schemes using lattices, specifically leveraging the lattice isomorphism problem (LIP) and the lattice automorphism problem (LAP) as underlying cryptographic assumptions. To the best of our knowledge, this is the first commitment scheme construction based on LIP/LAP. Additionally, we use LIP to provide a repair and improvement to the tensor isomorphism-based non-interactive commitment scheme proposed by D'Alconzo, Flamini, and Gangemi (ASIACRYPT 2023), which was recently shown to be insecure by an attack from Gilchrist, Marco, Petit, and Tang (CRYPTO 2024).

Note: extended version

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in EUROCRYPT 2025
Keywords: Cryptographic group action Dual-mode commitment Homomorphic commitment Lattice isomorphism problem
Contact author(s): jkj21 @ mails tsinghua edu cn
anyuwang @ tsinghua edu cn
luohengyi @ amss ac cn
lgx22 @ mails tsinghua edu cn
g tang 1 @ bham ac uk
panyanbin @ amss ac cn
xiaoyunwang @ tsinghua edu cn
History: 2025-03-04: approved; 2025-03-03: received; See all versions
Short URL: https://ia.cr/2025/400
License: CC BY

BibTeX

@misc{cryptoeprint:2025/400,
      author = {Kaijie Jiang and Anyu Wang and Hengyi Luo and Guoxiao Liu and Tang Gang and Yanbin Pan and Xiaoyun Wang},
      title = {Re-Randomize and Extract: A Novel Commitment Construction Framework Based on Group Actions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/400},
      year = {2025},
      url = {https://eprint.iacr.org/2025/400}
}