International Association
for Cryptologic Research

Applications are invited for tenure-track and tenured faculty positions in all areas related to cybersecurity, privacy, and cryptography.

A doctoral degree in computer science or related areas and an outstanding research track record are required. Applicants are expected to pursue an internationally visible research agenda and to build up their research team. Candidates for senior positions must be internationally accomplished scientists.

The cybersecurity research center CISPA, currently in the founding process to join the German Helmholtz Association as a new member, provides a unique work environment that offers the advantages of a university department and a research laboratory alike: Faculty will be offered highly competitive research salaries and institutional funding; they enjoy academic freedom, and build and lead their team of PhD students and postdocs; they attract additional third-party funds, supervise doctoral theses, and are granted the opportunity to teach graduate and undergraduate courses. CISPA moreover offers outstanding technical infrastructure and administrative support.

CISPA is located in Saarbrücken, in the tri-border area of Germany, France, and Luxembourg. We maintain an international and diverse work environment and seek applications from outstanding researchers worldwide. The working language is English.

All applicants are strongly encouraged to submit their complete application by June 30, 2017 for full consideration. However, applications will continue to be accepted until July 15, 2017. For more information and details on how to apply, please see here:

https://www.cispa.saarland/jobs/faculty/

CISPA values diversity and is committed to equality. We provide special support for dual-career couples. Female researchers are encouraged to apply.

Closing date for applications: 15 July 2017

Contact: Prof. Michael Backes

eMail: backes (at) cispa.saarland

More information: https://www.cispa.saarland/jobs/faculty/

We are looking for Research Fellow (Post-Doc), to join our group.

The applicants should have background and be interested in working on different aspects of lattice based cryptography, in particular on:

- security proofs for lattice-based schemes,

- building and implementing lattice-based constructions,

- fully homomorphic encryption,

- cryptanalysis.

The research will take place in the Embedded Security and Cryptography (EMSEC) team, within the IRISA computer science institute located in Rennes, France.

To apply please send your detailed CV (with publication list) and names of at least two people who can provide reference letters (e-mail).

The positions has flexible starting date. Review of applications will start immediately until the positions are filled.

Closing date for applications: 31 December 2017

Contact: Adeline Roux-Langlois, Adeline.Roux-Langlois (at) irisa.fr and Pierre-Alain Fouque, Pierre-Alain.Fouque (at) irisa.fr

We propose a new mode of operation called ZMAC allowing to construct a (stateless and deterministic) message authentication code (MAC) from a tweakable block cipher (TBC). When using a TBC with $n$-bit blocks and $t$-bit tweaks, our construction provides security (as a variable-input-length PRF) beyond the birthday bound with respect to the block-length $n$ and allows to process $n+t$ bits of inputs per TBC call. In comparison, previous TBC-based modes such as PMAC1, the TBC-based generalization of the seminal PMAC mode (Black and Rogaway, EUROCRYPT~2002) or PMAC_TBC1k (Naito, ProvSec~2015) only process $n$ bits of input per TBC call. Since an $n$-bit block, $t$-bit tweak TBC can process at most $n+t$ bits of input per call, the efficiency of our construction is essentially optimal, while achieving beyond-birthday-bound security. The ZMAC mode is fully parallelizable and can be directly instantiated with several concrete TBC proposals, such as Deoxyx and SKINNY. We also use ZMAC to construct a stateless and deterministic Authenticated Encryption scheme called ZAE which is very efficient and secure beyond the birthday bound.

In this paper, we study functional-graph-based (second) preimage attacks against hash combiners. Our contributions are threefold:

\begin{itemize}

\item in EUROCRYPT~2016, Dinur proposes generic (second) preimage attacks on the concatenation combiner and the XOR combiner using a new and essential observation on functional graph, which is experimentally verified but the proof is incomplete. Our first contribution is to provide a proof for Dinur's observation;

\item we find improved preimage attack against the XOR combiner with a complexity of $2^{5n/8}$, while the previous best-known complexity is $2^{2n/3}$;

\item we find the first generic second-preimage attack on Zipper hash with an optimal complexity of $2^{3n/5}$.

\end{itemize}

In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. Ambainis et al. gave a definition of non-malleability for the encryption of quantum data. In this work, we show that this definition is too weak, as it allows adversaries to ``inject'' plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of Ambainis et al.).

Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that ``total authentication'' (a notion recently proposed by Garg et al.) can be satisfied with two-designs, a significant improvement over their eight-design-based construction. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis et al.

``All-but-many lossy trapdoor functions'' (ABM-LTF) are a powerful cryptographic primitive studied by Hofheinz (Eurocrypt 2012). ABM-LTFs are parametrised with tags: a lossy tag makes the function lossy; an injective tag makes the function injective, and invertible with a trapdoor. Existing ABM-LTFs rely on non-standard assumptions.

Our first result is an ABM-LTF construction from lattices, based on the learning-with-errors (LWE) problem. Unlike the previous schemes which behaved as ``encrypted signatures'', the core of our construction is an ``encrypted, homomorphic-evaluation-friendly, weak pseudorandom function''. The weak pseudorandom function outputs matrices, where the lossy tags are preimages of the zero matrix, and the injective tags are preimages of random full-rank matrices.

Our second result is a public-key system tightly secure against ``selective opening'' attacks, where an attacker gets many challenges and can ask to see the random bits of any of them. Following the steps of Hemenway et al. (Asiacrypt 2011) and Hofheinz (Eurocrypt 2012), our ABM-LTF gives the first lattice-based, compact public-key encryption (PKE) scheme that has indistinguishability against adaptive chosen-ciphertext and selective opening attacks (IND-SO-CCA2), with tight security, and whose public-key size and security reduction are independent of the number of decryption queries and ciphertext challenges.

Meanwhile, this result provides an alternative solution to the problem of building pairing-free IND-CCA2 PKE schemes with tight security in the multi-challenge setting, which was firstly answered by Gay et al. (Eurocrypt 2016).

Additionally, our ABM-LTF answers the open question of constructing all-but-many trapdoor function from lattices, first asked by Alperin-Sheriff and Peikert (PKC 2012).

Side-channel attacks represent one of the most powerful category of attacks on cryptographic devices with profiled attacks in a promi- nent place as the most powerful among them. Indeed, for instance, template attack is a well-known real-world attack that is also the most powerful attack from the information theoretic perspective. On the other hand, machine learning techniques have proven their quality in a numerous applications where one is definitely side-channel analysis. As one could expect, most of the research concerning supervised machine learning and side-channel analysis concentrated on more powerful machine learning techniques. Although valid from the practical perspective, such attacks often remain lacking from the more theoretical side. In this paper, we investigate several Bayes classifiers, which present simple supervised techniques that have significant similarities with the template attack. More specifically, our analysis aims to investigate what is the influence of the feature (in)dependence in datasets with different amount of noise and to offer further insight into the efficiency of machine learning for side-channel analysis.

Non-malleable codes---introduced by Dziembowski, Pietrzak and Wichs at ICS 2010---are key-less coding schemes in which mauling attempts to an encoding of a given message, w.r.t.\ some class of tampering adversaries, result in a decoded value that is either identical or unrelated to the original message. Such codes are very useful for protecting arbitrary cryptographic primitives against tampering attacks against the memory. Clearly, non-malleability is hopeless if the class of tampering adversaries includes the decoding and encoding algorithm. To circumvent this obstacle, the majority of past research focused on designing non-malleable codes for various tampering classes, albeit assuming that the adversary is unable to decode. Nonetheless, in many concrete settings, this assumption is not realistic.

In this paper, we explore one particular such scenario where the class of tampering adversaries naturally includes the decoding (but not the encoding) algorithm. In particular, we consider the class of adversaries that are restricted in terms of memory/space. Our main contributions can be summarized as follows:

-- We initiate a general study of non-malleable codes resisting space-bounded tampering. In our model, the encoding procedure requires large space, but decoding can be done in small space, and thus can be also performed by the adversary. Unfortunately, in such a setting it is impossible to achieve non-malleability in the standard sense, and we need to aim for slightly weaker security guarantees. In a nutshell, our main notion (dubbed {\em leaky space-bounded non-malleability}) ensures that this is the best the adversary can do, in that space-bounded tampering attacks can be simulated given a small amount of leakage on the encoded value.

-- We provide a simple construction of a leaky space-bounded non-malleable code. Our scheme is based on any Proof of Space (PoS)---a concept recently put forward by Ateniese {\em et al.} (SCN 2014) and Dziembowski {\em et al.} (CRYPTO 2015)---satisfying a variant of soundness. As we show, our paradigm can be instantiated by extending the analysis of the PoS construction by Ren and Devadas (TCC 2016-A), based on so-called stacks of localized expander graphs.

-- Finally, we show that our flavor of non-malleability yields a natural security guarantee against memory tampering attacks, where one can trade a small amount of leakage on the secret key for protection against space-bounded tampering attacks.

The Keccak hash function is the winner of the SHA-3 competition and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced Keccak hash function, and two main results are achieved: the first practical collision attacks against 5-round Keccak-224 and an instance of 6-round Keccak collision challenge. Both improve the number of practically attacked rounds by one. These results are obtained by carefully studying the algebraic properties of the nonlinear layer in the underlying permutation of Keccak and applying linearization to it. In particular, techniques for partially linearizing the output bits of the nonlinear layer are proposed, utilizing which attack complexities are reduced significantly from the previous best results.

In the preprint [Characterizations of the differential uniformity of vectorial functions by the Walsh transform, IACR ePrint Archive 2017/516], the author has, for each even positive $\delta$, characterized in several ways differentially $\delta$-uniform functions by equalities satisfied by their Walsh transforms. These characterizations generalize the well-know characterization of APN functions by the fourth moment of their Walsh transform. We introduce two notions which are related to these characterizations: (1) that of componentwise APN (CAPN) $(n,n)$-function, which is a stronger version of APNness related to the characterization by the fourth moment, and is defined as follows: the arithmetic mean of $W_F^4(u,v)$ when $u$ ranges over ${\Bbb F}_2^n$ and $v$ is fixed nonzero in ${\Bbb F}_2^n$ equals $2^{2n+1}$, and (2) that of componentwise Walsh uniform (CWU) $(n,m)$-function ($m=n$, resp. $m= n-1$), which is a stronger version of APNness (resp. of differential 4-uniformity) related to one of the new characterizations, and is defined as follows: the arithmetic mean of $W_F^2(u_1,v_1)W_F^2(u_2,v_2)W_F^2(u_1+u_2,v_1+v_2)$ when $u_1,u_2$ range independently over ${\Bbb F}_2^n$ and $v_1,v_2$ are fixed nonzero and distinct in ${\Bbb F}_2^m$, equals $2^{3n}$. We observe that CAPN functions can exist only if $n$ is odd, that every plateaued function is CAPN if and only if it is AB and that APN power permutations are CAPN. We show that any APN function whose component functions are partially-bent (in particular, every quadratic APN function) is CWU, but we show also that other APN functions like Kasami functions and the inverse of one of the Gold APN permutations are CWU. To prove these two more difficult results, we first show that the CWUness of APN power permutations is equivalent to a property which is similar to the difference set with Singer parameters property of the complement of $\Delta_F=\{F(x)+F(x+1)+1; x\in {\Bbb F}_{2^n}\}$, proved in the case of Kasami APN functions by Dillon and Dobbertin in [New cyclic difference sets with Singer parameters, FFA 2004]. This new property, that we call cyclic-additive difference set property, involves both operations of addition and multiplication and is more complex. We prove it in the case of the inverse of Gold function. In the case of Kasami functions, it seems difficult to find a direct proof, even by adapting the sophisticated proof by Dillon and Dobbertin of the cyclic difference set property. But the properties of plateaued APN functions proved recently by the author in [Boolean and vectorial plateaued functions, and APN functions, IEEE Transactions on Information Theory 2015] allow proving that, for APN power functions, the cyclic-additive difference set property is equivalent to the cyclic difference set property. The case $n$ odd is then solved, but not the case $n$ even since, in such case, $F$ is not a permutation. Stronger properties proved in this same paper for the particular case of plateaued functions with unbalanced components allow proving in the same time that APN Kasami functions in even dimension are CWU and that their associated set $\Delta_F$ has the cyclic-additive difference set property. This provides as a side result a simple alternative proof of the difference set property with Singer parameters of the complement of the set $\Delta_F$ related to a Kasami APN function $F$ in even dimension, since it is known that these functions are plateaued.

We present a new mechanized prover for showing correspondence assertions for cryptographic protocols in the computational model. Correspondence assertions are useful in particular for establishing authentication. Our technique produces proofs by sequences of games, as standard in cryptography. These proofs are valid for a number of sessions polynomial in the security parameter, in the presence of an active adversary. Our technique can handle a wide variety of cryptographic primitives, including shared- and public-key encryption, signatures, message authentication codes, and hash functions. It has been implemented in the tool CryptoVerif and successfully tested on examples from the literature.

A common requirement in practice is to periodically rotate the keys used to encrypt stored data. Systems used by Amazon and Google do so using a hybrid encryption technique which is eminently practical but has questionable security in the face of key compromises and does not provide full key rotation. Meanwhile, symmetric updatable encryption schemes (introduced by Boneh et al. CRYPTO 2013) support full key rotation without performing decryption: ciphertexts created under one key can be rotated to ciphertexts created under a different key with the help of a re-encryption token. By design, the tokens do not leak information about keys or plaintexts and so can be given to storage providers without compromising security. But the prior work of Boneh et al. addresses relatively weak confidentiality goals and does not consider integrity at all. Moreover, as we show, a subtle issue with their concrete scheme obviates a security proof even for confidentiality against passive attacks.

This paper presents a systematic study of updatable Authenticated Encryption (AE). We provide a set of security notions that strengthen those in prior work. These notions enable us to tease out real-world security requirements of different strengths and build schemes that satisfy them efficiently. We show that the hybrid approach currently used in industry achieves relatively weak forms of confidentiality and integrity, but can be modified at low cost to meet our stronger confidentiality and integrity goals. This leads to a practical scheme that has negligible overhead beyond conventional AE. We then introduce re-encryption indistinguishability, a security notion that formally captures the idea of fully refreshing keys upon rotation. We show how to repair the scheme of Boneh et al., attaining our stronger confidentiality notion. We also show how to extend the scheme to provide integrity, and we prove that it meets our re- encryption indistinguishability notion. Finally, we discuss how to instantiate our scheme efficiently using off-the-shelf cryptographic components (AE, hashing, elliptic curves). We report on the performance of a prototype implementation, showing that fully secure key rotations can be performed at a throughput of approximately 116 kB/s.

Certificate authorities serve as trusted parties to help secure web communications. They are a vital component for ensuring the security of cloud infrastructures and big data repositories. Unfortunately, recent attacks using mis-issued certificates show this model is severely broken.

Much research has been done to enhance certificate management in order to create more secure and reliable cloud architectures. However, none of it has been widely adopted yet, and it is hard to judge which one is the winner. This chapter provides a survey with critical analysis on the existing proposals for managing public key certificates. This evaluation framework would be helpful for future research on designing an alternative certificate management system to secure the internet.

At EUROCRYPT 2016, Gay et al. presented the first pairing-free public-key encryption (PKE) scheme with a tight security reduction to a standard assumption. Their scheme is competitive in efficiency with state-of-the art PKE schemes and has very compact ciphertexts (of three group elements), but suffers from a large public key (of about 200 group elements).

In this work, we present an improved pairing-free PKE scheme with a tight security reduction to the Decisional Diffie-Hellman assumption, small ciphertexts (of three group elements), and small public keys (of six group elements). Compared to the work of Gay et al., our scheme thus has a considerably smaller public key and comparable other characteristics, although our encryption and decryption algorithms are somewhat less efficient.

Technically, our scheme borrows ideas both from the work of Gay et al. and from a recent work of Hofheinz (EUROCRYPT, 2017). The core technical novelty of our work is an efficient and compact designated-verifier proof system for an OR-like language. We show that adding such an OR-proof to the ciphertext of the state-of-the-art PKE scheme from Kurosawa and Desmedt enables a tight security reduction.

In structure-preserving cryptography, every building block shares the same bilinear groups. These groups must be generated for a specific, a prior fixed security level, and thus it is vital that the security reduction of all involved building blocks is as tight as possible. In this work, we present the first generic construction of structure-preserving signature schemes whose reduction cost is independent of the number of signing queries. Its chosen-message security is almost tightly reduced to the chosen-plaintext security of a structure-preserving public-key encryption scheme and the security of Groth-Sahai proof system. Technically, we adapt the adaptive partitioning technique by Hofheinz (Eurocrypt 2017) to the setting of structure-preserving signature schemes. To achieve a structure-preserving scheme, our new variant of the adaptive partitioning technique relies only on generic group operations in the scheme itself. Interestingly, however, we will use non-generic operations during our security analysis. Instantiated over asymmetric bilinear groups, the security of our concrete scheme is reduced to the external Diffie-Hellman assumption with linear reduction cost in the security parameter, independently of the number of signing queries. The signatures in our schemes consist of a larger number of group elements than those in other non-tight schemes, but can be verified faster, assuming their security reduction loss is compensated by increasing the security parameter to the next standard level.

When constructing zero-knowledge proofs based on the hardness of the Ring-LWE or the Ring-SIS problems over the ring $R_p^n=\Z_p[X]/(X^n+1)$, it is often necessary that the challenges come from a set $\mathcal{C}$ that satisfies three properties: the set should be exponentially large (around $2^{256}$), the elements in it should have small norms, and all the non-zero elements in the difference set $\mathcal{C}-\mathcal{C}$ should be invertible. The first two properties are straightforward to satisfy, while the third one requires us to make efficiency compromises. We can either work over rings where the polynomial $X^n+1$ only splits into two irreducible factors modulo $p$ which makes speed of the multiplication operation in $R_p^n$ sub-optimal, or we can limit our challenge set to polynomials of smaller degree which requires them to have (much) larger norms. \\

In this work we show that one can use the optimal challenge sets $\mathcal{C}$ and still have the polynomial $X^n+1$ split into more than two factors. For the most common parameters that are used in such zero-knowledge proofs, we show that $X^n+1$ can split into $8$ or $16$ irreducible factors. Experimentally, having the rings split in this fashion, increases the speed of polynomial multiplication by around $30\%$. This is a modest improvement, but it comes completely for free simply by working over the ring $R^n_p$ with a different modulus $p$. In addition to the speed improvement, the splitting of the ring into more factors is useful in scenarios where one embeds information into the Chinese Remainder representation of the ring elements.

In a recent paper \cite{eprint:2017:481}, Aggarwal, Joux, Prakash, and Santha (AJPS) describe an ingenious public-key cryptosystem mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. The security of the AJPS cryptosystem relies on the conjectured hardness of the Mersenne Low Hamming Ratio Assumption, defined in \cite{eprint:2017:481}.

This work shows that AJPS' security estimates are too optimistic and describes an algorithm allowing to recover the secret key from the public key much faster than foreseen in \cite{eprint:2017:481}.

In particular, our algorithm is \emph{experimentally practical} (within the reach of the computational capabilities of a large organization), at least for the parameter choice $\{n=1279,h=17\}$ conjectured in \cite{eprint:2017:481} as corresponding to a $2^{120}$ security level. The algorithm is fully parallelizable.

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS~2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity $O(N^5\log(N))$, which is much larger than the code book (but using many tweaks), where $N^2$ is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires $O(N^{\frac{11}{6}})$ chosen plaintexts with time complexity $O(N^{5})$. Our attack was successfully tested with $N\leq2^9$. It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4-round Feistel network. Biryukov et. al. already gave a 4-round Feistel structure attack in SAC~2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with $N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}$ known plaintexts and time complexity $O(N^{3})$. Our 4-round attack is simple to extend to five and more rounds with complexity $N^{(r-5)N+o(N)}$. It shows that FF1 with $N=7$ and FF3 with $7\leq N\leq10$ do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our $O(N^{5})$ attack.

Traditional protocols for secure multi-party computation (MPC) among $n$ parties that achieve optimal resiliency communicate at least a linear (in $n$) number of bits. In this work we investigate the feasibility of MPC with {\em sublinear} communication complexity. Concretely, we consider two clients, one of which may be corrupted, who wish to perform some joint computation using $n$ servers but without any trusted setup. We show that enforcing sublinear message complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated.

We provide a complete investigation of security against semi-honest adversaries---static and adaptive, with and without erasures---and initiate the study of malicious adversaries. For semi-honest static adversaries, our bounds match (up to any constant fraction of corruptions) the corresponding bounds when there is no communication restriction---i.e., we can tolerate up to $t < (1/2 -\epsilon)n$ corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures a constant fraction of corruptions is intolerable, and---most surprisingly---when erasures are allowed, we prove that $t < (1 - \sqrt{0.5} - \epsilon)n$ corruptions can be tolerated, which we also show to be optimal up to an arbitrarily small constant factor. The latter optimality proof hinges on a new treatment of probabilistic adversary structures which may be of independent interest. In the case of active corruptions in this setting, we prove that static security with abort is feasible when $t < (1/2 - \epsilon)n$, namely, the bound that is tight for semi-honest security.

These are exciting times for secure multi-party computation (MPC). While the feasibility of constant-round and actively secure MPC has been known for over two decades, the last few years have witnessed a flurry of designs and implementations that make its deployment a palpable reality. To our knowledge, however, existing concretely efficient MPC constructions are only for up to three parties.

In this paper we design and implement a new actively secure 5PC protocol tolerating two corruptions that requires $8$ rounds of interaction, only uses fast symmetric-key operations, and incurs~60\% less communication than the passively secure state-of-the-art solution [CCS 2016]. For example, securely evaluating the AES circuit when the parties are in different regions of the U.S. and Europe only takes $1.8$s which is $2.6\times$ faster than the passively secure 5PC in the same environment.

Instrumental for our efficiency gains (less interaction, only symmetric key primitives) is a new 4-party primitive we call \emph{Attested OT}, which in addition to Sender and Receiver involves two additional ``assistant parties'' who will attest to the respective inputs of both parties, and which might be of broader applicability in practically relevant MPC scenarios. Finally, we also show how to generalize our construction to $n$ parties with similar efficiency properties where the corruption threshold is $t \approx \sqrt n$, and propose a combinatorial problem which, if solved optimally, can yield even better corruption thresholds for the same cost.