Publication

Observations on the LPN Solving Algorithm from Eurocrypt'16

Serge Vaudenay
2016
Reports

Résumé

In this note we re-evaluate the Eurocrypt’16 paper by Zhang et al. [9] in the area of LPN solving algorithms. We present the history of LPN solving algorithms and give the general description of the algorithm from [9]. While this new algorithm claims to improve all the previous results, we have discovered issues in its analysis. We review inconsistencies in complexity estimates and a misconception of some new reduction algorithm. What we show is that the results of [9] do not provide better performance compared with the results from Asiacrypt’14 [5].

Source officielle

https://infoscience.epfl.ch/entities/publication/976d9abd-c552-4778-8122-fda422be341a

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Serge Vaudenay
2016
Reports

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/976d9abd-c552-4778-8122-fda422be341a

À propos de ce résultat

Concepts associés (31)

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Réduction (complexité)

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B.

Algorithme de Dijkstra

En théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.

Afficher plus

Publications associées (27)

Afficher plus

Observations on the LPN Solving Algorithm from Eurocrypt'16

Chattez avec Graph Search

Fundamental computational limits of weak learnability in high-dimensional multi-index models

Beyond Net Land Intake? Unravelling Stakeholder Perspectives on Wartime Land Use Governance in Ukraine

MATHICSE Technical Report : Quantifying uncertain system outputs via the multilevel Monte Carlo method – Part I: Central moment estimation