*12:56* [PhD][New]
Juraj Šarinay: Cryptographic Hash Functions in Groups and Provable Properties
Name: Juraj Šarinay

Topic: Cryptographic Hash Functions in Groups and Provable Properties

Category: (no category)

Description: We consider several “provably secure” hash functions that compute simple sums in a well chosen group (G, ?). Security properties of such functions provably translate in a natural way to computational problems in G\r\nthat are simple to define and possibly also hard to solve. Given k disjoint lists Li of group elements, the k-sum problem asks for gi ? Li such that\r\ng1 ? g2 ? . . . ? gk = 1G. Hardness of the problem in the respective groups follows from some “standard” assumptions used in public-key cryptology such\r\nas hardness of integer factoring, discrete logarithms, lattice reduction and syndrome decoding. We point out evidence that the k-sum problem may even be harder than the above problems.

\r\n\r\n\r\nTwo hash functions based on the group k-sum problem, SWIFFTX and FSB, were submitted to NIST as candidates for the future SHA-3 standard. Both submissions were supported by some sort of a security proof. We show\r\nthat the assessment of security levels provided in the proposals is not related to the proofs included. The main claims on security are supported exclusively\r\nby considerations about available attacks. By introducing “second-order” bounds on bounds on security, we expose the limits of such an approach to\r\nprovable security.

\r\n\r\nA problem with the way security is quantified does not necessarily mean a problem with security itself. Although FSB does have a history of failures,\r\nrecent versions of the two above functions have resisted cryptanalytic efforts well. This evidence, as well as the several connections to more standard\r\nproblems, suggests that the k-sum problem in some groups may be considered hard on its own and possibly lead to provable bounds on security. Complexity of the non-trivial tree algorithm is becoming a standard tool for measuring the associated hardness.

\r\n\r\n\r\nWe propose modifications to the multiplicative Very Smooth Hash and derive security from multiplicative k-sums in contra[...]

*00:17* [Pub][ePrint]
Foundations of Reconfigurable PUFs (Full Version), by Jonas Schneider and Dominique Schröder
A Physically Unclonable Function (PUF) can be seen as a source of randomness that can be challenged with a stimulus and responds in a way that is to some extent unpredictable. PUFs can be used to provide efficient solutions for common cryptographic primitives such as identification/authentication schemes, key storage, and hardware-entangled cryptography. Moreover, Brzuska et al.~have recently shown, that PUFs can be used to construct UC secure protocols (CRYPTO 2011). Most PUF instantiations, however, only provide a static challenge/response space which limits their usefulness for practical instantiations. To overcome this limitation, Katzenbeisser et al. (CHES 2011) introduced Logically Reconfigurable PUFs (LR-PUFs), with the idea to introduce an ``update\'\' mechanism that changes the challenge/response behaviour without physically replacing or modifying the hardware.

In this work, we revisit LR-PUFs. We propose several new ways to characterize the unpredictability of LR-PUFs covering a broader class of realistic attacks and examine their relationship to each other.

In addition, we reconcile existing constructions with these new characterizations and show that they can withstand stronger adversaries than originally shown.

Since previous constructions are insecure with respect to our strongest unpredictability notion, we propose a secure construction which relies on the same assumptions and is almost as efficient as previous solutions.

*00:17* [Pub][ePrint]
Black-Box Garbled RAM, by Sanjam Garg and Steve Lu and Rafail Ostrovsky
Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao\'s garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives.In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the OT-hybrid model.

*00:17* [Pub][ePrint]
TinyLEGO: An Interactive Garbling Scheme for Maliciously Secure Two-party Computation, by Tore Kasper Frederiksen and Thomas P. Jakobsen and Jesper Buus Nielsen and Roberto Trifiletti
This paper reports on a number of conceptual and technical contributions to the currently very lively field of two-party computation (2PC) based on garbled circuits. Our main contributions are as follows:1. We propose a notion of an interactive garbling scheme, where the garbled circuit is

generated as an interactive protocol between the garbler and the evaluator. The garbled circuit is correct and privacy preserving even if one of the two parties was acting maliciously during garbling. The security notion is game based.

2. We show that an interactive garbling scheme combined with a Universally Composable (UC) secure oblivious transfer protocol can be used in a black-box manner to implement two-party computation (2PC) UC securely against a static and malicious adversary. The protocol abstracts many recent protocols for implementing 2PC from garbled circuits and will allow future designers of interactive garbling schemes to prove security with the simple game based definitions, as opposed to directly proving UC security for each new scheme.

3. We propose a new instantiation of interactive garbling by designing a new protocol in the LEGO family of protocols for efficient garbling against a malicious adversary. The new protocol is based on several new technical contributions and many optimizations, including a highly efficient UC commitment scheme. A theoretical evaluation of the efficiency shows that the instantiation is one to two orders of magnitude faster than the previously most efficient LEGO protocol and that it in general compares favorably to all existing garbling-based 2PC protocols for malicious adversaries.

*00:17* [Pub][ePrint]
New algorithm for the discrete logarithm problem on elliptic curves, by Igor Semaev
A new algorithms for computing discrete logarithms on elliptic curves defined over finite fields is suggested. It is based on a new method to find zeroes of summation polynomials. In binary elliptic curves one is to solve a cubic system of Boolean equations. Under a first fall degree assumption the regularity degree of the system is at most $4$. Extensive experimental data which supports the assumption is provided. An heuristic analysis suggests a new asymptotical complexity bound $2^{c\\sqrt{n\\ln n}}, c\\approx 1.69$ for computing discrete logarithms on an elliptic curve over a field of size $2^n$. For several binary elliptic curves recommended by FIPS the new method performs better than Pollard\'s.