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



15:17 [Pub][ePrint] Practical approaches to varying network size in combinatorial key predistribution schemes, by Kevin Henry and Maura B. Paterson and Douglas R. Stinson

  Combinatorial key predistribution schemes can provide a practical solution to the problem of distributing symmetric keys to the nodes of a wireless sensor network. Such schemes often inherently suit networks in which the number of nodes belongs to some restricted set of values (such as powers of primes). In a recent paper, Bose, Dey and Mukerjee have suggested that this might pose a problem, since discarding keyrings to suit a smaller network might adversely affect the properties of the scheme.

In this paper we explore this issue, with specific reference to classes of key predistribution schemes based on transversal designs. We demonstrate through experiments that, for a wide range of parameters, randomly removing keyrings in fact has a negligible and largely predictable effect on the parameters of the scheme. In order to facilitate these computations, we provide a new, efficient, generally applicable approach to computing important properties of combinatorial key predistribution schemes.

We also show that the structure of a resolvable transversal design can be exploited to give a deterministic method of removing keyrings to adjust the network size, in such a way that the properties of the resulting scheme are easy to analyse. We show that these schemes have the same asymptotic properties as the transversal design schemes on which they are based, and that for most parameter choices their behaviour is very similar.



15:17 [Pub][ePrint] A Constructive Approach to Functional Encryption, by Christian Matt and Ueli Maurer

  Functional encryption is an important generalization of several types of encryption such as public-key, identity-based, and attribute-based encryption. Numerous different security definitions for functional encryption have been proposed, most of them being rather complex and involving several algorithms. Many of these definitions differ in details such as which algorithm has oracle access to which oracle, while the consequences of specific choices are often unclear. This spans a large space of possible definitions without a consensus on the adequacy of specific points in this space. What a particular definition means and for which applications it is suitable remains unsettled.

To remedy this situation, we propose a novel interpretation of functional encryption, based on the Constructive Cryptography framework, in which a protocol is seen as a construction of an ideal resource with desired properties from a real resource, which is assumed to be available. The resulting ideal resource can then be used as a real resource in other protocols to construct more advanced resources. The real resource we consider here corresponds to a public repository that allows everyone to read its contents. Such repositories are indeed widely available on the internet. Using functional encryption, we construct, as the ideal resource, a repository with fine-grained access control.

Based on this constructive viewpoint, we propose a new security definition, called FA-security, for functional encryption by adequately modifying an established definition, and prove the equivalence to our notion of construction. This gives evidence that FA-security is an appropriate definition. We further consider known impossibility results and examine a weaker security definition. We show that this weaker definition, for which secure schemes exist, is sufficient to construct a repository that restricts the number and order of interactions. This makes explicit how such schemes can be used.



15:17 [Pub][ePrint] Sometimes-Recurse Shuffle: Almost-Random Permutations in Logarithmic Expected Time, by Ben Morris and Phillip Rogaway

  We describe a security-preserving construction of a random permutation of domain size N from a random function, the construction tolerating adversaries asking all N plaintexts, yet employing just \\Theta(lg N) calls, on average, to the one-bit-output random function. The approach is based on card shuffling. The basic idea is to use the \\textit{sometimes-recurse} transformation: lightly shuffle the deck (with some other shuffle), cut the deck, and then recursively shuffle one of the two halves. Our work builds on a recent paper of Ristenpart and Yilek.



15:17 [Pub][ePrint] Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis, by Pawel Morawiecki and Josef Pieprzyk and Marian Srebrny and Michal Straus

  In this paper we use differential cryptanalysis to attack the winner of the SHA-3 competition, namely Keccak hash function. Despite more than 6 years of intensive cryptanalysis there have been known only two preimage attacks which reach 3 (or slightly more) rounds. Our 3-round preimage attack improves the complexity of those two existing attacks and it is obtained with a different technique. We also show the partial preimage attack on the 4-round Keccak, exploiting two properties of the linear step of the Keccak-f permutation.



13:32 [Event][New] Crypto 2014

  From August 17 to August 21
Location: Santa Barbara, USA
More Information: http://www.iacr.org/conferences/crypto2014/




2013-09-03
20:48 [Job][New] Junior Professorship in Mobile Security, Ruhr-Universität Bochum, Germany

  The Faculty of Electrical Engineering and Information Technology at the Ruhr-Universität Bochum invites applications for the position of a Junior Professorship for Mobile Security.

The future occupant of the position Mobile Security represents the department in this field in research and teaching. The appointment will be at the rank of an assistant professor.

His/her scientific work should focus on one or more of the following key research areas:

- Security of mobile systems at the hard- or software level

- Security aspects of new application domains (especially cyber-physical systems)

- Reverse engineering of hardware and software systems

- Security aspects of distributed systems

- Secure and dependable software systems

A doctoral degree of outstanding quality and evidence of special aptitude in teaching are just as much required as the willingness to participate in the self-governing bodies of the RUB. Furthermore, we expect the candidate to generally get involved in university processes according to RUB’s mission statement. Beside the specific skills the candidate should have a profound didactical qualification to develop new learning environments such as research oriented teaching.

We expect furthermore readiness to participate in interdisciplinary academic work, willingness and ability to attract external funding, ability to work in teams, and the will to participate in collaborative research.

The Ruhr-Universität Bochum is an equal opportunity employer.