International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2015-01-16
15:33 [Event][New]

Submission: 24 April 2015
From September 28 to September 30
Location: Florence, Italy

15:32 [Event][New]

Submission: 2 March 2015
From August 24 to August 28
Location: Toulouse, France

15:31 [Event][New]

Submission: 15 March 2015
From June 11 to June 12
Location: Gaithersburg, USA

10:17 [Pub][ePrint]

In the first part of this work, we introduce a new type of pseudo-random function for which aggregate queries\'\' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values

belonging to an exponential-sized interval, or the sum of all function values on points for which a polynomial time predicate holds. We show how to use algebraic properties of underlying

classical pseudo random functions, to construct aggregatable pseudo random functions for a number of classes of aggregation queries under cryptographic hardness assumptions. On the flip side, we show that certain aggregate queries are impossible to support.

In the second part of this work, we show how various extensions of pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s and 1990s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.

2015-01-15
19:17 [Pub][ePrint]

At AFRICACRYPT 2010 and CARDIS 2011, fresh re-keying schemes to counter side-channel and fault attacks were introduced. The idea behind those schemes is to shift the main burden of side-channel protection to a re-keying function $g$ that is easier to protect than the main block cipher. This function produces new session keys based on the secret master key and random nonces for every block of message that is encrypted. In this paper, we present a generic chosen-plaintext key-recovery attack on both fresh re-keying schemes. The attack is based on two observations: Since session key collisions for the same message are easy to detect, it is possible to recover one session key with a simple time-memory trade-off strategy; and if the re-keying function is easy to invert (such as the suggested multiplication constructions), the attacker can use the session key to recover the master key. The attack has a complexity of about $2 \\cdot 2^{n/2}$ (instead of the expected $2^n$) for an $n$-bit key. For the typically employed block cipher AES-128, this would result in a key-recovery attack complexity of only $2^{65}$. If weaker primitives like 80-bit PRESENT are used, even lower attack complexities are possible.

19:17 [Pub][ePrint]

Having ciphers that provide confidentiality and authenticity, that are fast in software and efficient in hardware, these are the goals of the CAESAR authenticated encryption competition. In this paper, the promising CAESAR candidate Ascon is implemented in hardware and optimized for different typical applications to fully explore Ascon\'s design space. Thus, we are able to present hardware implementations of Ascon suitable for RFID tags, Wireless Sensor Nodes, Embedded Systems, and applications that need maximum performance. For instance, we show that an Ascon implementation with a single unrolled round transformation is only 7 kGE large, but can process up to 5.5 Gbit/sec of data (0.75 cycles/byte), which is already enough to encrypt a Gigabit Ethernet connection. Besides, Ascon is not only fast and small, it can also be easily protected against DPA attacks. A threshold implementation of Ascon just requires about 8 kGE of chip area, which is only 3.1 times larger than the unprotected low-area optimized implementation.

19:17 [Pub][ePrint]

A simple and practical hashing scheme based on Cyclic Redundancy Check (CRC) is presented. Similarly to previously proposed cryptographically secure CRCs, the presented one detects both, random and malicious, errors without increasing bandwidth. However, we use a product of irreducible polynomials instead of a single irreducible polynomial for generating the CRC. This is an advantage since smaller irreducible polynomials are easier to compute. The price we pay is that the probability that two different messages map into the same CRC increases. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The presented method seems to be particularly attractive for the authentication of short messages.

19:17 [Pub][ePrint]

GLV curves (Gallant et al.) have performance advantages over standard elliptic curves, using half the number of point doublings for scalar multiplication. Despite their introduction in 2001, implementations of the GLV method have yet to permeate widespread software libraries. Furthermore, side-channel vulnerabilities, specifically cache-timing attacks, remain unpatched in the OpenSSL code base since the first attack in 2009 (Brumley and Hakala) even still after the most recent attack in 2014 (Benger et al.). This work reports on the integration of the GLV method in OpenSSL for curves from 160 to 256 bits, as well as deploying and evaluating two side-channel defenses. Performance gains are up to 51%, and with these improvements GLV curves are now the fastest elliptic curves in OpenSSL for these bit sizes.

19:17 [Pub][ePrint]

As low-cost RFID tags become more and more ubiquitous, it is necessary to design ultralightweight RFID authentication protocols to prevent possible attacks and threats. We reevaluate Ahmadian et al.\'s desynchronization attack on the ultralightweight RFID authentication protocol with permutation (RAPP). Our results are twofold: (1) we demonstrate that the probability of the desynchronization between the tag and the reader is 15/64 instead of 1/4 as claimed, when RAPP uses Hamming weight-based rotation; (2) we further improve the original attack and make the desynchronization more efficient.

19:17 [Pub][ePrint]

In the first part of this work, we introduce a new type of pseudo-random function for which aggregate queries\'\' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values

belonging to an exponential-sized interval, or the sum of all function values on points for which a polynomial time predicate holds. We show how to use algebraic properties of underlying

classical pseudo random functions, to construct aggregatable pseudo random functions for a number of classes of aggregation queries under cryptographic hardness assumptions. On the flip side, we show that certain aggregate queries are impossible to support.

In the second part of this work, we show how various extensions of pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s and 1990s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.

2015-01-14
22:17 [Pub][ePrint]

Boneh et al. (Crypto 13) and Banerjee and Peikert (Crypto 14) constructed pseudorandom functions (PRFs) from the Learning with Errors (LWE) assumption by embedding combinatorial objects, a path and a tree respectively, in instances of the LWE problem. In this work, we show how to generalize this approach to embed circuits, inspired by recent progress in the study of Attribute Based Encryption.

Embedding a universal circuit for some class of functions allows us to produce constrained keys for functions in this class, which gives us the first standard-lattice-assumption-based constrained PRF (CPRF) for general bounded-description bounded-depth functions, for arbitrary polynomial bounds on the description size and the depth. (A constrained key w.r.t a circuit $C$ enables one to evaluate the PRF on all $x$ for which $C(x)=1$, but reveals nothing on the PRF values at other points.) We rely on the LWE assumption and on the one-dimensional SIS (Short Integer Solution) assumption, which are both related to the worst case hardness of general lattice problems. Previous constructions for similar function classes relied on such exotic assumptions as the existence of multilinear maps or secure program obfuscation. The main drawback of our construction is that it does not allow collusion (i.e. to provide more than a single constrained key to an adversary).

Similarly to the aforementioned previous works, our PRF family is also key homomorphic.

Interestingly, our constrained keys are very short. Their length does not depend directly either on the size of the constraint circuit or on the input length.

We are not aware of any prior construction achieving this property, even relying on strong assumptions such as indistinguishability obfuscation.