The insecurity of nyberg–rueppel and other DSA-like signature schemes with partially known nonces

Edwin El Mahassni, Phong Q. Nguyen, Igor E. Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

11 Citations (Scopus)

Abstract

It has recently been proved by Nguyen and Shparlinski that the Digital Signature Algorithm (DSA) is insecure when a few consecutive bits of the random nonces k are known for a reasonably small number of DSA signatures. This result confirmed the efficiency of some heuristic lattice attacks designed and numerically verified by Howgrave-Graham and Smart. Here, we extend the attack to the Nyberg–Rueppel variants of DSA.We use a connection with the hidden number problem introduced by Boneh and Venkatesan and new bounds of exponential sums which might be of independent interest.

Original languageEnglish
Title of host publicationCryptography and Lattices
Subtitle of host publicationInternational Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers
EditorsJoseph H. Silverman
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages97-109
Number of pages13
ISBN (Electronic)9783540446705
ISBN (Print)3540424881, 9783540424888
DOIs
Publication statusPublished - Mar 2001
EventInternational Conference on Cryptography and Lattices, CaLC - 2001 - Providence, United States
Duration: 29 Mar 200130 Mar 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2146
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

OtherInternational Conference on Cryptography and Lattices, CaLC - 2001
CountryUnited States
CityProvidence
Period29/03/0130/03/01

    Fingerprint

Keywords

  • Closest vector problem
  • DSA
  • Exponential sums
  • Hidden number problem

Cite this

Mahassni, E. E., Nguyen, P. Q., & Shparlinski, I. E. (2001). The insecurity of nyberg–rueppel and other DSA-like signature schemes with partially known nonces. In J. H. Silverman (Ed.), Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers (pp. 97-109). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2146). Berlin; New York: Springer, Springer Nature. https://doi.org/10.1007/3-540-44670-2_9