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-10-01T06:56", 
    "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_3.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 Nf4ab0453f4c548c7a09457668b0aa0ec
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 Na45da606fcd24f338a11f7cf2e97bfe3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Na94eb2663dc74f5db888dcaaf563b7a7
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 N42256849c04c46aa8d6983135ceefdb2
50 Na42946279d294ff09d8d2399b4b1e511
51 schema:publisher Nf15ac31050164652818346b54128bdd1
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-10-01T06:56
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N3b3e323ac4b34791b4f351d7e06d01e3
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 N13e30c5c5c6749d8b02621c9d7abc43e rdf:first sg:person.011115044357.39
62 rdf:rest rdf:nil
63 N2058d03fd8394a5ba15a763521a7b012 schema:familyName Pieprzyk
64 schema:givenName Josef
65 rdf:type schema:Person
66 N3b3e323ac4b34791b4f351d7e06d01e3 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N42256849c04c46aa8d6983135ceefdb2 schema:name dimensions_id
69 schema:value pub.1101242709
70 rdf:type schema:PropertyValue
71 N4852c73d61a0482c8e1077ce5a8903cd rdf:first N2058d03fd8394a5ba15a763521a7b012
72 rdf:rest N7d738ad7d77842cc94dc2dfa64aae6c4
73 N74759e5f137c4b05963b7953124be75b schema:familyName Kaczorowski
74 schema:givenName Jerzy
75 rdf:type schema:Person
76 N7d738ad7d77842cc94dc2dfa64aae6c4 rdf:first Nedd3511e7e4a4f76a909053f63956275
77 rdf:rest rdf:nil
78 Na42946279d294ff09d8d2399b4b1e511 schema:name doi
79 schema:value 10.1007/978-3-319-76620-1_5
80 rdf:type schema:PropertyValue
81 Na45da606fcd24f338a11f7cf2e97bfe3 rdf:first N74759e5f137c4b05963b7953124be75b
82 rdf:rest N4852c73d61a0482c8e1077ce5a8903cd
83 Na94eb2663dc74f5db888dcaaf563b7a7 schema:isbn 978-3-319-76619-5
84 978-3-319-76620-1
85 schema:name Number-Theoretic Methods in Cryptology
86 rdf:type schema:Book
87 Nedd3511e7e4a4f76a909053f63956275 schema:familyName Pomykała
88 schema:givenName Jacek
89 rdf:type schema:Person
90 Nf15ac31050164652818346b54128bdd1 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nf4ab0453f4c548c7a09457668b0aa0ec rdf:first sg:person.013013776035.00
93 rdf:rest N13e30c5c5c6749d8b02621c9d7abc43e
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)


...