*21:17* [Pub][ePrint]
Round-Efficient Black-Box Construction of Composable Multi-Party Computation, by Susumu Kiyoshima
We present a round-efficient black-box construction of a general MPC protocol that satisfies composability in the plain model. The security of our protocol is proven in angel-based UC framework under the minimal assumption of the existence of semi-honest oblivious transfer protocols. When the round complexity of the underlying oblivious transfer protocol is Round(OT), the round complexity of our protocol is max(\\tilde{O}(log^2 n), O(Round(OT))). Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives \\tilde{O}(log^2 n)-round protocol under these assumptions. Previously, only an O(max(n^{\\epsilon}, Round(OT))-round protocol was shown, where \\epsilon>0 is an arbitrary constant.We obtain our MPC protocol by constructing a \\tilde{O}(log^2 n)-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

*21:17* [Pub][ePrint]
Countermeasures Against High-Order Fault-Injection Attacks on CRT-RSA, by Pablo Rauzy and Sylvain Guilley
In this paper we study the existing CRT-RSA countermeasures against fault-injection attacks.In an attempt to classify them we get to achieve deep understanding of how they work.

We show that the many countermeasures that we study (and their variations) actually share a number of common features, but optimize them in different ways.

We also show that there is no conceptual distinction between test-based and infective countermeasures and how either one can be transformed into the other.

Furthermore, we show that faults on the code (skipping instructions) can be captured by considering only faults on the data.

These intermediate results allow us to improve the state of the art in several ways:

(a) we fix an existing and that was known to be broken countermeasure (namely the one from Shamir);

(b) we drastically optimize an existing countermeasure (namely the one from Vigilant) which we reduce to 3 tests instead of 9 in its original version, and prove that it resists not only one fault but also an arbitrary number of randomizing faults;

(c) we also show how to upgrade countermeasures to resist any given number of faults: given a correct first-order countermeasure, we present a way to design a provable high-order countermeasure (for a well-defined and reasonable fault model).

Finally, we pave the way for a generic approach against fault attacks for any modular arithmetic computations, and thus for the automatic insertion of countermeasures.

*21:17* [Pub][ePrint]
An Investigation of Some Forward Security Properties for PEKS and IBE, by Qiang Tang
In cryptography, forward secrecy is a well-known property of key agreement protocols. Itensures that a session key remains secure even if one of the long-term secret keys is compromised in

the future. In this paper, we investigate some forward security properties for Public-key Encryption

with Keyword Search (PEKS) schemes, which allow a client to store encrypted data and delegate

search operations to a server. The proposed properties guarantee that the client\'s privacy is protected

to the maximum extent when his private key is compromised. Motivated by the generic transformation

from anonymous Identity-Based Encryption (IBE) to PEKS, we correspondingly propose some

forward security properties for IBE, in which case we assume the attacker learns the master secret

key. We then study several existing PEKS and IBE schemes, including a PEKS scheme by Nishioka,

an IBE scheme by Boneh, Raghunathan and Segev, and an IBE scheme by Arriaga, Tang and Ryan.

Our analysis indicates that the proposed forward security properties can be achieved by some of

these schemes if the attacker is RO-non-adaptive (the attacker does not define its distributions based

on the random oracle). Finally, we show how to extend the Boyen-Waters anonymous IBE scheme

to achieve the forward security properties for adaptive attackers.

*21:17* [Pub][ePrint]
hHB: a Harder HB+ Protocol, by Ka Ahmad Khoureich
In 2005, Juels and Weis proposed HB+, a perfectly adapted authentication protocol for resource-constrained devices such as RFID tags. The HB+ protocol is based on the Learning Parity with Noise (LPN) problem and is proven secure against active adversaries. Since a man-in-the-middle attack on HB+ due to Gilbert et al. was published, many proposals have been made to improve the HB+ protocol. But none of these was formally proven secure against general man-in-the-middle adversaries.In this paper we present a solution to make the HB+ protocol resistant to general man-in-the-middle adversaries without exceeding the computational and storage capabilities of the RFID tag.

*15:17* [Pub][ePrint]
On Virtual Grey Box Obfuscation for General Circuits, by Nir Bitansky and Ran Caentti and Yael Tauman-Kalai and Omer Paneth
An obfuscator $\\O$ is Virtual Grey Box (VGB) for a class $\\C$ of circuits if, for any $C\\in\\C$ and any predicate $\\pi$, deducing $\\pi(C)$ given $\\O(C)$ is tantamount to deducing $\\pi(C)$ given unbounded computational resources and polynomially many oracle queries to $C$. VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation.We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\\em strong IO} (SIO). Essentially, $\\O$ is SIO for class $\\C$ if $\\O(C)\\approx\\O(C\')$ whenever the pair $(C,C\')$ is taken from a distribution over $\\C$ where, for all $x$, $C(x)\\neq C\'(x)$ only with negligible probability.

We then show that an obfuscator is VGB for a class $\\C$ if and only if it is SIO for $\\C$. This result is unconditional and holds for any $\\C$. We also show that, for some circuit collections, SIO implies virtual black-box obfuscation.

Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC$^1$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security.

{\\em Put together, we obtain VGB obfuscation for all NC$^1$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$^1$ circuits.} We also show that semantic security is in essence {\\em necessary} for showing VGB obfuscation.

*15:17* [Pub][ePrint]
General Statistically Secure Computation with Bounded-Resettable Hardware Tokens, by Nico Döttling and Daniel Kraschewski and Jörn Müller-Quade and Tobias Nilges
Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Döttling, Kraschewski, Müller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for arbitrary secure computations (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010).We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.