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-04-01
09:17 [Pub][ePrint]

We present the homomorphic evaluation of the Prince block cipher. Our leveled implementation is based on a generalization of NTRU. We are motivated by the drastic bandwidth savings that may be achieved by scheme conversion. To unlock this advantage we turn to lightweight ciphers such as Prince. These ciphers were designed from scratch to yield fast and compact implementations on resource constrained embedded platforms. We show that some of these ciphers have the potential to enable near practical homomorphic evaluation of block ciphers. Indeed, our analysis shows that Prince can be implemented using only a 24 level deep circuit. Using an NTRU based implementation we achieve an evaluation time of 3.3 seconds per Prince block - one and two orders of magnitude improvement over homomorphic AES implementations achieved using NTRU, and BGV-style homomorphic encryption libraries, respectively.

09:17 [Pub][ePrint]

Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system.

With ORAM, a curious adversary cannot tell what data address the user is accessing when observing the bits moving between the user and the storage system.

All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses.

Such redundancy incurs a large performance overhead.

Though traditional data prefetching techniques successfully hide memory latency in DRAM based systems, it turns out that they do not work well for ORAM.

In this paper, we exploit ORAM locality by taking advantage of the ORAM internal structures.

Though it might seem apparent that obliviousness and locality are two contradictory concepts, we challenge this intuition by exploiting data locality in ORAM without sacrificing provable security.

In particular, we propose an ORAM prefetching technique called dynamic super block scheme and comprehensively explore its design space.

The dynamic super block scheme detects data locality in the program\'s working set at runtime, and exploits the locality in a data-independent way.

% based on the key observation that position map ORAMs have better locality than the data ORAM.

Our simulation results show that with dynamic super block scheme, ORAM performance without super blocks can be significantly improved. After adding timing protection to ORAM, the average performance gain is 25.5\\% (up to 49.4\\%) over the baseline ORAM and 16.6\\% (up to 30.1\\%) over the best ORAM prefetching technique proposed previously.

09:17 [Pub][ePrint]

We study the problem of efficient (sub-linear) fuzzy search on encrypted outsourced data, in the symmetric-key setting. In particular, a user who stores encrypted data on a remote untrusted server forms queries that enable the server to efficiently locate the records containing the requested keywords, even though the user may misspell keywords or provide noisy data in the query. We define an appropriate primitive for a general \\emph{closeness} function on the message space that we call \\emph{efficiently fuzzy-searchable encryption} (\\emph{EFSE}).

Next we identify an optimal security notion for EFSE. We demonstrate that existing schemes do not meet our security definition and propose a new scheme that we prove secure under basic assumptions. Unfortunately, the scheme requires large ciphertext length, but we show that, in a sense, this space-inefficiency is unavoidable for a general, optimally-secure scheme.

Seeking the right balance between efficiency and security, we then show how to construct schemes that are more efficient and satisfy a weaker security notion that we propose. To illustrate, we present and analyze a more space-efficient scheme for supporting fuzzy search on biometric data that achieves the weaker notion.

07:03 [Event][New]

Submission: 28 April 2014
From September 1 to September 5
Location: Paris, France

07:03 [Event][New]

Submission: 15 December 2014
From April 2 to April 3
Location: Gaithersburg, USA

2014-03-30
00:17 [Pub][ePrint]

Zorro is a 128-bit lightweight block cipher supporting 128-bit keys, presented at CHES~2013 by G\\\'erard et al. One of the main design goals of the cipher was to allow efficient masking according to the Rivain and Prouff Scheme, which lead to a very unconventional design, using partial non-linear layers. Despite the security claims of the designers, the cipher was recently broken by differential and linear attacks due to Wang et al., recovering its 128-bit key with complexity of about $2^{108}$. These attacks are based on high-probability iterative characteristics that are made possible due a special property of the linear layer of Zorro, which is shown to be devastating in combination with its partial non-linear layer.

In this paper, we analyze the security of Zorro-like ciphers with partial non-linear layers by devising differential and linear characteristic search algorithms and key recovery algorithms. These algorithms exploit in a generic way the small number of Sboxes in a Zorro-like round, and are independent of any specific property of its linear layer (such as the one exploited by Wang et al.), or its Sbox implementation. When applied to the Zorro block cipher itself, we were able to find \\emph{the highest} probability characteristics for the full cipher and devise significantly improved attacks. Our differential attack has a time complexity of about $2^{45}$, requiring about $2^{44}$ chosen plaintexts, and our linear attack has a time complexity of about $2^{45}$, requiring about $2^{45}$ known plaintexts.

Independently of our results, the recently published paper by Rasoolzadeh et al. found similar iterative characteristics for Zorro by exploiting in a different way the devastating property of its linear layer, described by Wang et al. However, our improved key recovery techniques result in differential and linear attacks which are at least $2^{11}$ times faster. More significantly, the surprisingly large number of Zorro-like rounds analyzed by some of our generic techniques raises questions over the general design strategy of Zorro, namely, the use of partial non-linear layers.

2014-03-29
21:17 [Pub][ePrint]

Mission critical applications on homogenous mo- bile wireless sensor networks (HMWSNs) mandate new sets of security appliances to be friendly with existing resource constrained hardware platforms. To deliver a promising security, particularly in military deployments, mechanisms have to build upon an efficient key management that compensates HMWSNs constraints. Cluster-based key establishment is being the prime focus among the recent works in key establishment due to its significant improvement on network efficiency, security, scal- ability and flexibility. Therefore, we propose a Cluster-based framework to support pre-distribution key establishment schemes for HMWSNs. The proposed framework is compatible with most of pre-distribution schemes, and two instantiations are provided in this work to support our claim that the proposed framework improves security and scalability of the adopted schemes. We develop analytical models and conduct extensive simulations to evaluate the security and performance of the proposed frame- work, and the network connectivity under different scenarios.

21:17 [Pub][ePrint]

Zorro is a 128-bit lightweight block cipher supporting 128-bit keys, presented at CHES~2013 by G\\\'erard et al. One of the main design goals of the cipher was to allow efficient masking according to the Rivain and Prouff Scheme, which lead to a very unconventional design, using partial non-linear layers. Despite the security claims of the designers, the cipher was recently broken by differential and linear attacks due to Wang et al., recovering its 128-bit key with complexity of about $2^{108}$. These attacks are based on high-probability iterative characteristics that are made possible due a special property of the linear layer of Zorro, which is shown to be devastating in combination with its partial non-linear layer.

In this paper, we analyze the security of Zorro-like ciphers with partial non-linear layers by devising differential and linear characteristic search algorithms and key recovery algorithms. These algorithms exploit in a generic way the small number of Sboxes in a Zorro-like round, and are independent of any specific property of its linear layer (such as the one exploited by Wang et al.), or its Sbox implementation. When applied to the Zorro block cipher itself, we were able to find \\emph{the highest} probability characteristics for the full cipher and devise significantly improved attacks. Our differential attack has a time complexity of about $2^{45}$, requiring about $2^{44}$ chosen plaintexts, and our linear attack has a time complexity of about $2^{45}$, requiring about $2^{45}$ known plaintexts.

Independently of our results, the recently published paper by Rasoolzadeh et al. found similar iterative characteristics for Zorro by exploiting in a different way the devastating property of its linear layer, described by Wang et al. However, our improved key recovery techniques result in differential and linear attacks which are at least $2^{11}$ times faster. More significantly, the surprisingly large number of Zorro-like rounds analyzed by some of our generic techniques raises questions over the general design strategy of Zorro, namely, the use of partial non-linear layers.

15:17 [Pub][ePrint]

We evaluate the security of the recently proposed authenticated encryption scheme POET with regard to weak keys when its universal hash functions are instantiated with finite field multiplications. We give explicit constructions for weak key classes not covered by POET\'s

weak key testing strategy, and demonstrate how to leverage them to obtain universal forgeries.

00:17 [Pub][ePrint]

In this paper, we present Functional Encryption (FE) schemes for finite languages from standard static assumption, viz., \\textit{Decisional Linear} (DLIN) assumption. These finite languages are described by Deterministic Finite Automatas (DFAs). Our first scheme is ciphertext-policy functional encryption (CP-FE), where a key $\\sk_w$ is labeled with a string $w$ over a fixed alphabet $\\Sigma$ and a ciphertext $\\cipher_\\amn$ is associated with a DFA $\\amn$ over the same alphabet $\\Sigma$. The key $\\sk_w$ can extract the message from the ciphertext $\\cipher_\\amn$ if the DFA $\\amn$ accepts the string $w$. This CP-FE scheme is constructed based on attribute-based encryption (ABE) structure of Okamoto-Takashima in Asiacrypt, 2012. To achieve the adaptive security, we put bounds on number of occurrences of any symbol in a string and in the set of transition tuples of a DFA. Due to this restriction, the size of key space (where the keys are indexed with strings) is reduced to finite. Hence, the functional scope of any DFA in our system can capture only finite language. Similarly, we obtain our second adaptively secure FE scheme in key-policy flavor from DLIN assumption. Both the schemes are shown to be secure in the standard model.

2014-03-28
09:17 [Pub][ePrint]

In this paper, we investigate the properties of iterative non-injective functions and the security of primitives where they are used. First, we introduce the Collision Probability Spectrum (CPS) parameter to quantify how far from a permutation a function is. In particular, we show that the output size decreases linearly with the number of iterations whereas the collision trees grow quadratically.

Secondly, we investigate the T-sponge construction and show how certain CPS and rate values lead to an improved preimage attack on long messages. As an example, we find collisions for the GLUON-64 internal function, approximate its CPS, and show an attack that violates the security claims. For instance, if a message ends with a sequence of 1~Mb (respectively 1~Gb) of zeros, then our preimage search takes time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$.