G+G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians

Julien Devevey; Alain Passelègue; Damien Stehlé

Paper 2023/1477

G+G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians

Julien Devevey, École Normale Supérieure de Lyon

Alain Passelègue, French Institute for Research in Computer Science and Automation, École Normale Supérieure de Lyon, CryptoLab, Inc.

Damien Stehlé, École Normale Supérieure de Lyon, CryptoLab, Inc.

Abstract

We describe an adaptation of Schnorr's signature to the lattice setting, which relies on Gaussian convolution rather than flooding or rejection sampling as previous approaches. It does not involve any abort, can be proved secure in the ROM and QROM using existing analyses of the Fiat-Shamir transform, and enjoys smaller signature sizes (both asymptotically and for concrete security levels).

Note: Fixed parameter sizes. Fixed minor editorial mistakes.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in ASIACRYPT 2023
Keywords: Fiat-Shamir Digital Signature Lattice-based cryptography convolution flooding rejection sampling sigma protocol
Contact author(s): julien devevey @ ens-lyon fr
alain passelegue @ cryptolab co kr
damien stehle @ cryptolab co kr
History: 2023-11-13: revised; 2023-09-26: received; See all versions
Short URL: https://ia.cr/2023/1477
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1477,
      author = {Julien Devevey and Alain Passelègue and Damien Stehlé},
      title = {G+G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1477},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1477}
}