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

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

doi:10.1007/3-540-44670-2_9

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

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

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Cryptography and Lattices
Subtitle of host publication	International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers
Editors	Joseph H. Silverman
Place of Publication	Berlin; New York
Publisher	Springer, Springer Nature
Pages	97-109
Number of pages	13
ISBN (Electronic)	9783540446705
ISBN (Print)	3540424881, 9783540424888
DOIs	https://doi.org/10.1007/3-540-44670-2_9
Publication status	Published - Mar 2001
Event	International Conference on Cryptography and Lattices, CaLC - 2001 - Providence, United States Duration: 29 Mar 2001 → 30 Mar 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2146
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	International Conference on Cryptography and Lattices, CaLC - 2001
Country	United States
City	Providence
Period	29/03/01 → 30/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

Mahassni, Edwin El ; Nguyen, Phong Q. ; Shparlinski, Igor E. / The insecurity of nyberg–rueppel and other DSA-like signature schemes with partially known nonces. Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers. editor / Joseph H. Silverman. Berlin; New York : Springer, Springer Nature, 2001. pp. 97-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0a03a526c36d4d99b6d1d6b4a9944210,

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

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.",

keywords = "Closest vector problem, DSA, Exponential sums, Hidden number problem",

author = "Mahassni, {Edwin El} and Nguyen, {Phong Q.} and Shparlinski, {Igor E.}",

year = "2001",

month = "3",

doi = "10.1007/3-540-44670-2_9",

language = "English",

isbn = "3540424881",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "97--109",

editor = "Silverman, {Joseph H.}",

booktitle = "Cryptography and Lattices",

address = "United States",

}

Mahassni, EE, Nguyen, PQ & Shparlinski, IE 2001, The insecurity of nyberg–rueppel and other DSA-like signature schemes with partially known nonces. in JH Silverman (ed.), Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2146, Springer, Springer Nature, Berlin; New York, pp. 97-109, International Conference on Cryptography and Lattices, CaLC - 2001, Providence, United States, 29/03/01. https://doi.org/10.1007/3-540-44670-2_9

The insecurity of nyberg–rueppel and other DSA-like signature schemes with partially known nonces. / Mahassni, Edwin El; Nguyen, Phong Q.; Shparlinski, Igor E.

Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers. ed. / Joseph H. Silverman. Berlin; New York : Springer, Springer Nature, 2001. p. 97-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2146).

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

TY - GEN

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

AU - Mahassni, Edwin El

AU - Nguyen, Phong Q.

AU - Shparlinski, Igor E.

PY - 2001/3

Y1 - 2001/3

N2 - 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.

AB - 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.

KW - Closest vector problem

KW - DSA

KW - Exponential sums

KW - Hidden number problem

UR - http://www.scopus.com/inward/record.url?scp=84958967057&partnerID=8YFLogxK

U2 - 10.1007/3-540-44670-2_9

DO - 10.1007/3-540-44670-2_9

M3 - Conference proceeding contribution

SN - 3540424881

SN - 9783540424888

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 109

BT - Cryptography and Lattices

A2 - Silverman, Joseph H.

PB - Springer, Springer Nature

CY - Berlin; New York

ER -

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

Access to Document

10.1007/3-540-44670-2_9

Link to publication in Scopus