Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-05-01

AUTHORS

Georg Fuchsbauer , Antoine Plouviez , Yannick Seurin

ABSTRACT

The Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the “ROS problem” is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal. We analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS.As ROS can be solved in sub-exponential time using Wagner’s algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL. More... »

PAGES

63-95

Book

TITLE

Advances in Cryptology – EUROCRYPT 2020

ISBN

978-3-030-45723-5
978-3-030-45724-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-45724-2_3

DOI

http://dx.doi.org/10.1007/978-3-030-45724-2_3

DIMENSIONS

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


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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "TU Wien, Vienna, Austria", 
          "id": "http://www.grid.ac/institutes/grid.5329.d", 
          "name": [
            "TU Wien, Vienna, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fuchsbauer", 
        "givenName": "Georg", 
        "id": "sg:person.013724605054.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013724605054.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ENS, CNRS, PSL, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "Inria, Paris, France", 
            "ENS, CNRS, PSL, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plouviez", 
        "givenName": "Antoine", 
        "id": "sg:person.013336667011.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013336667011.76"
        ], 
        "type": "Person"
      }, 
      {
        "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": "2020-05-01", 
    "datePublishedReg": "2020-05-01", 
    "description": "Abstract\nThe Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the \u201cROS problem\u201d is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal.\nWe analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS.As ROS can be solved in sub-exponential time using Wagner\u2019s algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL.", 
    "editor": [
      {
        "familyName": "Canteaut", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-45724-2_3", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-45723-5", 
        "978-3-030-45724-2"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2020", 
      "type": "Book"
    }, 
    "keywords": [
      "generic group model", 
      "discrete logarithm assumption", 
      "random oracle model", 
      "blind Schnorr signatures", 
      "ElGamal encryption", 
      "algebraic group model", 
      "Schnorr signature", 
      "signing protocol", 
      "one-more discrete logarithm problem", 
      "discrete logarithm problem", 
      "sub-exponential time", 
      "security analysis", 
      "CCA2 security", 
      "logarithm problem", 
      "security proof", 
      "oracle model", 
      "blockchain protocol", 
      "key encapsulation", 
      "tight security", 
      "group model", 
      "tight reduction", 
      "encryption", 
      "security", 
      "Wagner\u2019s algorithm", 
      "algorithm", 
      "ElGamal", 
      "scheme", 
      "practical relevance", 
      "protocol", 
      "rigorous proof", 
      "Schnorr", 
      "proof", 
      "model", 
      "simple modification", 
      "signatures", 
      "issuing", 
      "system", 
      "standard model", 
      "situation", 
      "time", 
      "assumption", 
      "variants", 
      "combination", 
      "relevance", 
      "analysis", 
      "ROS", 
      "DDH", 
      "modification", 
      "encapsulation", 
      "reduction", 
      "hardness", 
      "problem"
    ], 
    "name": "Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model", 
    "pagination": "63-95", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1127311205"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-45724-2_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-45724-2_3", 
      "https://app.dimensions.ai/details/publication/pub.1127311205"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_21.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-45724-2_3"
  }
]
 

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-030-45724-2_3'

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-030-45724-2_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-45724-2_3'

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-030-45724-2_3'


 

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

141 TRIPLES      22 PREDICATES      77 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-45724-2_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author Nceb0b420a0f04dd9b491ba624eb389c3
5 schema:datePublished 2020-05-01
6 schema:datePublishedReg 2020-05-01
7 schema:description Abstract The Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the “ROS problem” is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal. We analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS.As ROS can be solved in sub-exponential time using Wagner’s algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL.
8 schema:editor N844e777b77274eccb5585774e132fa31
9 schema:genre chapter
10 schema:isAccessibleForFree false
11 schema:isPartOf N6c6e54d2021745d394e83ae9983069bb
12 schema:keywords CCA2 security
13 DDH
14 ElGamal
15 ElGamal encryption
16 ROS
17 Schnorr
18 Schnorr signature
19 Wagner’s algorithm
20 algebraic group model
21 algorithm
22 analysis
23 assumption
24 blind Schnorr signatures
25 blockchain protocol
26 combination
27 discrete logarithm assumption
28 discrete logarithm problem
29 encapsulation
30 encryption
31 generic group model
32 group model
33 hardness
34 issuing
35 key encapsulation
36 logarithm problem
37 model
38 modification
39 one-more discrete logarithm problem
40 oracle model
41 practical relevance
42 problem
43 proof
44 protocol
45 random oracle model
46 reduction
47 relevance
48 rigorous proof
49 scheme
50 security
51 security analysis
52 security proof
53 signatures
54 signing protocol
55 simple modification
56 situation
57 standard model
58 sub-exponential time
59 system
60 tight reduction
61 tight security
62 time
63 variants
64 schema:name Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model
65 schema:pagination 63-95
66 schema:productId N46d8d6786eec4feca45edfed67cbb9d3
67 N5296ead096d248318d7fa7115b8d266c
68 schema:publisher N3553a664f6f74adc8ba4cfeeece8890d
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127311205
70 https://doi.org/10.1007/978-3-030-45724-2_3
71 schema:sdDatePublished 2022-12-01T06:48
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher N557f7095677944bdaf1a16a8768c36e9
74 schema:url https://doi.org/10.1007/978-3-030-45724-2_3
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N3553a664f6f74adc8ba4cfeeece8890d schema:name Springer Nature
79 rdf:type schema:Organisation
80 N436f34bcf39b4bc0b4c2a3aae3aa5c6c rdf:first sg:person.011724731171.01
81 rdf:rest rdf:nil
82 N46d8d6786eec4feca45edfed67cbb9d3 schema:name doi
83 schema:value 10.1007/978-3-030-45724-2_3
84 rdf:type schema:PropertyValue
85 N5296ead096d248318d7fa7115b8d266c schema:name dimensions_id
86 schema:value pub.1127311205
87 rdf:type schema:PropertyValue
88 N557f7095677944bdaf1a16a8768c36e9 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 N6c6e54d2021745d394e83ae9983069bb schema:isbn 978-3-030-45723-5
91 978-3-030-45724-2
92 schema:name Advances in Cryptology – EUROCRYPT 2020
93 rdf:type schema:Book
94 N844e777b77274eccb5585774e132fa31 rdf:first N8d7d15d24d634be29b41bb4d28ebd901
95 rdf:rest Nc2ea0b24219e49e6af5d99140ca6f876
96 N8d7d15d24d634be29b41bb4d28ebd901 schema:familyName Canteaut
97 schema:givenName Anne
98 rdf:type schema:Person
99 N9183287ea0c8474aa9528e94e991a221 rdf:first sg:person.013336667011.76
100 rdf:rest N436f34bcf39b4bc0b4c2a3aae3aa5c6c
101 Nc2ea0b24219e49e6af5d99140ca6f876 rdf:first Ndd14b0dd5bc5437fbd981e741584ce0c
102 rdf:rest rdf:nil
103 Nceb0b420a0f04dd9b491ba624eb389c3 rdf:first sg:person.013724605054.02
104 rdf:rest N9183287ea0c8474aa9528e94e991a221
105 Ndd14b0dd5bc5437fbd981e741584ce0c schema:familyName Ishai
106 schema:givenName Yuval
107 rdf:type schema:Person
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
112 schema:name Computation Theory and Mathematics
113 rdf:type schema:DefinedTerm
114 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
115 schema:name Data Format
116 rdf:type schema:DefinedTerm
117 sg:person.011724731171.01 schema:affiliation grid-institutes:None
118 schema:familyName Seurin
119 schema:givenName Yannick
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
121 rdf:type schema:Person
122 sg:person.013336667011.76 schema:affiliation grid-institutes:grid.4444.0
123 schema:familyName Plouviez
124 schema:givenName Antoine
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013336667011.76
126 rdf:type schema:Person
127 sg:person.013724605054.02 schema:affiliation grid-institutes:grid.5329.d
128 schema:familyName Fuchsbauer
129 schema:givenName Georg
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013724605054.02
131 rdf:type schema:Person
132 grid-institutes:None schema:alternateName ANSSI, Paris, France
133 schema:name ANSSI, Paris, France
134 rdf:type schema:Organization
135 grid-institutes:grid.4444.0 schema:alternateName ENS, CNRS, PSL, Paris, France
136 schema:name ENS, CNRS, PSL, Paris, France
137 Inria, Paris, France
138 rdf:type schema:Organization
139 grid-institutes:grid.5329.d schema:alternateName TU Wien, Vienna, Austria
140 schema:name TU Wien, Vienna, Austria
141 rdf:type schema:Organization
 




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


...