Public Key Compression for Constrained Linear Signature Schemes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2019-01-13

AUTHORS

Ward Beullens , Bart Preneel , Alan Szepieniec

ABSTRACT

We formalize the notion of a constrained linear trapdoor as an abstract strategy for the generation of signature schemes, concrete instantiations of which can be found in MQ-based, code-based, and lattice-based cryptography. Moreover, we revisit and expand on a transformation by Szepieniec et al. [39] to shrink the public key at the cost of a larger signature while reducing their combined size. This transformation can be used in a way that is provably secure in the random oracle model, and in a more aggressive variant whose security remained unproven. In this paper we show that this transformation applies to any constrained linear trapdoor signature scheme, and prove the security of the first mode in the quantum random oracle model. Moreover, we identify a property of constrained linear trapdoors that is sufficient (and necessary) for the more aggressive variant to be secure in the quantum random oracle model. We apply the transformation to an MQ-based scheme, a code-based scheme and a lattice-based scheme targeting 128-bits of post quantum security, and we show that in some cases the combined size of a signature and a public key can be reduced by more than a factor 300. More... »

PAGES

300-321

Book

TITLE

Selected Areas in Cryptography – SAC 2018

ISBN

978-3-030-10969-1
978-3-030-10970-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-10970-7_14

DOI

http://dx.doi.org/10.1007/978-3-030-10970-7_14

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "imec-COSIC KU\u00a0Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC KU\u00a0Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Beullens", 
        "givenName": "Ward", 
        "id": "sg:person.016403245376.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016403245376.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "imec-COSIC KU\u00a0Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC KU\u00a0Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "imec-COSIC KU\u00a0Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC KU\u00a0Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szepieniec", 
        "givenName": "Alan", 
        "id": "sg:person.013013776035.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2019-01-13", 
    "datePublishedReg": "2019-01-13", 
    "description": "We formalize the notion of a constrained linear trapdoor as an abstract strategy for the generation of signature schemes, concrete instantiations of which can be found in MQ-based, code-based, and lattice-based cryptography. Moreover, we revisit and expand on a transformation by Szepieniec\u00a0et al.\u00a0[39] to shrink the public key at the cost of a larger signature while reducing their combined size. This transformation can be used in a way that is provably secure in the random oracle model, and in a more aggressive variant whose security remained unproven. In this paper we show that this transformation applies to any constrained linear trapdoor signature scheme, and prove the security of the first mode in the quantum random oracle model. Moreover, we identify a property of constrained linear trapdoors that is sufficient (and necessary) for the more aggressive variant to be secure in the quantum random oracle model. We apply the transformation to an MQ-based scheme, a code-based scheme and a lattice-based scheme targeting 128-bits of post quantum security, and we show that in some cases the combined size of a signature and a public key can be reduced by more than a factor 300.", 
    "editor": [
      {
        "familyName": "Cid", 
        "givenName": "Carlos", 
        "type": "Person"
      }, 
      {
        "familyName": "Jacobson", 
        "givenName": "Michael J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-10970-7_14", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-10969-1", 
        "978-3-030-10970-7"
      ], 
      "name": "Selected Areas in Cryptography \u2013 SAC 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "quantum random oracle model", 
      "random oracle model", 
      "Public Key Compression", 
      "lattice-based cryptography", 
      "oracle model", 
      "lattice-based schemes", 
      "quantum security", 
      "post-quantum security", 
      "signature scheme", 
      "scheme", 
      "large signatures", 
      "factor 300", 
      "code-based schemes", 
      "first mode", 
      "et al", 
      "model", 
      "transformation", 
      "concrete instantiation", 
      "cryptography", 
      "public key", 
      "MQ", 
      "abstract strategy", 
      "properties", 
      "signatures", 
      "notion", 
      "size", 
      "key compression", 
      "al", 
      "mode", 
      "cases", 
      "variants", 
      "cost", 
      "instantiation", 
      "way", 
      "trapdoor", 
      "generation", 
      "key", 
      "security", 
      "compression", 
      "strategies", 
      "paper", 
      "aggressive variant"
    ], 
    "name": "Public Key Compression for Constrained Linear Signature Schemes", 
    "pagination": "300-321", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1111389530"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-10970-7_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-10970-7_14", 
      "https://app.dimensions.ai/details/publication/pub.1111389530"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_456.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-10970-7_14"
  }
]
 

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-10970-7_14'

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-10970-7_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-10970-7_14'

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-10970-7_14'


 

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

120 TRIPLES      22 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-10970-7_14 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N3edd7b9e6be943a7aac2457602661db0
4 schema:datePublished 2019-01-13
5 schema:datePublishedReg 2019-01-13
6 schema:description We formalize the notion of a constrained linear trapdoor as an abstract strategy for the generation of signature schemes, concrete instantiations of which can be found in MQ-based, code-based, and lattice-based cryptography. Moreover, we revisit and expand on a transformation by Szepieniec et al. [39] to shrink the public key at the cost of a larger signature while reducing their combined size. This transformation can be used in a way that is provably secure in the random oracle model, and in a more aggressive variant whose security remained unproven. In this paper we show that this transformation applies to any constrained linear trapdoor signature scheme, and prove the security of the first mode in the quantum random oracle model. Moreover, we identify a property of constrained linear trapdoors that is sufficient (and necessary) for the more aggressive variant to be secure in the quantum random oracle model. We apply the transformation to an MQ-based scheme, a code-based scheme and a lattice-based scheme targeting 128-bits of post quantum security, and we show that in some cases the combined size of a signature and a public key can be reduced by more than a factor 300.
7 schema:editor N48c465babf2c400690bfcc7b2d1232b3
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nd7d484c677d24e45ae383409affdf468
11 schema:keywords MQ
12 Public Key Compression
13 abstract strategy
14 aggressive variant
15 al
16 cases
17 code-based schemes
18 compression
19 concrete instantiation
20 cost
21 cryptography
22 et al
23 factor 300
24 first mode
25 generation
26 instantiation
27 key
28 key compression
29 large signatures
30 lattice-based cryptography
31 lattice-based schemes
32 mode
33 model
34 notion
35 oracle model
36 paper
37 post-quantum security
38 properties
39 public key
40 quantum random oracle model
41 quantum security
42 random oracle model
43 scheme
44 security
45 signature scheme
46 signatures
47 size
48 strategies
49 transformation
50 trapdoor
51 variants
52 way
53 schema:name Public Key Compression for Constrained Linear Signature Schemes
54 schema:pagination 300-321
55 schema:productId N1d5fa334e8654bda9c75bd1a10318097
56 N5a489da347494d1ea3119862fe152975
57 schema:publisher N70496497e5b6441e8fc06864e81a66c6
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111389530
59 https://doi.org/10.1007/978-3-030-10970-7_14
60 schema:sdDatePublished 2022-10-01T06:59
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N1dec3555bf7448f8976dfdd9cc86e1c2
63 schema:url https://doi.org/10.1007/978-3-030-10970-7_14
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N1d5fa334e8654bda9c75bd1a10318097 schema:name doi
68 schema:value 10.1007/978-3-030-10970-7_14
69 rdf:type schema:PropertyValue
70 N1dec3555bf7448f8976dfdd9cc86e1c2 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N3edd7b9e6be943a7aac2457602661db0 rdf:first sg:person.016403245376.49
73 rdf:rest Nb43f942aa4c744cf919aaa6645e42e5c
74 N48c465babf2c400690bfcc7b2d1232b3 rdf:first Nfd3b712df8fb47ddb1d20f4250b29c5e
75 rdf:rest Na249c586d3444c1887683eb0728d6c08
76 N5a489da347494d1ea3119862fe152975 schema:name dimensions_id
77 schema:value pub.1111389530
78 rdf:type schema:PropertyValue
79 N70496497e5b6441e8fc06864e81a66c6 schema:name Springer Nature
80 rdf:type schema:Organisation
81 N901cc97f9a6440f0ac8c3d42eb454ea4 rdf:first sg:person.013013776035.00
82 rdf:rest rdf:nil
83 Na249c586d3444c1887683eb0728d6c08 rdf:first Nf5b1578adcb84caa9c742906ddd5f03a
84 rdf:rest rdf:nil
85 Nb43f942aa4c744cf919aaa6645e42e5c rdf:first sg:person.011115044357.39
86 rdf:rest N901cc97f9a6440f0ac8c3d42eb454ea4
87 Nd7d484c677d24e45ae383409affdf468 schema:isbn 978-3-030-10969-1
88 978-3-030-10970-7
89 schema:name Selected Areas in Cryptography – SAC 2018
90 rdf:type schema:Book
91 Nf5b1578adcb84caa9c742906ddd5f03a schema:familyName Jacobson
92 schema:givenName Michael J.
93 rdf:type schema:Person
94 Nfd3b712df8fb47ddb1d20f4250b29c5e schema:familyName Cid
95 schema:givenName Carlos
96 rdf:type schema:Person
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
101 schema:name Data Format
102 rdf:type schema:DefinedTerm
103 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
104 schema:familyName Preneel
105 schema:givenName Bart
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
107 rdf:type schema:Person
108 sg:person.013013776035.00 schema:affiliation grid-institutes:grid.5596.f
109 schema:familyName Szepieniec
110 schema:givenName Alan
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00
112 rdf:type schema:Person
113 sg:person.016403245376.49 schema:affiliation grid-institutes:grid.5596.f
114 schema:familyName Beullens
115 schema:givenName Ward
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016403245376.49
117 rdf:type schema:Person
118 grid-institutes:grid.5596.f schema:alternateName imec-COSIC KU Leuven, Leuven, Belgium
119 schema:name imec-COSIC KU Leuven, Leuven, Belgium
120 rdf:type schema:Organization
 




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


...