*18:17* [Pub][ePrint]
Plug-and-Play IP Security: Anonymity Infrastructure Instead of PKI, by Yossi Gilad and Amir Herzberg
We present the Plug-and-Play IP Security (PnP-IPsec) protocol. PnP-IPsec automatically establishes IPsec security associations between gateways, avoiding the need for manual administration and coordination between gateways, and the dependency on IPsec public key certificates - the two problems which are widely believed to have limited the use of IPsec mostly to intra-organization communication.PnP-IPsec builds on Self-validated Public Data Distribution (SvPDD), a protocol that we present to establish secure connections between remote peers/networks, without depending on pre-distributed keys or certification infrastructure. Instead, SvPDD uses available anonymous communication infrastructures such as Tor, which we show to allow detection of MitM attacker interfering with communication. SvPDD may also be used in other scenarios lacking secure public key distribution, such as the initial connection to an SSH server.

We provide an open-source implementation of PnP-IPsec and SvPDD, and show that the resulting system is practical and secure.

*18:17* [Pub][ePrint]
Short collision search in arbitrary SL2 homomorphic hash functions, by Ciaran Mullan and Boaz Tsaban
We study homomorphic hash functions into SL2(q), the 2x2 matrices with determinant 1 over thefield 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.

*18:17* [Pub][ePrint]
Computational Fuzzy Extractors, by Benjamin Fuller and Xianrui Meng and Leonid Reyzin
Fuzzy extractors derive strong keys from noisy sources. Their security is defined information- theoretically, which limits the length of the derived key, sometimes making it too short to be useful. We ask whether it is possible to obtain longer keys by considering computational security, and show the following.-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.