*19:17* [Pub][ePrint]
Garbled RAM From One-Way Functions, by Sanjam Garg and Steve Lu and Rafail Ostrovsky and Alessandra Scafuro
Yao\'s garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards the goal of avoiding this inefficiency, Lu and Ostrovsky (Eurocrypt 2013) introduced the notion of ``garbled RAM\'\' as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao\'s garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size.Known realizations of this primitive, either need to rely on strong computational assumptions or do not achieve the aforementioned efficiency (Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014). In this paper we provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal and necessary assumption that one-way functions exist. Our scheme allows for garbling multiple programs being executed on a persistent database, and has the additional feature that the program garbling is decoupled from the database garbling. This allows a client to provide multiple garbled programs to the server as part of a pre-processing phase and then later determine the order and the inputs on which these programs are to be executed, doing work independent of the running times of the programs itself.

*19:17* [Pub][ePrint]
Public-Coin Differing-Inputs Obfuscation and Its Applications, by Yuval Ishai, Omkant Pandey, Amit Sahai
Differing inputs obfuscation (diO) is a strengthening of indistinguishability obfuscation (iO) that has recently found applications to improving the efficiency and generality of obfuscation, functional encryption, and related primitives. Roughly speaking, a diO scheme ensures that the obfuscations of two efficiently generated programs are indistinguishable not only if the two programs are equivalent, but also if it is hard to find an input on which their outputs differ. The above ``indistinguishability\'\' and ``hardness\'\' conditions should hold even in the presence of an auxiliary input that is generated together with the programs.

The recent works of Boyle and Pass (ePrint 2013) and Garg et al. (Crypto 2014) cast serious doubt on the plausibility of general-purpose diO with respect to general auxiliary inputs. This leaves open the existence of a variant of diO that is plausible, simple, and useful for applications.

We suggest such a diO variant that we call {\\em public-coin} diO. A public-coin diO restricts the original definition of diO by requiring the auxiliary input to be a public random string which is given as input to all relevant algorithms. In contrast to standard diO, we argue that it remains very plausible that current candidate constructions of iO for circuits satisfy the public-coin diO requirement.

We demonstrate the usefulness of the new notion by showing that several applications of diO can be obtained by relying on the public-coin variant instead. These include constructions of {\\em succinct} obfuscation and functional encryption schemes for Turing Machines, where the size of the obfuscated code or keys is essentially independent of the running time and space.

*19:17* [Pub][ePrint]
HaTCh: Hardware Trojan Catcher, by Syed Kamran Haider and Chenglu Jin and Masab Ahmad and Devu Manikantan Shila and Omer Khan and Marten van Dijk
With the growing trend of repeated reuse of existing design components, use of third party IP cores has become a common practice in Electronic Design Automation (EDA) industry. However third party IP cores are known to have potential malwares or hardware trojans which could compromise the security of the whole system.We provide a formal classification of possible hardware trojans according to their different properties and analyze in detail the class coined \\textit{XX-St-D-F}, which is the collection of trojans that (1) use \\textit{\\underline{St}}andard I/O channels to deliver malicious payload, (2) are embedded in an IP core with \\textit{\\underline{D}}eterministic functionality, and (3) are designed to violate the \\textit{\\underline{F}}unctional specification. We provide a hierarchy of subclasses $H_{t,1}\\subseteq H_{t,2}\\subseteq \\ldots \\subseteq H_{t,d} \\subseteq \\ldots \\subseteq \\underset{d \\ge 1}{\\cup} H_{t,d}=H_t \\subseteq \\underset{t \\ge 0}{\\cup} H_t=$\\textit{XX-St-D-F}, where $t$ indicates the number of clock cycles between ``activating/triggering\'\' the trojan and the moment a malicious payload is delivered and where $d$ stands for the number of wires involved in the ``trigger signal\'\'. We show that all \\textit{XX-St-D-F} trojans benchmarked by Trusthub~\\cite{trust_hub} belong to $H_{t,1}$ and we design new trojans that belong to each of the classes $H_{t,d}$.

This demonstrates that the currently found/benchmarked trojans are very likely only the tip of the iceberg.

By using the synthesized netlist description of an IP core as input, we introduce a new tool called HaTCh which learns in a precomputation or ``learning\'\' phase how to add additional ``tagging\'\' circuitry to the IP core such that, as soon as an embedded \\textit{XX-St-D-F} trojan is triggered, the tagging circuitry raises an exception to prevent the trojan from manifesting malicious behavior. We show that HaTCh parameterized for $H_{t,d}$ has zero false negatives among trojans in $H_{t,d}$ and depending on the duration of the precomputation (learning phase) the false positive rate can be designed to approach zero. For a sample among the Trusthub~\\cite{trust_hub} benchmarks in \\textit{XX-St-D-F}, we show a false positive rate of $10^{-5}$ (for $d=1$).

The learning phase of HaTCh has a complexity of $O(d2^d \\cdot |Core| \\ln |Core|)$ where $|Core|$ is the number of wires in the IP core. We show how this complexity can potentially be reduced by considering ``interesting\'\' subsets of $H_{t,d}$, one of which leads to $O(|Core|^3)$ complexity independent of $d$. The tagging circuitry for our sample of benchmarks has area overhead from $0.02\\%$ to $7.63\\%$ for non-pipelined tagging circuitry, and from $0.02\\%$ to $15.25\\%$ for pipelined tagging circuitry which is useful for designs having strict timing constraints.

*15:53* [Job][New]
PhD Studentship in Security/Privacy, *University College London*
A grant is available to support a fully-funded PhD studentship to work at the intersection of security, privacy engineering, applied cryptography, and machine learning.If you are interested and (1) have been involved in competitive research projects (possibly leading to a publication), (2) have a strong background in at least two of the aforementioned topics, please send an email with a short CV and a list of references to *jobs (at) emilianodc.com*

*15:52* [Job][New]
Visiting Post-Doc or Ph.D. student, *Aalto University School of Science, Helsinki, Finland*
We look for a post-doc researcher or advanced Ph.D. student who would like to come to work with us in 2015 for a period of **maximum seven months** starting May 1, 2015 at the latest. A full salary will be paid during the visit. The visiting researcher should have good background in linear (correlation) attacks on block or stream ciphers.To apply, send your CV and motivation letter to Prof. Kaisa Nyberg by email: kaisa (dot) nyberg (at) aalto (dot) fi

Applications arriving before Nov 30, 2014, are granted to be taken into consideration when filling this position.

*16:17* [Pub][ePrint]
Bicliques with Minimal Data and Time Complexity for AES (Extended Version $\\star$), by Andrey Bogdanov and Donghoon Chang and Mohona Ghosh and Somitra Kumar Sanadhya
Biclique cryptanalysis is a recent technique that has been successfully applied to AES resulting in key recovery faster than brute force. However, a major hurdle in carrying out biclique cryptanalysis on AES is that it requires very high data complexity. This naturally warrants questions over the practical feasibility ofimplementing biclique attack in the real world. In Crypto\'13, Canteaut et al. proposed biclique attack where the data complexity of the attack was reduced to a single plaintext-ciphertext pair. However, no application of the same on AES was suggested.

In this paper, we re-evaluate the security-bound of full round AES against biclique attack. Under some reasonable

restrictions, we exhaustively analyze the most promising class of biclique cryptanalysis as applied to AES through a computer-assisted search and find optimal attacks towards lowest computational and data

complexities:

- Among attacks with the minimal data complexity of the unicity distance, the ones with computational

complexity $2^{126.67}$ (for AES-128), $2^{190.9}$ (for AES-192) and $2^{255}$ (for AES-256) are the fastest. Each attack just requires 2 (for AES-128 and AES-192) or 3 (for AES-256) known plaintexts for success probability 1. We obtain these results using the improved biclique attack proposed in Crypto\'13.

- Among attacks with data complexity less than the full codebook, for AES-128, the ones of computational complexity $2^{126.16}$ are the fastest. Within these, the one with data complexity $2^{64}$ requires the smallest amount of data. Thus, the original attack (with data complexity $2^{88}$) did not have the optimal data complexity for AES-128. Similar findings are observed for AES-192 as well (data complexity $2^{48}$ as against $2^{80}$ in the original attack). For AES-256, we find an attack that has a lower computational complexity of $2^{254.31}$ as compared to the original attack complexity of $2^{254.42}$.

- Among all attacks covered, the ones of computational complexity $2^{125.56}$ (for AES-128), $2^{189.51}$ (for AES-192) and $2^{253.87}$ (for AES-256) are fastest, though requiring the full codebook. This can be considered as an indication of the limitations of the independent-biclique attack approach as applied to AES.

*16:17* [Pub][ePrint]
Certificateless Proxy Re-Encryption Without Pairing, by Akshayaram Srinivasan and C. Pandu Rangan
Proxy Re-Encryption was introduced by Blaze, Bleumer and Strauss to efficiently solve the problem of delegation of decryption rights. In proxy re-encryption, a semi-honest proxy transforms a ciphertext intended for Alice to a ciphertext of the same message for Bob without learning anything about the underlying message. From its introduction, several proxy re-encryption schemes in the Public Key Infrastructure (PKI) and Identity (ID) based setting have been proposed. In practice, systems in the public key infrastructure suffer from the certificate management problem and those in identity based setting suffer from the key escrow problem. Certificateless Proxy Re-encryption schemes enjoy the advantages provided by ID-based constructions without suffering from the key escrow problem. In this work, we construct the first unidirectional, single-hop CCA-secure certificateless proxy re-encryption scheme without pairing by extending the PKI based construction of Chow et al. proposed in 2010. We prove its security in the random oracle model under the Computational Diffie-Hellman (CDH) assumption. Prior to this work, the only secure certificateless proxy re-encryption scheme is due to Guo et al. proposed in 2013 using bilinear pairing. The construction proposed in this work is more efficient than that system and satisfies stronger security properties. We also show that the recently proposed construction of Yang et al. is insecure with respect to the security model considered in this work.

*16:17* [Pub][ePrint]
Efficient Generic Zero-Knowledge Proofs from Commitments, by Samuel Ranellucci and Alain Tapp and Rasmus Winther Zakarias
Even though Zero-knowledge has existed for more than 30years, few generic constructions for Zero-knowledge exist. In this paper

we present a new kind of commitment scheme on which we build a novel

and efficient Zero-knowledge protocol for circuit satisfiability.