Better Algorithms for LWE and LWR View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-04-14

AUTHORS

Alexandre Duc , Florian Tramèr , Serge Vaudenay

ABSTRACT

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al.In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q$$\end{document}, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest. More... »

PAGES

173-202

Book

TITLE

Advances in Cryptology -- EUROCRYPT 2015

ISBN

978-3-662-46799-2
978-3-662-46800-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-46800-5_8

DOI

http://dx.doi.org/10.1007/978-3-662-46800-5_8

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "EPFL, 1015, Lausanne, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "EPFL, 1015, Lausanne, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Duc", 
        "givenName": "Alexandre", 
        "id": "sg:person.013530063017.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013530063017.09"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "EPFL, 1015, Lausanne, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "EPFL, 1015, Lausanne, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tram\u00e8r", 
        "givenName": "Florian", 
        "id": "sg:person.011125325553.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011125325553.13"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "EPFL, 1015, Lausanne, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "EPFL, 1015, Lausanne, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vaudenay", 
        "givenName": "Serge", 
        "id": "sg:person.01353240467.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01353240467.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-04-14", 
    "datePublishedReg": "2015-04-14", 
    "description": "The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al.In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.Finally, we apply the same algorithm to the Learning With Rounding problem\u00a0(LWR) for prime \\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$$\\end{document}, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.", 
    "editor": [
      {
        "familyName": "Oswald", 
        "givenName": "Elisabeth", 
        "type": "Person"
      }, 
      {
        "familyName": "Fischlin", 
        "givenName": "Marc", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-46800-5_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-46799-2", 
        "978-3-662-46800-5"
      ], 
      "name": "Advances in Cryptology -- EUROCRYPT 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "best algorithm", 
      "Albrecht et al", 
      "homomorphic encryption scheme", 
      "encryption scheme", 
      "Learning Parity", 
      "independent interest", 
      "pseudorandom functions", 
      "first algorithm", 
      "rounding problem", 
      "Blum et al", 
      "LWE", 
      "same algorithm", 
      "multidimensional Fourier transform", 
      "BKW algorithm", 
      "algorithm", 
      "error problem", 
      "Gaussian noise", 
      "learning", 
      "concrete parameters", 
      "deterministic counterpart", 
      "cryptography", 
      "heuristics", 
      "instances", 
      "noise problem", 
      "technical results", 
      "subproblems", 
      "more attention", 
      "Gaussian", 
      "final complexity", 
      "complexity", 
      "scheme", 
      "knowledge", 
      "et al", 
      "transform", 
      "noise", 
      "design", 
      "interest", 
      "primordial importance", 
      "work", 
      "results", 
      "attention", 
      "LWR", 
      "analysis", 
      "parameters", 
      "Fourier transform", 
      "function", 
      "importance", 
      "counterparts", 
      "al", 
      "integrals", 
      "parity", 
      "problem", 
      "paper"
    ], 
    "name": "Better Algorithms for LWE and LWR", 
    "pagination": "173-202", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016645010"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-46800-5_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-46800-5_8", 
      "https://app.dimensions.ai/details/publication/pub.1016645010"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_198.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-46800-5_8"
  }
]
 

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-662-46800-5_8'

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-662-46800-5_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46800-5_8'

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-662-46800-5_8'


 

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

132 TRIPLES      23 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-46800-5_8 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nb99069b965b6420e9e83214c3e7d3f4c
4 schema:datePublished 2015-04-14
5 schema:datePublishedReg 2015-04-14
6 schema:description The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al.In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q$$\end{document}, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.
7 schema:editor Ndb8e0dd791d1424986f76513ce5556f3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nef2faf174c63487c806efb4f57d3fba2
12 schema:keywords Albrecht et al
13 BKW algorithm
14 Blum et al
15 Fourier transform
16 Gaussian
17 Gaussian noise
18 LWE
19 LWR
20 Learning Parity
21 al
22 algorithm
23 analysis
24 attention
25 best algorithm
26 complexity
27 concrete parameters
28 counterparts
29 cryptography
30 design
31 deterministic counterpart
32 encryption scheme
33 error problem
34 et al
35 final complexity
36 first algorithm
37 function
38 heuristics
39 homomorphic encryption scheme
40 importance
41 independent interest
42 instances
43 integrals
44 interest
45 knowledge
46 learning
47 more attention
48 multidimensional Fourier transform
49 noise
50 noise problem
51 paper
52 parameters
53 parity
54 primordial importance
55 problem
56 pseudorandom functions
57 results
58 rounding problem
59 same algorithm
60 scheme
61 subproblems
62 technical results
63 transform
64 work
65 schema:name Better Algorithms for LWE and LWR
66 schema:pagination 173-202
67 schema:productId Nbb7eefb1e7404921be29e7e31c76fe59
68 Ndcd932753fa94c1590c07b15f66273a0
69 schema:publisher Nfc217946735a47a58c42422090a2f805
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016645010
71 https://doi.org/10.1007/978-3-662-46800-5_8
72 schema:sdDatePublished 2022-05-10T10:40
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N453705f49222470ca51c32bf05ca6e5b
75 schema:url https://doi.org/10.1007/978-3-662-46800-5_8
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N21ba430f8522483bb17e2ee12a33bf5f rdf:first sg:person.011125325553.13
80 rdf:rest Nac8c455c42a14d06bc2da20f8677b2da
81 N29f24cb793cb40ba89b217560252bb15 schema:familyName Oswald
82 schema:givenName Elisabeth
83 rdf:type schema:Person
84 N453705f49222470ca51c32bf05ca6e5b schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 Nab3ac4f82cb44fcbb834ddbdacc87870 schema:familyName Fischlin
87 schema:givenName Marc
88 rdf:type schema:Person
89 Nac8c455c42a14d06bc2da20f8677b2da rdf:first sg:person.01353240467.39
90 rdf:rest rdf:nil
91 Nb99069b965b6420e9e83214c3e7d3f4c rdf:first sg:person.013530063017.09
92 rdf:rest N21ba430f8522483bb17e2ee12a33bf5f
93 Nbb7eefb1e7404921be29e7e31c76fe59 schema:name dimensions_id
94 schema:value pub.1016645010
95 rdf:type schema:PropertyValue
96 Nbc53b138b25b46c1b667c3803683e524 rdf:first Nab3ac4f82cb44fcbb834ddbdacc87870
97 rdf:rest rdf:nil
98 Ndb8e0dd791d1424986f76513ce5556f3 rdf:first N29f24cb793cb40ba89b217560252bb15
99 rdf:rest Nbc53b138b25b46c1b667c3803683e524
100 Ndcd932753fa94c1590c07b15f66273a0 schema:name doi
101 schema:value 10.1007/978-3-662-46800-5_8
102 rdf:type schema:PropertyValue
103 Nef2faf174c63487c806efb4f57d3fba2 schema:isbn 978-3-662-46799-2
104 978-3-662-46800-5
105 schema:name Advances in Cryptology -- EUROCRYPT 2015
106 rdf:type schema:Book
107 Nfc217946735a47a58c42422090a2f805 schema:name Springer Nature
108 rdf:type schema:Organisation
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
113 schema:name Artificial Intelligence and Image Processing
114 rdf:type schema:DefinedTerm
115 sg:person.011125325553.13 schema:affiliation grid-institutes:grid.5333.6
116 schema:familyName Tramèr
117 schema:givenName Florian
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011125325553.13
119 rdf:type schema:Person
120 sg:person.013530063017.09 schema:affiliation grid-institutes:grid.5333.6
121 schema:familyName Duc
122 schema:givenName Alexandre
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013530063017.09
124 rdf:type schema:Person
125 sg:person.01353240467.39 schema:affiliation grid-institutes:grid.5333.6
126 schema:familyName Vaudenay
127 schema:givenName Serge
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01353240467.39
129 rdf:type schema:Person
130 grid-institutes:grid.5333.6 schema:alternateName EPFL, 1015, Lausanne, Switzerland
131 schema:name EPFL, 1015, Lausanne, Switzerland
132 rdf:type schema:Organization
 




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


...