Short Code-based One-out-of-Many Proofs and Applications

Xindong Liu; Li-Ping Wang

Paper 2024/093

Short Code-based One-out-of-Many Proofs and Applications

Xindong Liu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Li-Ping Wang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

In this work, we propose two novel succinct one-out-of-many proofs from coding theory, which can be seen as extensions of the Stern's framework and Veron's framework from proving knowledge of a preimage to proving knowledge of a preimage for one element in a set, respectively. The size of each proof is short and scales better with the size of the public set than the code-based accumulator in \cite{nguyen2019new}. Based on our new constructions, we further present a logarithmic-size ring signature scheme and a logarithmic-size group signature scheme. Our schemes feature a short signature size, especially our group signature. To our best knowledge, it is the most compact code-based group signature scheme so far. At 128-bit security level, our group signature size is about 144 KB for a group with $2^{20}$ members while the group signature size of the previously most compact code-based group signature constructed by the above accumulator exceeds 3200 KB.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in PKC 2024
Keywords: one-out-of-many proofs set-membership proofs ring signatures group signatures code-based cryptography
Contact author(s): liuxindong @ iie ac cn
wangliping @ iie ac cn
History: 2024-01-22: approved; 2024-01-21: received; See all versions
Short URL: https://ia.cr/2024/093
License: CC BY

BibTeX

@misc{cryptoeprint:2024/093,
      author = {Xindong Liu and Li-Ping Wang},
      title = {Short Code-based One-out-of-Many Proofs and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2024/093},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/093}},
      url = {https://eprint.iacr.org/2024/093}
}