*09:17* [Pub][ePrint]
TUC: Time-sensitive and Modular Analysis of Anonymous Communication, by Michael Backes and Praveen Manoharan and Esfandiar Mohammadi
The anonymous communication (AC) protocol Tor constitutes the most widely deployed technology for providing anonymity for user communication over the Internet. Tor has been subject to several analyses which have shown strong anonymity guarantees for Tor. However, all previous analyses ignore time-sensitive leakage: timing patterns in web traffic allow for attacks such as website fingerprinting and traffic correlation, which completely break the anonymity provided by Tor. For conducting a thorough and comprehensive analysis of Tor that in particular includes all of these time-sensitive attacks, one of the main obstacles is the lack of a rigorous framework that allows for a time-sensitive analysis of complex AC protocols.In this work, we present TUC (for Time-sensitive Universal Composability): the first universal composability framework that includes a comprehensive notion of time, which is suitable for and tailored to the demands of analyzing AC protocols. As a case study, we extend previous work and show that the onion routing (OR) protocol, which underlies Tor, can be securely abstracted in TUC, i.e., all time-sensitive attacks are reflected in the abstraction. We finally leverage our framework and this abstraction of the OR protocol to formulate a countermeasure against website fingerprinting attacks and to prove this countermeasure secure.

*09:17* [Pub][ePrint]
A Note on the Impossibility of Obfuscation with Auxiliary Input, by Shafi Goldwasser and Yael Tauman Kalai
In this note we revisit the problem of obfuscation with auxiliary inputs. We show that the existence of indistinguishablity obfuscation (iO) implies that all functions with sufficient \"pseudo-entropy\" cannot be obfuscated with respect to a virtual box definition (VBB) in the presence of (dependent) auxiliary input.Namely, we show that for any candidate obfuscation O and for any function family F={f_s} with sufficient pseudo-entropy, there exists an (efficiently computable) auxiliary input aux, that demonstrates the insecurity of O. This is true in a strong sense: given O(f_s) and aux one can efficiently recover the seed s, whereas given aux and oracle access to f_s it is computationally hard to recover s.

A similar observation was pointed out in a recent work of Goldwasser et. al. (Crypto 2013), assuming *extractable* witness encryption. In this note we show that the extractability property of the witness encryption is not needed to get our negative result, and all that is needed is the existence of witness encryption, which in turn can be constructed from iO obfuscation.

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