Short Solutions to Nonlinear Systems of Equations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-02-28

AUTHORS

Alan Szepieniec , Bart Preneel

ABSTRACT

This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or Gröbner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility. More... »

PAGES

71-90

Book

TITLE

Number-Theoretic Methods in Cryptology

ISBN

978-3-319-76619-5
978-3-319-76620-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-76620-1_5

DOI

http://dx.doi.org/10.1007/978-3-319-76620-1_5

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "imec-COSIC, KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, KU Leuven, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "imec-COSIC, KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, KU Leuven, 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"
      }
    ], 
    "datePublished": "2018-02-28", 
    "datePublishedReg": "2018-02-28", 
    "description": "This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or Gr\u00f6bner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility.", 
    "editor": [
      {
        "familyName": "Kaczorowski", 
        "givenName": "Jerzy", 
        "type": "Person"
      }, 
      {
        "familyName": "Pieprzyk", 
        "givenName": "Josef", 
        "type": "Person"
      }, 
      {
        "familyName": "Pomyka\u0142a", 
        "givenName": "Jacek", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-76620-1_5", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-76619-5", 
        "978-3-319-76620-1"
      ], 
      "name": "Number-Theoretic Methods in Cryptology", 
      "type": "Book"
    }, 
    "keywords": [
      "system of equations", 
      "Gr\u00f6bner basis algorithm", 
      "multivariate quadratic (MQ) problem", 
      "short solution", 
      "hard problem", 
      "nonlinear systems", 
      "nonlinear equations", 
      "quadratic problem", 
      "solution problem", 
      "basis algorithm", 
      "secure hash function", 
      "lattice reduction", 
      "public key cryptosystem", 
      "new hard problem", 
      "equations", 
      "short integer solution problem", 
      "solving strategies", 
      "hash function", 
      "key cryptosystem", 
      "short representations", 
      "problem", 
      "solution", 
      "cryptography", 
      "cryptosystem", 
      "algorithm", 
      "joint requirements", 
      "system", 
      "representation", 
      "requirements", 
      "function", 
      "possibility", 
      "basis", 
      "strategies", 
      "use", 
      "reduction", 
      "paper"
    ], 
    "name": "Short Solutions to Nonlinear Systems of Equations", 
    "pagination": "71-90", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1101242709"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-76620-1_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-76620-1_5", 
      "https://app.dimensions.ai/details/publication/pub.1101242709"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "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_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-76620-1_5"
  }
]
 

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-319-76620-1_5'

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-319-76620-1_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-76620-1_5'

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-319-76620-1_5'


 

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

112 TRIPLES      22 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-76620-1_5 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nfc5ac61cd2544a8e85249f9b87a9b892
4 schema:datePublished 2018-02-28
5 schema:datePublishedReg 2018-02-28
6 schema:description This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or Gröbner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility.
7 schema:editor Ne4438a5f777b4d55ad2dd810491bd683
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nff69ac78ff774141823605d8a8cf7a90
11 schema:keywords Gröbner basis algorithm
12 algorithm
13 basis
14 basis algorithm
15 cryptography
16 cryptosystem
17 equations
18 function
19 hard problem
20 hash function
21 joint requirements
22 key cryptosystem
23 lattice reduction
24 multivariate quadratic (MQ) problem
25 new hard problem
26 nonlinear equations
27 nonlinear systems
28 paper
29 possibility
30 problem
31 public key cryptosystem
32 quadratic problem
33 reduction
34 representation
35 requirements
36 secure hash function
37 short integer solution problem
38 short representations
39 short solution
40 solution
41 solution problem
42 solving strategies
43 strategies
44 system
45 system of equations
46 use
47 schema:name Short Solutions to Nonlinear Systems of Equations
48 schema:pagination 71-90
49 schema:productId N4711505bff9344ea8629b843e5118dd0
50 N7d84556db4344c4e9827c1ea1869b6e0
51 schema:publisher N848c9335b86849afa989626785070031
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101242709
53 https://doi.org/10.1007/978-3-319-76620-1_5
54 schema:sdDatePublished 2022-11-24T21:15
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N9d2b00749c624b58938efe6c04fe2d57
57 schema:url https://doi.org/10.1007/978-3-319-76620-1_5
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N0309a6d9b5b6425996a8af92ff982c6c rdf:first N7138090347694f38aa94035fea5df97c
62 rdf:rest N7627593e38a545c99edafebefe3bcb97
63 N19d766c547eb4b9cbee0e19e6ba18770 schema:familyName Pomykała
64 schema:givenName Jacek
65 rdf:type schema:Person
66 N4711505bff9344ea8629b843e5118dd0 schema:name doi
67 schema:value 10.1007/978-3-319-76620-1_5
68 rdf:type schema:PropertyValue
69 N7138090347694f38aa94035fea5df97c schema:familyName Pieprzyk
70 schema:givenName Josef
71 rdf:type schema:Person
72 N7627593e38a545c99edafebefe3bcb97 rdf:first N19d766c547eb4b9cbee0e19e6ba18770
73 rdf:rest rdf:nil
74 N7d84556db4344c4e9827c1ea1869b6e0 schema:name dimensions_id
75 schema:value pub.1101242709
76 rdf:type schema:PropertyValue
77 N848c9335b86849afa989626785070031 schema:name Springer Nature
78 rdf:type schema:Organisation
79 N9d2b00749c624b58938efe6c04fe2d57 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nb58bc6fae6ca46dfb5885815240d33b3 schema:familyName Kaczorowski
82 schema:givenName Jerzy
83 rdf:type schema:Person
84 Ne4438a5f777b4d55ad2dd810491bd683 rdf:first Nb58bc6fae6ca46dfb5885815240d33b3
85 rdf:rest N0309a6d9b5b6425996a8af92ff982c6c
86 Nfc5ac61cd2544a8e85249f9b87a9b892 rdf:first sg:person.013013776035.00
87 rdf:rest Nfe3d4b3325e94ccab24e6d2a2a9a11ad
88 Nfe3d4b3325e94ccab24e6d2a2a9a11ad rdf:first sg:person.011115044357.39
89 rdf:rest rdf:nil
90 Nff69ac78ff774141823605d8a8cf7a90 schema:isbn 978-3-319-76619-5
91 978-3-319-76620-1
92 schema:name Number-Theoretic Methods in Cryptology
93 rdf:type schema:Book
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
98 schema:name Pure Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
101 schema:familyName Preneel
102 schema:givenName Bart
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
104 rdf:type schema:Person
105 sg:person.013013776035.00 schema:affiliation grid-institutes:grid.5596.f
106 schema:familyName Szepieniec
107 schema:givenName Alan
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00
109 rdf:type schema:Person
110 grid-institutes:grid.5596.f schema:alternateName imec-COSIC, KU Leuven, Leuven, Belgium
111 schema:name imec-COSIC, KU Leuven, Leuven, Belgium
112 rdf:type schema:Organization
 




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


...