The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2003-09

AUTHORS

Phong Q. Nguyen, Igor E. Shparlinski

ABSTRACT

Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about log1/2q, but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA). More... »

PAGES

201-217

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1025436905711

DOI

http://dx.doi.org/10.1023/a:1025436905711

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1007546108


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "D\u00e9partement d'Informatique, \u00e9cole Normale Sup\u00e9rieure, 45, rue d'Ulm, 75230, Paris Cedex 05, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nguyen", 
        "givenName": "Phong Q.", 
        "id": "sg:person.011726717205.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011726717205.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Macquarie University", 
          "id": "https://www.grid.ac/institutes/grid.1004.5", 
          "name": [
            "Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shparlinski", 
        "givenName": "Igor E.", 
        "id": "sg:person.013727467104.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013727467104.70"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-44670-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005490755", 
          "https://doi.org/10.1007/3-540-44670-2_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1991-1028291-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008244538"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/10722028_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012154622", 
          "https://doi.org/10.1007/10722028_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/10722028_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012154622", 
          "https://doi.org/10.1007/10722028_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0052242", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019436225", 
          "https://doi.org/10.1007/bfb0052242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0052242", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019436225", 
          "https://doi.org/10.1007/bfb0052242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1008354106356", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020246677", 
          "https://doi.org/10.1023/a:1008354106356"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44670-2_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028664185", 
          "https://doi.org/10.1007/3-540-44670-2_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0055739", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032238614", 
          "https://doi.org/10.1007/bfb0055739"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00145-002-0021-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032609859", 
          "https://doi.org/10.1007/s00145-002-0021-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9904-1978-14532-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038180486"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0025-5718-01-01358-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043651625"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s102070100002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043653709", 
          "https://doi.org/10.1007/s102070100002"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01457454", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048792211", 
          "https://doi.org/10.1007/bf01457454"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01457454", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048792211", 
          "https://doi.org/10.1007/bf01457454"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/10722028_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051705346", 
          "https://doi.org/10.1007/10722028_24"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003-09", 
    "datePublishedReg": "2003-09-01", 
    "description": "Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about log1/2q, but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA).", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1025436905711", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136552", 
        "issn": [
          "0925-1022", 
          "1573-7586"
        ], 
        "name": "Designs, Codes and Cryptography", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "30"
      }
    ], 
    "name": "The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces", 
    "pagination": "201-217", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "23f1c5f320b11e74504bb9a178d8e315d4003a7ef50dca8de550ca80f7d2aebf"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1025436905711"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007546108"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1025436905711", 
      "https://app.dimensions.ai/details/publication/pub.1007546108"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:29", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000503.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FA%3A1025436905711"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1025436905711'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1025436905711'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1025436905711'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1025436905711'


 

This table displays all metadata directly associated to this object as RDF triples.

119 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1025436905711 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N833eeec0fe744264be98e0e8d0bfc9ec
4 schema:citation sg:pub.10.1007/10722028_24
5 sg:pub.10.1007/10722028_4
6 sg:pub.10.1007/3-540-44670-2_12
7 sg:pub.10.1007/3-540-44670-2_9
8 sg:pub.10.1007/bf01457454
9 sg:pub.10.1007/bfb0052242
10 sg:pub.10.1007/bfb0055739
11 sg:pub.10.1007/s00145-002-0021-3
12 sg:pub.10.1007/s102070100002
13 sg:pub.10.1023/a:1008354106356
14 https://doi.org/10.1090/s0002-9904-1978-14532-7
15 https://doi.org/10.1090/s0002-9939-1991-1028291-1
16 https://doi.org/10.1090/s0025-5718-01-01358-8
17 schema:datePublished 2003-09
18 schema:datePublishedReg 2003-09-01
19 schema:description Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about log1/2q, but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA).
20 schema:genre research_article
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N38a61db531674b4a9c9f3c5869a02777
24 N5fcc05e826d4420d99e1b301bc6c2220
25 sg:journal.1136552
26 schema:name The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces
27 schema:pagination 201-217
28 schema:productId N39f4afe236744a9c83ada96484030c30
29 N6ffbbb7da0454cfdbc834af85971e95d
30 Nec0fa200556e40f8972b4ee7a25104be
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007546108
32 https://doi.org/10.1023/a:1025436905711
33 schema:sdDatePublished 2019-04-10T17:29
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N81338cbd4b50468db02103de4a701be8
36 schema:url http://link.springer.com/10.1023%2FA%3A1025436905711
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N38a61db531674b4a9c9f3c5869a02777 schema:volumeNumber 30
41 rdf:type schema:PublicationVolume
42 N39f4afe236744a9c83ada96484030c30 schema:name doi
43 schema:value 10.1023/a:1025436905711
44 rdf:type schema:PropertyValue
45 N57e2440e00fa4065afc6f7b43a527d05 schema:name Département d'Informatique, école Normale Supérieure, 45, rue d'Ulm, 75230, Paris Cedex 05, France
46 rdf:type schema:Organization
47 N5fcc05e826d4420d99e1b301bc6c2220 schema:issueNumber 2
48 rdf:type schema:PublicationIssue
49 N6ffbbb7da0454cfdbc834af85971e95d schema:name dimensions_id
50 schema:value pub.1007546108
51 rdf:type schema:PropertyValue
52 N81338cbd4b50468db02103de4a701be8 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N833eeec0fe744264be98e0e8d0bfc9ec rdf:first sg:person.011726717205.45
55 rdf:rest Na348ec860a4c46b3be9bb30660f6b0dc
56 Na348ec860a4c46b3be9bb30660f6b0dc rdf:first sg:person.013727467104.70
57 rdf:rest rdf:nil
58 Nec0fa200556e40f8972b4ee7a25104be schema:name readcube_id
59 schema:value 23f1c5f320b11e74504bb9a178d8e315d4003a7ef50dca8de550ca80f7d2aebf
60 rdf:type schema:PropertyValue
61 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
62 schema:name Mathematical Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
65 schema:name Pure Mathematics
66 rdf:type schema:DefinedTerm
67 sg:journal.1136552 schema:issn 0925-1022
68 1573-7586
69 schema:name Designs, Codes and Cryptography
70 rdf:type schema:Periodical
71 sg:person.011726717205.45 schema:affiliation N57e2440e00fa4065afc6f7b43a527d05
72 schema:familyName Nguyen
73 schema:givenName Phong Q.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011726717205.45
75 rdf:type schema:Person
76 sg:person.013727467104.70 schema:affiliation https://www.grid.ac/institutes/grid.1004.5
77 schema:familyName Shparlinski
78 schema:givenName Igor E.
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013727467104.70
80 rdf:type schema:Person
81 sg:pub.10.1007/10722028_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051705346
82 https://doi.org/10.1007/10722028_24
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/10722028_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012154622
85 https://doi.org/10.1007/10722028_4
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/3-540-44670-2_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028664185
88 https://doi.org/10.1007/3-540-44670-2_12
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/3-540-44670-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005490755
91 https://doi.org/10.1007/3-540-44670-2_9
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/bf01457454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048792211
94 https://doi.org/10.1007/bf01457454
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/bfb0052242 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019436225
97 https://doi.org/10.1007/bfb0052242
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bfb0055739 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032238614
100 https://doi.org/10.1007/bfb0055739
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s00145-002-0021-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032609859
103 https://doi.org/10.1007/s00145-002-0021-3
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/s102070100002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043653709
106 https://doi.org/10.1007/s102070100002
107 rdf:type schema:CreativeWork
108 sg:pub.10.1023/a:1008354106356 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020246677
109 https://doi.org/10.1023/a:1008354106356
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1090/s0002-9904-1978-14532-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038180486
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1090/s0002-9939-1991-1028291-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008244538
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1090/s0025-5718-01-01358-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043651625
116 rdf:type schema:CreativeWork
117 https://www.grid.ac/institutes/grid.1004.5 schema:alternateName Macquarie University
118 schema:name Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia
119 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...