International Association
for Cryptologic Research

Applications are invited for a fixed-term post-doctoral researcher position (Security in Cyber Physical Systems) at University College Cork, Ireland. The position is within the the Security Group in the Department of Computer Science in conjunction with the recently established CONNECT Research Centre. The researcher will be part of the IRC/Chist-ERA programme funded project DYPOSIT: Dynamic Policies for Shared Cyber-Physical Infrastructures Under Attack. This project is being undertaken in collaboration with the Lancaster University, UK and Katholieke Universiteit Leuven, Belgium.

DYPOSIT will investigate the problem of large, shared cyber physical systems under attack. The project will consider the challenge of dynamically formulating and adapting security controls, rapidly and on-demand, in the face of unfolding attacks on a shared cyber physical system fabric integrating multiple applications run by a variety of stakeholders. The Post-Doctoral Researcher will primarily contribute to the development and implementation of a distributed security model for cyber physical systems in which trade-offs between threats, controls and other constraints, can be reasoned about in managing security policy deployment.

Applications are invited from those with a PhD qualification and publications in a directly relevant area. Applicants with a background in Computer Security and who are interested in developing research experience in cyber-physcial systems, or applicants with background in the modeling and reasoning about systems/networks and are interested in developing research experience in cyber-physcial systems security, are also invited to apply.

Informal enquiries should be addressed to Dr. Simon Foley, Department of Computer Science, University College Cork, Ireland (http://security.ucc.ie/foley).

Closing data is March 4, 2016. More information, post requirements and application details at:

http://www.ucc.ie/en/hr/vacancies/research/full-details-611543-en.html

Closing date for applications: 4 March 2016

We introduce the novel notion of a Proof of Human-work (PoH) and present the first distributed consensus protocol from hard Artificial Intelligence problems. As the name suggests, a PoH is a proof that a {\em human} invested a moderate amount of effort to solve some challenge. A PoH puzzle should be moderately hard for a human to solve. However, a PoH puzzle must be hard for a computer to solve, including the computer that generated the puzzle, without sufficient assistance from a human. By contrast, CAPTCHAs are only difficult for other computers to solve --- not for the computer that generated the puzzle. We also require that a PoH be publicly verifiable by a computer without any human assistance and without ever interacting with the agent who generated the proof of human-work. We show how to construct PoH puzzles from indistinguishability obfuscation and from CAPTCHAs. We motivate our ideas with two applications: HumanCoin and passwords. We use PoH puzzles to construct HumanCoin, the first cryptocurrency system with human miners. Second, we use proofs of human work to develop a password authentication scheme which provably protects users against offline attacks.

PPSS is a central primitive introduced by Bagherzandi et al [BJSL10] which allows a user to store a secret among n servers such that the user can later reconstruct the secret with the sole possession of a single password by contacting t+1 servers for t<n. At the same time, an attacker breaking into t of these servers - and controlling all communication channels - learns nothing about the secret (or the password). Thus, PPSS schemes are ideal for on-line storing of valuable secrets when retrieval solely relies on a memorizable password.

We show the most efficient Password-Protected Secret Sharing (PPSS) to date (and its implied Threshold-PAKE scheme), which is optimal in round communication as in Jarecki et al [JKK14] but which improves computation and communication complexity over that scheme requiring a single per-server exponentiation for the client and a single exponentiation for the server. As with the schemes from [JKK14] and Camenisch et al [CLLN14], we do not require secure channels or PKI other than in the initialization stage.

We prove the security of our PPSS scheme in the Universally Composable (UC) model. For this we present a UC definition of PPSS that relaxes the UC formalism of [CLLN14] in a way that enables more efficient PPSS schemes (by dispensing with the need to extract the user's password in the simulation) and present a UC-based definition of Oblivious PRF (OPRF) that is more general than the (Verifiable) OPRF definition from [JKK14] and is also crucial for enabling our performance optimization.

In this paper, we study the problem of existence of almost perfect nonlinear (APN) functions of algebraic degree $n$ over $\ftwon$. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce some non-existence results which imply, in particular, that for most of the known APN functions $F$ over $\ftwon$ the function $x^{2^n-1}+F(x)$ is not APN.

AMAC is a simple and fast candidate construction of a PRF from an MD-style hash function which applies the keyed hash function and then a cheap, un-keyed output transform such as truncation. Spurred by its use in the widely-deployed Ed25519 signature scheme, this paper investigates the provable PRF security of AMAC to deliver the following three-fold message: (1) First, we prove PRF security of AMAC (2) Second, we show that AMAC has a quite unique and attractive feature, namely that its multi-user security is essentially as good as its single-user security and in particular superior in some settings to that of competitors. (3) Third, it is technically interesting, its security and analysis intrinsically linked to security of the compression function in the presence of leakage.

Recent observations on polynomial structures of AES-like round functions are analysed in this note. We present computational evidence that input/output bits of AES-like 2-round transform up to $40$-bit, constructed with $8$-bit AES S-boxes, do not satisfy any relations of degree $3$. So it is very unlikely that actual AES 2-round transform admits any relations of degree $\leq 3$.

In this paper, we present two new adaptively secure identity-based encryption (IBE) schemes from lattices. The size of the public parameters, ciphertexts, and private keys are $\tilde{O}(n^2 \kappa^{1/d})$, $\tilde{O}(n)$, and $\tilde{O}(n)$ respectively. Here, $n$ is the security parameter, $\kappa$ is the length of the identity, and $d$ is a flexible constant that can be set arbitrary (but will affect the reduction cost). Ignoring the poly-logarithmic factors hidden in the asymptotic notation, our schemes achieve the best efficiency among existing adaptively secure IBE schemes from lattices. In more detail, our first scheme is anonymous, but proven secure under the LWE assumption with approximation factor $n^{\omega(1)}$. Our second scheme is not anonymous, but proven adaptively secure assuming the LWE assumption for all polynomial approximation factors.

As a side result, based on a similar idea, we construct an attribute-based encryption scheme for branching programs that simultaneously satisfies the following properties for the first time: Our scheme achieves compact secret keys, the security is proven under the LWE assumption with polynomial approximation factors, and the scheme can deal with unbounded length branching programs.

We describe a polynomial time algorithm to solve the Computational Small Polynomial Ratio Problem in current parameter, which is to find a short element of an ideal <g>\subset Z[X]/\langle X^n+1 \rangle when |g| is smaller than some constant B ( in Q[X]/\langle X^n+1 \rangle) and a somewhat small multiple of g^{-1} ( in R_q) is given.

In GGH scheme, which is the first candidate of a (approximate) multilinear map, the algorithm, using any encodings, can be directly applied to obtain the any secret elements. Recently, the GGH scheme was known to be insecure by so called zeroizing attack {HJ15}, when an encoding of zero is published. Hence, this work leads to showing that GGH scheme without an encoding of zero is also insecure.

We present a new algorithm for residue multiplication modulo the Mersenne prime $2^{521}-1$ based on the Toeplitz matrix-vector product. For this modulo, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of R. Granger and M. Scott presented in Public Key Cryptography - PKC 2015. Although our algorithm has nine more multiplications than Granger-Scott multiplication algorithm, the total number of additions is forty-two less than their algorithm. Even if one takes a ratio of $1:4$ between multiplication and addition our algorithm still has less total number of operations. We also present the test results of both the multiplication algorithms on an Intel Sandy Bridge Corei5-2410M machine, with and without optimization option in GCC.

We propose the first UC commitment scheme for binary strings with the optimal properties of rate approaching 1 and linear time (in the amortised sense, using a small number of seed OTs). On top of this, the scheme is additively homomorphic, which allows for applications to maliciously secure 2-party computation. As tools for obtaining this, we make three contributions of independent interest: we construct the first (binary) linear time encodable codes with non-trivial distance and rate approaching 1, we construct the first almost universal hash function with small seed that can be computed in linear time, and we introduce a new primitive called interactive proximity testing that can be used to verify whether a string is close to a given linear code.

There are many kinds of attacks that can be mounted on block ciphers: differential attacks, impossible differential attacks, truncated differential attacks, boomerang attacks. We consider generic differential attacks used as distinguishers for various types of Feistel ciphers: they allow to distinguish a random permutation from a permutation generated by the cipher. These attacks are based on differences between the expectations of random variables defined by relations on the inputs and outputs of the ciphers. Sometimes, one has to use the value of the variance as well. In this paper, we will provide a tool that computes the exact values of these expectations and variances. We first explain thoroughly how these computations can be carried out by counting the number of solutions of a linear systems with equalities and non-equalities. Then we provide the first applications of this tool. For example, it enabled to discover a new geometry in 4-point attacks. It gave an explanation to some phenomena that can appear in simulations when the inputs and outputs have a small number of bits.

Multilinear maps serve as a basis for a wide range of cryptographic applications. The first candidate construction of multilinear maps was proposed by Garg, Gentry, and Halevi in 2013, and soon afterwards, another construction was suggested by Coron, Lepoint, and Tibouchi (CLT13), which works over the integers. However, both of these were found to be insecure in the face of so-called zeroizing attacks, by Hu and Jia, and by Cheon, Han, Lee, Ryu and Stehlé. To improve on CLT13, Coron, Lepoint, and Tibouchi proposed another candidate construction of multilinear maps over the integers at Crypto 2015 (CLT15).

This article presents two polynomial attacks on the CLT15 multilinear map, which share ideas similar to the cryptanalysis of CLT13. Our attacks allow recovery of all secret parameters in time polynomial in the security parameter, and lead to a full break of the CLT15 multilinear map for virtually all applications.

Direct-recording electronic (DRE) voting systems have been used in several countries including United States, India, and the Netherlands to name a few. In the majority of those cases, researchers discovered several security flaws in the implementation and architecture of the voting system. A common property of the machines inspected was that the votes were stored sequentially according to the time they were cast, which allows an attacker to break the anonymity of the voters using some side-channel information. Subsequent research (Molnar et al. Oakland’06, Bethencourt et al. NDSS’07, Moran et al. ICALP’07) pointed out the connection between vote storage and history-independence, a privacy property that guarantees that the system does not reveal the sequence of operations that led to the current state.

There are two flavors of history-independence. In a weakly history-independent data structure, every possible sequence of operations consistent with the current set of items is equally likely to have occurred. In a strongly history-independent data structure, items must be stored in a canonical way, i.e., for any set of items, there is only one possible memory representation. Strong history-independence implies weak history-independence but considerably constrains the design choices of the data structures.

In this work, we present and analyze an efficient hash table data structure that simultaneously achieves the following properties: • It is based on the classic linear probing collision-handling scheme. • It is weakly history-independent. • It is secure against collision-timing attacks. That is, we consider adversaries that can measure the time for an update operation, but cannot observe data values, and we show that those adversaries cannot learn information about the items in the table. • All operations are significantly faster in practice (in particular, almost 2x faster for high load factors) than those of the commonly used strongly history-independent linear probing method proposed by Blelloch and Golovin (FOCS’07), which is not secure against collision-timing attacks.

The first property is desirable for ease of implementation. The second property is desirable for the sake of maximizing privacy in scenarios where the memory of the hash table is exposed, such as post-election audit of DRE voting machines or direct memory access (DMA) attacks. The third property is desirable for maximizing privacy against adversaries who do not have access to memory but nevertheless are capable of accurately measuring the execution times of data structure operations. To our knowledge, our hash table construction is the first data structure that combines history-independence and protection against a form of timing attacks.

We first prove the truthfulness of a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper ``Cryptographic properties of monotone Boolean functions", by D. Joyner, P. Stanica, D. Tang and the author, to appear in the Journal of Mathematical Cryptology. We prove then an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. This bound shows a deep weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear.

In this paper we focus on the PRINCE block cipher reduced to 6 rounds, with two known plaintext/ciphertext pairs. We develop two attacks on 6-round PRINCE based on accelerated exhaustive search, one with negligible memory usage and one having moderate memory requirements. The time complexities for the two attacks are $2^{96.78}$ and $2^{88.85}$, respectively. The memory consumption of the second attack is less than 200MB and so is not a restricting factor in a real-world setting.

We study the security of the concatenation combiner $H_1(M) \| H_2(M)$ for two independent iterated hash functions with $n$-bit outputs that are built using the Merkle-Damg{\aa}rd construction. In 2004 Joux showed that the concatenation combiner of hash functions with an $n$-bit internal state does not offer better collision and preimage resistance compared to a single strong $n$-bit hash function. On the other hand, the problem of devising second preimage attacks faster than $2^n$ against this combiner has remained open since 2005 when Kelsey and Schneier showed that a single Merkle-Damg{\aa}rd hash function does not offer optimal second preimage resistance for long messages.

In this paper, we develop new algorithms for cryptanalysis of hash combiners and use them to devise the first second preimage attack on the concatenation combiner. The attack finds second preimages faster than $2^n$ for messages longer than $2^{2n/7}$ and has optimal complexity of $2^{3n/4}$. This shows that the concatenation of two Merkle-Damg{\aa}rd hash functions is not as strong a single ideal hash function.

Our methods are also applicable to other well-studied combiners, and we use them to devise a new preimage attack with complexity of $2^{2n/3}$ on the XOR combiner $H_1(M) \oplus H_2(M)$ of two Merkle-Damg{\aa}rd hash functions. This improves upon the attack by Leurent and Wang (presented at Eurocrypt 2015) whose complexity is $2^{5n/6}$ (but unlike our attack is also applicable to HAIFA hash functions).

Our algorithms exploit properties of random mappings generated by fixing the message block input to the compression functions of $H_1$ and $H_2$. Such random mappings have been widely used in cryptanalysis, but we exploit them in new ways to attack hash function combiners.

Barreto, Lynn and Scott elliptic curves of embedding degree 12 denoted BLS12 have been proven to present fastest results on the implementation of pairings at the 192-bit security level [1]. The computation of pairings in general involves the execution of the Miller algorithm and the nal exponentiation. In this paper, we improve the complexity of these two steps up to 8% by searching an appropriate parameter. We compute the optimal ate pairing on BLS curves of embedding degree 12 and we also extend the same analysis to BLS curves with embedding degree 24. Furthermore, as many pairing based protocols are implemented on memory constrained devices such as SIM or smart cards, we describe an ecient algorithm for the computation of the nal exponentiation less memory intensive with an improvement up to 25% with respect to the previous work.

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of information security and cryptography. The position is for five years at the Department of Computer Science and Engineering. The PhD student will join Katerina Mitrokotsa’s group and will be funded by a project funded by the Swedish research council focusing on security and privacy issues in resource constrained devices.

The PhD student is expected to have a MSc degree or equivalent, and strong background in mathematics and/or theoretical computer science, with some background in cryptography.

The position is fully funded for five years. The call for expressions of interest will remain open until a suitable candidate is appointed.

For any inquiries or to apply for the position, submit a full research curriculum-vitae (cv), names of two references, and a research statement to Prof. Katerina Mitrokotsa (aikmitr@ chalmers.se) clearly indicating the position sought.

Successful candidates will help to design and evaluate cryptographically reliable and privacy-preserving authentication protocols.

Closing date for applications: 15 March 2016

Contact: Katerina Mitrokotsa
Associate Professor
Chalmers University of Technology
Department of Computer Science and Engineering
Göteborg, Sweden

More information: http://www.chalmers.se/en/about-chalmers/vacancies/Pages/default.aspx?rmpage=job&rmjob=3333

We present the first physical side-channel attack on elliptic curve cryptography running on a PC. The attack targets the ECDH public-key encryption algorithm, as implemented in the latest version of GnuPG.

By measuring the target's electromagnetic emanations, the attack extracts the secret decryption key within seconds, from a target located in an adjacent room across a wall. The attack utilizes a single carefully chosen ciphertext, and tailored time-frequency signal analysis techniques, to achieve full key extraction.

Committing integers and proving relations between them is an essential ingredient in many cryptographic protocols. Among them, range proofs have shown to be fundamental. They consist of proving that a committed integer lies in a public interval. By the way, it can also be seen as a particular case of the more general Diophantine relations: for the committed vector of integers x, there exists a vector of integers w such that P(x,w) = 0, where P is a polynomial. In this paper, we revisit the security strength of the statistically hiding commitment scheme over the integers due to Damgård-Fujisaki, and the zero-knowledge proofs of knowledge of openings. Our first main contribution shows how to remove the Strong RSA assumption and replace it by the standard RSA assumption in the security proofs. This improvement naturally extends to generalized commitments and more complex proofs without modifying the original protocols. Thereafter, we show that this commitment scheme over the integers is compatible with a commitment scheme modulo a prime p, which allows for more efficient proofs of relations between the committed values, still under the RSA assumption. Our second contribution is thus a more efficient and more secure interactive technique to prove Diophantine relations. We illustrate it with the most efficient range proofs. In addition, the security is proven under the sole RSA assumption.