Practical signatures from the partial fourier recovery problem revisited: A provably-secure and gaussian-distributed construction

Xingye Lu, Zhenfei Zhang, Man Ho Au

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)

Abstract

In this paper, we present a new lattice-based signature scheme, PASSG, based on signatures from the partial Fourier recovery problem PASSRS introduced by Hoffstein et al. in 2014. Same as PASSRS, security of our construction relies on the average-case hardness of a special kind of Short Integer Solution (SIS) problem and the hardness of partial Fourier recovery problem. PASSG improves PASSRS in two aspects. Firstly, unlike PASSRS, PASSG comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2008 to reduce the signature size and improve the efficiency. More concretely, signatures of PASSG are Gaussian-distributed and is more space efficient. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 23rd Australasian Conference, ACISP 2018, Proceedings
EditorsWilly Susilo, Guomin Yang
PublisherSpringer Verlag
Pages813-820
Number of pages8
ISBN (Print)9783319936376
DOIs
Publication statusPublished - 2018
Event23rd Australasian Conference on Information Security and Privacy, ACISP 2018 - Wollongong, Australia
Duration: 11 Jul 201813 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10946 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd Australasian Conference on Information Security and Privacy, ACISP 2018
Country/TerritoryAustralia
CityWollongong
Period11/07/1813/07/18

Keywords

  • Digital signature
  • Lattice-based cryptography
  • Partial fourier recovery problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Practical signatures from the partial fourier recovery problem revisited: A provably-secure and gaussian-distributed construction'. Together they form a unique fingerprint.

Cite this