Paper 2013/281

Adapting Lyubashevsky’s Signature Schemes to the Ring Signature Setting

Carlos Aguilar-Melchor, Slim Bettaieb, Xavier Boyen, Laurent Fousse, and Philippe Gaborit

Abstract

Basing signature schemes on strong lattice problems has been a long standing open issue. Today, two families of lattice-based signature schemes are known: the ones based on the hash-and-sign construction of Gentry et al.; and Lyubashevsky’s schemes, which are based on the Fiat-Shamir framework. In this paper we show for the first time how to adapt the schemes of Lyubashevsky to the ring signature setting. In particular we transform the scheme of ASIACRYPT 2009 into a ring signature scheme that provides strong properties of security under the random oracle model. Anonymity is ensured in the sense that signatures of different users are within negligible statistical distance even under full key exposure. In fact, the scheme satisfies a notion which is stronger than the classical full key exposure setting as even if the keypair of the signing user is adversarially chosen, the statistical distance between signatures of different users remains negligible. Considering unforgeability, the best lattice-based ring signature schemes provide either unforgeability against arbitrary chosen subring attacks or insider corruption in log-sized rings. In this paper we present two variants of our scheme. In the basic one, unforgeability is ensured in those two settings. Increasing signature and key sizes by a factor k (typically 80 − 100), we provide a variant in which unforgeability is ensured against insider corruption attacks for arbitrary rings. The technique used is pretty general and can be adapted to other existing schemes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Ring signatureslattices
Contact author(s)
carlos aguilar @ unilim fr
History
2013-05-16: received
Short URL
https://ia.cr/2013/281
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/281,
      author = {Carlos Aguilar-Melchor and Slim Bettaieb and Xavier Boyen and Laurent Fousse and Philippe Gaborit},
      title = {Adapting Lyubashevsky’s Signature Schemes to the Ring Signature Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2013/281},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/281}},
      url = {https://eprint.iacr.org/2013/281}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.