*10:17* [Pub][ePrint]
Why Proving HIBE Systems Secure is Difficult, by Allison Lewko and Brent Waters
Proving security of Hierarchical Identity-Based Encryption (HIBE) andAttribution Based Encryption scheme is a challenging problem. There are multiple well-known schemes in the literature where the best known (adaptive) security proofs degrade exponentially in the maximum

hierarchy depth. However, we do not have a rigorous understanding of

why better proofs are not known. (For ABE, the analog of hierarchy depth is the maximum number of attributes used in a ciphertext.)

In this work, we define a certain commonly found checkability property on ciphertexts and private keys. Roughly the property states that any two different private keys that are both ``supposed to\'\' decrypt a ciphertext will decrypt it to the same message. We show that any simple black box reduction to a non-interactive assumption for a HIBE or ABE system that contains this property will suffer an exponential degradation of security.

*10:17* [Pub][ePrint]
Hardness of SIS and LWE with Small Parameters, by Daniele Micciancio and Chris Peikert
The Short Integer Solution (SIS) and Learning With Errors (LWE) problems are the foundations for countless applications in lattice-based cryptography, and are provably as hard as approximate lattice problems in the worst case. A important question from both a practical and theoretical perspective is how small their parameters can be made, while preserving their hardness.We prove two main results on SIS and LWE with small parameters. For SIS, we show that the problem retains its hardness for moduli $q \\geq \\beta \\cdot n^{\\delta}$ for any constant $\\delta > 0$, where $\\beta$ is the bound on the Euclidean norm of the solution. This improves upon prior results which required $q \\geq \\beta \\cdot \\sqrt{n \\log n}$, and is essentially optimal since the problem is trivially easy for $q \\leq \\beta$. For LWE, we show that it remains hard even when the errors are small (e.g., uniformly random from $\\set{0,1}$), provided that the number of samples is small enough (e.g., linear in the dimension $n$ of the LWE secret). Prior results required the errors to have magnitude at least $\\sqrt{n}$ and to come from a Gaussian-like distribution.

*10:17* [Pub][ePrint]
Related-key Attacks Against Full Hummingbird-2, by Markku-Juhani O. Saarinen
We present attacks on full Hummingbird-2 which are able to recover the 128-bit secret keys of two black box cipher instances that have a certain type of low-weight XOR difference in their keys. We call these

highly correlated keys as they produce the same ciphertext with a

significant probability. The complexity of our main chosen-IV

key-recovery attack is $2^{64}$. The first 64 bits of the key can be independently recovered with only $2^{36}$ effort. This is the first sub-exhaustive attack on the full cipher under two related keys. Our attacks use some novel tricks and techniques which are made possible by Hummingbird-2\'s unique word-based structure. We have verified the correctness and complexity of our attacks by fully implementing them.

We also discuss enabling factors of these attacks and describe an alternative design for the WD16 nonlinear keyed function which is resistant to attacks of this type. The new experimental function replaces S-boxes with simple $\\chi$ functions.

*10:17* [Pub][ePrint]
Relation collection for the Function Field Sieve, by Jérémie Detrey and Pierrick Gaudry and Marion Videau
In this paper, we focus on the relation collection step of the Function Field Sieve (FFS), which is to date the best algorithm known for computing discrete logarithms in small-characteristic finite fields of cryptographic sizes. Denoting such a finite field by GF(p^n), where p is much smaller than n, the main idea behind this step is to find polynomials of the form a(t)-b(t)x in GF(p)[t][x] which, when considered as principal ideals in carefully selected function fields, can be factored into products of low-degree prime ideals. Such polynomials are called \"relations\", and current record-sized discrete-logarithm computations need billions of those.Collecting relations is therefore a crucial and extremely expensive step in FFS, and a practical implementation thereof requires heavy use of cache-aware sieving algorithms, along with efficient polynomial arithmetic over GF(p)[t]. This paper presents the algorithmic and arithmetic techniques which were put together as part of a new public implementation of FFS, aimed at medium- to record-sized computations.

*10:17* [Pub][ePrint]
Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently, by Marek Jawurek and Florian Kerschbaum and Claudio Orlandi
Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice.In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao\'s garbled circuit technique.

The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., ``I know x s.t. y=SHA-256(x)\'\' for a

common input y (or other ``unstructured\'\' languages), but no efficient protocols for this task are currently known.

It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case).

The protocol achieves active security and is essentially only twice as slow as Yao\'s garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao\'s protocol actively secure, where the complexity grows linearly with the security parameter.

*10:17* [Pub][ePrint]
On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\\F_{2^{1971}}$, by Faruk Gologlu and Robert Granger and Gary McGuire and Jens Zumb
In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as $L_{q^n}(1/3,2/3)$ for computing arbitrary logarithms, but also in an heuristic {\\em polynomial time} algorithmfor finding the discrete logarithms of degree one elements. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite field with $2^{1971}$ elements.

*10:17* [Pub][ePrint]
Design Space Exploration and Optimization of Path Oblivious RAM in Secure Processors, by Ling Ren and Xiangyao Yu and Christopher Fletcher and Marten van Dijk and Srinivas Devadas
Keeping user data private is a huge problem both in cloud computing and computation outsourcing. One paradigm to achieve data privacy in these settings is to use tamper-resistant processors. Users\' private data is decrypted and computed upon in a secure compartment from which that data will not be revealed to an untrusted party. Since program working sets seldom fit within the on-chip storage of today\'s processor solutions, a secure and efficient way of transporting and storing data off-chip is required. A simple solution to this problem is to encrypt all data that leaves the chip. However, the address sequence that goes off-chip may still leak information. ORAM (Oblivious RAM) has been previously proposed to hide the address leakage of the program. However, ORAM has mainly been explored in server/file settings which assume a vastly different computation model than secure processors (e.g., accesses are for files not processor cache blocks). Not surprisingly, naively applying ORAM to a secure processor setting incurs large performance overheads.In this paper, we demonstrate techniques to make ORAM practical in a secure processor setting. A particular ORAM proposed recently, called Path ORAM, is studied. For the first time, we thoroughly explore the design space of Path ORAM, and introduce a novel throughput-driven design space exploration approach based on ORAM background eviction schemes and super blocks. With our ORAM optimizations, ORAM latency drops by 45%, and SPEC benchmark execution time improves by 39% in relation to a baseline configuration. We also propose an efficient integrity verification scheme for Path ORAM.

Our work can be used to improve the security level of previous secure processors.