*15:17* [Pub][ePrint]
A key recovery attack to the scale-invariant NTRU-based somewhat homomorphic encryption scheme, by Eduardo Morais and Ricardo Dahab
In this paper we present a key recovery attack to the scale-invariant NTRU-based somewhat homomorphic encryption scheme proposed by Bos et al~\\cite{NTRUbasedFHE} in 2013. The attack allows us to compute the private key for $t>2$ and when the private key is chosen with coefficients in $\\{-1,0,1\\}$. The efficiency of the attack is optimal since it requires just one decryption oracle query, showing that if we don\'t look for this kind of vulnerabilities in homomorphic encryption constructions we are likely to choose insecure parameters. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to this kind of attack, hence our result indicates that building CCA1-secure homomorphic schemes is not trivial.We also provide tables showing how the multiplicative depth is affected when the critical parameter $\\Bkey$ is chosen in order to mitigatte the attack.

*15:17* [Pub][ePrint]
Side Channel Power Analysis of an AES-256 Bootloader, by Colin O\'Flynn and Zhizhang Chen
Side Channel Attacks (SCA) using power measurements are a known method of breaking cryptographic algorithms such as AES. Published research into attacks on AES frequently target only AES-128, and often target only the core Electronic Code-Book (ECB) version, without discussing surrounding issues such as triggering, along with breaking the initialization vector.This paper demonstrates a complete attack on a secure bootloader, where the firmware files have been encrypted with AES-256-CBC. A Correlation Power Analysis (CPA) attack is performed on AES-256 to recover the complete 32-byte key, and a CPA attack is also used to attempt recovery of the initialization vector (IV).

The attack on the IV demonstrates a CPA attack against a single XOR operation, which has relevance to cryptographic functions beyond AES.

*21:17* [Pub][ePrint]
Protecting obfuscation against arithmetic attacks, by Eric Miles and Amit Sahai and Mor Weiss
Recently, the work of Garg et al. (FOCS 2013) gave the first candidate general-purpose obfuscator. This construction is built upon multilinear maps, also called a graded encoding scheme. Several subsequent works have shown that variants of this obfuscator achieves the highest notion of security (VBB security) against \"purely algebraic\" attacks, namely attacks that respect the restrictions of the graded encoding scheme. While important, the scope of these works is somewhat limited due to the strong restrictions imposed on the adversary.We propose and analyze another variant of the Garg et al. obfuscator in a setting that imposes fewer restrictions on the adversary that we call the arithmetic setting. This setting captures a broader class of algebraic attacks than considered in previous works. Most notably, it allows for unlimited additions across different \"levels\" of the encoding. In this setting, we present two results:

- First, in the arithmetic setting where the adversary is limited to creating only multilinear polynomials, we obtain an unconditional proof of VBB security.

- Second, in the arithmetic setting where the adversary can create polynomials of arbitrary degree, we prove VBB security under an assumption that is closely related to the Bounded Speedup Hypothesis of Brakerski and Rothblum (TCC 2014). We also give evidence that any unconditional proof of VBB security in this model would entail proving the algebraic analog of P \\neq NP.

*21:17* [Pub][ePrint]
Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective, by Joppe W. Bos and Michael Naehrig and Joop van de Pol
Lattice-based cryptography is a promising candidate for providing cryptographic functions that remain secure in a post-quantum era. The security of lattice-based schemes relies on the hardness of lattice problems such as the problem of finding short vectors in integral lattices. In this work, we propose a new variant of the parallel Gauss sieve algorithm which can compute such short vectors. Our algorithm combines favorable properties of previous approaches: all vectors in the global list remain pairwise Gauss reduced (reducing the list size and runtime) while this list is split up between the participating nodes (lowering the memory requirements per node). To demonstrate the benefits of this variant, we present an optimized implementation of our parallel algorithm, using commonly available vector instruction set extensions. We conducted experiments with lattices of dimensions 80, 88, and 96, and the results show that the new approach outperforms the previous parallel Gauss sieve algorithms. The implementation will be made available, and we hope that it will serve as a basis for additional experiments.Almost all recent implementations of lattice-based cryptographic schemes use ideal lattices, and it is known that sieving algorithms can benefit from their additional algebraic structure. Namely, the list size can be reduced by considering vectors along with all their rotations. We show that ideal lattices allow more optimizations, which enhance the performance of sieving algorithms even further. We use the fast Fourier transform (FFT) to speed up the computation of inner products between a vector and the rotations of another. On a conventional, academic computer cluster, our algorithm solved an SVP ideal lattice challenge in a negacyclic ideal lattice of dimension 128 in less than nine days using 1024 cores. This is more than twice as fast as the recent computation by Ishiguro et al. that solved the same challenge on a cluster with the same computer architecture, but without using large shared memory. This indicates that the FFT version can lead to a practical performance increase compared to a naive version using only rotations. Our results shed additional light on the security of schemes which rely on the hardness of computing short vectors in this special setting.

*21:17* [Pub][ePrint]
Obfuscation of Probabilistic Circuits and Applications, by Ran Canetti and Huijia Lin and Stefano Tessaro and Vinod Vaikuntanathan
This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic indistinguishability obfuscation (pIO).We define several variants of pIO, using different approaches to formalizing the above security requirement, and study non-trivial relations among them. Moreover, we give a construction of one of our pIO variants from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions, and conjecture this construction to be a good candidate for other pIO variants.

We then move on to show a number of applications of pIO:

* We give a general and natural methodology to achieve leveled homomorphic encryption (LHE) from variants of semantically secure encryption schemes and of pIO. In particular, we propose instantiations from lossy and re-randomizable encryption schemes, assuming the two weakest notions of pIO.

* We enhance the above constructions to obtain a full-fledged (i.e., non-leveled) FHE scheme under the same (or slightly stronger) assumptions. In particular, this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security.

* Finally, we show that assuming sub-exponentially secure puncturable PRFs computable in NC1, sub-exponentially-secure indistinguishability obfuscation for (deterministic) NC1 circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits.

*18:17* [Pub][ePrint]
CM55: special prime-field elliptic curves almost optimizing den Boer\'s reduction between Diffie-Hellman and discrete logs, by Daniel R. L. Brown
Using the Pohlig--Hellman algorithm, den Boer reduced the discrete logarithm problem to the Diffie--Hellman problem in groups of an order whose prime factors were each one plus a smooth number. This report reviews some related general conjectural lower bounds on the Diffie-Hellman problem in elliptic curve groups that relax the smoothness condition into a more commonly true condition.This report focuses on some elliptic curve parameters defined over a prime field size of size 9+55(2^288), whose special form may provide some efficiency advantages over random fields of similar sizes. The curve has a point of Proth prime order 1+55(2^286), which helps to nearly optimize the den Boer reduction. This curve is constructed using the CM method. It has cofactor 4, trace 6, and fundamental discriminant -55.

This report also tries to consolidate the variety of ways of deciding between elliptic curves (or other algorithms) given the efficiency and security of each.