Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via
To receive your credentials via mail again, please click here.
You can also access the full news archive.
field with q elements.
Modulo a well supported number theoretic hypothesis, which holds in particular for all concrete
homomorphisms proposed thus far, we prove that
a random homomorphism is at least as secure as any concrete homomorphism.
For a family of homomorphisms containing several concrete proposals in the literature,
we prove that collisions of length O(log q) can be found in running time O(sqrt q).
For general homomorphisms we offer an algorithm that, heuristically and according to experiments,
in running time O(sqrt q) finds collisions of length O(log q) for q even, and length O(log^2 q/loglog q) for arbitrary q.
For any conceivable practical scenario, our algorithms are substantially faster than all earlier algorithms
and produce much shorter collisions.
-Negative Result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a \"secure sketch.\" The security of this component, which directly affects the length of the resulting key, is subject to lower bounds from coding theory. We show that, even when defined computationally, secure sketches are still subject to lower bounds from coding theory. Specifically, we consider two computational relaxations of the information-theoretic security requirement of secure sketches, using conditional HILL entropy and unpredictability entropy. For both cases we show that computational secure sketches cannot outperform the best information-theoretic secure sketches in the case of high-entropy Hamming metric sources.
-Positive Result: We show that the negative result can be overcome by analyzing computational fuzzy extractors directly. Namely, we show how to build a computational fuzzy extractor whose output key length equals the entropy of the source (this is impossible in the information-theoretic setting). Our construction is based on the hardness of the Learning with Errors (LWE) problem, and is secure when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed). As part of the security proof, we show a result of independent interest, namely that the decision version of LWE is secure even when a small number of dimensions has no error.
In this paper we introduce a new meta-reduction technique, which allows to prove lower bounds for the large and very natural class of generic reductions. A generic reduction is independent of a particular representation of group elements. Most reductions in state-of-the-art security proofs have this desirable property. This new approach allows to show unconditionally that there is no tight generic reduction from any natural computational problem \\Pi defined over algebraic groups (including even interactive problems) to breaking Schnorr signatures, unless solving \\Pi is easy.
The Department of Mathematics and Computer Science of the Eindhoven University of Technology (TU/e) has a vacancy for a Tenure Track Assistant Professor position for five years in the Coding and Crypto group (section Discrete Mathematics, DM).
The tenure-track nature of the position will be as follows. The successful candidate will first be appointed for a fixed period of five years. Before the start of the contract, the department and the candidate negotiate a list of conditions for successful conversion. If the candidate meets these conditions at the end of the five years, the position becomes permanent; if not, the temporary position is not continued.