Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:
To receive your credentials via mail again, please click here.
You can also access the full news archive.
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\n
Two 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\n
A 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\n
We propose modifications to the multiplicative Very Smooth Hash and derive security from multiplicative k-sums in contra[...]
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.
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.