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-10-22
18:17 [Pub][ePrint]

We initiate the study of good rate homomorphic encryption schemes.

Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme

for {\\em large-output} polynomial-size branching programs (which we call $\\mathbf{L/poly}$) that possesses near optimal-rate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree-$m$ polynomial, where $m$ is the length of the branching program. We employ the Newton-Puiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\\Theta (\\log m)$-time algorithm to find an integer approximation to $s$.

We also describe a rate-optimal 1-out-of-$n$ CPIR based on rate-optimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\\ell = 3.8 \\cdot 10^{9}$-bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\\%$ of bandwidth for privacy.

We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$-out-of-$n$ CPIR has rate $1- 1.72 \\sqrt{k / \\ell} \\cdot \\log_{2} n + O_\\ell(\\ell^{-1})$, while we show that no black-box construction surpasses $1 - \\sqrt{k / \\ell} (\\log n/ \\log \\log n) + O_\\ell(\\ell^{-1})$ in terms of rate, where $\\ell$ is the length of the database elements and $k$ the security parameter.

18:17 [Pub][ePrint]

In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime $2^{521} - 1$.

Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST\'s (and SECG\'s) curve P-521 requires $989,000$ cycles, while on the recently proposed Edwards curve E-521 it requires just $779,000$ cycles. As a comparison, on the same architecture openSSL\'s ECDH speed test for curve P-521 requires $1,319,000$ cycles.

Furthermore, our code was written entirely in C with no non-compiler optimisations and so is robust across different platforms.

The basic observation behind these speedups is that the form of the modulus allows

one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very

little overhead from extra additions, in contrast to the usual Karatsuba methods.

18:17 [Pub][ePrint]

We design and implement dynamic symmetric searchable encryption schemes that efficiently and privately search server-held encrypted databases with tens of billions of record-keyword pairs. Our basic theoretical construction supports single-keyword searches and offers asymptotically optimal server index size, fully parallel searching, and minimal leakage. Our implementation effort brought to the fore several factors ignored by earlier coarse-grained theoretical performance analyses, including low-level space utilization, I/O parallelism and goodput. We accordingly introduce several optimizations to our theoretically optimal construction that model the prototype\'s characteristics designed to overcome these factors. All of our schemes and optimizations are proven secure and the information leaked to the untrusted server is precisely quantified. We evaluate the performance of our prototype using two very large datasets: a synthesized census database with 100 million records and hundreds of keywords per record and a multi-million webpage collection that includes Wikipedia as a subset. Moreover, we report on an implementation that uses the dynamic SSE schemes developed here as the basis for supporting recent SSE advances, including complex search queries (e.g., Boolean queries) and richer operational settings (e.g., query delegation), in the above terabyte-scale databases.

18:17 [Pub][ePrint]

Keccak is the hash function selected by NIST as the new SHA-3 standard. Keccak is built on Sponge construction and it provides a new MAC function called MAC-Keccak. These new algorithms have raised questions with regards to side-channel leakage and analysis attacks of MAC-Keccak. So far there exists prior work on attacks of software implementations of MAC-Keccak, but there has been no comprehensive side-channel vulnerability assessment of its hardware implementation. In this paper we describe an attack on the $\\theta$ step of the first round of MAC-Keccak implemented on an FPGA. We construct several different side-channel leakage models and implement attacks based on them. Our work shows that an unmasked hardware implementation of SHA-3 is vulnerable to power-based side-channel attacks.

18:17 [Pub][ePrint]

Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the undisturbed bits in the S-Box an attack of this type can only reach 7 rounds. Although the observation and the cryptanalytic application of undisturbed bits are given, their relation with other properties of an S-Box remain unknown. This paper presents some results on mathematical properties of S-Boxes having undisturbed bits. We show that an S-Box has undisturbed bits if any of its coordinate functions has a nontrivial linear structure. The relation of undisturbed bits with other cryptanalytic tools such as difference distribution table (DDT) and linear approximation table (LAT) are also given. We show that autocorrelation table is proven to be a more useful tool, compared to DDT, to obtain all nonzero input differences that yield undisturbed bits. Autocorrelation table can then be viewed as a counterpart of DDT for truncated differential cryptanalysis. Given an nxm balanced S-Box, we state that the S-Box has undisturbed bits whenever the degree of any of its coordinate function is quadratic.

15:17 [Pub][ePrint]

Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated

variants of slide attacks which slide an encryption operation against a decryption operation, and were used in 2000 to attack several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework, which was used to attack 20-round GOST and several additional variants of the Even-Mansour construction. In this paper, we revisit all the previously published applications of these techniques and show that in almost all cases, the same or better results can be achieved

by a simpler attack which is based on the seemingly unrelated idea of exploiting their internal fixed points. The observation that such fixed points can be useful in cryptanalysis had already been pointed out in 2007 by Kara, but all the examples he gave for his reflection attack were based on particular constructions such as Feistel structures or GOST key schedules in which it was easy to explicitly

list and count their fixed points.

In this paper, we generalize Kara\'s reflection attack by using the combinatorial result that random involutions on 2^n values are expected to have a surprisingly large number of O(2^{n/2}) fixed points (whereas random permutations are expected to have only O(1) fixed points). This makes it possible to reduce the complexity of the best known attack on additional cryptographic schemes in which it is difficult to explicitly characterize and count their internal fixed points.

15:17 [Pub][ePrint]

In this paper we study the question of key management and

practical operational security in bitcoin digital currency storage systems. We study the security two most used bitcoin HD Wallet key management solutions (e.g. in BIP032 and in earlier systems). These systems have extensive audit capabilities but this property comes at a very high price. They are excessively fragile. One small security incident in a remote corner of the system and everything collapses, all private keys can be recovered and ALL bitcoins within the remit of the system can be stolen. Privilege escalation attacks on HD Wallet solutions are not new. In this paper we take it much further. We propose new more advanced combination attacks in which the security of keys hold in cold storage can be compromised without executing any software exploit on the cold system, but through security incidents at operation such as bad random number or related random events.

In our new attacks all bitcoins over whole large security domains can be stolen by people who have the auditor keys which are typically stored in hot systems connected to the Internet and can be stolen easily. Our combination attacks allow to recover private keys which none of the earlier attacks in isolation could hope to recover. Classical bad random attacks typically concern only very few bitcoin accounts, and only some very lucky holders of bitcoins can actually steal other people\'s bitcoins.

In this paper we go beyond identical random attacks and show several

attacks which also work with related random events, which events are

more probable and yet less likely to be detected before it is too late. We also present several attacks which work across distinct security domains which share no common setup, code or keys. Yet in certain circumstances all the bitcoins in each domain can be stolen. All our attacks are practical and realistic given the numerous relevant events have already happened in the bitcoin blockchain hundreds of times, some as recently as September 2014.

It is not clear if this problem can be repaired, i.e. if there exists a key management solution with similar audit capabilities as BIP032 which would be immune against this sort of advanced combination attacks.

15:17 [Pub][ePrint]

Proxy re-encryption (PRE) schemes are cryptosystems which allow a proxy who has a re-encryption key to convert a ciphertext originally encrypted for one party into a ciphertext which can be decrypted by another party. In IWSEC 2011, Hayashi et al. proposed the new security notion for PRE called unforgeability of re-encryption keys against collusion attacks,\'\' UFReKey-CA for short. They proposed the PRE schemes and claimed that their schemes meet UFReKey-CA. However, Isshiki et al. pointed out that the schemes do not meet UFReKey-CA in IWSEC 2013. It is an open problem of constructing the scheme which meets UFReKey-CA. In this paper, we propose new PRE schemes which meet confidentiality (RCCA security) assuming that the q-wDBDHI problem is hard and meet UFReKey-CA assuming that the 2-DHI problem is hard.

13:45 [Event][New]

Submission: 31 March 2015
From August 26 to August 28
Location: Nara, Japan

2014-10-21
06:17 [Pub][ePrint]

The increasing ubiquity of the cloud computing paradigm has renewed focus on the classical problem of allowing weak clients to check the results of computation delegated to powerful servers. Recent advances in proof-based verifiable computation have led to several near-practical protocols. Protocols based on interactive proofs (IPs) work with highly restrictive models of computation and are thus efficient only for a limited class of computations. In contrast, protocols based on argument systems apply to a much larger class of computations, but efficiency requires amortization of very expensive setup costs.

This paper initiates the study of the practical efficiency of multiprover interactive proofs (MIPs). We present a new MIP for delegating computation that extends insights from a powerful IP protocol (Goldwasser et al., STOC, 2008). Without reductions or amplification, our protocol uses only two provers (departing from prior work on MIPs), and achieves both the efficiency of interactive proof-based protocols and the generality of argument system-based protocols. Also, this result, together with recently developed machinery, creates a potential avenue toward concretely efficient arguments without setup costs.

We describe Clover, a built system for verifiable computation, based on our protocol. Although Clover does not implement the full theory (it has setup costs), it applies to problems that existing IPs cannot efficiently handle, and achieves performance comparable to, or better than, the best argument systems.

03:17 [Pub][ePrint]

Adaptively secure multiparty computation first studied by Canetti, Feige, Goldreich, and Naor in 1996, is a fundamental notion in cryptography. Adaptive security is particulary hard to achieve in settings where arbitrary number of parties can be corrupted and honest parties are not trusted to properly erase their internal state. We still do not know how to realize constant round protocols for this task against even if we were to restrict ourselves to semi-honest adversaries and to the simpler two-party setting. Specifically the round complexity of known protocols grows with the depth of the circuit the parties are trying to compute.

In this work, using indistinguishability obfuscation, we construct a UC-secure two-round adaptively secure multiparty computation protocol.