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] Physical Unclonable Functions in Cryptographic Protocols: Security Proofs and Impossibility Results, by Marten van Dijk and Ulrich Rührmair

  We investigate the power of physical unclonable functions (PUFs) as a new primitive in cryptographic protocols. Our contributions split into three parts. Firstly, we focus on the realizability of PUF-protocols in a special type of stand-alone setting (the \"stand-alone, good PUF setting\") under minimal assumptions. We provide new PUF definitions that require only weak average security properties of the PUF, and prove that these definitions suffice to realize secure PUF-based oblivious transfer (OT), bit commitment (BC) and key exchange (KE) in said setting. Our protocols for OT, BC and KE are partly new, and have certain practicality and security advantages compared to existing schemes.

In the second part of the paper, we formally prove that there are very sharp limits on the usability of PUFs for OT and KE {\\em beyond} the above stand-alone, good PUF scenario. We introduce two new and realistic attack models, the so-called posterior access model (PAM) and the bad PUF model, and prove several impossibility results in

these models. First, OT and KE protocols whose security is solely based on PUFs are generally impossible in the PAM. More precisely, one-time access of an adversary to the PUF after the end of a single protocol (sub-)session makes all previous (sub-)sessions provably insecure. Second, OT whose security is solely based on PUFs is

impossible in the bad PUF model, even if only a stand alone execution of the protocol is considered (i.e., even if no adversarial PUF access after the protocol is allowed). Our impossibility proofs do not only hold for the weak PUF definition of the first part of the paper, but even apply if ideal randomness and unpredictability is assumed in the PUF, i.e., if the PUF is modeled as a random permutation oracle.

In the third part, we investigate the feasibility of PUF-based bit commitment beyond the stand-alone, good PUF setting. For a number of reasons, this case is more complicated than OT and KE. We first prove that BC is impossible in the bad PUF model if players have got access to the PUF between the commit and the reveal phase. Again, this result holds even if the PUF is \"ideal\" and modeled as a random permutation oracle. Secondly, we sketch (without proof) two new BC-protocols, which can deal with bad PUFs or with adversarial access between the commit and reveal phase, but not with both.

We hope that our results can contribute to a clarification of the usability of PUFs in cryptographic protocols. They show that new hardware properties such as offline certifiability and the erasure of PUF responses would be required in order to make PUFs a broadly applicable cryptographic tool. These features have not yet been realized in practical PUF-implementations and generally seem hard to achieve at low costs. Our findings also show that the question how PUFs can be modeled comprehensively in a UC-setting must be considered at least partly open.



18:17 [Pub][ePrint] Languages with Efficient Zero-Knowledge PCP\'s are in SZK, by Mohammad Mahmoody and David Xiao

  A \\emph{Zero-Knowledge PCP} (ZK-PCP) is a randomized PCP such that

the view of any (perhaps cheating) efficient verifier can be

efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC \'97)

constructed ZK-PCPs for all languages in $\\NEXP$. Ishai, Mahmoody,

and Sahai (TCC \'12), motivated by cryptographic applications,

revisited the possibility of \\emph{efficient} ZK-PCPs for all $L \\in

\\NP$ where the PCP is encoded as a polynomial-size circuit that

given a query $i$ returns the $i\\th$ symbol of the PCP.

Ishai \\etal showed that there is no efficient ZK-PCP for $\\NP$ with

a \\emph{non-adaptive} verifier, who prepares all of its PCP queries

before seeing any answers, unless $\\NP \\se \\coAM$ and

polynomial-time hierarchy collapses. The question of whether

\\emph{adaptive} verification can lead to efficient ZK-PCPs for $\\NP$

remained open.

In this work, we resolve this question and show that any language or

promise problem with efficient ZK-PCPs must be in $\\SZK$ (the class

of promise problems with a statistical zero-knowledge \\emph{single

prover} proof system). Therefore, no $\\NP$-complete problem can

have an efficient ZK-PCP unless $\\NP \\se \\SZK$ (which also implies

$\\NP \\se \\coAM$ and the polynomial-time hierarchy collapses).

We prove our result by reducing any promise problem with an efficient

ZK-PCP to two instances of the $\\CEA$ problem defined and studied by

Vadhan (FOCS\'04) which is known to be complete for the class $\\SZK$.



18:17 [Pub][ePrint] On Ideal Lattices and Learning with Errors Over Rings, by Vadim Lyubashevsky and Chris Peikert and Oded Regev

  The ``learning with errors\'\' (LWE) problem is to distinguish random

linear equations, which have been perturbed by a small amount of

noise, from truly uniform ones. The problem has been shown to be as

hard as worst-case lattice problems, and in recent years it has served

as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an

inherent quadratic overhead in the use of LWE. A main open question

was whether LWE and its applications could be made truly efficient by

exploiting extra algebraic structure, as was done for lattice-based

hash functions (and related primitives).

We resolve this question in the affirmative by introducing an

algebraic variant of LWE called \\emph{ring-LWE}, and proving that it

too enjoys very strong hardness guarantees. Specifically, we show

that the ring-LWE distribution is pseudorandom, assuming that

worst-case problems on ideal lattices are hard for polynomial-time

quantum algorithms. Applications include the first truly practical

lattice-based public-key cryptosystem with an efficient security

reduction; moreover, many of the other applications of LWE can be made

much more efficient through the use of ring-LWE.



18:17 [Pub][ePrint] A General Construction for 1-round $\\delta$-RMT and (0, $\\delta$)-SMT, by Reihaneh Safavi-Naini and Mohammed Ashraful Alam Tuhin and Pengwei Wang

  In Secure Message Transmission (SMT) problem, a sender $\\cal S$ is connected to a

receiver $\\cal R$ through $N$ node disjoint bidirectional paths in the network, $t$ of

which are controlled by an adversary with \\textit{unlimited computational power}.

$\\cal{S}$ wants to send a message $m$ to $\\cal{R}$ in a \\textit{reliable} and \\textit{private} way. It is proved that SMT is possible if and only if $N\\ge2t+1$. In Reliable Message Transmission (RMT) problem, the network setting is the same and the goal is to provide reliability for communication, only.

In this paper we focus on 1-round $\\delta$-RMT and $(0,\\delta)$-SMT where the chance of protocol failure (receiver cannot decode the sent message) is at most $\\delta$, and in the case of SMT, privacy is perfect.

We propose a new approach to the construction of 1-round $\\delta$-RMT and (0, $\\delta$)-SMT for all connectivities $N \\ge 2t+1$, using list decodable codes and message authentication codes. Our concrete constructions use folded Reed-Solomon codes and multireceiver message authentication codes. The protocols have optimal transmission rates and provide the highest reliability among all known comparable protocols. Important advantages of these constructions are, (i) they can be adapted to all connectivities, and (ii) have simple and direct security (privacy and reliability) proofs using properties of the underlying codes, and $\\delta$ can be calculated from parameters of the underlying codes.

We discuss our results in relation to previous work in this area and propose directions for future research.



18:17 [Pub][ePrint] Implementing Pairings at the 192-bit Security Level, by Diego F. Aranha and Laura Fuentes-Castañeda and Edward Knapp and Alfred Menezes and Francisco Rodríguez-Henríquez

  We implement asymmetric pairings derived from Kachisa-Schaefer-Scott (KSS), Barreto-Naehrig (BN), and Barreto-Lynn-Scott (BLS) elliptic curves at the 192-bit security level. Somewhat surprisingly, we find pairings derived from BLS curves with embedding degree 12 to be the fastest for our serial as well as our parallel implementations. Our serial implementations provide a factor-3 speedup over the previous state-of-the-art, demonstrating that pairing computation at the 192-bit security level is not as expensive as previously thought. We also present a general framework for deriving a Weil-type pairing that is well-suited for computing a single pairing on a multi-processor machine.



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.