International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates 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).

00:17 [Pub][ePrint] Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems, by Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir

  In this paper we show that a large class of diverse problems have a

bicomposite structure which makes it possible to solve them with a new

type of algorithm called {\\it dissection}, which has much better time/memory

tradeoffs than previously known algorithms. A typical example is the problem

of finding the key of multiple encryption schemes with $r$ independent

$n$-bit keys. All the previous error-free attacks required time $T$ and memory

$M$ satisfying $TM = 2^{rn}$, and even if ``false negatives\'\' are allowed, no

attack could achieve $TM

00:17 [Pub][ePrint] Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams, by T-H. Hubert Chan and Mingfei Li and Elaine Shi and Wenchang Xu

  We consider applications scenarios where an untrusted aggregator wishes to continually monitor the heavy-hitters across a set of distributed streams. Since each stream can contain sensitive data, such as the purchase history of customers, we wish to guarantee the privacy of each stream, while allowing the untrusted aggregator to accurately detect the heavy hitters and their approximate frequencies.

Our protocols are scalable in settings where the volume of streaming data is large, since we guarantee low memory usage and processing overhead by each data source, and low communication overhead between the data sources and the aggregator.

00:17 [Pub][ePrint] Private Fingerprint Matching, by Siamak F. Shahandashti and Reihaneh Safavi-Naini and Philip Ogunbona

  We propose a fully private fingerprint matching protocol that compares two fingerprints based on the most widely-used minutia-based fingerprint matching algorithm. The protocol enables two parties, each holding a private fingerprint, to find out if their fingerprints belong to the same individual. Unlike previous works, we do not make any simplifying assumption on the matching algorithm or use generic multiparty computation protocols in our constructions. We employ a commonly-used algorithm that works by first comparing minutia pairs from the two fingerprints based on their types, locations, and orientations, and then checking if the number of matching minutia pairs is more than a threshold, and we propose a concrete, scalable, and modular protocol. We prove security against honest-but-curious adversaries and discuss how security against malicious adversaries can be achieved using standard cryptographic techniques. Our protocol is realized using common cryptographic primitives and do not require pairing- or lattice-based cryptography.

00:17 [Pub][ePrint] Hedged Public-key Encryption: How to Protect against Bad Randomness, by Mihir Bellare and Zvika Brakerski and Moni Naor and Thomas Ristenpart and Gil Segev and Hovav Shacham and Scott Yilek

  Public-key encryption schemes rely for their IND-CPA security on per-message fresh randomness. In practice, randomness may be of poor quality for a variety of reasons, leading to failure of the schemes. Expecting the systems to improve is unrealistic. What we show in this paper is that we can, instead, improve the cryptography to offset the lack of possible randomness. We provide public-key encryption schemes that achieve IND-CPA security when the randomness they use is of high quality, but, when the latter is not the case, rather than breaking completely, they achieve a weaker but still useful notion of security that we call IND-CDA. This hedged public-key encryption provides the best possible security guarantees in the face of bad randomness. We provide simple RO-based ways to make in-practice IND-CPA schemes hedge secure with minimal software changes. We also provide non-RO model schemes relying on lossy trapdoor functions (LTDFs) and techniques from deterministic encryption. They achieve adaptive security by establishing and exploiting the anonymity of LTDFs which we believe is of independent interest.

00:17 [Pub][ePrint] Almost-Everywhere Secure Computation with Edge Corruptions, by Nishanth Chandran and Juan Garay and Rafail Ostrovsky

  We consider secure multi-party computation (MPC) in a setting where

the adversary can separately corrupt not only the parties (nodes) but

also the communication channels (edges), and can furthermore choose

selectively and adaptively which edges or nodes to corrupt. Note that

if an adversary corrupts an edge, even if the two nodes that share

that edge are honest, the adversary can control the link and thus

deliver wrong messages to both players. We consider this question in

the information-theoretic setting, and require security against a

computationally unbounded adversary.

In a fully connected network the above question is simple (and we

also provide an answer

that is optimal up to a constant factor). What makes the problem

more challenging is to consider the case of sparse networks.

Partially connected networks are far more realistic than fully

connected networks, which led Garay and Ostrovsky [Eurocrypt\'08] to

formulate the notion of (unconditional) \\emph{almost everywhere (a.e.)

secure computation} in the node-corruption model, i.e., a model in

which not all pairs of nodes are connected by secure channels and the

adversary can corrupt some of the nodes (but not the edges). In such a setting,

MPC amongst all honest nodes cannot be guaranteed due

to the possible poor connectivity of some honest nodes with other

honest nodes, and hence some of

them must be ``given up\'\' and left out of the

computation. The number of such nodes is a function of the underlying

communication graph and the adversarial set of nodes.

In this work we introduce the notion of \\emph{almost-everywhere secure

computation with edge corruptions}, which is exactly the same problem as

described above, except that we additionally allow the adversary to

completely control some of the communication channels between two

correct nodes---i.e., to ``corrupt\'\' edges in the network. While it is

easy to see that an a.e. secure computation protocol for the original

node-corruption model is also an a.e. secure computation protocol tolerating

edge corruptions (albeit for a reduced fraction of edge corruptions

with respect to the bound for node corruptions), no polynomial-time

protocol is known in the case where a {\\bf constant fraction} of the edges can be corrupted (i.e., the maximum that can be tolerated)

and the degree of the network is sub-linear.

We make progress on this front, by constructing graphs of degree

$O(n^\\epsilon)$ (for arbitrary constant $0

09:17 [Pub][ePrint] (Pseudo) Preimage Attack on Round-Reduced Gr{\\o}stl Hash Function and Others (Extended Version), by Shuang Wu and Dengguo Feng and Wenling Wu and Jian Guo and Le Dong and Jian Zou

  The Gr{\\o}stl hash function is one of the 5 final round candidates of the {\\shathree} competition hosted by NIST. In this paper, we study the preimage resistance of the Gr{\\o}stl hash function. We propose pseudo preimage attacks on Gr{\\o}stl hash function for both 256-bit and 512-bit versions, i.e. we need to choose the initial value in order to invert the hash function. Pseudo preimage attack on 5(out of 10)-round Gr{\\o}stl-256 has a complexity of $(2^{244.85},2^{230.13})$ (in time and memory) and pseudo preimage attack on 8(out of 14)-round Gr{\\o}stl-512 has a complexity of $(2^{507.32},2^{507.00})$. To the best of our knowledge, our attacks are the first (pseudo) preimage attacks on round-reduced Gr{\\o}stl hash function, including its compression function and output transformation. These results are obtained by a variant of meet-in-the-middle preimage attack framework by Aoki and Sasaki. We also improve the time complexities of the preimage attacks against 5-round Whirlpool and 7-round AES hashes by Sasaki in FSE~2011.

09:17 [Pub][ePrint] Cryptanalysis of Hummingbird-2, by Kai Zhang, Lin Ding and Jie Guan

  Hummingbird is a lightweight encryption and message authentication primitive published in RISC\'09 and WLC\'10. In FSE\'11, Markku-Juhani O.Saarinen presented a differential divide-and-conquer method which has complexity upper bounded by 264 operations and requires processing of few megabytes of chosen messages under two related nonces (IVs). The improved version, Hummingbird-2, was presented in RFIDSec 2011. Based on the idea of differential collision, this paper discovers some weaknesses of the round function WD16 combining with key loading algorithm and we propose a related-key chosen-IV attack which can recover the full secret key. Under 24 pairs of related keys, the 128 bit initial key can be recovered, with the computational complexity of O(232.6) and data complexity of O(232.6). The result shows that the Hummingbird-2 cipher can\'t resist related key attack.

18:01 [PhD][New] Tolga Acar: High-Speed Algorithms & Architectures For Number-Theoretic Cryptosystems

  Name: Tolga Acar
Topic: High-Speed Algorithms & Architectures For Number-Theoretic Cryptosystems
Category: implementation

Description: Computer and network security systems rely on the privacy and authenticity of information, which requires implementation of cryptographic functions. Software implementations of these functions are often desired because of their flexibility and cost effectiveness. In this study, we concentrate on developing high-speed and area-efficient modular multiplication and exponentiation algorithms for number-theoretic cryptosystems.\r\nThe RSA algorithm, the Diffie-Hellman key exchange scheme and Digital Signature\r\nStandard require the computation of modular exponentiation, which is broken into a series\r\nof modular multiplications. One of the most interesting advances in modular exponentiation has been the introduction of Montgomery multiplication. We are interested in two aspects of modular multiplication algorithms: development of fast and convenient methods on a given hardware platform, and hardware requirements to achieve high-performance\r\nalgorithms.\r\nArithmetic operations in the Galois field GF(2^k) have several applications in coding\r\ntheory, computer algebra, and cryptography. We are especially interested in cryptographic applications where k is large, such as elliptic curve cryptosystems.[...]

16:52 [Event][Update] FSE 2013: Fast Software Encryption

  From March 11 to March 13
Location: Singapore, Singapore
More Information:

08:17 [Event][New] FSE 2013: Fast Software Encryption

  From March 11 to March 13
Location: Singapore, Singapore
More Information:

21:12 [Event][New] STM 2012: 8th International Workshop on Security and Trust Management

  Submission: 25 May 2012
Notification: 15 July 2012
From September 13 to September 14
Location: Pisa, Italy
More Information: