International Association
for Cryptologic Research

The keyed duplex construction was introduced by Bertoni et al.(SAC 2011) and recently generalized to full-state absorption by Mennink et al.(ASIACRYPT 2015). We present a generalization of the full-state keyed duplex that natively supports multiple instances by design, and perform a security analysis that improves over that of Mennink et al. in terms of a more modular security analysis and a stronger and more adaptive security bound. Via the introduction of an additional parameter to the analysis, our bound demonstrates a significant security improvement in case of nonce-respecting adversaries. Furthermore, by supporting multiple instances by design, instead of adapting the security model to it, we manage to derive a security bound that is largely independent of the number of instances.

Proof-of-work (PoW) schemes are cryptographic primitives with numerous applications, and in particular, they play a crucial role in maintaining consensus in cryptocurrency networks. Ideally, a cryptocurrency PoW scheme should have several desired properties, including efficient verification on one hand, and high memory consumption of the prover's algorithm on the other hand, making the scheme less attractive for implementation on dedicated hardware.

At the USENIX Security Symposium 2016, Biryukov and Khovratovich presented a new promising PoW scheme called MTP (Merkle Tree Proof) that achieves essentially all desired PoW properties. As a result, MTP has received substantial attention from the cryptocurrency community. The scheme uses a Merkle hash tree construction over a large array of blocks computed by a memory consuming (memory-hard) function. Despite the fact that only a small fraction of the memory is verified by the efficient verification algorithm, the designers claim that a cheating prover that uses a small amount of memory will suffer from a significant computational penalty.

In this paper, we devise a sub-linear computation-memory tradeoff attack on MTP. We apply our attack to the concrete instance proposed by the designers which uses the memory-hard function Argon2d and computes a proof by allocating 2 gigabytes of memory. The attack computes arbitrary malicious proofs using less than a megabyte of memory (about 1/3000 of the honest prover's memory) at a relatively mild penalty of 170 in computation. This is more than 55,000 times faster than what is claimed by the designers. The attack requires a one-time precomputation step of complexity $2^{64}$, but its online cost is only increased by a factor which is less than 2 when spending $2^{48}$ precomputation time.

The main idea of the attack is to exploit the fact that Argon2d accesses its memory in a way which is determined by its previous computations. This allows to inject a small fraction of carefully selected memory blocks that manipulate Argon2d's memory access patterns, significantly weakening its memory-hardness.

We examine how two parallel modes of operation for Authenticated Encryption (namely CTR+PMAC and OTR mode) work when evaluated in a multi-party computation engine. These two modes are selected because they suit the PRFs examined in previous works. In particular the modes are highly parallel, and do not require evaluation of the inverse of the underlying PRF. In order to use these modes one needs to convert them from their original instantiation of being defined on binary blocks of data, to working on elememts in a large prime finite field. The latter fitting the use case of many secret-sharing based MPC engines. In doing this conversion we examine the associated security proofs of PMAC and OTR, and show that they carry over to this new setting.

We study the security of symmetric encryption schemes in settings with multiple users and realistic adversaries who can adaptively corrupt encryption keys. To avoid confinement to any particular definitional paradigm, we propose a general framework for multi-key security definitions. By appropriate settings of the parameters of the framework, we obtain multi-key variants of many of the existing single-key security notions. This framework is instrumental in establishing our main results.

We show that for all single-key secure encryption schemes satisfying a minimal key uniqueness assumption and almost any instantiation of our general multi-key security notion, any reasonable reduction from the multi-key game to a standard single-key game necessarily incurs a linear loss in the number of keys. We prove this result for all three classical single-key security notions capturing confidentiality, authenticity and the combined authenticated encryption notion.

The University of Luxembourg seeks to hire three outstanding PhD candidates at the Computer Science and Communications Research Unit. The positions are part of the FNR PRIDE doctoral training programme on Security and Privacy for System Protection. The University offers highly competitive salaries and is an equal opportunity employer. You will work in an exciting international environment and will have the opportunity to participate in the development of a dynamic and growing centre.

Successful candidates will participate in the activities of the Security and Trust of Software Systems (SaToSS) research group led by Prof. Dr. Sjouke Mauw. The group is focused on formalising and applying formal reasoning to real-world security problems and trust issues. We offer three different research projects:

- Multi-party Authentication Protocols. Further information and submission guidelines can be found at: https://goo.gl/yqPo6q

- Adaptive Cyber-defenses. Further information and submission guidelines can be found at: https://goo.gl/FlMo5E

- Security and Privacy in Social Networks. Further information and submission guidelines can be found at: https://goo.gl/TpZ3S7

Applicants can apply to more than one research project. Each application will be considered on receipt, therefore applying before the deadline is encouraged.

Closing date for applications: 31 August 2017

Contact: Prof. Sjouke Mauw

Université du Luxembourg

Faculté des Sciences, de la Technologie et de la Communication (FSTC)

Maison du Nombre

6, avenue de la Fonte

L-4364 Esch-sur-Alzette

Telephone: (+352) 466 644 5480

Email: sjouke.mauw (at) uni.lu

Guo et al. recently presented a reaction attack against the QC-MDPC McEliece cryptosystem. Their attack is based on the observation that when a bit-flipping decoding algorithm is used in the QC-MDPC McEliece, then there exists a dependence between the secret matrix $H$ and the failure probability of the bit-flipping algorithm. This dependence can be exploited to reveal the matrix $H$ which constitutes the private key in the cryptosystem. It was conjectured that such dependence is present even when a soft-decision decoding algorithm is used instead of a bit-flipping algorithm.

This paper shows that a similar dependence between the secret matrix $H$ and the failure probability of a decoding algorithm is also present in the QC-LDPC McEliece cryptosystem. Unlike QC-MDPC McEliece, the secret key in QC-LDPC McEliece also contains matrices $S$ and $Q$ in addition to the matrix $H$. We observe that there also exists a dependence between the failure probability and the matrix $Q$. We show that these dependences leak enough information to allow an attacker to construct a sparse parity-check matrix for the public code. This parity-check matrix can then be used for decrypting ciphertexts.

We tested the attack on an implementation of the QC-LDPC McEliece using a soft-decision decoding algorithm. Thus we also confirmed that soft-decision decoding algorithms can be vulnerable to leaking information about the secret key.

Fuzzy extractors have been proposed in 2004 by Dodis et al. as a secure way to generate cryptographic keys from noisy sources. Originally, biometrics were the main motivation for fuzzy extractors but in recent years their practical relevance stems mainly from their use in secure key generation based on Physical Unclonable Functions (PUFs). Fuzzy extractors are provably secure against passive attackers, i.e., attackers that can observe the helper data. A year later, robust fuzzy extractors were introduced which are also provably secure against an active attacker, i.e., attackers that can manipulate the helper data. Hence, the problem of how to build provably secure robust fuzzy extractors appears to have been solved a long time ago.

However, in this paper we show that from a practical perspective the problem of building a provably secure fuzzy extractor is actually not solved yet. The originally proposed robust fuzzy extractors based on BCH codes either do not have the required error-correction rates for practical applications or violate the parameters in the security proof. Since no helper data manipulation attacks on linear codes are known which work in the robust fuzzy extractor construction, it might be tempting to simply ignore the parameters of the proof. However, we present new helper data manipulation attacks on several decoding strategies for linear codes which set a key as opposed to recovering the key. These new attacks show that helper data manipulation attacks are indeed feasible against such constructions if the parameters in the proof are ignored. Robust fuzzy extractors therefore need to be revisited by both engineers and cryptographers to solve the problem of building both provably secure as well as practical robust fuzzy extractors.

In both information theoretic and computationally secure Multi-Party Computation (MPC) protocols the parties are usually assumed to be connected by a complete network of, respectively, secure or authenticated channels. Taking inspiration from a recent, highly efficient, 1-out-of-3 computationally secure MPC protocol of Araki et al, we show how to perform computationally secure MPC for an arbitrary $Q^2$ access structure over an incomplete network. Our tool is to combine the practical techniques of Araki with the information theoretic approach of Maurer for arbitrary $Q^2$ structures. We present both passive and actively secure (with abort) variants of our protocol. In all cases we require less communication channels than Maurer's protocol, at the expense of requiring pre-shared secret keys for Pseudo-Random Functions (PRFs). By shedding light on the theoretical underpinnings of the recent protocol of Araki et al. we hope that our work may result in future highly communication-efficient protocols for other access structures.

Event date: 10 January to 12 January 2018
Submission deadline: 5 October 2017
Notification: 4 December 2017

In this work, we introduce a novel technique for secure computation over large inputs. Specifically, we provide a new oblivious transfer (OT) protocol with a laconic receiver. Laconic OT allows a receiver to commit to a large input $D$ (of length $M$) via a short message. Subsequently, a single short message by a sender allows the receiver to learn $m_{D[L]}$, where the messages $m_0, m_1$ and the location $L \in [M]$ are dynamically chosen by the sender. All prior constructions of OT required the receiver's outgoing message to grow with $D$.

Our key contribution is an instantiation of this primitive based on the Decisional Diffie-Hellman (DDH) assumption in the common reference string (CRS) model. The technical core of this construction is a novel use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems. Next, we show applications of laconic OT to non-interactive secure computation on large inputs and multi-hop homomorphic encryption for RAM programs.

In the search for post-quantum secure alternatives to RSA and ECC, lattice-based cryptography appears to be an attractive and efficient option. A particularly interesting lattice-based signature scheme is BLISS, offering key and signature sizes in the range of RSA moduli. A range of works on efficient implementations of BLISS is available, and the scheme has seen a first real-world adoption in strongSwan, an IPsec-based VPN suite. In contrast, the implementation-security aspects of BLISS, and lattice-based cryptography in general, are still largely unexplored. At CHES 2016, Groot Bruinderink et al. presented the first side-channel attack on BLISS, thus proving that this topic cannot be neglected. Nevertheless, their attack has some limitations. First, the technique is demonstrated via a proof-of-concept experiment that was not performed under realistic attack settings. Furthermore, the attack does not apply to BLISS-B, an improved variant of BLISS and also the default option in strongSwan. This problem also applies to later works on implementation security of BLISS. In this work, we solve both of the above problems. We present a new side-channel key-recovery algorithm against both the original BLISS and the BLISS-B variant. Our key-recovery algorithm draws on a wide array of techniques, including learning-parity with noise, integer programs, maximimum likelihood tests, and a lattice-basis reduction. With each application of a technique, we reveal additional information on the secret key culminating in a complete key recovery. Finally, we show that cache attacks on post-quantum cryptography are not only possible, but also practical. We mount an asynchronous cache attack on the production-grade BLISS-B implementation of strongSwan. The attack recovers the secret signing key after observing roughly 6000 signature generations.

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant hash functions in which it is difficult to find a t-way collision (i.e., t strings that hash to the same value) although finding (t-1)-way collisions could be easy. We show the following:

- The existence of MCRH follows from the average case hardness of a variant of Entropy Approximation, a problem known to be complete for the class NISZK.

- MCRH imply the existence of constant-round statistically hiding (and computationally binding) commitment schemes.

In addition, we show a blackbox separation of MCRH from any one-way permutation

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. In the unkeyed setting we only require that the size of collisions an adversarial algorithm can find is not much larger than its description size, or non-uniform advice.

We show how to replace collision resistance with multi-collision resistance in several foundational applications, improving on the best known round complexity, obtaining:

- 3-message zero-knowledge arguments for NP.

- 3-message succinct arguments of knowledge for NP.

- 4-message epsilon-zero-knowledge proofs for NP.

- 5-message public-coin zero-knowledge arguments for NP.

Our techniques can also be applied in the keyed setting, at the cost of adding another message. In this case, we weaken the known complexity assumptions for the last three applications, while still matching the state of the art in terms of round complexity.

The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property.

Defined in the standard GOST 28147-89, GOST is a Soviet and Russian government standard symmetric-key block cipher. GOST has the 64-bit block size and a key length of 256 bits. It is a Feistel network of 32 rounds. In 2010, GOST was submitted to ISO 18033 to become a worldwide industrial encryption standard. GOST 28147-89 has also been published as informational RFC 5830 with IETF.

In this paper, we study linear attacks on GOST 28147-89. Prior to us, [Shorin-Jelezniakov-Gabidulin'2001] did some analysis on the linear approximation of GOST without giving any detailed results. [Shorin-Jelezniakov-Gabidulin'2001] claimed that the complexity of the linear attack on GOST is higher than $2^{256}$ after 5 rounds. In our work, we show that this is not true. First, we give the detailed bias analysis on the GOST round function for the first time. We show that the largest bias is $2^{-7}$. Secondly, we proposed the first known linear attacks on GOST. The recent idea of synthetic linear analysis [Lu-Vaudenay-Meier'2012] is then successfully applied to improve the bias for the $r$-round linear approximation of GOST. In summary, our attack on 8-round GOST recovers the key in time $2^{37}$ with $2^{50}$ known plaintexts in the single-key setting. For the 16-round GOST with last 8 rounds using subkeys in reverse order, our distinguishing attack works in time $2^{85}$ using $2^{85}$ known plaintexts, in the plain multiple-key setting without the related-key assumption. That is, the plaintexts can be encrypted by arbitrary number of keys, with each key encrypting arbitrary number of plaintexts, as long as we have a total of $2^{85}$ known plaintexts. For the 32-round GOST with the slightly tweaked key schedule, i.e., assuming last 16 rounds using subkeys in reverse order, our distinguishing attack works in time $2^{170.8}$, given $2^{170.8}$ known plaintexts, in the plain multiple-key setting without the related-key assumption. To the best of our knowledge, our distinguishing attacks are the first known distinguishers on block ciphers in the plain multiple-key setting without the usual related-key assumption. Finally, for the 32-round GOST with the original key schedule, our distinguisher works in time $2^{173.8}$, given $2^{173.8}$ known plaintexts, in the related-key setting. This is the fastest attack known so far, compared with the best attacks [Dinur-Dunkelman-Shamir'2012], [Courtois'2012] on the full 32-round GOST.

A collision resistant hash (CRH) function is one that compresses its input, yet it is hard to find a collision, i.e. a $x_1 \neq x_2$ s.t. $h(x_1) = h(x_2)$. Collision resistant hash functions are one of the more useful cryptographic primitives both in theory and in practice and two prominent applications are in signature schemes and succinct zero-knowledge arguments.

In this work we consider a relaxation of the above requirement that we call Multi-CRH: a function where it is hard to find $x_1, x_2, \ldots, x_k$ which are all distinct, yet $ h(x_1) = h(x_2) = \cdots = h(x_k)$. We show that for some of the major applications of CRH functions it is possible to replace them by the weaker notion of an Multi-CRH, albeit at the price of adding interaction: we show a statistically hiding commitment schemes with succinct interaction (committing to $\mathsf{poly}(n)$ bits requires exchanging $O(n)$ bits) that can be opened locally (without revealing the full string). This in turn can be used to provide succinct arguments for any statement. On the other hand we show black-box separation results from standard CRH and a hierarchy of such Multi-CRHs.

A service may be implemented over several servers, and those servers may become compromised by an attacker, e.g. through software vulnerabilities. When this happens, the service manager will remove the vulnerabilities and re-instate the server. Typically, this will involve regenerating the public key by which clients authenticate the service, and revoking the old one.

This paper presents a scheme which allows a storage service composed of several servers to create a group public key in a decentralised manner, and maintain its security even when such compromises take place. By maintaining keys for a long term, we reduce the reliance on public-key certification. The storage servers periodically update the decryption secrets corresponding to a public key, in such a way that secrets gained by an attacker are rendered useless after an update takes place. An attacker would have to compromise all the servers within a short period lying between two updates in order to fully compromise the system.

The overstretched NTRU problem, which is the NTRU problem with super-polynomial size q in n, is one of the important security foundation of cryptosystems which are recently suggested. Albrecht et al. in Crypto 2016 and Cheon et al. in ANTS 2016 proposed so-called subeld attacks which demonstrate that the overstretched NTRU problems with power-of-two cyclotomic modulus are not secure enough with given parameters in GGH multilinear map and YASHE/LTV fully homomorphic encryption. Unfortunately, they heavily depend on the algebraic structure of the base ring. On the other hand, Kirchner and Fouque presented new cryptanalysis of the overstretched NTRU problem over general modulus in Eurocrypt 2017. They achieve the similar performance compare to previous subeld attacks. In this paper, we present a new algorithm to the overstretched NTRU problem. This algorithm has same complexity to subeld attacks, but threaten more general base ring with poly(n) expansion factor as common in suggested schemes like original GGH, YASHE scheme and NTRU prime rings. Our algorithm implies that cryptosystem related to the overstretched NTRU problem cannot be secure by changing base ring. In addition, we present an extended (trace/norm) subeld attack for the power-of-two cyclotomic modulus. This extended subeld attack has a similar asymptotic complexity to the previous subeld attacks, but with smaller constant in the exponent term.

In this work we propose a multi-start heuristic which aims at minimizing the multiplicative depth of boolean circuits. The multiplicative depth objective is encountered in the field of homomorphic encryption where ciphertext size depends on the number of consecutive multiplications. The heuristic is based on rewrite operators for multiplicative depth-2 paths. Even if the proposed rewrite operators are simple and easy to understand the experimental results show that they are rather powerful. The multiplicative depth of the benchmarked circuits was hugely improved. In average the obtained multiplicative depths were lower by more than 3 times than the initial ones. The proposed rewrite operators are not limited to boolean circuits and can also be used for arithmetic circuits.

The successful candidate will join the CRYPTOLUX group led by Prof. Alex Biryukov. He/she will contribute to a research project on future directions in symmetric cryptography, cryptanalysis and in particular on ultra-lightweight encryption schemes for the Internet of Things.

Closing date for applications: 30 July 2017

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Home#PhD_in_Applied_Cryptography.2C_the_PRIDE_project

Since last year, FSE has moved to a new open-access journal/conference hybrid model. Submitted articles undergo a journal-style reviewing process. Accepted papers are published in Gold Open Access (free availability from day one) by the Ruhr University of Bochum in an issue of the newly established journal IACR Transactions on Symmetric Cryptology.

The next deadline (ToSC 2017, issue 3) is June 1, 2017.

For more information, see the call for Papers or submission server:
General information: https://www.cosic.esat.kuleuven.be/events/fse2018/call-for-papers/
Submission server: http://tosc.iacr.org/index.php/ToSC/pages/view/Submission