Here you can see all recent updates to the IACR webpage. These updates are also available:

29
April
2017

Event Calendar
ICITS 2017: 10th International Conference on Information Theoretic Security
Hong Kong, China, 29 November - 2 December 2017

Event date: 29 November to 2 December 2017

Submission deadline: 5 June 2017

Notification: 14 August 2017

Submission deadline: 5 June 2017

Notification: 14 August 2017

28
April
2017

ePrint Report
A crossbred algorithm for solving Boolean polynomial systems
Antoine Joux, Vanessa Vitse

We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of $m$ polynomials of degree at most $d$ in $n$ variables, we want to find its solutions over $\F_2$. Except for $d=1$, the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, the first named author has been able to solve all the Fukuoka Type~I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and with a lot of luck).

ePrint Report
On the Efficient Construction of Lightweight Orthogonal MDS Matrices
Lijing Zhou, Licheng Wang, Yiru Sun

In present paper, we mainly investigate the problem of efficiently constructing lightweight orthogonal MDS matrices over the matrix polynomial residue ring. Surprisingly, this problem did not receive much attention previously. We propose a necessary-and-sufficient condition, which is more efficient than the traditional method, about judging whether an orthogonal matrix is MDS. Although it has been proved that the circulant orthogonal MDS matrix does not exist over the finite field, we discuss anew this problem and get a new method to judge which polynomial residue ring can be used to construct the circulant orthogonal MDS matrix. According to this method, the minimum polynomials of non-singular matrices over $\FF$ are factorized. With these results of factorizations, finally, we propose an extremely efficient algorithm for constructing lightweight circulant orthogonal MDS matrices. By using this algorithm, a lot of new lightweight circulant orthogonal MDS matrices are constructed for the first time.

ePrint Report
Too Simple to be UC-Secure: On the UC-Insecurity of the ``Simplest Protocol for Oblivious Transfer'' of Chou and Orlandi
Ziya Alper Genç, Vincenzo Iovino, Alfredo Rial

In 2015, Chou and Orlandi presented an oblivious transfer protocol that already drew a lot of attention both from theorists and practitioners due to its extreme simplicity and high efficiency. Chou and Orlandi claimed that their protocol is UC-secure under dynamic corruptions, which is a very strong security guarantee. Unfortunately, in this work we point out a serious flaw in their security proof. Moreover, we show that their protocol cannot be proven UC-secure even under static corruptions unless some computational assumption, which we conjecture to hold, is false.

ePrint Report
Enforcing Input Correctness via Certification in Garbled Circuit Evaluation
Yihua Zhang, Marina Blanton, Fattaneh Bayatbabolghani

Secure multi-party computation allows a number of participants to securely
evaluate a function on their private inputs and has a growing number of
applications. Two standard adversarial models that treat the participants as
semi-honest or malicious, respectively, are normally considered for showing
security of constructions in this framework. In this work, we go beyond the
standard security model in the presence of malicious participants and treat
the problem of enforcing correct inputs to be entered into the computation.
We achieve this by having a certification authority certify user's
information, which is consequently used in secure two-party computation
based on garbled circuit evaluation. The focus of this work on enforcing
correctness of garbler's inputs via certification, as prior work already
allows one to achieve this goal for circuit evaluator's input. Thus, in
this work, we put forward a novel approach for certifying user's input and
tying certification to garbler's input used during secure function
evaluation based on garbled circuits. Our construction achieves notable
performance of adding only one (standard) signature verification and
$O(n\rho)$ symmetric key/hash operations to the cost of garbled circuit
evaluation in the malicious model via cut-and-choose, in which $\rho$
circuits are garbled and $n$ is the length of the garbler's input in bits.
Security of our construction is rigorously proved in the standard model.

This work considers the problem of constructing efficient MDS matrices over the field $\F_{2^m}$. Efficiency is measured by the metric XOR count which was introduced by Khoo et al. in CHES 2014. Recently Sarkar and Syed (ToSC Vol. 1, 2016) have shown the existence of $4\times 4$ Toeplitz MDS matrices with optimal XOR counts. In this paper, we present some characterizations of Toeplitz matrices in light of MDS property. Our study leads to improving the known bounds of XOR counts of $8\times 8$ MDS matrices by obtaining Toeplitz MDS matrices with lower XOR counts over $\F_{2^4}$ and $\F_{2^8}$.

ePrint Report
Forking-Free Hybrid Consensus with Generalized Proof-of-Activity
Shuyang Tang, Zhiqiang Liu, Sherman S. M. Chow, Zhen Liu, Yu Long, Shengli Liu

Bitcoin and its underlying blockchain mechanism have been attracting much attention. One of their core innovations, Proof-of-Work (PoW), is notoriously inefficient and potentially motivates a centralization of computing power, which defeats the original aim of decentralization. Proof-of-Stake (PoS) is later proposed to replace PoW. However, both PoW and PoS have different inherent advantages and disadvantages, so does Proof-of-Activity (PoA) of Bentov et al. (SIGMETRICS 2014) which only offers limited combinations of two mechanisms. On the other hand, the hybrid consensus protocol of Pass
and Shi (ePrint 2016/917) aims to improve the efficiency by dynamically maintaining a rotating committee. Yet, there are unsatisfactory issues including selfish mining and fair committee election.
In this paper, we firstly devise a generalized variant of PoW. After that, we leverage our newly proposed generalized PoW to construct forking-free hybrid consensus, which addresses issues faced by a regular hybrid consensus mechanism. We further combine our forking-free hybrid consensus mechanism with PoS for a generalization of PoA. Compared with PoA, our generalized PoA improves the efficiency and provides more flexible combinations of PoW and PoS, resulting in a more powerful and applicable consensus scheme.

We present a cipher that represents a novel strategy: replacing algorithmic complexity with computational simplicity while generating cryptographic efficacy through large as desired quantities of randomness. The BitFlip cipher allows its user to defend herself with credibly appraised mathematical intractability, well-hinged on solid combinatorics. This is the situation when the amount of randomness is small relative to the accumulated amount of processed plaintext. Deploying more randomness, BitFlip will frustrate its cryptanalyst with terminal equivocation among two or more plausible message candidates. This equivocation defense can be increased by simply increasing the amount of deployed randomness, coming at-will close to Vernam’s perfect secrecy. BitFlip is structured as a super polyalphabetic cipher where a letter comprised of 2n bits is pointed-to by any 2n bits string with a Hamming distance of n from it. When a passed 2n bits string is found to have no n-valued Hamming distance from any letter in the reader’s alphabet, it is regarded as null. This allows for co-encryption of several messages each over its respective alphabet; thereby offering a powerful equivocation defense because the ciphertext does not indicate which alphabet the intended reader is using. BitFlip becomes increasingly timely and practical, exploiting the advent of high quality non-algorithmic randomness, as well as the effect of Moore’s law on the cost of handling large amounts of memory. BitFlip is a natural fit for what fast emerges as the biggest customer of cryptography: the Internet of Things

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.

26
April
2017

An ECRYPT White-Box Cryptography Competition

Can you obfuscate an AES encryption in practice? Can you break a secretly obfuscated AES program?

Starting from May 15, the EU-sponsored ECRYPT-CSA project is organising an open competition on white-box cryptography.

The competition comes in two flavors for competitors:

- Developers are invited to post challenge programs that are white-box implementations of AES-128 under freely chosen keys. Challenges are expected to resist key extraction against a white-box attacker.
- Attackers are invited to break the submitted challenges i.e. extract their hard-coded encryption key.

May 15, 2017: Competition starting date, submission server opens

Aug 31, 2017: Submission deadline (attacks continue)

Sep 24, 2017: Final deadline (attacks stop)

CHES 2017 rump session: Announcement of winners

ePrint Report
Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols
Ran Cohen, Sandro Coretti, Juan Garay, Vassilis Zikas

An important benchmark for multi-party computation protocols (MPC) is their round complexity. For several important MPC tasks, (tight) lower bounds on the round complexity are known. However, for some of these tasks, such as broadcast, the lower bounds can be circumvented when the termination round of every party is not a priori known, and simultaneous termination is not guaranteed. Protocols with this property are called \emph{probabilistic-termination (PT)} protocols.

Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of $m$ protocols with constant expected round complexity might take $O(\log m)$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing '03) developed a technique for parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al.(CRYPTO '16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is "privacy free," and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity.

In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, secure against a dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying \emph{protocols}. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the \emph{functionalities} realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol.

To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.

Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of $m$ protocols with constant expected round complexity might take $O(\log m)$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing '03) developed a technique for parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al.(CRYPTO '16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is "privacy free," and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity.

In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, secure against a dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying \emph{protocols}. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the \emph{functionalities} realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol.

To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.

ePrint Report
TOPPSS: Cost-minimal Password-Protected Secret Sharing based on Threshold OPRF
Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, Jiayu Xu

We present TOPPSS, the most efficient Password-Protected Secret Sharing (PPSS) scheme to date. A (t; n)-threshold PPSS, introduced
by Bagherzandi et al, allows a user to share a secret among n servers so that the secret can later be reconstructed by the user from any subset of t+1 servers with the sole knowledge of a password. It is guaranteed that any coalition of up to t corrupt servers learns nothing about the secret (or the password). In addition to providing strong protection to secrets stored online, PPSS schemes give rise to efficient Threshold PAKE (T-PAKE) protocols that armor single-server password authentication against the inherent vulnerability to offline dictionary attacks in
case of server compromise.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satises threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satises threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.

Since its introduction the UC framework by Canetti has received a lot of attention. A
contributing factor to its popularity is that it allows to capture a large number of common cryptographic primitives using ideal functionalities and thus can be used to give modular proofs for many cryptographic protocols. However, an important member of the cryptographic family has not yet been captured by an ideal functionality, namely the zero-knowledge proof of membership. We give the first formulation of a UC zero-knowledge proof of membership and show that it is closely related to the notions of straight-line zero-knowledge and simulation soundness.

ePrint Report
Indistinguishability Obfuscation for All Circuits from Secret-Key Functional Encryption
Fuyuki Kitagawa, Ryo Nishimaki, Keisuke Tanaka

We show that indistinguishability obfuscation (IO) for all circuits can be constructed solely from secret-key functional encryption (SKFE). In the construction, SKFE need to be able to issue a-priori unbounded number of functional keys, that is, collusion-resistant.

Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from ordinary SKFE.

In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is also sufficient for constructing IO.

Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from ordinary SKFE.

In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is also sufficient for constructing IO.

ePrint Report
Provably Secure Three-party Password Authenticated Key Exchange Protocol Based On Ring Learning With Error
Dongqing Xu, Debiao He, Kim-Kwang Raymond Choo, Jianhua Chen

Three-party Password Authenticated Key Exchange (3PAKE) protocol is an important cryptographic primitive, where clients can establish a session key using easy-to-remember passwords. A number of 3PAKE protocols based on traditional mathematical problems have been presented in the literature, but these protocols are not able to resist attacks using quantum computers. In this paper, we construct the first 3PAKE protocol from lattices. Lattice-based cryptography is a promising post-quantum cryptography approach. We then prove its security in the random oracle model, and implement the proposed protocol using LatticeCrypto. The implementation results shows our protocol is very efficient in practice.

ePrint Report
New Protocols for Conditional Disclosure of Secrets (and More)
Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ communication.

- As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on $N$ vertices, there is a secret-sharing scheme for $N$ parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in $G$ are connected, and where each party gets a share of size $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required communication complexity $\tilde{O}(N^{1/2})$. Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called ``linear reconstruction''. This is the first work to break this $O(N^{1/2})$ ``linear reconstruction'' barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval.

We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ communication.

- As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on $N$ vertices, there is a secret-sharing scheme for $N$ parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in $G$ are connected, and where each party gets a share of size $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required communication complexity $\tilde{O}(N^{1/2})$. Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called ``linear reconstruction''. This is the first work to break this $O(N^{1/2})$ ``linear reconstruction'' barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval.

We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.

ePrint Report
Almost Optimal Oblivious Transfer from QA-NIZK
Olivier Blazy, Céline Chevalier, Paul Germouty

We show how to build a UC-Secure Oblivious Transfer in the presence of Adaptive Corruptions from Quasi-Adaptive Non-Interactive Zero-Knowledge proofs. Our result is based on the work of Jutla and Roy at Asiacrypt 2015, where the authors proposed a constant-size very efficient PAKE scheme. As a stepping stone, we first show how a two-flow PAKE scheme can be generically transformed in an optimized way, in order to achieve an efficient three-flow Oblivious-Transfer scheme.
We then compare our generic transformations to existing OT constructions and see that we manage to gain at least a factor 2 to the best known constructions. To the best of our knowledge, our scheme is the first UC-secure Oblivious Transfer with a constant size flow from the receiver, and nearly optimal size for the server.

ePrint Report
Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model
Nico D\"ottling, Jesper Buus Nielsen, Maciej Obremski

We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding.

Prior to our result only codes with computational security were known for this model, and it has been an open problem to construct such a code with information theoretic security.

As a conceptual contribution we also introduce the notion of a one-way non-malleable code, which is the main new ingredient in our construction. In this notion, the tampering adversary's goal is to recover the encoded message rather than to distinguish the encodings of two messages.

Our technical contributions are two-fold. \begin{itemize} \item

We show how to construct a full fledged continuously non-malleable code from a one-way continuously non-malleable code while only increasing the number of states by a constant factor.

\item

We construct a one-way continuously non-malleable code in the constant split state model with information theoretic security.

\end{itemize}

Prior to our result only codes with computational security were known for this model, and it has been an open problem to construct such a code with information theoretic security.

As a conceptual contribution we also introduce the notion of a one-way non-malleable code, which is the main new ingredient in our construction. In this notion, the tampering adversary's goal is to recover the encoded message rather than to distinguish the encodings of two messages.

Our technical contributions are two-fold. \begin{itemize} \item

We show how to construct a full fledged continuously non-malleable code from a one-way continuously non-malleable code while only increasing the number of states by a constant factor.

\item

We construct a one-way continuously non-malleable code in the constant split state model with information theoretic security.

\end{itemize}

In the classical world, the XOR of pseudorandom permutations $E_{k_1}\xor\cdots\xor E_{k_r}$ for $r\geq2$ is a well-established way to design a pseudorandom function with ``optimal'' security: security up to approximately $\min\{|K|,|X|\}$ queries, where $K$ and $X$ are the key and state space of the block cipher $E$. We investigate security of this construction against adversaries who have access to quantum computers.

We first present a key recovery attack in $|K|^{r/(r+1)}$ complexity. The attack relies on a clever application of a claw-finding algorithm and testifies of a significant gap with the classical setting where $2$ pseudorandom permutations already yield optimal security.

Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to $\min\{|K|^{1/2}/r,|X|\}$ queries. The analysis relies on a generic characterization of classical and quantum distinguishers and a universal transformation of classical security proofs to the quantum setting that is of general interest.

We first present a key recovery attack in $|K|^{r/(r+1)}$ complexity. The attack relies on a clever application of a claw-finding algorithm and testifies of a significant gap with the classical setting where $2$ pseudorandom permutations already yield optimal security.

Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to $\min\{|K|^{1/2}/r,|X|\}$ queries. The analysis relies on a generic characterization of classical and quantum distinguishers and a universal transformation of classical security proofs to the quantum setting that is of general interest.

ePrint Report
White-Box Cryptography: Don't Forget About Grey Box Attacks
Joppe W. Bos, Charles Hubain, Wil Michiels, Cristofaro Mune, Eloi Sanfelix Gonzalez, Philippe Teuwen

Despite the fact that all current scientific white-box approaches of standardized cryptographic primitives have been publicly broken, these attacks require knowledge of the internal data representation used by the implementation. In practice, the level of implementation knowledge required is only attainable through significant reverse engineering efforts.

In this paper we describe new approaches to assess the security of white-box implementations which require neither knowledge about the look-up tables used nor expensive reverse engineering effort. We introduce the differential computation analysis (DCA) attack which is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community. Similarly, the differential fault analysis (DFA) attack is the software counterpart of fault-injection attacks on cryptographic hardware.

For DCA, we developed plugins to widely available dynamic binary instrumentation (DBI) frameworks to produce software execution traces which contain information about the memory addresses being accessed. For the DFA attack, we developed modified emulators and plugins for DBI frameworks that allow injecting faults at selected moments within the execution of the encryption or decryption process as well as a framework to automate static fault injection.

To illustrate the effectiveness, we show how DCA and DFA can extract the secret key from numerous publicly available non-commercial white-box implementations of standardized cryptographic algorithms. These approaches allow one to extract the secret key material from white-box implementations significantly faster and without specific knowledge of the white-box design in an automated or semi-automated manner.

In this paper we describe new approaches to assess the security of white-box implementations which require neither knowledge about the look-up tables used nor expensive reverse engineering effort. We introduce the differential computation analysis (DCA) attack which is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community. Similarly, the differential fault analysis (DFA) attack is the software counterpart of fault-injection attacks on cryptographic hardware.

For DCA, we developed plugins to widely available dynamic binary instrumentation (DBI) frameworks to produce software execution traces which contain information about the memory addresses being accessed. For the DFA attack, we developed modified emulators and plugins for DBI frameworks that allow injecting faults at selected moments within the execution of the encryption or decryption process as well as a framework to automate static fault injection.

To illustrate the effectiveness, we show how DCA and DFA can extract the secret key from numerous publicly available non-commercial white-box implementations of standardized cryptographic algorithms. These approaches allow one to extract the secret key material from white-box implementations significantly faster and without specific knowledge of the white-box design in an automated or semi-automated manner.

ePrint Report
Tightly Secure Ring-LWE Based Key Encapsulation with Short Ciphertexts
Martin R. Albrecht, Emmanuela Orsini, Kenneth G. Paterson, Guy Peer, Nigel P. Smart

We provide a tight security proof for an IND-CCA Ring-LWE based Key Encapsulation Mechanism that is derived from a generic construction of Dent (IMA Cryptography and Coding, 2003). Such a tight reduction is not known for the generic construction. The resulting scheme has shorter ciphertexts than can be achieved with other generic constructions of Dent or by using the well-known Fujisaki-Okamoto constructions (PKC 1999, Crypto 1999). Our tight security proof is obtained by reducing to the security of the underlying Ring-LWE problem, avoiding an intermediate reduction to a CPA-secure encryption scheme. The proof technique maybe of interest for other schemes based on LWE and Ring-LWE.

ePrint Report
Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease
San Ling, Khoa Nguyen, Huaxiong Wang, Yanhong Xu

Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), eight other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, most of the existing constructions work only in the static setting where the group population is fixed at the setup phase. The only two exceptions are the schemes by Langlois et al. (PKC 2014) that handles user revocations (but new users cannot join), and by Libert et al. (Asiacrypt 2016) which addresses the orthogonal problem of dynamic user enrollments (but users cannot be revoked).

In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al.'s fully static construction (Eurocrypt 2016) - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former. The scheme satisfies the strong security requirements of Bootle et al.'s model (ACNS 2016), under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions.

In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al.'s fully static construction (Eurocrypt 2016) - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former. The scheme satisfies the strong security requirements of Bootle et al.'s model (ACNS 2016), under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions.

ePrint Report
A low-resource quantum factoring algorithm
Daniel J. Bernstein, Jean-François Biasse, Michele Mosca

In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just $(\log N)^{2/3+o(1)}$ qubits to factor an integer $N$ in time $L^{q+o(1)}$ where $L = \exp((\log N)^{1/3}(\log\log N)^{2/3})$ and $q=\sqrt[3]{8/3}\approx 1.387$. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is $L^{p+o(1)}$ where $p>1.9$. The new time complexity is asymptotically worse than Shor's algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.

This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today's computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.

ePrint Report
The Montgomery ladder on binary elliptic curves
Thomaz Oliveira, Julio López, Francisco Rodrı́guez-Henrı́quez

In this survey paper we present a careful analysis of the Montgomery ladder procedure applied to the computation of the constant-time point multiplication operation on elliptic curves defined over binary extension fields. We give a general view of the main improvements and formula derivations that several researchers have contributed across the years, since the publication of Peter Lawrence Montgomery seminal work in 1987. We also report a fast software implementation of the Montgomery ladder applied on a Galbraith-Lin-Scott (GLS) binary elliptic curve that offers a security level close to 128 bits. Using our software we can execute the ephemeral Diffie-Hellman protocol in just 95,702 clock cycles when implemented on an Intel Skylake machine running at 4 GHz.

ePrint Report
LMS vs XMSS: A comparison of the Stateful Hash-Based Signature Proposed Standards
Panos Kampanakis, Scott Fluhrer

Quantum computing poses challenges to public key signature schemes as we know them today. LMS and XMSS are two hash based signature schemes that have been proposed in the IETF as quantum secure. Both schemes are based on well-studied hash trees, but their similarities and differences have not yet been discussed. In this work, we attempt to compare the two standards. We compare their security assumptions and quantify their signature and public key sizes. We also address the computation overhead they introduce. Our goal is to provide a clear understanding of the schemes' similarities and differences for implementers and protocol designers to be able to make a decision as to which standard to chose.

ePrint Report
Removal Attacks on Logic Locking and Camouflaging Techniques
Muhammad Yasin, Bodhisatwa Mazumdar, Ozugr Sinanoglu, Jeyavijayan Rajendran

With the adoption of a globalized and distributed IC design flow, IP piracy, reverse engineering, and counterfeiting threats are becoming more prevalent. Logic obfuscation techniques including logic locking and IC camouflaging have been developed to address these emergent challenges. A major challenge for logic locking and camouflaging techniques is to resist Boolean satisfiability (SAT) based attacks that can circumvent state-of-the-art solutions within minutes. Over the past year, multiple SAT attack resilient solutions such as Anti-SAT and AND-tree insertion (ATI) have been presented. In this paper, we perform a security analysis of these countermeasures and show that they leave structural traces behind in their attempts to thwart the SAT attack. We present two attacks, namely “signal probability skew” (SPS) attack and “sensitization guided SAT” (SGS) attack, that can break Anti-SAT and ATI, respectively, within minutes.

Event Calendar
: The First NIST Post-Quantum Cryptography (PQC) Standardization Conference
Fort Lauderdale, USA, 12 April - 13 April 2018

Event date: 12 April to 13 April 2018

Submission deadline: 30 November 2017

Submission deadline: 30 November 2017

Event Calendar
CT-RSA 2018: CT-RSA 2018
San Francisco, United States of America, 16 April - 20 April 2018

Event date: 16 April to 20 April 2018

Submission deadline: 1 October 2017

Notification: 10 December 2017

Submission deadline: 1 October 2017

Notification: 10 December 2017

24
April
2017

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 up to five years at the Department of Computer Science and Engineering, within the group of Prof. Katerina Mitrokotsa who is doing research in cryptographic protocols that guarantee reliable authentication, privacy-preservation and verifiable delegation of computation. The topic of this project is focusing on investigating security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The overall aim of the PhD position will be to design and evaluate cryptographically reliable and privacy-preserving authentication and verifiable delegation of computation protocols. The research shall also consider the case where multiple clients outsource jointly computations to untrusted cloud servers. Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial. Mathematical maturity is essential.

The PhD student will be supervised by Prof. Katerina Mitrokotsa: http://www.cse.chalmers.se/~aikmitr/

Full-time temporary employment. PhD student positions are limited to five years. Starting salary is 27,835 SEK a month before tax. The position is intended to start in Sept 2017.

**Closing date for applications:** 31 May 2017

**Contact:** Katerina Mitrokotsa, Associate Professor, Chalmers Univ. of Technology, *aikmitr (at) chalmers.se*

**More information:** http://www.cse.chalmers.se/~aikmitr/PhD-Cryptography-Cloud.html