International Association
for Cryptologic Research

We exploit the presence of a subfield to solve the NTRU problem for large moduli $q$: norming-down the public key $h$ to a subfield may lead to an easier lattice problem, and any sufficiently good solution may be lifted to a short vector in the full NTRU-lattice.

We restrict ourselves to choices of dimensions $n(\lambda)$ and modulus $q(\lambda)$ that were previously thought to offer resistance against attacks in time exponential in the security parameter $\lambda$. For any super-polynomial $q(\lambda)$, the subfield attack can be made sub-exponential in $\lambda$, or even polynomial as $q(\lambda)$ gets larger.

The subfield lattice attack directly affects the asymptotic security of the bootstrappable homomorphic encryption schemes LTV and YASHE. It also makes GGH-like Multilinear Maps vulnerable to principal ideals attacks --- therefore leading to a quantum break --- and almost vulnerable to a statistical attack a-la Gentry-Szydlo. No *encodings of zero* nor *zero-testing parameter* are required.

We also provide meaningful practical experiments. Using just LLL in dimension $512$ we obtain vectors that would have required running BKZ with block-size $130$ in dimension $8192$.

Finally, we discuss concrete aspects of this attack, the potential immunity of NTRUEncrypt and Bliss parameters, issue preliminary recommendations and suggest countermeasures.

SSL/TLS is the de facto protocol for providing secure communication over the Internet. It relies on the Web PKI model for authentication and secure key exchange. Despite its relatively successful past, the number of Web PKI incidents observed have increased recently. These incidents revealed the risks of forged certificates issued by certificate authorities without the consent of the domain owners. Several solutions have been proposed to solve this problem, but no solution has yet received widespread adaption due to complexity and deployability issues. In this paper, we propose a practical mechanism that enables servers to get their certificate views across the Internet, making detection of a certificate substitution attack possible. The origin of the certificate substitution attack can also be located by this mechanism. We have conducted simulation experiments and evaluated our proposal using publicly available, real-world BGP data. We have obtained promising results on the AS-level Internet topology.

We construct an identity-based encryption (IBE) scheme from the standard Learning with Errors (LWE) assumption, which both has a \emph{compact} public-key (with size similar to known lattice-based PKE schemes) and also achieves \emph{adaptive} security in the standard model. This improves over previous IBE schemes from lattices, which either have a public key that grows at least linearly with the length of the supported identities, or achieve a non-adaptive notion of security, or require a random oracle.

Additionally, our techniques from IBE can be adapted to construct a compact digital signature scheme, which achieves existential unforgeability under the standard Short Integer Solution (SIS) assumption with small polynomial parameters.

In order to assess the security of cryptosystems based on the discrete logarithm problem in non-prime finite fields, as are the torus-based or pairing-based ones, we investigate thoroughly the case in $GF(p^6)$ with the Number Field Sieve. We provide new insights, improvements, and comparisons between different methods to select polynomials intended for a sieve in dimension 3 using a special-q strategy. We also take into account the Galois action to increase the relation productivity of the sieving phase. To validate our results, we ran several experiments and real computations for various selection methods and field sizes with our publicly available implementation of the sieve in dimension 3, with special-q and various enumeration strategies.

\emph{Password-protected secret sharing} (PPSS) schemes allow a user to publicly share this high-entropy secret across different servers and to later recover it by interacting with some of these servers using only his password without requiring \emph{any} authenticated data. In particular, this secret will remain safe as long as not too many servers get corrupted. However, servers are not always reliable and the communication can be altered. To address this issue, a \emph{robust} PPSS should additionally guarantee that a user can recover his secret as long as enough servers provide correct answers, and these are received without alteration. In this paper, we propose new robust PPSS schemes which are significantly more efficient than the existing ones. We achieve this goal in two steps. First, we introduce a \emph{Robust Threshold Secret Sharing Scheme with respect to Random Failures} that allows us to drop the verifiable property of \emph{Oblivious Pseudorandom Functions}. Then, we use this new construction to introduce two new robust PPSS schemes that are quite efficient.

This paper introduces Simpira, a family of cryptographic permutations that supports inputs of $128 \times b$ bits, where $b$ is a positive integer. Its design goal is to achieve high throughput on virtually all modern 64-bit processor architectures, that nowadays already have native instructions to support AES computations. To achieve this goal, Simpira uses only one building block: the AES round function. For $b=1$, Simpira corresponds to 12-round AES with fixed round keys, whereas for $b\ge 2$, Simpira is a Generalized Feistel Structure (GFS) with an $F$-function that consists of two rounds of AES. From the security viewpoint, we claim that there are no structural distinguishers for Simpira with a complexity below $2^{128}$, and analyze its security against a variety of attacks in this setting. From the efficiency viewpoint, we show that the throughput of Simpira is close to the theoretical optimum, namely, the number of AES rounds in the construction. For example, on the latest Intel Skylake processor, Simpira has throughput below 1 cycle per byte for $b \le 4$ and $b=6$. For larger permutations, where moving data in memory has a more pronounced effect, Simpira with $b=32$ (512 byte inputs) evaluates 732 AES rounds, and performs at 802 cycles (1.56 cycles per byte), i.e., less than $10\%$ off the theoretical optimum. The Simpira family offers an efficient solution for multiple usages where operating on wide blocks, larger than 128 bits, is desired.

We introduce a new technique for tight security proofs called work factor partitioning. Using this technique in a modified version of the framework of Döttling and Schröder (CRYPTO 2015), we obtain the first generic construction of tightly-secure pseudorandom functions (PRFs) from PRFs with small domain.

By instantiating the small-domain PRFs with the Naor-Reingold function (FOCS 1997) or its generalization by Lewko and Waters (ACM CCS 2009), this yields the first fully-secure PRFs whose black-box security proof loses a factor of only O(log^2 \lambda), where \lambda is the security parameter.

Interestingly, our variant of the Naor-Reingold construction can be seen as a standard Naor-Reingold PRF (whose security proof has a loss of \Theta(\lambda)), where a special encoding is applied to the input before it is processed. The tightness gain comes almost for free: the encoding is very efficiently computable and increases the length of the input only by a constant factor smaller than 2.

A $(\gamma,\delta)$-elastic channel is a binary symmetric channel between a sender and a receiver where the error rate of an honest receiver is $\delta$ while the error rate of a dishonest receiver lies within the interval $[\gamma, \delta]$. In this paper, we show that from \emph{any} non-trivial elastic channel (i.e., $0<\gamma<\delta<\frac{1}{2}$) we can implement oblivious transfer with information theoretic security. This was previously (Khurana et al., Eurocrypt 2016) only known for a subset of these parameters. Our technique relies on a new way to exploit protocols for information-theoretic key agreement from noisy channels. We also show that information theoretically secure commitments where the receiver commits follow from any non-trivial elastic channel.

In this paper we consider the fundamental question of optimizing finite field multiplications with one fixed element. Surprisingly, this question did not receive much attention previously. We investigate which field representation, that is which choice of basis, allows for an optimal implementation. Here, the efficiency of the multiplication is measured in terms of the number of XOR operations needed to implement the multiplication. While our results are potentially of larger interest, we focus on a particular application in the second part of our paper. Here we construct new MDS matrices which outperform all previous results when focusing on a round-based hardware implementation.

Research associate (or post-doctoral fellow) position in Department of Electrical and Computer Engineering at the University of Waterloo in the field of embedded hardware security (side channel analysis, fault injection, microprobing, reverse engineering) for one year appointment (second year dependent upon funding).

The successful candidate must have a PhD in Electrical and Computer Engineering, Computer Science, Mathematics or a related discipline. In addition theoretical/practical experience in side channel analysis, fault injection, microprobing and/or reverse engineering is preferred.

Please email with subject ‘RA position’ statement of research, CV, recommendation letters or referees, and copies of 3 most significant publications to cgebotys (at) uwaterloo.ca

Closing date for applications: 31 August 2016

Contact: Contact: Professor Catherine H. Gebotys, cgebotys (at) uwaterloo.ca

Event date: 26 July to 28 July 2016
Submission deadline: 1 March 2016
Notification: 18 May 2016

Event date: 14 November to 16 November 2016
Submission deadline: 6 July 2016
Notification: 10 September 2016

We construct an LWE-based key-policy attribute-based encryption (ABE) scheme that supports attributes of unbounded polynomial length. Namely, the size of the public parameters is a fixed polynomial in the security parameter and a depth bound, and with these fixed length parameters, one can encrypt attributes of arbitrary length. Similarly, any polynomial size circuit that adheres to the depth bound can be used as the policy circuit regardless of its input length (recall that a depth $d$ circuit can have as many as $2^d$ inputs). This is in contrast to previous LWE-based schemes where the length of the public parameters has to grow linearly with the maximal attribute length.

We prove that our scheme is semi-adaptively secure, namely, the adversary can choose the challenge attribute after seeing the public parameters (but before any decryption keys). Previous LWE-based constructions were only able to achieve selective security. (We stress that the complexity leveraging technique is not applicable for unbounded attributes.)

We believe that our techniques are of interest at least as much as our end result. Fundamentally, selective security and bounded attributes are both shortcomings that arise out of the current LWE proof techniques that program the challenge attributes into the public parameters. The LWE toolbox we develop in this work allows us to "delay" this programming. In a nutshell, the new tools include a way to generate an a-priori unbounded sequence of LWE matrices, and have fine-grained control over which trapdoor is embedded in each and every one of them, all with succinct representation.

We describe a public key encryption that is IND-CPA secure under the Learning with Errors (LWE) assumption, but that is not circular secure for arbitrary length cycles. Previous separation results for cycle length greater than 2 require the use of indistinguishability obfuscation, which is not currently realizable under standard assumptions.

We initiate the study of a proof system model that naturally combines two well-known models: interactive proofs (IPs) and probabilistically-checkable proofs (PCPs). An *interactive oracle proof* (IOP) is an interactive proof in which the verifier is not required to read the prover's messages in their entirety; rather, the verifier has oracle access to the prover's messages, and may probabilistically query them.

IOPs simultaneously generalize IPs and PCPs. Thus, IOPs retain the expressiveness of PCPs, capturing NEXP rather than only PSPACE, and also the flexibility of IPs, allowing multiple rounds of communication with the prover. These degrees of freedom allow for more efficient "PCP-like" interactive protocols, because the prover does not have to compute the parts of a PCP that are not requested by the verifier.

As a first investigation into IOPs, we offer two main technical contributions. First, we give a compiler that maps any public-coin IOP into a non-interactive proof in the random oracle model. We prove that the soundness of the resulting proof is tightly characterized by the soundness of the IOP against *state restoration attacks*, a class of rewinding attacks on the IOP verifier. Our compiler preserves zero knowledge, proof of knowledge, and time complexity of the underlying IOP. As an application, we obtain blackbox unconditional ZK proofs in the random oracle model with quasilinear prover and polylogarithmic verifier, improving on the result of Ishai et al.\ (2015).

Second, we study the notion of state-restoration soundness of an IOP: we prove tight upper and lower bounds in terms of the IOP's (standard) soundness and round complexity; and describe a simple adversarial strategy that is optimal across all state restoration attacks.

Our compiler can be viewed as a generalization of the Fiat--Shamir paradigm for public-coin IPs (CRYPTO~'86), and of the "CS proof" constructions of Micali (FOCS~'94) and Valiant (TCC~'08) for PCPs. Our analysis of the compiler gives, in particular, a unified understanding of all of these constructions, and also motivates the study of state restoration attacks, not only for IOPs, but also for IPs and PCPs.

A memory-hard function (MHF) $f$ is equipped with a {\em space cost} $\sigma$ and {\em time cost} $\tau$ parameter such that repeatedly computing $f_{\sigma,\tau}$ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF $f_{\sigma,\tau}$ has area $\times$ time (AT) complexity at $\Theta(\sigma^2 * \tau)$. A data-independent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) $G$ on $n=\Theta(\sigma * \tau)$ nodes representing its computation graph.

In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of {\em energy} (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm $\mathcal{A}$ for repeatedly evaluating an iMHF based on an arbitrary DAG $G$. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of $G$.

Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters $\sigma$ and $\tau$ (and thread-count) such that $n=\sigma*\tau$.

1) The Catena-Dragonfly function of~\cite{forler2013catena} has AT and energy complexities $O(n^{1.67})$.

2) The Catena-Butterfly function of~\cite{forler2013catena} has complexities is $O(n^{1.67})$.

3) The Double-Buffer and the Linear functions of~\cite{CBS16} both have complexities in $O(n^{1.67})$.

4) The Argon2i function of~\cite{Argon2} (winner of the Password Hashing Competition~\cite{PHC}) has complexities $O(n^{7/4}\log(n))$.

5) The Single-Buffer function of~\cite{CBS16} has complexities $O(n^{7/4}\log(n))$.

6) \emph{Any} iMHF can be computed by an algorithm with complexities $O(n^2/\log^{1-\epsilon}(n))$ for all $\epsilon > 0$. In particular when $\tau=1$ this shows that the goal of constructing an iMHF with AT-complexity $\Theta(\sigma^2 * \tau)$ is unachievable.

Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest.

Event date: 29 May to 2 June 2016

The missions of this permanent position is to conduct research and teach Hardware security in the Digital Electronics group of Telecom ParisTech. It also includes the development of industrial and academics collaboration.

Required competences:

• Theoretical and practical knowledge in the field of security for integrated circuits and embedded systems
• Architectures and HW/SW design methods of circuits and embedded systems
• Significant experience in research and teaching
• Fluency in english

Closing date for applications: 14 April 2016

Contact: Pr. Jean-Luc Danger
jean-luc.danger (at) telecom-paristech.fr
+33 1 45 81 81 17

More information: http://www.telecom-paristech.fr/nc/telecom-paristech/offres-emploi-stages-theses/fiche-offre-demploi.html?offre_emploi=1

We introduce the notion of an \emph{Extremely Lossy Function} (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial $r$ (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size $r$.

We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomially-many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions --- for example polynomially-many hardcore bits were only know from differing inputs obfuscation, a notion whose plausibility has been seriously challenged. We also use ELFs to build a simple hash function with \emph{output intractability}, a new notion we define that may be useful for generating common reference strings.

Next, we give a construction of ELFs relying on the \emph{exponential} hardness of the decisional Diffie-Hellman problem, which is plausible in pairing-based groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different --- and arguably better --- assumptions than prior works.

We consider the related notions of two-prover and of relativistic commitment schemes. In recent work, Lunghi et al. proposed a new relativistic commitment scheme with a multi-round sustain phase that keeps the binding property alive as long as the sustain phase is running. They prove security of their scheme against classical attacks; however, the proven bound on the error parameter is very weak: it blows up double exponentially in the number of rounds.

In this work, we give a new analysis of the multi-round scheme of Lunghi et al., and we show a linear growth of the error parameter instead (also considering classical attacks only). Our analysis is based on a new composition theorem for two-prover commitment schemes. The proof of our composition theorem is based on a better understanding of the binding property of two-prover commitments that we provide in the form of new definitions and relations among them. As an additional consequence of these new insights, our analysis is actually with respect to a strictly stronger notion of security than considered by Lunghi et al.