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-23
15:17 [Pub][ePrint]

15:17 [Pub][ePrint]

We propose graph encryption schemes that efficiently support approximate shortest distance queries on large-scale encrypted graphs. Shortest distance queries are one of the most fundamental graph operations and have a wide range of applications. Using such graph encryption schemes, a client can outsource large-scale privacy-sensitive graphs to an untrusted server without losing the ability to query it. Other applications include encrypted graph databases and controlled disclosure systems. We propose GRECS (stands for GRaph EnCryption for approximate Shortest distance queries) which includes three schemes that are provably secure against any semi-honest server. Our first construction makes use of only symmetric-key operations, resulting in a computationally-efficient construction. Our second scheme, makes use of somewhat-homomorphic encryption and is less computationally-efficient but achieves optimal communication complexity (i.e., uses a minimal amount of bandwidth). Finally, our third scheme is both computationally- efficient and achieves optimal communication complexity at the cost of a small amount of additional leakage. We implemented and evaluated the efficiency of our constructions experimentally. The experiments demonstrate that our schemes are efficient and can be applied to graphs that scale up to 1.6 million nodes and 11 million edges.

15:17 [Pub][ePrint]

Oblivious Transfer (OT) is the fundamental building block of cryptographic protocols. In this paper we describe the simplest and most efficient protocol for $1$-out-of-$2$ OT to date, which is obtained by tweaking the Diffie-Hellman key-exchange protocol. The protocol achieves UC-security against active corruptions in the random oracle model.

Due to its simplicity, the protocol is extremely efficient and it allows to perform $n$ OTs using only:

\\begin{itemize}

\\item \\textbf{Computation:} $3n+2$ exponentiations ($2n$ for the receiver, $n+2$ for the sender) and

\\item \\textbf{Communication:} $32(n+1)$ bytes (for the group elements), and $2n$ ciphertexts.

\\end{itemize}

We also report on an implementation of the protocol using elliptic curves (Curve25519), and on a number of mechanisms we employ to ensure that our software is secure against active attacks too.

Experimental results show that our protocol (thanks to both algorithmic and implementation optimizations) is at least one order of magnitude faster than previous work.

15:17 [Pub][ePrint]

The fundamental problem of differential cryptanalysis is to find the highest entries in the Difference Distribution Table (DDT) of a given mapping F over n-bit values, and in particular to find the highest diagonal entries which correspond to the best iterative characteristics of $F$. The standard bottom-up approach to this problem is to consider all the internal components of the mapping along some differential characteristic, and to multiply their transition probabilities. However, this can provide seriously distorted estimates since the various events can be dependent, and there can be a huge number of low probability characteristics contributing to the same high probability entry.

In this paper we use a top-down approach which considers the given mapping as a black box, and uses only its input/output relations in order to obtain direct experimental estimates for its DDT entries which are likely to be much more accurate. In particular, we describe three new techniques which reduce the time complexity of three crucial aspects of this problem: Finding the exact values of all the diagonal entries in the DDT for small values of n, approximating all the diagonal entries which correspond to low Hamming weight differences for large values of $n$, and finding an accurate approximation for any $DDT$ entry whose large value is obtained from many small contributions. To demonstrate the potential contribution of our new techniques, we apply them to the SIMON family of block ciphers, show experimentally that most of the previously published bottom-up estimates of the probabilities of various differentials are off by a significant factor, and describe new differential properties which can cover more rounds with roughly the same probability for several of its members. In addition, we show how to use our new techniques to attack a 1-key version of the iterated Even-Mansour scheme in the related key setting, obtaining the first generic attack on 4 rounds of this well-studied construction.

15:17 [Pub][ePrint]

Cryptographic multilinear maps have found many applications, such as multipartite Diffie-Hellman key exchange, general software obfuscation. However, currently only three constructions are known, and are \"noisy\" and bounded to polynomial degree. In this paper, we describe constructions of ideal multilinear maps using ideal lattices, which support arbitrary multilinearity levels. The security of our construction depends on hardness assumption over ideal lattices. Moreover, we describe one-round multipartite Diffie-Hellman key exchange protocols by using our construction.

15:17 [Pub][ePrint]

Fibonacci ring oscillators are shown to have a risk to oscillate periodically instead of chaotically. The security implications of this are discussed. The probability of the occurrence of the periodic oscillations is determined experimentally on an FPGA for Fibonacci ring oscillators of lengths 16 and 32. Means to overcome the problem of the periodic oscillations are also discussed.

15:17 [Pub][ePrint]

We analyse the security regarding timing attacks of implementations of the decryption in McEliece PKC with binary Goppa codes. First, we review and extend the existing attacks, both on the messages and on the keys. We show that, until now, no satisfactory countermeasure could erase all the timing leakages in the Extended Euclidean Algorithm (EEA) step. Then, we describe a version of the EEA never used for McEliece so far. It uses a constant number of operations for given public parameters. In particular, the operation flow does not depend on the input of the decryption, and thus closes all previous timing attacks. We end up with what should become a central tool toward a secure implementation of McEliece decryption.

13:01 [Event][New]

From June 1 to June 4
Location: College Park, USA

2015-03-22
20:21 [Event][New]

From August 10 to August 12