Publication

Observations on the LPN Solving Algorithm from Eurocrypt'16

Serge Vaudenay
2016
Reports

Abstract

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].

Official source

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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Serge Vaudenay
2016
Reports

Abstract

Official source

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

About this result

Related concepts (31)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Reduction (complexity)

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B.

Dijkstra's algorithm

Dijkstra's algorithm (ˈdaɪkstrəz ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Related publications (27)

Observations on the LPN Solving Algorithm from Eurocrypt'16

Chat with 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