Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices

Eric Sageloli; Pierre Pébereau; Pierrick Méaux; Céline Chevalier

Paper 2023/489

Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices

Eric Sageloli, Thales (France)

Pierre Pébereau, Thales (France), Sorbonne University, Laboratoire de Recherche en Informatique de Paris 6, French National Centre for Scientific Research

Pierrick Méaux, University of Luxembourg

Céline Chevalier, École Normale Supérieure - PSL, CNRS, CRED (Centre de Recherche en Economie et Droit), PSL University

Abstract

We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length). Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from non-adaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation. On the whole, we get better security bounds, shorter signatures and faster algorithms.

Note: Some fixed typos; Details added about hash simulation in demonstrations of Theorems 2 and 3.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. ACNS 2023
Keywords: Identity-based signatures tight security short integer solution assumption lattices QROM
Contact author(s): eric sageloli @ protonmail com
pierre pebereau @ lip fr
pierrick meaux @ uni lu
celine chevalier @ ens fr
History: 2023-05-26: last of 2 revisions; 2023-04-04: received; See all versions
Short URL: https://ia.cr/2023/489
License: CC BY

BibTeX

@misc{cryptoeprint:2023/489,
      author = {Eric Sageloli and Pierre Pébereau and Pierrick Méaux and Céline Chevalier},
      title = {Shorter and Faster Identity-Based Signatures with Tight Security in the (Q){ROM} from Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/489},
      year = {2023},
      url = {https://eprint.iacr.org/2023/489}
}