International Association
for Cryptologic Research

First-order secure Threshold Implementations (TI) of symmetric cryptosystems provide provable security at a moderate overhead; yet attacks using higher-order statistical moments are still feasible. Cryptographic instances compliant to Higher-Order Threshold Implementation (HO-TI) can prevent such attacks, however, usually at unacceptable implementation costs. As an alternative concept we investigate in this work the idea of dynamic hardware modification, i.e., random changes and transformations of cryptographic implementations in order to render higher-order attacks on first-order TI impractical. In a first step, we present a generic methodology which can be applied to (almost) every cryptographic implementation. In order to investigate the effectiveness of our proposed strategy, we use an instantiation of our methodology that adapts ideas from White-Box Cryptography and applies this construction to a first-order secure TI. Further, we show that dynamically updating cryptographic implementations during operation provides the ability to avoid higher-order leakages to be practically exploitable.

In this paper, we present a new post-quantum digital signature algorithm that derives its security entirely from assumptions about symmetric-key primitives, which are very well studied and believed to be quantum-secure (with increased parameter sizes). We present our new scheme with a complete post-quantum security analysis, and benchmark results from a prototype implementation.

Our construction is an efficient instantiation of the following design: the public key is $y=f(x)$ for preimage-resistant function $f$, and $x$ is the private key. A signature is a non-interactive zero-knowledge proof of $x$, that incorporates a message to be signed. Our security analysis uses recent results of Unruh (EUROCRYPT'12,'15,'16) that show how to securely convert an interactive sigma protocol to a non-interactive one in the quantum random oracle model (QROM). The Unruh construction is generic, and does not immediately yield compact proofs. However, when we specialize the construction to our application, we can reduce the size overhead of the QROM-secure construction to 1.6x, when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. Our implementation results compare both instantiations, with multiple choices of $f$ for comparison. Our signature scheme proposal uses the block cipher LowMC for $f$, as it gives the shortest signatures. In addition to reducing the size of signatures with Unruh's construction, we also improve the size of proofs in the underlying sigma protocol (of Giacomelli et al., USENIX'16) by a factor of two. This is of independent interest as it yields more compact proofs for arbitrary choices of $f$ in the classical case as well. Further, this reduction in size comes at no additional computational cost.

In this work we provide the first practical instantiation of ring-LWE-based public-key encryption that is protected against active attacks (i.e., adaptive chosen-ciphertext attacks) and equipped with countermeasures against side-channel attacks (masking and hiding). We propose a novel provably first-order secure masking scheme that outperforms previous work and we combine this masking approach with blinding and shuffing techniques to further thwart higher-order attacks. Our work shows that extremely fast and secured implementations of postquantum public-key encryption are possible on constrained devices and we give evidence that ring-LWE-based schemes are highly suitable for implementations on smart cards due to the large amount of linear operations. Even with conservative parameter choices (n = 1024; q = 12289) for ring-LWE encryption we obtain 243 bits of quantum security based on a recently established model. Our implementation requires 1,222,054 cycles for encryption and 2,372,242 cycles for decryption with masking and hiding countermeasures on a Cortex-M4F. Furthermore, the first-order security of our masked implementation is practically verified using the non-specific t-test evaluation methodology.

In CRYPTO'16, a new family of tweakable lightweight block ciphers - SKINNY was introduced. Denoting the variants of SKINNY as SKINNY-$n$-$t$, where $n$ represents the block size and $t$ represents the tweakey length, the design specifies $t \in \{n, 2n, 3n\}$. In this work, we evaluate the security of SKINNY against differential cryptanalysis in the related-tweakey model. First, we investigate truncated related-tweakey differential trails of SKINNY and search for longest impossible and rectangle distinguishers where there is only one active cell in the input and the output. Based on the distinguishers obtained, $18$, $22$ and $27$ rounds of SKINNY-$n$-$n$, SKINNY-$n$-$2n$ and SKINNY-$n$-$3n$ can be attacked respectively. Moreover, actual differential trails for SKINNY under related-tweakey model are also explored and optimal differential trails of SKINNY-64 within certain number of rounds are searched with an indirect searching method based on Mixed-Integer Linear Programming. The results show a trend that as the number of rounds increases, the probability of optimal differential trails is much lower than the probability derived from lower bounds of active Sboxes in SKINNY.

We prove that \emph{at least} one of the following statements is true:

\begin{itemize} \item (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions; \item For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any efficiently samplable distribution over any OR NP-relations with distinguishability gap bounded by $\epsilon$. \end{itemize}

Both these statements have been shown to be unprovable [Impagliazzo and Rudich, STOC 89; Canetti et. al., STOC 01] via black-box reduction. Our win-win result also establishes an unexpected connection between the complexity of public-key encryption and the round-complexity of concurrent zero knowledge.

As the main technical contribution, we introduce a dissection procedure for concurrent adversaries, which enables us to show that, if there is a magic concurrent adversary that breaks the $\epsilon$-distributional concurrent zero knowledge of the Feige-Shamir protocol for some OR NP-relations, for efficiently samplable distribution on an NP relation of an OR-language, then we transform it to an (infinitely-often) public-key encryption and key agreement based on injective one-way functions. If it could be proved that the reduction from injective one-way functions to public-key encryption does not exist, then our dissection reveals that all possible concurrent verifiers for the Feige-Shamir protocol share a common structure in their computation.

This dissection of adversary algorithms also gives insight into the fundamental gap between the known \emph{universal} security reduction that works for \emph{any} adversaries, and the security definition (of almost all cryptographic primitives/protocols), which switches the order of qualifiers and only requires that for every adversary there \emph{exists} an \emph{individual} reduction.

Event date: 1 April 2017
Submission deadline: 8 December 2016
Notification: 25 January 2017

The side channel lab, which is part of the Bristol crypto group, is expanding. With several new grants coming through we are looking to substantially increase our team. We are looking for a variety of people on different levels of experience and interest. In particular we are looking for people who have (or would like to develop) expertise in

- practical attacks (i.e. the hands on aspects of physical attacks),

- developing efficient attacks (based on parallel implementations building on our existing HPC framework)

- utilising compilers to detect and mitigate side channel leaks (timing, cache, as well as physical leaks)

- working with open source processors and hardware implementations

- statistical aspects of side channel analysis

The lab has state-of-the-art equipment, access to a high performance computing platform, and is integrated in the vibrant Crypto group. You are encouraged to engage with the wider group (and indeed Computer Science department) and, assuming sufficient seniority, take responsibility for your research direction. There are opportunities to contribute to teaching and to network in the context of the project with industrial partners and so to move more towards industry.

There are multiple positions available and we will recruit until all positions are filled. Posts are on either the Research associate level (typically this is for people who are close to finishing their PhD), or, on Senior Research Associate level. The salary for Research associates is between £31656-35609 (Grade I), and for Senior Research Associates it is between £35609-40082 (Grade J). PhD students will benefit from an enhanced stipend (fees will be covered, and the stipend is just under 20000 on which no tax is payable). All grants have ample resources for trips, professional training, and internships.

We consider all applicants that have a background in either computer science, electrical engineering, or mathematics (or any combination thereof). We do not require you to have prior experience in side channel attacks, but expect you are keen to learn and explore.

Closing date for applications: 31 January 2017

Contact: Please contact Prof. Elisabeth Oswald (elisabeth.oswaldATbristol.ac.uk) for further information.

Job Responsibilities:

•To design and develop cryptographic protocols and schemes

•To design, analyze and implement cryptographic systems and related systems such as blockchain

•To study the latest cryptographic algorithms and protocols

Requirements:

•Master degree in computer science, electronic engineering or other relevant disciplines with 3+ years experience; less experience for PhD holders.

•Experience on cryptographic system design and cryptanalysis

•Deep knowledge on number theory and security proofs

•Hands-on experience with C/C++ and Java

•Preferably having experiences on using cryptographic libraries such as OpenSSL, MIRACL, PBC, etc.

•Experience on developing cloud computing systems an advantage, but not a must

•Strong interpersonal and communications skills

•Good command of both written and spoken English and Chinese

Closing date for applications: 30 November 2016

Contact: charlenechoo (at) astri.org

More information: http://www.astri.org/careers/work-at-astri/jobs/senior-software-engineer-software-engineer-applied-cryptography-4/

We present a functional encryption scheme based on standard assumptions where ciphertexts are associated with a tuple of values (x 1 ,...,x n ) in Z p n, secret keys are associated with a degree-two polynomial, and the decryption of a ciphertext ct (x 1 ,...,x n )in Z p n with a secret key sk P in Z p [X 1 ,...,X n ],deg(P)≤2 recovers P(x 1 ,...,x n ), where the ciphertext contains only O(n) group elements. Our scheme, which achieves selective security based on pairings, also yields a new predicate encryption scheme that supports degree-two polynomial evaluation, generalizing both [24] and [9].

Predicate encodings are information-theoretic primitives that can be transformed generically into predicate encryption schemes for a broad class of predicates (Wee, TCC 2014; Chen, Gay, Wee, EUROCRYPT 2015). Starting from the observation that predicate encodings admit a purely algebraic characterization equivalent to the original notion, we obtain several new results about predicate encodings. First, we propose two generic optimizations that improve their efficiency. Second, we propose new transformations for boolean combinations of predicate encodings. Third, we develop several new predicate encodings for boolean formulas and arithmetic span programs. In the important case of boolean formulas, our encodings are more efficient and attribute-hiding; moreover, they support revocation and delegation. Finally, we implement our approach and experimentally validate its efficiency gains.

We present a practically efficient functional encryption scheme for the class of functionalities that can be expressed via bilinear forms over the integers. Bilinear forms are a general class of quadratic functions that includes, for instance, multivariate quadratic polynomials. Our realization works over asymmetric bilinear groups and is surprisingly simple, efficient and easy to implement. For instance, in our scheme the public key and each ciphertext consist of $2n+1$ and $4n+2$ group elements respectively, where $n$ is the dimension of the encrypted vectors, while secret keys are only two group elements.

The scheme is proved secure under the standard (adaptive) indistinguishability based security notion of Boneh, Sahai and Waters (TCC 2011). The proof is rather convoluted and relies on the so-called generic bilinear group model. Specifically, our proof comes in two main stages. In a preliminary step, we put forward and prove a new master theorem to argue hardness in the generic bilinear group model of a broad family of interactive decisional problems, which includes the indistinguishability-based security game for our functional encryption scheme. Next, the more technically involved part of the proof consists in showing that our scheme actually fits the requirements of our master theorem.

Universal hash functions based on univariate polynomials are well known, e.g. \sym{Poly1305} and \sym{GHASH}. Using Horner's rule to evaluate such hash functions require $\ell-1$ field multiplications for hashing a message consisting of $\ell$ blocks where each block is one field element. A faster method is based on the class of Bernstein-Rabin-Winograd (BRW) polynomials which require $\lfloor\ell/2\rfloor$ multiplications and $\lfloor\lg\ell\rfloor$ squarings for $\ell\geq 3$ blocks. Though this is significantly smaller than Horner's rule based hashing, implementation of BRW polynomials for variable length messages present significant difficulties. In this work, we propose a two-level hash function where BRW polynomial based hashing is done at the lower level and Horner's rule based hashing is done at the higher level. The BRW polynomial based hashing is applied to a fixed number of blocks and hence the difficulties in handling variable length messages is avoided. Even though the hash function has two levels, we show that it is sufficient to use a single field element as the hash key. The basic idea is instantiated to propose two new hash functions, one which hashes a single binary string and the other can hash a vector of binary strings. We describe two actual implementations, one over $\mathbb{F}_{2^{128}}$ and the other over $\mathbb{F}_{2^{256}}$ both using the {\tt pclmulqdq} instruction available in modern Intel processors. On both the Haswell and Skylake processors, the implementation over $\mathbb{F}_{2^{128}}$ is faster than the highly optimised implementation of \sym{GHASH} by Gueron. We further show that the Fast Fourier Transform based field multiplication over $\mathbb{F}_{2^{256}}$ proposed by Bernstein and Chou can be used to evaluate the new hash function at a cost of about at most 46 bit operations per bit of digest, but, unlike the Bernstein-Chou analysis, there is no hidden cost of generating the hash key. More generally, the new idea of building a two-level hash function having a single field element as the hash key can be applied to other finite fields to build new hash functions.

In the past two years there have been several advances in Number Field Sieve (NFS) algorithms for computing discrete logarithms in finite fields $\fpn$ where $p$ is prime and $n > 1$ is a small integer. This article presents a concise overview of these algorithms and discusses some of the challenges with assessing their impact on keylengths for pairing-based cryptosystems.

The huge time and memory complexities of utilizing bit-based division property, which was first presented by Todo and Morri at FSE 2016, bothered cryptographers for quite some time and it had been solved by Xiang \textit{et al.} at ASIACRYPT 2016. They applied MILP method to search integral distinguisher based on division property, and used it to analyze six lightweight block ciphers. Later on, Sun \textit{et al.} handled the feasibility of MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. Although MILP-aided bit-based division property has gave many perfect results since its appearance, there still are many left problems when we want to develop its further applications. In this paper, we focus on the feasibility of MILP-aided bit-based division property for ARX-based primitive. More specifically, we consider the construction of MILP models for some components of ARX-based structure. Firstly, the \texttt{Modulo} model is proposed by using its iterated expression and introducing some auxiliary variables. Then, to propagate the operations of \texttt{AND} and \texttt{OR} with a constant (or a subkey), we prove that the known-region deduced by the input division property is always included in the known-region derived from the output division property, which allows us to ignore these operations. Furthermore, with its help, we also handle the \texttt{Modulo} operation with a constant (or a subkey). As a result, these new models are exploited to search integral distinguishers for some ARX-based block ciphers. For HIGHT and LEA, the lengths of the distinguishers both are improved by one round. Some 15-round integral distinguishers for TEA/XTEA are presented. Comparing with the existing one transformed by utilizing the equivalence between zero-correlation and integral cryptanalysis, our newly obtained distinguishers either reduces the data requirement or increases the number of zero-sum bits. Moreover, the bit-based division properties for KATAN and KTANTAN families of block ciphers are also provided.

A Fuzzy Extractor (Dodis et al., Eurocrypt 2004) is a two-step protocol that turns a noisy secret into a uniformly distributed key R. To eliminate noise, the generation procedure takes as inputs an enrollment value w to output R and an helper string P that will enable further reproduction of R from some close reading w'. Nevertheless, Boyen fast highlighted the need for reusable fuzzy extractors (CCS 2004) that remain secure even when numerous calls to the generation procedure are made on the same fuzzy secret. Only recently has been proposed such a fuzzy extractor by Canetti et al (Eurocrypt 2016). Even if not explicitly mentioned in their work, their main construction based on Hamming distance can also handle the set difference metric, an important metric also used for fuzzy extractors.

In this work, we propose a new and generic framework to solve the reusability problem. Our approach is simple, reaps benefits of any nonreusable fuzzy extractor and naturally applies to set difference metric. When the universe size is polynomial in the set size, our work permits to handle, in polynomial time, the case where the number of errors is linear in the length of the code, when the recent work of Canetti et al. can only handle a sublinear number of errors in polynomial time. This last point makes our construction more efficient than previous constructions since the practical efficiency of a fuzzy extractor depends on its capacity to handle errors. Our scheme has also benefits better storing capacities. Now when the universe size is superpolynomial in the set size, our work enjoys satisfying complexities of existing and efficient nonreusable Fuzzy Extractors while the approach of Canetti et al. does not apply.

Besides considering the reusability issue, we also propose the field of browser and device fingerprinting as a new and promising playground for Fuzzy Extractors. Philosophically close to biometrics, this burgeoning field of fingerprinting mainly considers list of features but comes with deeper variations over time while still enabling users' identification. We then define Adaptive Fuzzy Extractors, meant to handle these changes. More precisely, such a Fuzzy Extractor enables to recover a key R from a reading w' as long as w' has naturally drifted from w.

Akleylek et al have proposed Ring-TESLA, a practical and efficient digital signature scheme based on the Ring Learning With Errors problem. However we have identified there are some problems with the parameters proposed for Ring-TESLA, as we believe they do not ensure the correct operation of the scheme and do not provide the targeted levels of security under either the provable Ring-TESLA reduction, or an assessment of practical modern attacks such as lattice sieving.

We recommend new Ring-TESLA parameters that target more security levels and provide for correct, secure, and efficient instantiation. We describe the necessary preliminaries, recap the Ring-TESLA scheme, and present our parameter recommendations, selection methodology, and analysis.

The tweakable Even-Mansour construction generalizes the conventional Even-Mansour scheme through replacing round keys by strings derived from a master key and a tweak. Besides providing plenty of inherent variability, such a design builds a tweakable block cipher from some lower level primitive. In the present paper, we evaluate the multi-key security of TEM-1, one of the most commonly used one-round tweakable Even-Mansour schemes (introduced at CRYPTO 2015), which is constructed from a single $n$-bit permutation $E$ and a function $f(k,t)$ linear in $k$ from some tweak space to ${\{ 0,1\} ^n}$. Based on giant component theorem in random graph theory, we propose collision-based multi-key attacks on TEM-1 in the known-plaintext setting. Furthermore, inspired by the methodology of Fouque et al. presented at ASIACRYPT 2014, we devise a novel way of detecting collisions to obtain memory-efficient attacks in the blockwise-adaptive chosen-plaintext setting.

As applications, we utilize our techniques to analyze the authenticated encryption algorithm Minalpher (a second-round candidate of CAESAR) and OPP (proposed at EUROCRYPT 2016) in the multi-key setting. First, we present our known-plaintext attacks on Minalpher and OPP without nonce misuse, which enable us to recover almost all $O(2^{(n/3)})$ independent equivalent keys by making $O(2^{(n/3)})$ queries per key and costing $O(2^{(2n/3)})$ memory overall. Moreover, after defining appropriate iterated functions and accordingly changing the mode of creating chains, we improve the basic blockwise-adaptive chosen-plaintext attack to make it applicable for the nonce-respecting setting.

While our attacks do not contradict the security proofs of Minalpher and OPP in the classical setting, nor pose an immediate threat to their uses, our results demonstrate their security margins in the multi-user setting should be carefully considered. We emphasize this is the very first third-party analysis on Minalpher and OPP.

In this work, we propose a variant of functional encryption called projective arithmetic functional encryption (PAFE). Roughly speaking, our notion is like functional encryption for arithmetic circuits, but where secret keys only yield partially decrypted values. These partially decrypted values can be linearly combined with known coefficients and the result can be tested to see if it is a small value.

We give a degree-preserving construction of PAFE from multilinear maps. That is, we show how to achieve PAFE for arithmetic circuits of degree d using only degree-d multilinear maps. Our construction is based on an assumption over such multilinear maps, that we justify in a generic model. We then turn to applying our notion of PAFE to one of the most pressing open problems in the foundations of cryptography: building secure indistinguishability obfuscation (iO) from simpler building blocks.

iO from degree-5 multilinear maps. Recently, the works of Lin [Eurocrypt 2016] and Lin-Vaikuntanathan [FOCS 2016] showed how to build iO from constant-degree multilinear maps. However, no explicit constant was given in these works, and an analysis of these published works shows that the degree requirement would be in excess of 30. The ultimate "dream" goal of this line of work would be to reduce the degree requirement all the way to 2, allowing for the use of well-studied bilinear maps, or barring that, to a low constant that may be supportable by alternative secure low-degree multilinear map candidates. We make substantial progress toward this goal by showing how to leverage PAFE for degree-5 arithmetic circuits to achieve iO, thus yielding the first iO construction from degree-5 multilinear maps.

We present a new construction of Indistinguishability Obfuscation (IO) from the following:

1. asymmetric $L$-linear maps [Boneh and Silverberg, Eprint 2002] with subexponential Decisional Diffie-Hellman (DDH) assumption,

2. locality-$L$ polynomial-stretch pseudorandom generators (PRG) with subexponential security, and

3. the subexponential hardness of Learning With Errors (LWE).

When plugging in a candidate PRG with locality-$5$ (eg, [Goldreich, ECCC 2010, O'Donnell and Witmer, CCC 2014]), we obtain a construction of IO from subexponential DDH on 5-linear maps and LWE. Previous IO constructions rely on multilinear maps or graded encodings with higher degrees (at least larger than 30), more complex functionalities (eg, graded encodings with complex label structures), and stronger assumptions (eg, the joint-SXDH assumption).

From the proposal of key-recovery algorithms for RSA secret key from its noisy version at Crypto2009, there have been considerable researches on RSA key recovery from discrete noise. At CHES2014, two efficient algorithms for recovering secret keys are proposed from noisy analog data obtained through physical attacks such as side channel attacks. One of the algorithms works even if the noise distributions are unknown. However, the algorithm is not optimal especially if the noise distribution is imbalanced. To overcome this problem, we propose new algorithms to recover from such an imbalanced analog noise. We first present a generalized algorithm and show its success condition. We then construct the algorithm suitable for imbalanced noise under the condition that the variances of noise distributions are a priori known. Our algorithm succeeds in recovering the secret key from much more noise. We present the success condition in the explicit form and verify that our algorithm is superior to the previous results. We then show its optimality. Note that the proposed algorithm has the same performance as the previous one in the balanced noise. We next propose a key recovery algorithm that does not use the values of the variances. The algorithm first estimates the variance of noise distributions from the observed data with help of the EM algorithm and then recover the secret key by the first algorithm with their estimated variances. The whole algorithm works well even if the values of the variance is unknown in advance. We examine that our proposed algorithm succeeds in recovering the secret key from much more noise than the previous algorithm.