Publication

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Related publications (33)

Graph Chatbot

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.

Testing additive integrality gaps

Friedrich Eisenbrand, Nicolai Hähnle, Gennady Shmonin

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...

2010

The interval constrained 3-coloring problem

Laura Sanità

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-co ...

Springer Verlag2010

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

On the security of 1024-bit RSA and 160-bit elliptic curve cryptography

Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung, Marcelo Kaihara

Meeting the requirements of NIST’s new cryptographic standard ‘Suite B Cryptography’ means phasing out usage of 1024-bit RSA and 160-bit Elliptic Curve Cryptography (ECC) by the year 2010. This write-up comments on the vulnerability of these systems to an ...

2009

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

Secure Position-Based Routing for VANETs

Panagiotis Papadimitratos, Charles Harsch

Vehicular communication (VC) systems have the potential to improve road safety and driving comfort. Nevertheless, securing the operation is a prerequisite for deployment. So far, the security of VC applications has mostly drawn the attention of research ef ...

2007

Precoloring with cliques and stable sets in cographs

Tinaz Ekim

Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...

2006

On the Use of GF-Inversion as a Cryptographic Primitive

Serge Vaudenay

Inversion in Galois Fields is a famous primitive permutation for designing cryptographic algorithms e.g. for Rijndael because it has suitable differential and linear properties. Inputs and outputs are usually transformed by addition (e.g. XOR) to key bits. ...

2004

Cryptography with Guardian Angels: Bringing civilization to pirates - Abstract

Serge Vaudenay, Gildas Avoine

In contrast with traditional cryptographic protocols in which parties can have access to common third parties, and where at least one of them is assumed to be honest, we propose here a new model which is relevant for networks of communication devices with ...

2003

High performance VLSI architectures implementing strong cryptographic primitives

Feth Allah Cherigui

The main topic of this thesis is related to the state of the art in designing cryptographic primitives from a hardware point of view. A special emphasis is dedicated to low-power/low-energy CMOS design. A set of solutions is proposed including an LFSR base ...

EPFL2002