International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

2013-09-04
15:17 [Pub][ePrint] Automatic Security Evaluation of Block Ciphers with S-bP Structures against Related-key Differential Attacks, by Siwei Sun and Lei Hu and Ling Song and Yonghong Xie and Peng Wang

  Counting the number of active S-boxes is a common way to evaluate the security of symmetric key cryptographic schemes against differential attack. Based on Mixed Integer Linear Programming (MILP), Mouha et al proposed a method to accomplish this task automatically for word-oriented symmetric-key ciphers with SPN structures. However, this method can not be applied directly to block ciphers of SPN structures with bitwise permutation diffusion layers (S-bP structures), due to its ignorance of the diffusion effect derived collaboratively by nonlinear substitution layers and bitwise permutation layers. Moreover, the MILP constrains presented in Mouha et al\'s method are not enough to describe the differential propagation behaviour of a linear diffusion layer constructed from a non-MDS code, even an almost MDS code. In this paper we extend Mouha et al\'s method for S-bP structures by introducing new representations for exclusive-or (XOR) differences to describe bit/word level differences simultaneously and by taking the collaborative diffusion effect of S-boxes and bitwise permutations into account. Our method is applied to the block cipher PRESENT-80, an international standard for lightweight symmetric key cryptography, to automatically evaluate its security against differential attacks. We obtain lower bounds on the numbers of active S-boxes in the single-key model for full 31-round PRESENT-80 and in related-key model for round-reduced PRESENT-80 up to 12 rounds, and therefore automatically prove that the full-round PRESENT-80 is secure against single-key differential attack, and the cost of related-key differential attack on the full-round PRESENT-80 is close to that of an exhaustive search: the best related-key differential characteristic for full PRESENT-80 is upper bounded by $2^{-72}$.



15:17 [Pub][ePrint] Decomposition formula of the Jacobian group of plane curve, by Koh-ichi Nagao

  We give an algorithm for decomposing given element of Jacobian gruop

into the sum of the decomposed factor, which consists of certain subset of the points of curve.



15:17 [Pub][ePrint] Equations System coming from Weil descent and subexponential attack for algebraic curve , by Koh-ichi Nagao

  Faug\\\'ere et al. shows that the decomposition problem of an element of elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system over $bF_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over $F_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is pity that at least using linear constrains, it is exponential.

Petit et al. shows that assuming first fall degree assumption and using Gr\\\"obner basis computation, its complexity is heuristically subexponential.

On the other hands, the author shows that the decomposition problem of Jacobian of plane curve over $F_{p^n}$ also essentially reduces to solving low degree equations system over $F_p$ coming from Weil descent.

In this paper, we generalize ($p>2$ cases, Jacobian cases) and revise (precise estimation of first fall degree) the results of Petit et al. and show that the discrete logarithm problem

of elliptic curve over small characteristic field $F_{p^n}$ is subexponential of input size $n$, and the discrete logarithm problem of Jacobian of small genus curve over small characteristic field $F_{p^n}$ is also subexponential of input size $n$,

under first fall degree assumption.



15:17 [Pub][ePrint] More Efficient Cryptosystems From k-th Power Residues, by Zhenfu Cao, Xiaolei, Licheng Wang and Jun Shao

  At Eurocrypt 2013, Joye and Libert proposed a method for constructing public key cryptosystems (PKCs) and lossy trapdoor functions (LTDFs) from $(2^\\alpha)^{th}$-power residue symbols. Their work can be viewed as non-trivial extensions of the well-known PKC scheme due to Goldwasser and Micali, and the LTDF scheme due to Freeman et al., respectively. In this paper, we will demonstrate that this kind of work can be extended \\emph{more generally}: all related constructions can work for any $k^{th}$ residues if $k$ only contains small prime factors, instead of $(2^\\alpha)^{th}$-power residues only. The resultant PKCs and LTDFs are more efficient than that from Joye-Libert method in terms of decryption speed with the same message length.



15:17 [Pub][ePrint] Puzzle Encryption Algorithm, by Gregory Alvarez and Charles Berenguer

  This document describes the symmetric encryption algorithm called Puzzle. It is free and open. The objective of this paper is to get an opinion about its security from the cryptology community. It is separated in two parts, a technical description of the algorithm and its cryptanalysis. The algorithm has some interesting properties :

The block size is variable and unknown from an attacker. The size of the key has no limit and is unknown from an attacker. The key size does not affect the algorithm speed (using a 256 bit key is the same as using a 1024 bit key). The algorithm is much faster than the average cryptographic function. Experimental test showed 600 Mo/s - 4 cycles/byte on an Intel Core 2 Duo P8600 2.40GHz and 1,2 Go/s - 2 cycles/byte on an Intel i5-3210M 2.50GHz. Both CPU had only 2 cores.



15:17 [Pub][ePrint] More Efficient Oblivious Transfer and Extensions for Faster Secure Computation, by Gilad Asharov and Yehuda Lindell and Thomas Schneider and Michael Zohner

  Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.

In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.



15:17 [Pub][ePrint] Multi-Valued Byzantine Broadcast: the $t < n$ Case, by Martin Hirt and Pavel Raykov

  All known protocols implementing broadcast from synchronous point-to-point channels tolerating any $t < n$ Byzantine corruptions have communication complexity at least $\\Omega(\\ell n^2)$. We give cryptographically secure and information-theoretically secure protocols for $t < n$ that communicate $O(\\ell n)$ bits in order to broadcast sufficiently long $\\ell$ bit messages. This matches the optimal communication complexity bound for any protocol allowing to broadcast $\\ell$ bit messages. While broadcast protocols with the optimal communication complexity exist in cases where $t < n/3$ (by Liang and Vaidya in PODC \'11) or $t < n/2$ (by Fitzi and Hirt in PODC \'06), this paper is the first to present such protocols for $t < n$.



15:17 [Pub][ePrint] Formally Proved Security of Assembly Code Against Leakage, by Pablo Rauzy and Sylvain Guilley and Zakaria Najm

  In his keynote speech at CHES 2004, Kocher advocated that side-channel attacks were an illustration that formal cryptography was not as secure as it was believed because some assumptions (e.g., no auxiliary information is available during the computation) were not modeled.

This failure is due to the fact that formal methods work with models rather than implementations.

Of course, we can use formal methods to prove non-functional security properties such as the absence of side-channel leakages.

But a common obstacle is that those properties are very low-level and appear incompatible with formalization.

To avoid the discrepancy between the model and the implementation, we apply formal methods directly on the implementation.

Doing so, we can formally prove that an assembly code is leak-free, provided that the hardware it runs on satisfies a finite (and limited) set of properties that we show are realistic.

We apply this technique to prove that a PRESENT implementation in 8~bit AVR assembly code is leak-free.



15:17 [Pub][ePrint] Key Exchange with Unilateral Authentication: Composable Security Definition and Modular Protocol Design, by Ueli Maurer and Björn Tackmann and Sandro Coretti

  Key exchange with unilateral authentication (short: unilateral key exchange)

is an important primitive in practical security protocols; a prime example is

the widely deployed TLS protocol, which is usually run in this mode.

Unilateral key-exchange protocols are employed in a client-server setting

where only the server has a certified public key. The client is then

authenticated by sending credentials via a connection that is secured with the

key obtained from the protocol. Somewhat surprisingly and despite its

importance in practical scenarios, this type of key exchange has received

relatively little attention in the cryptographic literature compared to the

type with mutual authentication.

In this work, we follow the constructive cryptography paradigm of Maurer and

Renner (ICS 2011) to obtain a (composable) security definition for

key-exchange protocols with unilateral authentication: We describe a

\"unilateral key\" resource and require from a key-exchange protocol that it

constructs this resource in a scenario where only the server is authenticated.

One main advantage of this approach is that it comes with strong composition

guarantees: Any higher-level protocol proven secure with respect to the

unilateral key resource remains secure if the key is obtained using a secure

unilateral key-exchange protocol.

We then describe a simple protocol based on any CPA-secure KEM and prove that

it constructs a unilateral key (previous protocols in this setting relied on a

CCA-secure KEM). The protocol design and our security analysis are fully

modular and allow to replace a sub-protocol $\\pi$ by a different sub-protocol

$\\pi\'$ by only proving security of the sub-protocol $\\pi\'$; the composition

theorem immediately guarantees that the security of the modified full protocol

is maintained. In particular, one can replace the KEM by a sub-protocol based

on Diffie-Hellman, obtaining a protocol that is similar to the A-DHKE protocol

proposed by Shoup. Moreover, our analysis is simpler because the actual

key-exchange part of the protocol can be analyzed in a simple three-party

setting; we show that the extension to the multi-party setting follows

generically.

Compared to the TLS handshake protocol, the \"de facto\" standard for unilateral

key exchange on the Internet, our protocol is more efficient (only two

messages) and is based on weaker assumptions.



15:17 [Pub][ePrint] Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012, by Oleksandr Kazymyrov and Valentyna Kazymyrova

  New GOST R 34.11-2012 standard has been recently selected by the Russian government to replace the old one. The algorithm is based on the hash function Stribog introduced in 2010. The high-level structure of the new hash function is similar to GOST R 34.11-94 with minor modifications. However, the compression function was changed significantly. Such a choice of the compression algorithm has been motivated by the Rjndael due to simplicity and understandable algebraic structure.

In this paper we consider a number of algebraic aspects of the GOST R 34.11. We show how one can express the cipher in AES-like form over the finite field $\\F_{2^8}$, and consider some approaches that can be used for the fast software implementation.



15:17 [Pub][ePrint] Black-Box Obfuscation for d-CNFs, by Zvika Brakerski and Guy N. Rothblum

  We show how to securely obfuscate a new class of functions: {\\em conjunctions of $NC0_d$ circuits}. These are functions of the form $C(x) = \\bigwedge_{i=1}^m C_i(x)$, where each $C_i$ is a boolean $NC0_d$ circuit, whose output bit is only a function of $d = O(1)$ bits of the input $x$. For example, $d$-CNFs, where each clause is a disjunction of at most $d$ variables, are in this class. Given such a function, we produce an obfuscated program that preserves the input-output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron, Lepoint and Tibouchi (CRYPTO 2013).

We prove that the construction is a secure obfuscation in a generic multilinear group model, under the black-box definition of Barak et al.\\ (CRYPTO 2001). Security is based on a new {\\em worst-case} hardness assumption about exponential hardness of the NP-complete problem 3-SAT, the {\\em Bounded Speedup Hypothesis}.

One of the new techniques we introduce is a method for enforcing input consistency, which we call {\\em randomizing sub-assignments}. We hope that this technique can find further application in constructing secure obfuscators.

The family of functions we obfuscate is considerably richer than previous works that consider black-box obfuscation. As one application, we show how to achieve {\\em obfuscated functional point testing}: namely, to construct a circuit that checks whether $f(x)=y$, where $f$ is an arbitrary ``public\'\' polynomial-time computable function, but $y$ is a ``secret\'\' point that is hidden in the obfuscation.