International Association
for Cryptologic Research

We discuss the design of symmetric primitives, in particular Pseudo-Random Functions (PRFs) which are suitable for use in a secret-sharing basedMPC system. We consider three different PRFs: the Naor-Reingold PRF, a PRF based on the Legendre symbol, and a specialized block cipher design called MiMC. We present protocols for implementing these PRFs within a secret-sharing based MPC system, and discuss possible applications. We then compare the performance of our protocols. Depending on the application, different PRFs may offer different optimizations and advantages over the classic AES benchmark. Thus, we cannot conclude that there is one optimal PRF to be used in all situations.

This paper aims to move research in the bounded retrieval model (BRM) from theory to practice by considering symmetric (rather than public-key) encryption, giving efficient schemes, and providing security analyses with sharp, concrete bounds. The threat addressed is malware that aims to exfiltrate a user's key. Our schemes aim to thwart this by using an enormously long key, yet paying for this almost exclusively in storage cost, not speed. Our main result is a general-purpose lemma, the subkey prediction lemma, that gives a very good bound on an adversary's ability to guess a (modest length) subkey of a big key, the subkey consisting of the bits of the big key found at random, specified locations, after the adversary has exfiltrated partial information about the big key (e.g., half as many bits as the big key is long). We then use this to design a new kind of key encapsulation mechanism, and, finally, a symmetric encryption scheme. Both are in the random-oracle model. We also give a less efficient standard-model scheme that is based on universal computational extractors (UCE). Finally, we define and achieve hedged BRM symmetric encryption, which provides authenticity in the absence of leakage.

A common countermeasure against side-channel attacks consists in using the masking scheme originally introduced by Ishai, Sahai and Wagner (ISW) at Crypto 2003, and further generalized by Rivain and Prouff at CHES 2010. The countermeasure is provably secure in the probing model, and it was showed by Duc, Dziembowski and Faust at Eurocrypt 2014 that the proof can be extended to the more realistic noisy leakage model. However the extension only applies if the leakage noise $\sigma$ increases at least linearly with the masking order $n$, which is not necessarily possible in practice.

In this paper we investigate the security of an implementation when the previous condition is not satisfied, for example when the masking order $n$ increases for a constant noise $\sigma$. We exhibit two (template) horizontal side-channel attacks against the Rivain-Prouff's secure multiplication scheme and we analyze their efficiency thanks to several simulations and experiments.

Eventually, we describe a variant of Rivain-Prouff's multiplication that is still provably secure in the original ISW model, and also heuristically secure against our new attacks.

The Department of Informatics (www.uib.no/en/ii) has a vacancy for a PhD position within cryptography. The position is for a fixed-term period of 3 years, starting as soon as possible in 2016, and funded by the project “Modern Methods and Tools for Theoretical and Applied Cryptology” (CryptoWorld), awarded by the Research Council of Norway.

About the Department:

The Department has 6 research groups, Algorithms, Bioinformatics, Optimization, Programming Theory, Reliable Communication and Visualization. The Department is ranked first in Norway with respect to the quality of its research by the Research Council of Norway. For more information visit our Web pages: http://www.uib.no/en/ii

About the project/work tasks:

• Focus is on mathematical methods of cryptography, in particular Elliptic Curve Cryptography and algebraic attacks.

• Develop new methods of algebraic cryptanalysis and apply them to modern cryptographic primitives.

• Advance theoretical understanding of the complexity of Elliptic Curve Discrete Logarithm Problem.

The fellowship position is for a fixed term of 3 years. Closing date for application: 30 June 2016

Closing date for applications: 30 June 2016

Contact: Professor Tor Helleseth, Tor.Helleseth (at) uib.no / phone (+47) 55 58 41 60,

Professor Igor Semaev, igor (at) uib.no / phone (+47) 55 58 4279

More information: https://www.jobbnorge.no/en/available-jobs/job/126236/phd-position-in-cryptography?p=1&reset=1

The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009. In this paper, we apply methods intended to reverse-engineer S-Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over $GF(2^3)$. More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are $2n$-bit mappings with two CCZ-equivalent representations: one is a quadratic non-bijective function and one is a degree $n+1$ permutation. We show that these structures always have differential uniformity at most 4 when $n$ is odd. A particular case of this structure is actually a 3-round Feistel Network with similar differential and linear properties. These functions also share an excellent non-linearity for $n=3,5,7$. Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6-bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive.

We propose a new zero-knowledge protocol applicable to additively homomorphic functions that map integer vectors to an Abelian group. The protocol demonstrates knowledge of a short preimage and achieves amortised efficiency comparable to the approach of Cramer and Damgård from Crypto 2010, but gives a much tighter bound on what we can extract from a dishonest prover. Towards achieving this result, we develop an analysis for bins-and-balls games that might be of independent interest. We also provide a general analysis of rewinding of a cut-and-choose protocol as well as a method to use Lyubachevsky's rejection sampling technique efficiently in an interactive protocol when many proofs are given simultaneously.

Our new protocol yields improved proofs of plaintext knowledge for (Ring-)LWE-based cryptosystems, where such general techniques were not known before. Moreover, they can be extended to prove preimages of homomorphic hash functions as well.

In a recent work, Kim and Barbulescu showed how to combine previous polynomial selection methods with the extended tower number field sieve algorithm to obtain improved complexity for the discrete logarithm problem on finite fields $\mathbb{F}_{p^n}$ for the medium prime case and where $n$ is composite and not a prime-power. A follow up work by Sarkar and Singh presented a general polynomial selection method and showed how to lower the complexity in the medium prime case even when $n$ is composite and a prime-power. This complexity, though, was higher than what was reported for the case of $n$ composite and not a prime-power. By suitably combining the Conjugation method of polynomial selection proposed earlier by Barbulescu et al. with the extended tower number field sieve algorithm, Jeong and Kim showed that the same asymptotic complexity is achieved for any composite $n$. The present work generalises the polynomial selection method of Jeong and Kim for all composite $n$. Though the best complexity that can be achieved is not lowered, there is a significant range of finite fields for which the new algorithm achieves complexity which is lower than all previously proposed methods.

Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al.~construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem.

We first show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model.

On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to "bypass" our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another intriguing example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes.

Midori is a light weight block cipher recently presented by Banik et al in ASIACRYPT 2015. There are two versions of Midori with state sizes of 64-bit and 128-bit respectively. The round function is based on Substitution-Permutation Network(SPN). In this paper, we give impossible differential cryptanalysis of Midori64. We studied the non-linear layer of the cipher and give two useful properties. We also find the first 6- round impossible differential paths with two non-zero and equal input cells and one non-zero output cell, and then mount 10-round attack. This is the first impossible differential attack on Midori.

One of the submissions to the CAESAR competition for the design of a new authenticated encryption scheme is Offset Merkle-Damgård (OMD). At FSE 2015, Reyhanitabar et al. introduced p-OMD, an improvement of OMD that processes the associated data almost for free. As an extra benefit, p-OMD was claimed to offer integrity against nonce-misusing adversaries, a property that OMD does not have.

In this work we show how a nonce-misusing adversary can forge a message for the original p-OMD using only 3 queries (including the forgery). As a second contribution, we generalize and simplify p-OMD. This is done via the introduction of the authenticated encryption scheme Spoed. The most important difference is the usage of a generalized padding function GPAD, which neatly eliminates the need for a case distinction in the design specification and therewith allows for a significantly shorter description of the scheme and a better security bound. Finally, we introduce the authenticated encryption scheme Spoednic, a variant of Spoed providing authenticity against a nonce-misusing adversary at a modest price.

It has been proved in Eurocrypt 2016 that if the details of the S-boxes are not exploited, an impossible differential and a zero-correlation hull can extend over at most 4 rounds of the AES. This paper concentrates on distinguishing attacks on AES-like SPN ciphers by investigating the details of both the S-boxes and the MDS matrices and illustrates some new insights on the security of these schemes. Firstly, we construct several types of $5$-round zero-correlation linear hulls for AES-like ciphers that adopt identical S-boxes to construct the round function and that have two identical elements in a column of the inverse of their MDS matrices. We then use these linear hulls to construct 5-round integrals provided that the difference of two sub-key bytes is known. Furthermore, we prove that we can always distinguish 5 rounds of such ciphers from random permutations even when the difference of the sub-keys is unknown. Secondly, the constraints for the S-boxes and special property of the MDS matrices can be removed if the cipher is used as a building block of the Miyaguchi-Preneel hash function. As an example, we construct two types of 5-round distinguishers for the hash function Whirlpool. Finally, we show that, in the chosen-ciphertext mode, there exist some nontrivial distinguishers for 5-round AES. To the best of our knowledge, this is the longest distinguishing attack for the round-reduced AES in the secret-key setting. Since the 5-round distinguisher for the AES can only be constructed in the chosen-ciphertext mode, the security margin for the round-reduced AES under the chosen-plaintext attack may be different from that under the chosen-ciphertext attack.

GOST 28147 is a 256-bit key 64-bit block cipher developed by the USSR, later adopted by the Russian government as a national standard. In 2010, GOST was suggested to be included in ISO-18033, but was rejected due to weaknesses found in its key schedule.

In 2015, a new version of GOST was suggested by Russia's standardization body (TC 26), with the purpose of mitigating such attacks. In this paper, we show that similar weaknesses exist in the new version as well. More specifically, we present a fixed-point attack on the full cipher with time complexity of $2^{237}$ encryptions. We also present a reflection attack with time complexity of $2^{192}$ for a key that is chosen from a class of $2^{224}$ weak keys. Finally, we discuss an impossible reflection attack and several possible related-key attacks.

In this paper, we describe how to compute smallest monic polynomials that define a given number field $\mathbb K$. We make use of the one-to-one correspondence between monic defining polynomials of $\mathbb K$ and algebraic integers that generate $\mathbb K$. Thus, a smallest polynomial corresponds to a vector in the lattice of integers of $\mathbb K$ and this vector is short in some sense. The main idea is to consider weighted coordinates for the vectors of the lattice of integers of $\mathbb K$. This allows us to find the desired polynomial by enumerating short vectors in these weighted lattices. In the context of the subexponential algorithm of Biasse and Fieker for computing class groups, this algorithm can be used as a precomputation step that speeds up the rest of the computation. It also widens the applicability of their faster conditional method -- which requires a defining polynomial of small height -- to a much larger set of number field descriptions.

We describe a general technique to protect randomized algorithms against kleptographic attacks. We then apply the technique to construct the first IND-CPA secure public-key encryp- tion scheme in the kleptographic setting. Our scheme preserves IND-CPA security, even when all relevant cryptographic algorithms—including key generation—are subject to adversarial subversion. The scheme requires no trusted parties or re-randomization reverse firewalls. The technique also gives a secure symmetric key encryption scheme that advances the state-of-the- art by permitting adversarial subversion of key generation and, furthermore, requiring no a priori decryptability assumptions.

Designing cryptographic primitives immune to kleptographic subversion is an active area which has led to remarkable new models and techniques; many of these are realizable by systems and can reduce the threat of such strong attacks. The feasibility of public-key encryption that is kleptographically secure in the CPA sense has been open till now.

Applications are invited for a postdoctoral researcher position in the Information Security Group at the UCL Department of Computer Science, to be supervised by Dr Sarah Meiklejohn (PI) and Prof. Tomaso Aste and Dr George Danezis (co investigators). The position are in support of an EPSRC project on the Digital Economy, and in particular will examine the applications of distributed ledgers and the challenges in designing and deploying these technologies.

The position focuses on the cryptographic and privacy-related design challenges of distributed ledgers. As such, we expect successful candidates to explore research topics such as balancing the transparency of distributed ledgers with the sensitive data that may be stored on them, developing formal cryptographic models for the auditability and privacy guarantees of distributed ledgers, and methods for establishing identity and credential infrastructures using such ledgers.

We expect candidates to have a PhD in Computer Science, Economics, or a related field, and a strong track record in cryptography, systems and network security, privacy-enhancing technologies, or similar topics.

For any enquiries or to apply for the position, please submit a full curriculum vitae and a research statement to me (s.meiklejohn at ucl.ac.uk), or apply online at http://www.jobs.ac.uk/job/ANT392/research-associate-in-the-security-and-privacy-of-distributed-ledgers/. The position is available starting September 2016 (with the start date negotiable) and will last for two years, with the possibility to extend by another 6-12 months. In a somewhat less cryptographic vein, the project is also hiring two other postdocs; these vacancies can be found here (http://www.jobs.ac.uk/job/ANQ770/research-associate-in-the-foundations-of-distributed-ledgers/) and here (http://www.jobs.ac.uk/job/ANR854/research-associate-in-the-economics-and-usability-of-distributed-ledgers/).

Closing date for applications: 16 June 2016

Contact: Sarah Meiklejohn (s.meiklejohn [at] ucl [dot] ac [dot] uk)

More information: http://www.jobs.ac.uk/job/ANT392/research-associate-in-the-security-and-privacy-of-distributed-ledgers/

Our lab is committed to laying the foundations and developing the tools for protecting privacy in tomorrow’s hyper-connected world. We are recruiting a post-doctoral researcher in the area of data privacy and security, with an emphasis on health-related data (including genomic data).

Required skills and expertise:

• Very good knowledge of written and spoken English (French is not required)

• Strong background in security, privacy, and applied cryptography (some familiarity with homomorphic encryption, secure multi-party computation, or hardware security would be welcome)

• Some background in databases, statistics, networking, electronic health records, genomics, game theory, microeconomics, or machine learning would be an asset

• Strong analytical skills

• Good knowledge of languages and tools such as C, C++, Java, Go, Python, and MATLAB

Education: a PhD degree in computer science, electrical engineering, communication systems, computer engineering, or a similar area; with a strong publication track record in information security and privacy or in cryptography.

Mission: The contribution to the research efforts of the group will involve many interactions with PhD and undergraduate students, senior researchers, and external partners (from industry, academia, and hospitals); some participation in teaching is also expected. The research activities will include notably the design and the validation of protocols and algorithms.

We offer:

• A fascinating investigation topic of global prominence in security and privacy

• A young, dynamic, and international team

• Collaboration with strategic external partners, including the Lausanne University Hospital (CHUV)

• A modern working environment

• A substantial help to obtain a faculty position (usually in another institution) at the end of the stay here.

Annual salary: 80,000 Swiss Francs (around US$80,000) and above, based on experience.

Closing date for applications: 15 June 2016

Contact: Prof. Jean-Pierre Hubaux

EPFL

More information: http://emploi.epfl.ch/page-132462-en.html

We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard number-theoretic assumptions.

The model of bounded tamper resistance was recently put forward by Damg{\aa}rd {\em et al.} (Asiacrypt 2013) as an attractive path to achieve security against arbitrary memory tampering attacks without making hardware assumptions (such as the existence of a protected self-destruct or key-update mechanism), the only restriction being on the number of allowed tampering attempts (which is a parameter of the scheme). This allows to circumvent known impossibility results for unrestricted tampering (Gennaro {\em et al.}, TCC 2010), while still being able to capture realistic tampering attacks.

Lattice reduction is fundamental in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (called LLL or L3) has been improved in many ways through the past decades and remains one of the central tool for reducing lattice basis. In particular, its floating-point variants — where the long-integer arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic — are now the fastest known. Yet, the running time of these floating-point versions is mostly determined by the precision needed to perform sound computa- tions: theoretical lower bounds are large whereas the precision actually needed on average is much lower. In this article, we present an adaptive precision version of LLL and one of its variant Potential-LLL. In these algorithms, floating-point arithmetic is replaced by Interval Arithmetic. The certification property of interval arithmetic enables runtime detection of precision defects in numerical computations and accordingly, makes it possible to run the reduction algorithms with guaranteed nearly optimal precision. As such, these adaptive reduction algorithms run faster than the state-of-the-art implementations, while still being provable.

The fabrication process of integrated circuits (ICs) is complex and requires the use of off-shore foundries to lower the costs and to have access to leading-edge manufacturing facilities. Such an outsourcing trend leaves the possibility of inserting malicious circuitry (a.k.a. hardware Trojans) during the fabrication process, causing serious security issues. Hardware Trojans are very hard and expensive to detect and can disrupt the entire circuit or covertly leak sensitive information. In this paper, we propose a formal model for assessing the security of ICs whose fabrication has been outsourced to an untrusted off-shore manufacturer. We assume that the IC specification and design are trusted but the fabrication facility(ies) may be untrusted. Our objective is to stop Trojans from releasing sensitive information to the outside while still using its circuitry for day-to-day operations. We also provide two different methodologies for constructing compilers relying on verifiable computation (VC) schemes and secure multiparty computation (MPC) protocols with certain properties. Suitable VC schemes, with the properties we require, were recently constructed, e.g., by Parno et al. (Oakland '13), and by Fiore, Gennaro, and Pastro (CCS '14). Similarly, many MPC protocols readily comply (or can be easily adapted to comply) with our requirements. By allowing manufacturers to use off-shore fabrication facilities, we ensure a high degree of competition among suppliers, thus providing lower cost without hindering innovation or access to leading-edge microelectronics.

In a recent work, Kim and Barbulescu~(CRYPTO~2016) proposed an algorithm, called exTNFS, that improves asymptotic complexity for the discrete logarithm problems over $\mathbb{F}_{p^n}$ in medium prime case, when the extension degree $n=\eta \kappa$ satisfies $\eta, \kappa \in \Z_{>1}$ and $\gcd(\eta, \kappa)=1$. Following to this work, Sarkar and Singh~(preprint) recently observed that exTNFS algorithm also admits a variant that applies when $n$ is arbitrary composite, although their best complexity is slightly larger than that of Kim and Barbulescu.

In this article, we show that exTNFS algorithm enjoys their best complexity as well for arbitrary composite extension degree $n$: we show that the discrete logarithm problem over $\mathbb{F}_{p^n}$ for a medium-sized prime $p$ and $n= \eta\kappa$, with $\eta$ and $\kappa >1$ not necessarily coprime, can be solved in time $L_{p^n}(1/3, (48/9)^{1/3})$ for a general prime $p$ and $L_{p^n}(1/3, (32/9)^{1/3})$ for a special prime $p$.

The result asserts that one should be careful of choosing parameters in the pairing-based construction regarding with the best-complexity of the variant by Kim-Barbulescu whenever the embedding degree is composite.