On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Yannick Seurin

ABSTRACT

The Schnorr signature scheme has been known to be provably secure in the Random Oracle Model under the Discrete Logarithm (DL) assumption since the work of Pointcheval and Stern (EUROCRYPT ’96), at the price of a very loose reduction though: if there is a forger making at most qh random oracle queries, and forging signatures with probability εF, then the Forking Lemma tells that one can compute discrete logarithms with constant probability by rewinding the forger \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}(q_h/\varepsilon_F)$\end{document} times. In other words, the security reduction loses a factor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}(q_h)$\end{document} in its time-to-success ratio. This is rather unsatisfactory since qh may be quite large. Yet Paillier and Vergnaud (ASIACRYPT 2005) later showed that under the One More Discrete Logarithm (OMDL) assumption, any algebraic reduction must lose a factor at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{1/2}$\end{document} in its time-to-success ratio. This was later improved by Garg et al. (CRYPTO 2008) to a factor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{2/3}$\end{document}. Up to now, the gap between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{2/3}$\end{document} and qh remained open. In this paper, we show that the security proof using the Forking Lemma is essentially the best possible. Namely, under the OMDL assumption, any algebraic reduction must lose a factor f(εF)qh in its time-to-success ratio, where f ≤ 1 is a function that remains close to 1 as long as εF is noticeably smaller than 1. Using a formulation in terms of expected-time and queries algorithms, we obtain an optimal loss factor Ω(qh), independently of εF. These results apply to other signature schemes based on one-way group homomorphisms, such as the Guillou-Quisquater signature scheme. More... »

PAGES

554-571

Book

TITLE

Advances in Cryptology – EUROCRYPT 2012

ISBN

978-3-642-29010-7
978-3-642-29011-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-29011-4_33

DOI

http://dx.doi.org/10.1007/978-3-642-29011-4_33

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "ANSSI, Paris, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ANSSI, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seurin", 
        "givenName": "Yannick", 
        "id": "sg:person.011724731171.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "The Schnorr signature scheme has been known to be provably secure in the Random Oracle Model under the Discrete Logarithm (DL) assumption since the work of Pointcheval and Stern (EUROCRYPT \u201996), at the price of a very loose reduction though: if there is a forger making at most qh random oracle queries, and forging signatures with probability \u03b5F, then the Forking Lemma tells that one can compute discrete logarithms with constant probability by rewinding the forger \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}${\\mathcal O}(q_h/\\varepsilon_F)$\\end{document} times. In other words, the security reduction loses a factor \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}${\\mathcal O}(q_h)$\\end{document} in its time-to-success ratio. This is rather unsatisfactory since qh may be quite large. Yet Paillier and Vergnaud (ASIACRYPT 2005) later showed that under the One More Discrete Logarithm (OMDL) assumption, any algebraic reduction must lose a factor at least \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$q_h^{1/2}$\\end{document} in its time-to-success ratio. This was later improved by Garg\u00a0et al. (CRYPTO 2008) to a factor \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$q_h^{2/3}$\\end{document}. Up to now, the gap between \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$q_h^{2/3}$\\end{document} and qh remained open. In this paper, we show that the security proof using the Forking Lemma is essentially the best possible. Namely, under the OMDL assumption, any algebraic reduction must lose a factor f(\u03b5F)qh in its time-to-success ratio, where f\u2009\u2264\u20091 is a function that remains close to 1 as long as \u03b5F is noticeably smaller than 1. Using a formulation in terms of expected-time and queries algorithms, we obtain an optimal loss factor \u03a9(qh), independently of \u03b5F. These results apply to other signature schemes based on one-way group homomorphisms, such as the Guillou-Quisquater signature scheme.", 
    "editor": [
      {
        "familyName": "Pointcheval", 
        "givenName": "David", 
        "type": "Person"
      }, 
      {
        "familyName": "Johansson", 
        "givenName": "Thomas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-29011-4_33", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-29010-7", 
        "978-3-642-29011-4"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2012", 
      "type": "Book"
    }, 
    "keywords": [
      "algebraic reduction", 
      "random oracle queries", 
      "Guillou-Quisquater signature scheme", 
      "group homomorphism", 
      "discrete logarithm assumption", 
      "random oracle model", 
      "constant probability", 
      "oracle model", 
      "lemma", 
      "signature scheme", 
      "discrete logarithm", 
      "oracle queries", 
      "loose reduction", 
      "scheme", 
      "Schnorr signature scheme", 
      "assumption", 
      "exact security", 
      "homomorphism", 
      "et al", 
      "forking lemma", 
      "success ratio", 
      "loss factor", 
      "model", 
      "security reduction", 
      "formulation", 
      "probability", 
      "\u03b5f", 
      "security proof", 
      "proof", 
      "Garg", 
      "logarithm", 
      "QH", 
      "Stern", 
      "Pointcheval", 
      "terms", 
      "function", 
      "signatures", 
      "time", 
      "al", 
      "ratio", 
      "gap", 
      "work", 
      "results", 
      "Paillier", 
      "prices", 
      "Vergnaud", 
      "reduction", 
      "forger", 
      "security", 
      "factors", 
      "queries", 
      "words", 
      "paper"
    ], 
    "name": "On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model", 
    "pagination": "554-571", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019042387"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-29011-4_33"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-29011-4_33", 
      "https://app.dimensions.ai/details/publication/pub.1019042387"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_258.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-29011-4_33"
  }
]
 

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.1007/978-3-642-29011-4_33'

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.1007/978-3-642-29011-4_33'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-29011-4_33'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-29011-4_33'


 

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

117 TRIPLES      22 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-29011-4_33 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd94b172205524ef39ddad5bb5e8532fd
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description The Schnorr signature scheme has been known to be provably secure in the Random Oracle Model under the Discrete Logarithm (DL) assumption since the work of Pointcheval and Stern (EUROCRYPT ’96), at the price of a very loose reduction though: if there is a forger making at most qh random oracle queries, and forging signatures with probability εF, then the Forking Lemma tells that one can compute discrete logarithms with constant probability by rewinding the forger \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}(q_h/\varepsilon_F)$\end{document} times. In other words, the security reduction loses a factor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}(q_h)$\end{document} in its time-to-success ratio. This is rather unsatisfactory since qh may be quite large. Yet Paillier and Vergnaud (ASIACRYPT 2005) later showed that under the One More Discrete Logarithm (OMDL) assumption, any algebraic reduction must lose a factor at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{1/2}$\end{document} in its time-to-success ratio. This was later improved by Garg et al. (CRYPTO 2008) to a factor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{2/3}$\end{document}. Up to now, the gap between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$q_h^{2/3}$\end{document} and qh remained open. In this paper, we show that the security proof using the Forking Lemma is essentially the best possible. Namely, under the OMDL assumption, any algebraic reduction must lose a factor f(εF)qh in its time-to-success ratio, where f ≤ 1 is a function that remains close to 1 as long as εF is noticeably smaller than 1. Using a formulation in terms of expected-time and queries algorithms, we obtain an optimal loss factor Ω(qh), independently of εF. These results apply to other signature schemes based on one-way group homomorphisms, such as the Guillou-Quisquater signature scheme.
7 schema:editor N3434ff6a8662473c9ded520d1606a7e6
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N49e791cfe7e8494b8b736df70b534171
11 schema:keywords Garg
12 Guillou-Quisquater signature scheme
13 Paillier
14 Pointcheval
15 QH
16 Schnorr signature scheme
17 Stern
18 Vergnaud
19 al
20 algebraic reduction
21 assumption
22 constant probability
23 discrete logarithm
24 discrete logarithm assumption
25 et al
26 exact security
27 factors
28 forger
29 forking lemma
30 formulation
31 function
32 gap
33 group homomorphism
34 homomorphism
35 lemma
36 logarithm
37 loose reduction
38 loss factor
39 model
40 oracle model
41 oracle queries
42 paper
43 prices
44 probability
45 proof
46 queries
47 random oracle model
48 random oracle queries
49 ratio
50 reduction
51 results
52 scheme
53 security
54 security proof
55 security reduction
56 signature scheme
57 signatures
58 success ratio
59 terms
60 time
61 words
62 work
63 εf
64 schema:name On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model
65 schema:pagination 554-571
66 schema:productId N992001e13463416ca70f60dfe0397bb0
67 Nfddf9b07f94c4b7c8833d5b79ed67dc4
68 schema:publisher N880e2ea1a62d4be48f82d32565ebb72f
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019042387
70 https://doi.org/10.1007/978-3-642-29011-4_33
71 schema:sdDatePublished 2022-11-24T21:14
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher Nc39ce8ad67724a34950d4ff65bc37274
74 schema:url https://doi.org/10.1007/978-3-642-29011-4_33
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N108ce4e78a984059b8f4e5874c2f05cf rdf:first Na411e06d74f44aa882c080879753ba54
79 rdf:rest rdf:nil
80 N3434ff6a8662473c9ded520d1606a7e6 rdf:first Na936758cba264f96916bf3277f9fde76
81 rdf:rest N108ce4e78a984059b8f4e5874c2f05cf
82 N49e791cfe7e8494b8b736df70b534171 schema:isbn 978-3-642-29010-7
83 978-3-642-29011-4
84 schema:name Advances in Cryptology – EUROCRYPT 2012
85 rdf:type schema:Book
86 N880e2ea1a62d4be48f82d32565ebb72f schema:name Springer Nature
87 rdf:type schema:Organisation
88 N992001e13463416ca70f60dfe0397bb0 schema:name doi
89 schema:value 10.1007/978-3-642-29011-4_33
90 rdf:type schema:PropertyValue
91 Na411e06d74f44aa882c080879753ba54 schema:familyName Johansson
92 schema:givenName Thomas
93 rdf:type schema:Person
94 Na936758cba264f96916bf3277f9fde76 schema:familyName Pointcheval
95 schema:givenName David
96 rdf:type schema:Person
97 Nc39ce8ad67724a34950d4ff65bc37274 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Nd94b172205524ef39ddad5bb5e8532fd rdf:first sg:person.011724731171.01
100 rdf:rest rdf:nil
101 Nfddf9b07f94c4b7c8833d5b79ed67dc4 schema:name dimensions_id
102 schema:value pub.1019042387
103 rdf:type schema:PropertyValue
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
108 schema:name Computation Theory and Mathematics
109 rdf:type schema:DefinedTerm
110 sg:person.011724731171.01 schema:affiliation grid-institutes:None
111 schema:familyName Seurin
112 schema:givenName Yannick
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
114 rdf:type schema:Person
115 grid-institutes:None schema:alternateName ANSSI, Paris, France
116 schema:name ANSSI, Paris, France
117 rdf:type schema:Organization
 




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


...