*09:17* [Pub][ePrint]
A TPM Diffie-Hellman Oracle, by Tolga Acar and Lan Nguyen and Greg Zaverucha
This note describes a Diffie-Hellman oracle, constructed using standard Trusted Platform Module (TPM) signature APIs. The oracle allows one to compute the exponentiation of an arbitrary group element to a specified TPM-protected private key.By employing the oracle, the security provided by a group of order p is reduced by log k bits, provided k oracle queries are made and p +/- 1 is divisible by k. The security reduction follows from a straightforward application of results from Brown and Gallant (IACR ePrint 2004/306) and Cheon (Eurocrypt 2006) on the strong Diffie-Hellman problem.

On a more positive note, the oracle may allow a wider range of cryptographic protocols to make use of the TPM.

*09:17* [Pub][ePrint]
Obfuscation for Evasive Functions, by Boaz Barak and Nir Bitansky and Ran Canetti and Yael Tauman Kalai and Omer Paneth and Amit Sahai
An evasive circuit family is a collection of circuits C such that for every input x, a random circuit from C outputs 0 on x with overwhelming probability. We provide a combination of definitional, constructive, and impossibility results regarding obfuscation for evasive functions:

- The (average case variants of the) notions of virtual black box obfuscation (Barak et al, CRYPTO \'01) and virtual gray box obfuscation (Bitansky and Canetti, CRYPTO \'10) coincide for evasive function families. We also define the notion of input-hiding obfuscation for evasive function families, stipulating that for a random c \\in C it is hard to find, given O(c), a value outside the preimage of 0. Interestingly, this natural definition, also motivated by applications, is likely not implied by the seemingly stronger notion of average-case virtual black-box obfuscation.

- If there exist average-case virtual gray box obfuscators for all evasive function families, then there exist (quantitatively weaker) average-case virtual gray obfuscators for all function families.

- There does not exist a worst-case virtual black box obfuscator even for evasive circuits, nor is there an average-case virtual gray box obfuscator for evasive Turing machine families.

- Let C be an evasive circuit family consisting of functions that test if a low-degree polynomial (represented by an efficient arithmetic circuit) evaluates to zero modulo some large prime p.

Then under a natural analog of the discrete logarithm assumption in a group supporting multilinear maps, there exists an input-hiding obfuscator O for C. Under a new perfectly-hiding multilinear encoding assumption, there is an average-case virtual black box obfuscator for the family C.

*09:17* [Pub][ePrint]
Switching Lemma for Bilinear Tests and Constant-size NIZK Proofs for Linear Subspaces, by Charanjit Jutla and Arnab Roy
We state a switching lemma for tests on adversarial inputs involving bilinear pairings in hard groups, where the tester can effectively switch the randomness used in the test from being given to the adversary to being chosen after the adversary commits its input. The switching lemma can be based on any $k$-linear hardness assumptions on one of the groups. In particular, this enables convenient information theoretic arguments in the construction of sequence of games proving security of cryptographic schemes, paralleling proofs and constructions in the random oracle model.

As an immediate application, we show that the quasi-adaptive NIZK proofs of Jutla and Roy (ASIACRYPT 2013) for linear subspaces can be further shortened to \\emph{constant}-size proofs, independent of the number of witnesses and equations. In particular, under the SXDH assumption, a length $n$ vector of group elements can be proven to belong to a subspace of rank $t$ with a quasi-adaptive NIZK proof of just a single group element. Similar quasi-adaptive aggregation of proofs is also shown for Groth-Sahai NIZK proofs of linear multi-scalar multiplication equations, as well as linear pairing-product equations (equations without any quadratic terms).

*09:17* [Pub][ePrint]
Robust Pseudorandom Generators, by Yuval Ishai and Eyal Kushilevitz and Xin Li and Rafail Ostrovsky and Manoj Prabhakaran and Amit Sahai and David Zuckerman
Let $G:\\bits^n\\to\\bits^m$ be a pseudorandom generator.We say that a circuit implementation of $G$ is {\\em $(k,q)$-robust} if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ the remaining outputs are pseudorandom.

We initiate the study of robust PRGs, presenting explicit and non-explicit constructions in which $k$ is close to $n$, $q$ is constant, and $m>>n$. These include unconditional constructions of robust $r$-wise independent PRGs and small-bias PRGs, as well as conditional constructions of robust cryptographic PRGs.

In addition to their general usefulness as a more resilient form of PRGs, our study of robust PRGs is motivated by cryptographic applications in which an adversary has a local view of a large source of secret randomness. We apply robust $r$-wise independent PRGs towards reducing the randomness complexity of private circuits and protocols for secure multiparty computation, as well as improving the ``black-box complexity\'\' of constant-round secure two-party computation.

*09:17* [Pub][ePrint]
Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians, by Benjamin Smith
The first step in elliptic curve scalar multiplication algorithms based on scalar decompositions using efficient endomorphisms---including Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) multiplication, as well as higher-dimensional and higher-genus constructions---is to produce a short basis of a certain integer lattice involving the eigenvalues of the endomorphisms. The shorter the basis vectors, the shorter the decomposed scalar coefficients, and the faster the resulting scalar multiplication. Typically, knowledge of the eigenvalues allows us to write down a long basis, which we then reduce using the Euclidean algorithm, Gauss reduction, LLL, or even a more specialized algorithm.In this work, we use elementary facts about quadratic rings to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS, and Q-curve constructions on elliptic curves, and for genus 2 real multiplication constructions. We do not pretend that this represents a significant optimization in scalar multiplication, since the lattice reduction step is always an offline precomputation---but it does give a better insight into the structure of scalar decompositions. In any case, it is always more convenient to use a ready-made short basis than it is to compute a new one.

*09:17* [Pub][ePrint]
Traps to the BGJT-Algorithm for Discrete Logarithms, by Qi Cheng and Daqing Wan and Jincheng Zhuang
In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thom{\\\'e}, a quasi-polynomial time

algorithm (QPA) is proposed for the discrete logarithm problem over finite fields

of small characteristic. The time complexity analysis of the algorithm is

based on several heuristics presented in their paper.

We show that some of the heuristics

are problematic in their original forms,

in particular, when the field is not a Kummer extension.

We believe that the basic idea behind the new approach should still work,

and propose a fix to the algorithm in non-Kummer cases,

without altering the quasi-polynomial time complexity.

The modified algorithm is also heuristic.

Further study is required in order

to fully understand the effectiveness of the new approach.

*09:17* [Pub][ePrint]
A Practical Related-Key Boomerang Attack for the Full MMB Block Cipher, by Tomer Ashur and Orr Dunkelman
The MMB block cipher (Modular Multiplication-based Block cipher) is an iterative block cipher designed by Daemen, Govaerts, and Vandewalle in 1993 as an improvement of the PES and IPES ciphers. In this paper we present several new related-key differential characteristics of MMB. These characteristics can be used to form several related-key boomerangs to attack the full MMB. Using 2^{20} adaptive chosen plaintexts and ciphertexts we recover all key bits in 2^{35} time for the full MMB. Our attack was experimentally verified, and it takes less than 15 minutes on a standard Intel i5 machine to recover the full MMB key.

After showing this practical attack on the full key of the full MMB, we present partial attacks on extended versions of MMB with up to 9 rounds (which is three more rounds than in the full MMB). We recover 62 out of the 128-bit key in time of 2^{29.2} for 7-round MMB, using 2^{20} adaptive chosen plaintexts and ciphertexts encrypted under 4 related-keys, and time of 2^{29} for 8-round MMB using 2^{20} adaptive chosen plaintexts and ciphertexts, encrypted under 6 related-keys. We show how an adversary can recover 31 out of the 128-bit key for the 9-round MMB in time of 2^{27.8} using 2^{19} adaptive chosen plaintexts and ciphertexts, encrypted under only 2 related-keys. We also show how the time complexity of all attacks can be reduced by partially precomputing the difference distribution table of MMB\'s components.

*09:17* [Pub][ePrint]
Automatic Security Evaluation for Bit-oriented Block Ciphers in Related-key Model: Application to PRESENT-80, LBlock and Others, by Siwei Sun, Lei Hu, Peng Wang
Since AES and PRESENT are two international standard block ciphers representing the most elegant design strategies for byte-oriented and bit-oriented designs respectively, we regard AES and PRES\\-ENT the two most significant candidates to scrutinize with respect to related-key differential attack.In EUROCRYPT 2010 and CRYPTO 2013, the security of AES with respect to related-key differential attack has been completely analyzed by Alex Biryukov et al and Pierre-Alain Fouque et al with automatic related-key differential characteristic searching tools.

In this paper, we propose two methods to describe the differential behaviour of an S-box with linear inequalities based on logical condition modelling and computational geometry.

In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box.

For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-Integer Linear Programming (MILP) technique, we successfully prove that the full-round PRESENT-80 is secure against standard related-key differential attack, which solves an open problem of the symmetric-key cryptography community. This proof is accomplished automatically on a workstation with 8 CPU cores in a time within 16 days. In a similar way, we also prove that the probability of the best related-key differential characteristic of full LBlock is upper bounded by $2^{-56}$, which is the first result concerning the security of full LBlock with respect to related-key differential attack.

The methodology presented in this paper is generic, automatic and applicable to lightweight constructions with small block size, small S-boxes, and bit-oriented operations, including but not limited to PRESENT, EPCBC, LBlock, etc, which opens a new interesting direction of research for bit-oriented ciphers and for the application of MILP technique in cryptography.