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

19:17 [Pub][ePrint]

We present a candidate obfuscator based on composite-order Graded Encoding Schemes (GES), which are a generalization of multilinear maps. Our obfuscator operates on circuits directly without converting them into formulas or branching programs as was done in previous solutions. As a result, the time and size complexity of the obfuscated program, measured by the number of GES elements, is directly proportional to the circuit complexity of the program being obfuscated. This improves upon previous constructions whose complexity was related to the formula or branching program size. Known instantiations of Graded Encoding Schemes allow us to obfuscate circuit classes of polynomial degree, which include for example families of circuits of logarithmic depth.

We prove that our obfuscator is secure against a class of generic algebraic attacks, formulated by a generic graded encoding model. We further consider a more robust model which provides more power to the adversary and extend our results to this setting as well.

As a secondary contribution, we define a new simple notion of \\emph{algebraic security} (which was implicit in previous works) and show that it captures standard security relative to an ideal GES oracle.

19:17 [Pub][ePrint]

Linear approximations of modular addition modulo a power of two was studied by Wallen in 2003. He presented an efficient algorithm for computing linear probabilities of modular addition. In 2013 Sculte-Geers investigated the problem from another viewpoint and derived a somewhat explicit for these probabilities. In this note we give a closed formula for linear probabilities of modular addition modulo a power of two, based on what Schlte-Geers presented: our closed formula gives a better insight on these probabilities and more information can be extracted from it.

19:17 [Pub][ePrint]

We provide new bounds on how close to regular the map x |--> x^e is on arithmetic progressions in Z_N, assuming e | Phi(N) and N is composite. We use these bounds to analyze the security of natural cryptographic problems related to RSA, based on the well-studied Phi-Hiding assumption. For example, under this assumption, we show that RSA PKCS #1 v1.5 is secure against chosen-plaintext attacks for messages of length roughly (log N)/4 bits, whereas the previous analysis, due to Lewko et al (2013), applies only to messages of length less than (log N)/32.

In addition to providing new bounds, we also show that a key lemma of Lewko et al. is incorrect. We prove a weaker version of the claim which is nonetheless sufficient for most, though not all, of their applications.

Our technical results can be viewed as showing that exponentiation in Z_N is a deterministic extractor for every source that is uniform on an arithmetic progression. Previous work showed this type of statement only on average over a large class of sources, or for much longer progressions (that is, sources with much more entropy).

19:17 [Pub][ePrint]

Field inversion in GF($2^m$) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. Itoh--Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations, but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh--Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on 8 binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.

19:17 [Pub][ePrint]

In predicate encryption, a ciphertext is associated with descriptive

attribute values $x$ in addition to a plaintext $\\mu$, and a secret key is associated with a predicate $f$. Decryption returns plaintext

$\\mu$ if and only if $f(x) = 1$. Moreover, security of predicate

encryption guarantees that an adversary learns nothing about the attribute $x$ or the plaintext $\\mu$ from a ciphertext, given arbitrary many secret keys that are not authorized to decrypt the ciphertext individually.

We construct a leveled predicate encryption scheme for all circuits, assuming the hardness of the subexponential learning with errors (LWE) problem. That is, for any polynomial function $d = d(\\secp)$,

we construct a predicate encryption scheme for the class of all circuits with depth bounded by $d(\\secp)$, where $\\secp$ is the security parameter.

19:17 [Pub][ePrint]

We present a detailed security analysis of the CAESAR candidate Ascon. Amongst others, cube-like, differential and linear cryptanalysis are used to evaluate the security of Ascon. Our results are practical key-recovery attacks on round-reduced versions of Ascon-128, where the initialization is reduced to 5 out of 12 rounds. Theoretical key-recovery attacks are possible for up to 6 rounds of initialization. Moreover, we present a practical forgery attack for 3 rounds of the finalization, a theoretical forgery attack for 4 rounds finalization and zero-sum distinguishers for the full 12-round Ascon permutation. Besides, we present the first results regarding linear cryptanalysis of Ascon, improve upon the results of the design document regarding differential cryptanalysis, and prove bounds on the minimum number of (linearly and differentially) active S-boxes for the Ascon permutation.

19:17 [Pub][ePrint]

We present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments (Pass-Venkitasubramaniam, STOC\'07, Hastad et al, TCC\'10, Chung-Liu, TCC\'10). We follow the same proof framework as the previous non-tight parallel-repetition theorem of Hastad et al---which relied on *statistical distance* to measure the distance between experiments---and show that it can be made tight (and further simplied) if instead relying on *KL-divergence* as the distance between the experiments.

We then show that our proof technique directly yields tight Chernoff-type\'\' parallel-repetition theorems (where one considers a threshold\'\' verifier that accepts iff the prover manages to convince a certain fraction of the parallel verifiers, as opposed to all of them) for any public-coin interactive argument; previously, tight results were only known for either constant-round protocols, or when the gap between the threshold and the original error-probability is a constant.