Ontology type: schema:ScholarlyArticle Open Access: True
2015-07-31
AUTHORSSonia Bogos, Florian Tramèr, Serge Vaudenay
ABSTRACTThe Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing LPN solving algorithms, both for the general case and for the sparse secret scenario. In practice, the LPN-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of LPN solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms BKW and its variants. Following from our results, we further propose practical parameters for different security levels. More... »
PAGES331-369
http://scigraph.springernature.com/pub.10.1007/s12095-015-0149-2
DOIhttp://dx.doi.org/10.1007/s12095-015-0149-2
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1008687870
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"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "EPFL, CH-1015, Lausanne, Switzerland",
"id": "http://www.grid.ac/institutes/grid.5333.6",
"name": [
"EPFL, CH-1015, Lausanne, Switzerland"
],
"type": "Organization"
},
"familyName": "Bogos",
"givenName": "Sonia",
"id": "sg:person.011576475127.40",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011576475127.40"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "EPFL, CH-1015, Lausanne, Switzerland",
"id": "http://www.grid.ac/institutes/grid.5333.6",
"name": [
"EPFL, CH-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, CH-1015, Lausanne, Switzerland",
"id": "http://www.grid.ac/institutes/grid.5333.6",
"name": [
"EPFL, CH-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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-642-24412-4_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006037661",
"https://doi.org/10.1007/978-3-642-24412-4_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-25385-0_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008943366",
"https://doi.org/10.1007/978-3-642-25385-0_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-54631-0_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046405046",
"https://doi.org/10.1007/978-3-642-54631-0_1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45682-1_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027730722",
"https://doi.org/10.1007/3-540-45682-1_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00145-010-9061-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012126245",
"https://doi.org/10.1007/s00145-010-9061-2"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22792-9_42",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042462397",
"https://doi.org/10.1007/978-3-642-22792-9_42"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-36140-1_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032773845",
"https://doi.org/10.1007/978-3-642-36140-1_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-662-46800-5_8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016645010",
"https://doi.org/10.1007/978-3-662-46800-5_8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11941378_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033812388",
"https://doi.org/10.1007/11941378_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-20465-4_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043195135",
"https://doi.org/10.1007/978-3-642-20465-4_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38553-7_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042338881",
"https://doi.org/10.1007/978-3-642-38553-7_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11832072_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009973045",
"https://doi.org/10.1007/11832072_24"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22006-7_34",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012978110",
"https://doi.org/10.1007/978-3-642-22006-7_34"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-03356-8_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053603939",
"https://doi.org/10.1007/978-3-642-03356-8_35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-34961-4_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042915066",
"https://doi.org/10.1007/978-3-642-34961-4_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11535218_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048110650",
"https://doi.org/10.1007/11535218_18"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-662-45611-8_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038534677",
"https://doi.org/10.1007/978-3-662-45611-8_1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-40084-1_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010980912",
"https://doi.org/10.1007/978-3-642-40084-1_18"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-54631-0_25",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037345013",
"https://doi.org/10.1007/978-3-642-54631-0_25"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0019850",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029429475",
"https://doi.org/10.1007/bfb0019850"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-34047-5_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024908214",
"https://doi.org/10.1007/978-3-642-34047-5_20"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-78967-3_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028765794",
"https://doi.org/10.1007/978-3-540-78967-3_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-48329-2_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045214757",
"https://doi.org/10.1007/3-540-48329-2_24"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11538462_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022279726",
"https://doi.org/10.1007/11538462_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10623-013-9864-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023628569",
"https://doi.org/10.1007/s10623-013-9864-x"
],
"type": "CreativeWork"
}
],
"datePublished": "2015-07-31",
"datePublishedReg": "2015-07-31",
"description": "The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing LPN solving algorithms, both for the general case and for the sparse secret scenario. In practice, the LPN-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of LPN solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms BKW and its variants. Following from our results, we further propose practical parameters for different security levels.",
"genre": "article",
"id": "sg:pub.10.1007/s12095-015-0149-2",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1136695",
"issn": [
"1936-2447",
"1936-2455"
],
"name": "Cryptography and Communications",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "8"
}
],
"keywords": [
"different security levels",
"post-quantum world",
"cryptographic constructions",
"security level",
"Learning Parity",
"security parameters",
"theoretical analysis",
"lightweight devices",
"new theoretical analysis",
"algorithm",
"practical complexity",
"tight bounds",
"general case",
"complexity",
"cryptography",
"practical parameters",
"BKW",
"noise problem",
"Fouque",
"parameters",
"bounds",
"secrets",
"scenarios",
"LPN",
"theory",
"devices",
"problem",
"comprehensive analysis",
"simplicity",
"good candidate",
"gap",
"world",
"variants",
"construction",
"analysis",
"practice",
"cases",
"results",
"reference",
"candidates",
"parity",
"levels",
"paper"
],
"name": "On solving LPN using BKW and variants",
"pagination": "331-369",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1008687870"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s12095-015-0149-2"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s12095-015-0149-2",
"https://app.dimensions.ai/details/publication/pub.1008687870"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:30",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_654.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s12095-015-0149-2"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s12095-015-0149-2'
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/s12095-015-0149-2'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12095-015-0149-2'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12095-015-0149-2'
This table displays all metadata directly associated to this object as RDF triples.
223 TRIPLES
22 PREDICATES
95 URIs
60 LITERALS
6 BLANK NODES