*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.

*15:17* [Pub][ePrint]
Securing Cloud Data in the New Attacker Model, by Ghassan O. Karame, Claudio Soriente, Krzysztof Lichota, Srdjan Capkun
The world just witnessed the surge of a new and powerful attacker,which was able to coerce operators and acquire the necessary keys to break the privacy of users. Once the encryption key is exposed, the only viable measure to preserve data confidentiality is to limit the adversary\'s access to the ciphertext. This may be achieved, for example, using multi-cloud storage systems. These systems spread data across multiple servers in different administrative domains, to cater for availability and fault tolerance. If the adversary can only compromise a subset of these domains, multi-cloud storage systems may prevent the adversary from accessing the entire ciphertext. However, if data is encrypted using existing encryption schemes, spreading the ciphertext on multiple servers does not entirely solve the problem since an adversary which has the encryption key, can still compromise single servers and decrypt the ciphertext stored therein.

In this paper, we leverage multi-cloud storage systems to provide data confidentiality against an adversary which has access to the encryption key, and can compromise a large fraction of the storage servers. For this purpose, we first introduce a novel security definition that captures data confidentiality in the new adversarial

model. We then propose Bastion, a primitive that is secure according to our definition and, therefore, guarantees data confidentiality even when the encryption key is exposed, as long as the adversary cannot compromise all storage servers. We analyze the security of Bastion, and we evaluate its performance by means of a prototype implementation. Our results show that Bastion incurs less than 5%

overhead compared to existing semantically secure encryption modes. We also discuss practical insights with respect to the integration of Bastion in commercial multi-cloud storage systems.