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

2015-03-19
09:17 [Pub][ePrint]

NXP Semiconductors and its academic partners challenged the

cryptographic community with finding practical attacks on the block

cipher they designed, PRINCE. Instead of trying to attack as many

rounds as possible using attacks which are usually impractical

despite being faster than brute-force, the challenge invites

cryptographers to find practical attacks and encourages them to

actually implement them.

In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the

6 and 8-round categories --- the highest for which winners were

identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher.

We also describe heuristic methods we used to find practical SAT-based and differential attacks.

Finally, we also present an analysis of the cycle structure of the

internal rounds of PRINCE leading both to a low complexity

distinguisher for 4-round PRINCE-core and an alternative

representation of the cipher valid in particular contexts and which

highlights, in this cases, a poor diffusion.

09:17 [Pub][ePrint]

TWINE is a recent lightweight block cipher based on a Feistel

structure. We first present two new attacks on TWINE-128

reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity.

Then, we introduce alternative representations of both the round

function of this block cipher and of a sequence of 4 rounds. LBlock,

another lightweight block cipher, turns out to exhibit the same

behaviour. Then, we illustrate how this alternative representation

can shed new light on the security of TWINE by deriving high

probability iterated truncated differential trails covering 4 rounds

with probability $2^{-16}$.

The importance of these is shown by combining different

truncated differential trails to attack 23-rounds TWINE-128 and by

giving a tighter lower bound on the high probability of some

differentials by clustering differential characteristics following

one of these truncated trails. A comparison between these high

probability differentials and those recently found in a variant of

LBlock by Leurent highlights the importance of considering the whole

distribution of the coefficients in the difference distribution

table of a S-Box and not only their maximum value.

09:17 [Pub][ePrint]

The demand for more efficient ciphers is a likely to sharpen with new generation of products and applications. Previous cipher designs typically focused on optimizing only one of the two parameters - hardware size or speed, for a given security level. In this paper, we present a methodology for designing a class of stream ciphers which takes into account both parameters simultaneously. We combine the advantage of the Galois configuration of NLFSRs, short propagation delay, with the advantage of the Fibonacci configuration of NLFSRs, which can be analyzed formally. According to our analysis, the presented stream cipher Espresso is the fastest among the ciphers below 1500 GE, including Grain-128 and Trivium.

09:17 [Pub][ePrint]

Quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proofs is a powerful paradigm, suggested recently by Jutla and Roy (Asiacrypt\'13), which is motivated by the Groth-Sahai seminal techniques for efficient non-interactive zero-knowledge (NIZK) proofs. In this paradigm, the common reference string may depend on specific language parameters, a fact that allows much shorter proofs in important cases. It even makes certain standard model applications competitive with the Fiat-Shamir heuristic in the Random Oracle idealization (such QA-NIZK proofs were recently optimized to constant size by Jutla and Roy (Crypto\'14) and Libert et al. (Eurocrypt\'14) for the important case of proving that a vector of group elements belongs to a linear subspace). While, e.g., the QA-NIZK arguments of Libert et al. provide unbounded simulation-soundness and constant proof length, their simulation-soundness is only loosely related to the underlying assumption (with a gap proportional to the number of adversarial queries) and it is unknown how to alleviate this limitation without sacrificing efficiency. Here, we deal with the basic question of whether and to what extent we can simultaneously optimize the proof size and the tightness of security reductions, allowing for important applications with tight security (which are typically to date quite lengthy) to be of shorter size. In this paper, we resolve this question by describing a novel simulation-sound QA-NIZK argument showing that a vector $\\vec{v} \\in \\G^n$ belongs to a subspace of rank $t 09:17 [Pub][ePrint] A fundamental primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party to another, despite the presence of byzantine corruptions. In this work we address the problem in the general adversary model of Hirt and Maurer, which subsumes earlier models such as the global or local threshold adversaries. Regarding the topology knowledge, we employ the recently introduced Partial Knowledge Model [13], which encompasses both the full knowledge and the ad hoc model; the latter assumes knowledge of the local neighborhood only. Our main contributions are: (a) a necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary; in order to show sufficiency, we propose a protocol that solves RMT whenever this is possible, therefore the protocol is unique (cf.[14]), and (b) a study of efficiency in the special case of the ad hoc network model; we present a unique protocol scheme that is fully polynomial for a class of instances, if there exists any fully polynomial protocol for RMT on the decomposition of this class to instances of a certain basic topology. To obtain our results we employ, among others, an operation on adversary structures, an appropriate notion of separator in unreliable networks, and a self-reducibility property of the RMT problem. 09:17 [Pub][ePrint] We introduce internal differential boomerang distinguisher as a combination of internal differentials and classical boomerang distinguishers. The new boomerangs can be successful against cryptographic primitives having high-probability round-reduced internal differential characteristics. The internal differential technique, which follow the evolution of differences between parts of the state, is particularly meaningful for highly symmetric functions like the inner permutation Keccak-f of the hash functions defined in the future SHA-3 standard. We find internal differential and standard characteristics for three to four rounds of Keccak-f, and with the use of the new technique, enhanced with a strong message modification, show practical distinguishers for this permutation. Namely, we need$2^{12}$queries to distinguish 7 rounds of the permutation starting from the first round, and approximately$2^{18}$queries to distinguish 8 rounds starting from the fourth round. Due to the exceptionally low complexities, all of our results have been completely verified with a computer implementation of the analysis. 09:17 [Pub][ePrint] The PRINCE cipher is the result of a cooperation between the Technical University of Denmark (DTU), NXP Semiconductors and the Ruhr University Bochum. The cipher was designed to reach an extremely low-latency encryption and instant response time. PRINCE has already gained a lot of attention from the academic community, however, most of the attacks are theoretical, usually with very high time or data complexity. Our work helps to fill the gap in more practically oriented attacks, with more realistic scenarios and complexities. We present new attacks, up to 7 rounds, relying on integral and higher-order differential cryptanalysis. 09:17 [Pub][ePrint] We introduce \\emph{implicit zero-knowledge} arguments (iZK) and simulation-sound variants thereof (SSiZK); these are lightweight alternatives to zero-knowledge arguments for enforcing semi-honest behavior. Our main technical contribution is a construction of efficient two-flow iZK and SSiZK protocols for a large class of languages under the (plain) DDH assumption in cyclic groups in the common reference string model. As an application of iZK, we improve upon the round-efficiency of existing protocols for securely computing inner product under the DDH assumption. This new protocol in turn provides privacy-preserving biometric authentication with lower latency. 09:17 [Pub][ePrint] Pairings are typically implemented using ordinary pairing-friendly elliptic curves. The two input groups of the pairing function are groups of elliptic curve points, while the target group lies in the multiplicative group of a large finite field. At moderate levels of security, at least two of the three pairing groups are necessarily proper subgroups of a much larger composite-order group, which makes pairing implementations potentially susceptible to small-subgroup attacks. To minimize the chances of such attacks, or the effort required to thwart them, we put forward a property for ordinary pairing-friendly curves called subgroup security. We point out that existing curves in the literature and in publicly available pairing libraries fail to achieve this notion, and propose a list of replacement curves that do offer subgroup security. These curves were chosen to drop into existing libraries with minimal code change, and to sustain state-of-the-art performance numbers. In fact, there are scenarios in which the replacement curves could facilitate faster implementations of protocols because they can remove the need for expensive group exponentiations that test subgroup membership. 09:17 [Pub][ePrint] Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assumption. All previous efficient VES schemes in the standard model are either secure under standard assumptions (such as the computational Diffie-Hellman assumption) with large verification (or secret) keys or secure under \\emph{(non-standard) dynamic$q$-type assumptions} (such as the$q$-strong Diffie-Hellman extraction assumption) with short verification keys. Our construction is the first efficient VES scheme with short verification (and secret) keys secure under \\emph{a standard assumption (DLIN)}. As by-products of our VES scheme, we construct new obfuscators for ES/EVES based on our new VES scheme. They are more efficient than previous obfuscators with respect to the public key size. Previous obfuscators for EVES are secure under non-standard assumption and use zero-knowledge (ZK) proof systems and Fiat-Shamir heuristics to obtain non-interactive ZK, i.e., its security is considered in the random oracle model. Thus, our construction also has an advantage with respect to assumptions and security models. Our new obfuscator for ES is obtained from our new obfuscator for EVES. 09:17 [Pub][ePrint] Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan~(Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over$R^{\\mu}$, where the ring is$R = \\mathbb{Z}_q$. Several applications require the ring$R$to be exponentially large and, thus, they set$q = 2^{O(n)}$to implement such applications. This choice results in the AFV IPE scheme with public parameters of size$O(\\mu n^2 \\lg^3{q}) = O(\\mu n^5)$and ciphertexts of size$O(\\mu n \\lg^3{q}) = O(\\mu n^4)$, where$n$is the security parameter. Hence, this makes the scheme impractical, as they noted. We address this efficiency issue by untwisting\'\' their twist and providing another twist. Our scheme supports inner-product predicates over$R^\\mu$where$R = \\mathrm{GF}(q^n)$instead of$\\mathbb{Z}_q$. Our scheme has public parameters of size$O(\\mu n^2 \\lg^2{q})$and ciphertexts of size$O(\\mu n \\lg^2{q})$. Since the cardinality of$\\mathrm{GF}(q^n)$is inherently exponential in$n$, we have no need to set$q\$ as the exponential size for applications.

As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti (Latincrypt 2012). Our fuzzy IBE is secure under a much weaker assumption than that employed by Agrawal et al.~(PKC 2012), who constructed the first lattice-based fuzzy IBE scheme.