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 proofsset-membership proofsring signaturesgroup signaturescode-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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/093}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.