International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-07-18
21:17 [Pub][ePrint]

By introducing extra shields on Shpilrain and Ushakov\'s Ko-Lee-like protocol based on the decomposition problem of group elements we propose two new key exchange schemes and then a number of public key cryptographic protocols. We show that these protocols are free of known attacks. Particularly,if the entities taking part in our protocols create their private keys composed by the generators of the Mihailova subgroups of Bn, we show that the safety of our protocols are very highly guarantied by the insolvability of subgroup membership problem of the Mihailova subgroups.

21:17 [Pub][ePrint]

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]

In cryptography, forward secrecy is a well-known property of key agreement protocols. It

ensures 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]

Authors propose several approaches for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm (EEA). First approach is based on Extended Euclidean Algorithm specificity: either invariant polynomial u remains intact or swaps with invariant polynomial v. It makes it possible to avoid necessity of polynomial v degree computing. The second approach is based on searching the \"next matching index\" when calculating the degree of the polynomial, since degree polynomial invariant u at least decreases by 1, then it is possible to use current value while further calculation the degree of the polynomial.

21:17 [Pub][ePrint]

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.

21:17 [Pub][ePrint]

In order to obtain differential patterns over many rounds of a cryptographic primitive, the cryptanalyst often needs to work on local differential trail analysis. Examples include merging two differential trail parts into one or, in the case of boomerang and rectangle attacks, connecting two short trails within the quartet boomerang setting. In the latter case, as shown by Murphy in 2011, caution should be exercised as there is increased chance of running into contradictions in the middle rounds of the primitive. In this paper, we propose the use of a SAT-based constraint solver URSA as aid in analysis of differential trails and find that previous rectangle/boomerang attacks on XTEA and SHACAL-1 block ciphers and SM3 hash function are based on incompatible trails. Given the C specification of the cryptographic primitive, verifying differential trail portions requires minimal work on the side of the cryptanalyst.

15:17 [Pub][ePrint]

We propose a log signing scheme that enables (a) verification of the integrity of the whole log, and (b) presentation of any record, along with a compact proof that the record has not been altered since the log was signed, without leaking any information about the contents of other records in the log. We give a formal proof of the security of the proposed scheme, discuss practical considerations, and provide an implementation case study.

15:17 [Pub][ePrint]

In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for standard\'\' two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a \\emph{fixed set of parties} who know each other\'s identities ahead of time, and machines \\emph{cannot be added dynamically} to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework. Nevertheless, standard secure computation tasks (like secure function evaluation) can be expressed. Importantly, we show a natural security-preserving transformation from protocols in the SUC model to protocols in the full-fledged UC model. Consequently, the UC composition theorem holds in the SUC model, and any protocol that is proven secure under SUC can be transformed to a protocol that is secure in the UC model.

15:17 [Pub][ePrint]

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]

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]

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.