International Association
for Cryptologic Research

Despite fifteen years of research on the round complexity of non-malleable commitments, their exact round complexity has remained open. In particular, the goal of achieving non-malleable commitment protocols with only two messages has been especially elusive. We resolve this question, obtaining the following positive results from standard sub-exponential assumptions.

- We construct two-message public-coin non-malleable commitments with respect to commitment, assuming sub-exponentially hard one-way permutations, sub-exponential ZAPs, and sub-exponentially hard DDH.

- We obtain two-message private-coin non-malleable commitments with respect to commitment, assuming only sub-exponentially hard DDH or QR or Nth-residuosity.

- We also bootstrap the above protocols (under the same assumptions) to obtain bounded-concurrent non-malleability while preserving round complexity.

In order to obtain our results, we develop a new two-round black-box extraction technique that is based on two-party secure computation, and may be of independent interest.

Logic encryption is a hardware security technique that uses extra key inputs to lock a given combinational circuit. A recent study by Subramanyan et al. shows that all existing logic encryption techniques can be successfully attacked. As a countermeasure, SARLock was proposed to enhance the security of existing logic encryptions. In this paper, we re- evaluate the security of these approaches. A SAT-based at- tack called Double DIP is proposed and shown to success- fully defeat SARLock-enhanced encryptions.

Time-Memory-Data tradeoff attacks (TMD-attacks) like those of Babbage, Biryukov and Shamir, and Dunkelman and Keller reduce the security level of keystream generator based-stream ciphers to $L/2$, where $L$ denotes the inner state length. This is one of the reasons why stream ciphers like Trivium and Grain use a session key length $n$ of at most $L/2$. In this paper, we deal with the question if this small-key-large-state design principle really provides the maximal possible security of $\min\{n,\frac{L}{2}\}$ w.r.t. to TMD-attacks, or if it opens the door for new TMD-attack approaches, which possibly allow to discover a secret inner state and/or the secret session key with cost essentially lower than $2^n$. We give an answer by analyzing the security of stream ciphers like Trivium and Grain w.r.t. generic TMD-attacks in an appropriate random oracle model. We show that each TMD-attacker with TMD-costs bounded by $M$ can only achieve an advantage of $\min\left\{\frac{2M}{2^n-M},\frac{(8L-4)M^2}{2^L-(4L-2)M^2}\right\}$ for distinguishing a truly random bitstream from a pseudorandom bitstream generated by the stream cipher. This lower bound matches the security upper bounds defined by exhaustive key search and the classical TMD-attacks mentioned above.

We study the security of symmetric primitives under the incorrect usage of keys. Roughly speaking, a key-robust scheme does not output ciphertexts/tags that are valid with respect to distinct keys. Key-robustness is a notion that is often tacitly expected/assumed in protocol design — as is the case with anonymous auction, oblivious transfer, or public-key encryption. We formalize simple, yet strong definitions of key robustness for authenticated-encryption, message-authentication codes and PRFs. We show standard notions (such as AE or PRF security) guarantee a basic level of key-robustness under honestly generated keys, but fail to imply key-robustness under adversarially generated (or known) keys. We show robust encryption and MACs compose well through generic composition, and identify robust PRFs as the main primitive used in building robust schemes. Standard hash functions are expected to satisfy key-robustness and PRF security, and hence suffice for practical instantiations. We however provide further theoretical justifications (in the standard model) by constructing robust PRFs from (left-and-right) collision-resistant PRGs.

Evaluation of side channel leakage for the embedded crypto systems requires sound leakage detection procedures. We relate the test vector leakage assessment (TVLA) procedure to the statistical minimum p-value (mini-p) procedure, and propose a sound method of deciding leakage existence in the statistical hypothesis setting. To improve detection, an advanced statistical procedure Higher Criticism (HC) is applied. The detection of leakage existence and the identification of exploitable leakage are separated when there are multiple leakage points. For leakage detection, the HC-based procedure is shown to be optimal in that, for a given number of traces with given length, it detects existence of leakage at the signal level as low as possibly detectable by any statistical procedure. Numerical studies show that the HC-based procedure perform as well as the mini-p based procedure when leakage signals are very sparse, and can improve the leakage detection significantly when there are multiple leakages.

Midori is a family of lightweight block cipher proposed by Banik et al. in ASIACRYPT 2015 and it is optimized with respect to the energy consumed by the circuit per bit in encryption or decryption operation. Midori is based on the Substitution-Permutation Network, which has two variants according to the state sizes, i.e. Midori64 and Midori128. It attracted a lot of attention of cryptanalyst since its release. For Midori64, the first meet-in-the-middle attack was proposed by Lin and Wu, which was published on the ToSC 2017 recently. The first impossible differential attack of Midori64 was presented by Chen et al. and Dong gave the first related-key differential attack. Guo et al. introduced an invariant space attack against full-round Midori64 in weak key setting, which was published in ToSC 2017 recently. However, for Midori128, there are only one impossible differential cryptanalysis result proposed by Chen et al. against 10-round reduced Midori128 and one related-key result by Gerault et al. in INDOCRYPT 2016. In this paper, we present a new impossible differential attack on Midori128 by using a new impossible differential proposed by Sasaki et al., we achieve 10-round impossible differential attack with the time complexity $2^{111}$ and 11-round impossible differential attack with the time complexity $2^{126.94}$ finally. This is the best single-key cryptanalytic result of Midori128 as far as we know. We should point out the our attacks do not threaten the security of full-round Midori128.

The Department of Computer Science and Mathematics at Universitat Rovira i Virgili (www.urv.cat) offers a PhD scholarship for research in cryptography. The research will be focussed on secret sharing schemes and information-theoretic cryptography, and it will be advised by Oriol Farràs.

The scholarship is a Martí Franquès - COFUND grant, which receives funding from a Marie Sk?odowska-Curie Horizon 2020 research and innovation programme (http://www.urv.cat/en/research/support/programmes/marti-franques/cofund/). This research project is called \"Characterizing access structures with efficient secret sharing schemes\" (2017MFP-COFUND-12). The gross anual salary is 26443.80 €, and there is also an anual budget of 6500 € for travels, research and training.

The submission deadline is April 15, the official notification of winners is on July 31, and the fellowship will start on October 1.

If you are interested in it, send an email to oriol.farras (at) urv.cat and start the submission process (http://www.urv.cat/en/research/support/programmes/marti-franques/cofund/submission/).

Closing date for applications: 15 April 2017

Contact: Oriol Farràs (oriol.farras (at) urv.cat, https://sites.google.com/site/oriolfv/)

Post-doctoral fellow position in Department of Computer and Information Communications Engineering at Hongik University in the field of cryptography or information security. Applicants should have their Ph.D degrees within four years as of March 31, 2017. Please email with subject ‘Postdoc position’ by attaching statement of research, CV, recommendation letters, and copies of 3 most significant publications to sohwang (at) hongik.ac.kr

Closing date for applications: 20 April 2017

Contact: Professor Seong Oun Hwang at sohwang (at) hongik.ac.kr

More information: http://shinan.hongik.ac.kr/~sohwang/index_e.htm

We report on our implementation of a new Gaussian sampling algorithm for lattice trapdoors. Lattice trapdoors are used in a wide array of lattice-based cryptographic schemes including digital signatures, attributed-based encryption, program obfuscation and others. Our implementation provides Gaussian sampling for trapdoor lattices with prime moduli, and supports both single- and multi-threaded execution. We experimentally evaluate our implementation through its use in the GPV hash-and-sign digital signature scheme as a benchmark. We compare our design and implementation with prior work reported in the literature. Evaluation shows that our implementation 1) has smaller space requirements and faster runtime, 2) does not require multi-precision floating-point arithmetic, and 3) can be used for a broader range of cryptographic primitives than previous implementations.

Side-channel analysis attacks, particularly power analysis attacks, have become one of the major threats, that hardware designers have to deal with. To defeat them, the majority of the known concepts are based on either masking, hiding, or rekeying (or a combination of them). This work deals with a hiding scheme, more precisely a power-equalization technique which is ideally supposed to make the amount of power consumption of the device independent of its processed data. We propose and practically evaluate a novel construction dedicated to Xilinx FPGAs, which rules out the state of the art with respect to the achieved security level and the resource overhead.

Applying random and uniform masks to the processed intermediate values of cryptographic algorithms is arguably the most common countermeasure to thwart side-channel analysis attacks. So-called masking schemes exist in various shapes but are mostly used to prevent side-channel leakages up to a certain statistical order. Thus, to learn any information about the key-involving computations a side-channel adversary has to estimate the higher-order statistical moments of the leakage distributions. However, the complexity of this approach increases exponentially with the statistical order to be estimated and the precision of the estimation suffers from an enormous sensitivity to the noise level. In this work we present an alternative procedure to exploit higher-order leakages which captivates by its simplicity and effectiveness. Our approach, which focuses on (but is not limited to) univariate leakages of hardware masking schemes, is based on categorizing the power traces according to the distribution of leakage points. In particular, at each sample point an individual subset of traces is considered to mount ordinary first-order attacks. We present the theoretical concept of our approach based on simulation traces and examine its efficiency on noisy real-world measurements taken from a first-order secure threshold implementation of the block cipher PRESENT-80, implemented on a 150nm CMOS ASIC prototype chip. Our analyses verify that the proposed technique is indeed a worthy alternative to conventional higher-order attacks and suggest that it might be able to relax the sensitivity of higher-order evaluations to the noise level.

We investigate the post-quantum security of hash functions based on the sponge construction. A crucial property for hash functions in the post-quantum setting is the collapsing property (a strengthening of collision-resistance). We show that the sponge construction is collapsing (and in consequence quantum collision-resistant) under suitable assumptions about the underlying block function. In particular, if the block function is a random function or a (non-invertible) random permutation, the sponge construction is collapsing.

We design a novel, communication-efficient, failure-robust protocol for secure aggregation of high-dimensional data. Our protocol allows a server to compute the sum of large, user-held data vectors from mobile devices in a secure manner (i.e. without learning each user's individual contribution), and can be used, for example, in a federated learning setting, to aggregate user-provided model updates for a deep neural network. We prove the security of our protocol in the honest-but-curious and malicious settings, and show that security is maintained even if an arbitrarily chosen subset of users drop out at any time. We evaluate the efficiency of our protocol and show, by complexity analysis and a concrete implementation, that its runtime and communication overhead remain low even on large data sets and client pools. For 16-bit input values, our protocol offers $1.73\times$ communication expansion for $2^{10}$ users and $2^{20}$-dimensional vectors, and $1.98\times$ expansion for $2^{14}$ users and $2^{24}$-dimensional vectors over sending data in the clear.

For a linear function $f$, a vector $\mathbf x$ with small coefficients, and a vector $y=f(\mathbf x)$, we would like to be able to give a zero-knowledge proof for the knowledge of an $\mathbf x'$ with small coefficients that satisfies $f(\mathbf x')=y$. This is a common scenario in lattice-based cryptography, and there is currently no satisfactory solution for this problem. All known protocols are built via the repetition a basic protocol that only has constant ($1/2$ or $2/3$) soundness error. This implies that the communication complexity of the final protocol will be at least a factor of $k$ larger than that of the basic one, where $k$ is the security parameter.

One can do better if one considers simultaneously proving the knowledge of many instances of the above linear equation. The protocol that has the smallest amortized communication complexity while achieving close-to-optimal slack (i.e. the ratio between the coefficients in the secret and those that can be extracted from the proof) is due to Cramer et al. (Eurocrypt '17) which builds on an earlier work of Baum et al. (Crypto '16). The main downside of this protocol is that the amortization only kicks in when the number of equations is rather large -- $4k^2$. This means that for $k=128$, it is only truly optimal when one has more than $2^{16}$ equations to prove. The aforementioned work of Cramer et al. also shows how to achieve a protocol requiring $o(k^2)$ samples, but it is only applicable for much larger values of $k$ and the number of required samples ends up being larger than $2^{16}$.

The main result of our work is reducing the concrete minimal number of equations required for the amortization, while keeping the communication complexity almost unchanged. The cost of this is an increase in the running time of the zero-knowledge proof. More specifically, we show that one can decrease the required number of equations by a factor of $\Omega(\log^2{\alpha})$ at the cost of increasing the running time by a factor of $\Omega(\alpha)$. For example, increasing the running time by a factor of $8$ allows us to decrease the required number of samples from $66000$ to $4500$ -- a factor of $14$. As a side benefit, the slack of our protocol decreases by a factor of $\log{\alpha}$ as well.

We also show that in the case that $f$ is a function over the polynomial ring $\mathbb Z[X]/(X^d+1)$ and we would like to give a proof of knowledge of an $\mathbf x'$ with small coefficients such that $f(\mathbf x')=2y$, then the number of samples needed for amortization is even lower. Without any trade-offs in the running time, our algorithm requires around $2000$ samples, and for the same factor $8$ increase in the running time, the requirement goes down to $850$.

We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parametrizable.

In our signature constructions, the public key is an image y=f(x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX'16) in constructing an efficient sigma protocol for statements over general circuits. We improve this sigma protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes.

We consider two possibilities for making the proof non-interactive, the Fiat-Shamir transform, and Unruh's transform (EUROCRYPT'12,'15,'16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh's transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis.

We implement and benchmark both approaches and explore the possible choice of f, taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC.

The early registration deadline for EUROCRYPT 2017 and its affiliated workshops is approaching. After Friday, March 31st, 2017, prices will increase by US$100.

You can register online at https://secure.iacr.org/conferences/eurocrypt2017/register/

There are two available registration options:

1. If you are registering to attend EUROCRYPT 2017, regardless of whether you are attending any additional workshops, please select option #1 of the registration form.
2. If you are registering to attend the workshops but not attending EUROCRYPT 2017, please select option #2 of the registration form.

EUROCRYPT 2017 will be held in the heart of Paris from April 30th to May 4th at Maison de la Mutualité, within 5-min walking distance to Notre-Dame, Sainte-Chapelle, and many other attractions. A detailed program can be found at https://eurocrypt2017.di.ens.fr/program.html

The program includes invited talks by:

• Gilles Barthe (IMDEA Software Institute, Spain) on Advances in computer-aided cryptography
• Nigel Smart (University of Bristol) on Living Between the Ideal and Real Worlds

In addition to the conference, this edition of EUROCRYPT has a large number of affiliated and co-located workshops jointly organized with EuroS&P 2017. This includes 9 workshops on Saturday, April 29th; and 9 on Sunday, April 30th. For more information, please refer to https://eurocrypt2017.di.ens.fr/acceptedEvents.html

The University of York is one of the UK\'s leading higher education institutions and a member of the prestigious Russell Group of universities. The Department is renowned internationally for its high impact research, combined with a dedication to high-quality teaching and excellent student satisfaction, as well as strong industrial links, making us one of the UK\'s top Computer Science departments.

The Role

We welcome applications from researchers with a track record as an international leader in Cybersecurity, with some emphasis on pragmatic aspects of Cybersecurity. You will actively engage and collaborate with colleagues leading the development of Cybersecurity research and teaching. You\'ll develop relationships across the wider University and beyond, to help build a distinctive and positive working environment that emphasises excellence.

Salary will be commensurate with experience on the professorial scale: current minimum £61,539 a year

Interviews will be held in York on: 25th May 2017

Why York?

We are a dynamic, research-intensive university and have experienced significant growth over the past ten years, securing national and international recognition for our academic excellence. Our attractive landscaped campus has seen significant development which will continue as the University continues to develop. We are recognised consistently for our family-friendly policies and proud of our Athena SWAN Award.

Closing date for applications: 10 April 2017

Contact: Informal enquiries may be directed to Professor Neil Audsley (neil.audsley (at) york.ac.uk)

More information: https://jobs.york.ac.uk/wd/plsql/wd_portal.show_job?p_web_site_id=3885&p_web_page_id=305603

The rise of decentralized networks, such as Tor and cryptocurrencies like Bitcoin, has enabled numerous applications, and these technologies offer the potential to enable many more. One could also argue, however, that they have enabled new types of crime. For example, the number of underground markets selling drugs and other illicit goods, such as Silk Road, has grown enormously after the introduction of Bitcoin (and they also rely on the use of Tor). Attacks such as ransomware also seem to some extent impossible to carry out without the use of these technologies.

In order to remove any regulatory obstacles to the adoption of the positive applications of these technologies, it is therefore important to address these negative applications and convince regulators they can be dealt with appropriately. To achieve this, we will develop (1) new heuristics for identifying relationships in a cryptocurrency ecosystem; (2) tools for collecting and analyzing data from underground markets; and (3) new techniques to ensure that honest users continue to maintain their privacy. Eventually, these will all be incorporated into a microservice architecture that provides a forensic tool.

This project is funded by an EU H2020 grant, and will be carried out with partners across Europe. The ideal candidate will have a strong degree in Computer Science, Mathematics, or a related MSc course, and some proficiency with cryptography, machine learning, and/or data analytics.

Closing date for applications: 1 June 2017

Contact: Sarah Meiklejohn

More information: https://www.prism.ucl.ac.uk/#!/?project=229

Invariant subspace attack is a novel cryptanalytic technique which breaks several recently proposed lightweight block ciphers. In this paper, we propose a new method to bound the dimension of some invariant subspaces in a class of lightweight block ciphers which have a similar structure as the AES but with 4-bit Sboxes. With assumptions on the diffusion layer, the dimension of any invariant subspaces is at most 32 when the inputs into each Sboxes are linearly independent. The observation brings new insights about the invariant subspace attack, as well as lightweight countermeasures to enhance the resistance against it.

In the study of cryptography in $\text{NC}^0$, it was previously known that Goldreich's candidate pseudorandom generator (PRG) is insecure when instantiated with a predicate $P$ in $4$ or fewer variables, if one wants to achieve polynomial stretch (that is, stretching $n$ bits to $n^{1+\epsilon}$ bits for some constant $\epsilon>0$). The current standard candidate predicate for this setting is the ``tri-sum-and'' predicate $\text{TSA}(x) = \text{XOR}_3 \oplus \text{AND}_2(x) = x_1\oplus x_2\oplus x_3\oplus x_4x_5$, yielding a candidate PRG of locality $5$. Moreover, Goldreich's PRG, when instantiated with TSA as the predicate, is known to be secure against several families of attacks, including $\mathbb F_2$-linear attacks and attacks using SDP hierarchies such as the Lasserre/Parrilo sum-of-squares hierarchy.

However, it was previously unknown if $\text{TSA}$ is an ``optimal'' predicate according to other complexity measures: in particular, decision tree (DT-)complexity (i.e., the smallest depth of a binary decision tree computing $P$) and $\mathbb Q$-degree (i.e., the degree of $P$ as a polynomial over $\mathbb Q$), which are important measures of complexity in cryptographic applications such as the construction of an indistinguishability obfuscation scheme. In this work, we ask: Can Goldreich's PRG be instantiated with a predicate with DT-complexity or $\mathbb Q$-degree less than $5$?

We show that this is indeed possible: we give a candidate predicate for Goldreich's PRG with DT-complexity $4$ and $\mathbb Q$-degree $3$; in particular, this candidate PRG therefore has the property that every output bit is a degree 3 polynomial in its input. Moreover, Goldreich's PRG instantiated with our predicate has security properties similar to what is known for $\text{TSA}$, namely security against $\mathbb F_2$-linear attacks and security against attacks from SDP hierarchies such as the Lasserre/Parrilo sum-of-squares hierarchy.

We also show that all predicates with either DT-complexity less than $4$ or $\mathbb Q$-degree less than $3$ yield insecure PRGs, so our candidate predicate simultaneously achieves the best possible locality, DT-complexity, $\mathbb Q$-degree, and $\mathbb F_2$-degree according to all known attacks.