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

2012-04-30
18:17 [Pub][ePrint] A Cryptanalysis of HummingBird-2: The Differential Sequence Analysis, by Qi Chai and Guang Gong

  Hummingbird-2 is one recent design of lightweight block ciphers targeting constraint devices, which not only enables a compact hardware implementation and ultra-low power consumption but also meets the stringent response time as specified in ISO18000-6C.

In this paper, we present the first cryptanalytic result on the full version of this cipher using two pairs of related keys. We discover that the differential sequences for the last invocation of the round function can be computed by running the full cipher, due to which the search space for the key can be reduced. Base upon this observation, we propose a probabilistic attack encompassing two phases, preparation phase and key recovery phase. The preparation phase, requiring $2^{80}$ effort in time, aims to reach an internal state, with $0.5$ success probability, that satisfies particular conditions. In the key recovery phase, by attacking the last invocation of the round function of the encryption (decryption resp.) using the proposed differential sequence analysis (DSA), we are able to recover $36$ bits (another $44$ bits resp.) of the $128$-bit key. In addition, the rest $48$ bits of the key can be exhaustively searched and the overall time complexity of the key recovery phase is $2^{49.63}$.

Note that the proposed attack, though exhibiting an interesting tradeoff between the success probability and time complexity, is only of a theoretical interest at the moment and does not affect the security of the Hummingbird-2 in practice.



18:17 [Pub][ePrint] SPN-Hash: Improving the Provable Resistance Against Differential Collision Attacks, by Jiali Choy, Huihui Yap, Khoongming Khoo, Jian Guo, Thomas Peyrin, Axel Poschmann, Chik How Tan

  Collision resistance is a fundamental property required for cryptographic hash functions. One way to ensure collision resistance is to use hash functions based on public key cryptography (PKC) which reduces collision resistance to a hard mathematical problem, but such primitives are usually slow. A more practical approach is to use symmetric-key design techniques which lead to faster schemes, but collision resistance can only be heuristically inferred from the best probability of a single differential characteristic path. We propose a new hash function design with variable hash output sizes of 128, 256, and 512 bits, that reduces this gap. Due to its inherent Substitution-Permutation Network (SPN) structure and JH mode of operation, we are able to compute its differential collision probability using the concept of differentials. Namely, for each possible input differences, we take into account all the differential paths leading to a collision and this enables us to prove that our hash function is secure against a differential collision attack using a single input difference. None of the SHA-3 finalists could prove such a resistance. At the same time, our hash function design is secure against pre-image, second pre-image and rebound attacks, and is faster than PKC-based hashes. Part of our design includes a generalization of the optimal diffusion used in the classical wide-trail SPN construction from Daemen and Rijmen, which leads to near-optimal differential bounds when applied to non-square byte arrays. We also found a novel way to use parallel copies of a serial matrix over the finite field GF(2^4), so as to create lightweight and secure byte-based diffusion for our design. Overall, we obtain hash functions that are fast in software, very lightweight in hardware (about 4625 GE for the $256$-bit hash output) and that provide much stronger security proofs regarding collision resistance than any of the SHA-3 finalists.



18:17 [Pub][ePrint] Ring-LWE in Polynomial Rings, by Leo Ducas and Alain Durmus

  The Ring-LWE problem, introduced by Lyubashevsky, Peikert, and Regev

(Eurocrypt 2010), has been steadily finding many uses in numerous

cryptographic applications. Still, the Ring-LWE problem defined

in [LPR10] involves the

fractional ideal $R^\\vee$, the dual of the ring $R$, which is the

source of many theoretical and implementation technicalities. Until

now, getting rid of $R^\\vee$, required some relatively complex

transformation that substantially increase the magnitude of the

error polynomial and the practical complexity to sample it.

It is only for rings $R=\\Z[X]/(X^n+1)$ where $n$ a power of

$2$, that this transformation is simple and benign.

In this work we show that by applying a different, and much simpler

transformation, one can transfer the results from [LPR10] into an ``easy-to-use\'\' Ring-LWE setting ({\\em i.e.} without the dual ring $R^\\vee$), with only a very

slight increase in the magnitude of the noise coefficients.

Additionally, we show that creating the correct noise distribution

can also be simplified by generating a Gaussian distribution over a

particular extension ring of $R$, and then performing a reduction

modulo $f(X)$. In essence, our results show that one does not need

to resort to using any algebraic structure that is more complicated

than polynomial rings in order to fully utilize the hardness of the

Ring-LWE problem as a building block for cryptographic applications.



18:17 [Pub][ePrint] On Necessary and Sufficient Conditions for Private Ballot Submission, by D. Bernhard and O. Pereira and B. Warinschi

  We exhibit the precise security guarantees that a public key encryption scheme needs to satisfy to guarantee ballot privacy when used in a large class of voting systems. We also identify new security notions for public key encryption that characterize the number of times that a public key can be used in different elections, and show that the most common ballot preparation approach that consists in encrypting the vote and adding a NIZK proof of its validity is sound, even without hardwiring the voter identity in the proof. Our results provide important steps towards proving the privacy of the ballot submission procedure in the widely deployed Helios voting system.



18:17 [Pub][ePrint] In the point of view security, An efficient scheme in IBE with random oracle, by Rkia Aouinatou1, Mostafa Belkasmi2

  We present in these papers a scheme, which bypasses the weakness presented in the existed scheme of IBE with random oracle. We propose, a secure scheme which project into Zp contrary to elliptic

curve as with Boneh and Franklin. More, our scheme is basing in its study of simulation in the problem 4-EBDHP which is more efficient than q-BDHIP used by Skai Kasarah. We provide the prove of security of our scheme and we show its efficiency by comparison with the scheme declared

above. Even if it we have a little cost in complexity, but as in the field cryptography we are more interested to the security, this makes our proposition more efficient.



18:17 [Pub][ePrint] The Boomerang Attacks on the Round-Reduced Skein-512, by Hongbo Yu and Jiazhe Chen and XIaoyun Wang

  The hash function Skein is one of the five finalists of the NIST SHA-3 competition;it is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with complexities 2^{104.5} and 2^{454} respectively. Examples of the distinguishers on 28-round and 31-round are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^{181}, 2^{305} and 2^{424}. Because Laurent et al. [14] pointed out that the previous boomerang distinguishers for Threefish-512 are in fact not compatible, our attacks are the first valid boomerang attacks for the final round Skein-512.



18:17 [Pub][ePrint] Zero-Knowledge for Multivariate Polynomials, by Valerie Nachef and Jacques Patarin and Emmanuel Volte

  In~\\cite{SSH} a Zero-Knowledge scheme $ZK(2)$ was designed from a solution of a set of multivariate quadratic equations over a finite field. In this paper we will give two methods to generalize this construction for polynomials of any degree $d$, i.e. we will design two Zero-Knowledge schemes $ZK(d)$ and $\\tilde {ZK}(d)$ from a set of polynomial equations of degree $d$. We will show that $\\tilde {ZK} (d)$ is optimal in term of the number of computations to be performed and that $ZK(d)$ is optimal in term of the number of bits to be send. Moreover this

property is still true for all kinds of polynomials: for example if the polynomials are sparse or dense. Finally, we will present two examples of applications: with

Brent equations, or with morphisms of polynomials.



18:17 [Pub][ePrint] Ring Switching in BGV-Style Homomorphic Encryption, by Craig Gentry and Shai Halevi and Nigel P. Smart

  BGV-style homomorphic encryption schemes over polynomial rings, rely for their security on rings of very large dimension. This large dimension is needed because of the large modulus-to-noise ratio in the key-switching matrices that are used for the top few levels of the evaluated circuit. However, larger noise (and hence smaller modulus-to-noise ratio) is used in lower levels of the circuit, so from a security standpoint it is permissible to switch to lower-dimension rings. Switching to a smaller ring, if possible, can help speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such ring-switching is nontrivial, since these schemes rely on the ring algebraic structure for their homomorphic properties.

A basic ring-switching operation was introduced by Brakerski, Gentry and Vaikuntanathan, in the context of bootstrapping over polynomial rings of the form $\\Z[X]/(X^{2^n}+1)$. In this work we first extend this technique to work over any cyclotomic ring. Then we build on the extended technique and show how it can be used not only for bootstrapping but also during the computation itself, in conjunction with the ``packed ciphertext\'\' techniques of Gentry, Halevi and Smart.



18:17 [Pub][ePrint] Key distribution system and attribute-based encryption , by Masahiro Yagisawa

  I propose the new key distribution system and attribute-based encryption scheme on non-commutative ring where the complexity required for enciphering and deciphering is small. As in this system encryption keys and decryption keys involve the attributes of each user, the system is adaptive for cloud computing systems. The security of this system is based on the complexity for solving the multivariate algebraic equations of high degree over finite field, that is, one of NP complete problems. So this system is immune from the Gröbner basis attacks. The key size of this system becomes to be small enough to handle.



18:17 [Pub][ePrint] Less is More: Relaxed yet Composable Security Notions for Key Exchange, by C. Brzuska and M. Fischlin and N.P. Smart and B. Warinschi and S. Williams

  Although they do not suffer from clear attacks, various key agreement protocols (for example that used within the TLS protocol) are deemed as insecure by existing security models for key exchange. The reason is that the derived keys are used within the key exchange step, violating the common key indistinguishability requirement.

In this paper we propose a new security definition for key exchange

protocols that offers two important benefits. Our notion is weaker than the more established ones and thus allows the analysis of a larger class of protocols. Furthermore, security in the sense that we define enjoys rather general composability properties. In addition our composability properties are derived within game based formalisms, and do not appeal to any simulation based paradigm.

Specifically, for protocols whose security relies exclusively on some underlying symmetric primitive we show that they can be securely composed with key exchange protocols provided that two main requirements hold: 1) no adversary can break the underlying {\\em primitive}, even when the primitive uses keys obtained from executions of the key exchange protocol in the presence of the adversary (this is essentially the security requirement that we introduce and formalize in this paper), and 2) the security of the protocol can be reduced to that of the primitive, no matter how the keys for the primitive are distributed. Proving that the two conditions are satisfied, and then applying our generic theorem, should be simpler than performing a monolithic analysis of the composed protocol. We exemplify our results in the case of a profile of the TLS protocol. Our definition and results are set entirely within the framework of cryptographic games (and thus avoid the use of simulation).



16:55 [Job][New] Ph.D. scholarship, Center for Advanced Security Research Darmstadt (CASED)

  CASED offers PhD Scholarships in Cybersecurity (Resilient Critical Infrastructures) at the CASED lab under the authority of Technische Universität Darmstadt and Prof. Dr. Max Mühlhäuser with funding from AGT Germany.

Relevant research topics in Cybersecurity range from adversary detection to network resilience, including mitigation and healing. Regarding the application domains, a main emphasis is put on critical infrastructures with Internet backbones. This comprises Smart Cities, Smart Grids, Smart Transport,and large-scale industrial sites.

Experience in IT security, preferably with a focus on Cybersecurity, as well as profound knowledge in computer science, distributed systems and networks are mandatory. Candidates should hold a Diploma or Master degree and should have an excellent command of English and preferably some command of German.

What we offer is an international environment and contact to experienced researchers and other PhD students working on related topics in the area of IT security. Candidates obtain a 3 year scholarship and become members of the CASED graduate school, which supports them during their entire PhD research. This includes professional courses for transferable skills like trainings in giving scientific presentations or writing scientific papers.

Your application should include your Curriculum Vitae, M.Sc./Diploma certificates and grades, a letter of motivation stating your interest in the position as well as your research interests. Furthermore, you should attach at least one letter of recommendation.

Please send your complete application by email to Prof. Dr. Max Mühlhäuser (max (at) informatik.tu-darmstadt.de).