International Association
for Cryptologic Research

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software.

Our chosen prime $p$ looks random, and $p-1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our $p$ has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\GF p^*$, yet detecting that $p$ has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of backdoored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild.

Recent results of Kaplan et al., building on previous work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems are completely broken when exposed to quantum CPA attacks. In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others. In this work, we study simple algebraic adaptations of such schemes that replace $(\mathbb Z/2)^n$ addition with operations over alternate finite groups--such as $\mathbb Z/{2^n}$--and provide evidence that these adaptations are secure against quantum CPA attacks. These adaptations furthermore retain the classical security properties (and basic structural features) enjoyed by the original schemes.

We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a basic cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and--in many cases of interest--a reduction from the "search version" to the "decisional version." We then establish, under this assumption, the security of several such hidden-shift adaptations of symmetric-key constructions against quantum CPA attack. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon's algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.

Learning for Security in IoT

This Post-Doc position is located in Grenoble, France, at the CEA-LETI institute. Its context is the realization of a lightweight Security Audit Module capable of making low-cost, pervasive IoT nodes tolerant to attacks.

The goal of this project is to propose machine learning methods to identify and react to security attacks in IoT nodes. The first part of the work consists of modelling normal and attack behavior starting with a set of hardware and software probes. These models will be used to design low-cost attack classifiers, suitable for typical IoT nodes consisting of a processor, a radio interface, and a set of sensors/actuators.

We are looking for applicants with expertise in machine learning, data analysis, with focus on clustering and classification. Prior knowledge on security, e.g., physical attacks and countermeasures, are preferred but not essential. The candidate should be at ease with classical software programming environments, e.g., Python, C/C++, and simulation tools, e.g., Matlab, Scilab, and should understand conventional computer architecture concepts, e.g., processor, bus, memory, registers.

The main tasks of the Postdoctoral researcher are as follows:

- Define the attack scenarios and security reactions, given the specifications of an IoT node.

- Define software and hardware probes that can be used to determine attack cases.

- Construct of normal/attack behavior models.

- Investigate of low-cost classifiers for on-line attack detection, and their cost evaluation in terms of performance, algorithm complexity and overhead.

- Propose the specification of the Security Audit Module.

The final outcome of the work is a lightweight Security Audit Module capable of making low-cost, pervasive embedded devices tolerant to attacks. The candidate will work with a pool of experts coming from different research teams of the Leti, namely the embedded system’s design team and the security teams.

Closing date for applications: 20 December 2016

Contact: Anca Molnos, anca.molnos (at) cea.fr

Damien Couroussé, damien.courousse (at) cea.fr

More information: http://www.cea.fr/technologies

The Security and Privacy group is recruiting a new permanent Lecturer in Computer Security. The post involves research, teaching and administration/management in the School of Computer Science, with a particular focus on Computer Security (broadly conceived). We are interested in hearing from excellent researchers with expertise that complements or expands our current research areas.

The Security and Privacy group currently consists of eleven academic staff researching all aspects of computing security and privacy. Particular expertise within the group includes designing secure systems, formal analysis of systems, applied cryptography, security testing, and developing attack methods and defenses. The research ethos of the group is to tackle problems that are important to society, government and industry. We are recognised as an EPSRC/GCHQ Academic Centre of Excellence in Cybersecurity Research. Current areas of expertise within the group include: applied cryptography, formal verification, automotive security, cloud security, embedded devices and internet of things security (including industrial control systems), wireless security, electronic voting, security and privacy for society, and cyber security education.

Closing date for applications: 3 November 2016

More information: http://sec.cs.bham.ac.uk/index.html#lecturer

In this work we study the feasibility of achieving simulation security in functional encryption (FE) in the random oracle model. Our main result is negative in that we give a functionality for which it is impossible to achieve simulation security even with the aid of random oracles.

We begin by giving a formal definition of simulation security that explicitly incorporates the random oracles. Next, we show a particular functionality for which it is impossible to achieve simulation security. Here messages are interpreted as seeds to a (weak) pseudorandom function family $F$ and private keys are ascribed to points in the domain of the function. On a message $s$ and private key $x$ one can learn $F(s,x)$. We show that there exists an attacker that makes a polynomial number of private key queries followed by a single ciphertext query for which there exists no simulator.

Our functionality and attacker access pattern closely matches the standard model impossibility result of Agrawal, Gorbunov, Vaikuntanathan and Wee (CRYPTO 2013). The crux of their argument is that no simulator can succinctly program in the outputs of an unbounded number of evaluations of a pseudorandom function family into a fixed size ciphertext. However, their argument does not apply in the random oracle setting since the oracle acts as an additional conduit of information which the simulator can program. We overcome this barrier by proposing an attacker who decrypts the challenge ciphertext with the secret keys issued earlier without using the random oracle, even though the decryption algorithm may require it. This involves collecting most of the useful random oracle queries in advance, without giving the simulator too many opportunities to program. We note that our negative result contradicts a theorem of De Caro et al. (CRYPTO 2013) which claims that random oracles can transform any indistinguishability secure functional encryption system into one that is simulation secure.

On the flip side, we demonstrate the utility of the random oracle in simulation security. Given only public key encryption and low-depth PRGs we show how to build an FE system that is simulation secure for any poly-time attacker that makes an unbounded number of message queries, but an a-priori bounded number of key queries. This bests what is possible in the standard model where it is only feasible to achieve security for an attacker that is bounded both in the number of key and message queries it makes. We achieve this by creating a system that leverages the random oracle to get one-key security and then adapt previously known techniques to boost the system to resist up to $q$ queries.

Finally, we ask whether it is possible to achieve simulation security for an unbounded number of messages and keys, but where all key queries are made after the message queries. We show this too is impossible to achieve using a different twist on our first impossibility result.

CRIME and BREACH attacks on TLS/SSL leverage the fact that compression ratio is not hidden by encryption to recover content of secrets. We introduce SafeDeflate---a modification of a standard Deflate algorithm which compression ratio does not leak information about secret tokens. The modification is compatible with existing Deflate and gzip decompressors. We introduce a model in which attacker can obtain ciphertexts of arbitrary compressed plaintext containing secret values. Then we prove that SafeDeflate is secure in this model.

The Principal Ideal Problem (resp. Short Principal Ideal Problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. Yet, in practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert and Regev show that solving the SPIP in such cyclotomic rings boils down to solving the PIP. We complete their result by an algorithm that solves PIP in cyclotomic fields in subexponential time $L_{|\Delta_K|} (1/2) = 2^{N^{1/2+o(1)}}$, where $\Delta_K$ denotes the discriminant of the number field and N its degree. This asymptotic complexity could be compared with the one obtained by Biasse and Fieker method, that aims at finding a generator as we do, but runs in L_{|\Delta_K|} (2/3). Besides this theoretical improvement, our algorithm permits to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters.

We will present here two simple theorems that show that when we compose permutation generators with independent keys, then the ``quality'' of CCA security increases. These theorems are written in terms of H-coefficients.

An active research trend is to exploit the consensus mechanism of cryptocurrencies to secure the execution of distributed applications. In particular, some recent works have proposed fair lotteries which work on Bitcoin. These protocols, however, require a deposit from each player which grows quadratically with the number of players. We propose a fair lottery on Bitcoin which only requires a constant deposit.

In this paper, we improve the lower bound on the maximum nonlinearity of 1-resilient Boolean functions, for $n$ even, by proposing a method of constructing this class of functions attaining the best nonlinearity currently known. Thus for the first time, at least for small values of $n$, the upper bound on nonlinearity can be reached in a deterministic manner in difference to some heuristic search methods proposed previously. The nonlinearity of these functions is extremely close to the maximum nonlinearity attained by bent functions and it might be the case that this is the highest possible nonlinearity of 1-resilient functions. Apart form this theoretical contribution, it turns out that the cryptographic properties of these functions are overall good apart from their moderate resistance to fast algebraic attacks (FAA). This weakness is repaired by a suitable modification of the original functions giving a class of balanced functions with almost optimal resistance to FAA whose nonlinearity is better than the nonlinearity of other methods.

We present a \textit{tightly secure} broadcast encryption scheme of composite-order bilinear groups in the selective security model. Our construction and proof rely on the recently novel technique from Chen (eprint 2016/891). The proof of our construction will lead to only \(O(\log n)\) or \(O(\log \lambda)\) security loss, rather than \(O(n)\) security loss as the construction given by Wee (TCC-A 16) and many other previous constructions.

Side-channel attacks and in particular differential power analysis (DPA) attacks pose a serious threat to cryptographic implementations. One approach to counteract such attacks are cryptographic schemes based on fresh re-keying. In settings of pre-shared secret keys, such schemes render DPA infeasible by deriving session keys and by ensuring that the attacker cannot collect side-channel leakage on the session key during cryptographic operations with different inputs. While these schemes can be applied to secure standard communication settings, current re-keying approaches are unable to provide protection in settings where the same input needs to be processed multiple times.

In this work, we therefore adapt the re-keying approach to present the first symmetric authenticated encryption scheme that is inherently secure against DPA attacks and that does not have such a usage restriction. This means that our scheme fully complies with the requirements given in the CAESAR call and hence, can be used like other standard authenticated encryption schemes without loss of side-channel protection. Its resistance against side-channel analysis is highly relevant for several applications in practice, like bulk storage settings in general and the protection of FPGA bitfiles and firmware images in particular.

Is it feasible for parties to securely evaluate a function on their joint inputs, while hiding not only their private input, but even the very fact that they are taking part to the protocol? This intriguing question was given a positive answer in the two-party case at STOC’05, and in the general case at FOCS’07, under the name of covert multiparty computation (CMPC). A CMPC protocol allows n players with inputs (x1 ···xn) to compute a function f with the following guarantees: – If all the parties are taking part to the protocol, and if the result of the computation is favorable to all the parties, then they get to learn f(x1,··· ,xn) (and nothing more) – Else, when the result is not favorable to all the parties, or if some player does not participate to the computation, no one gets to learn anything (and in particular, no player can learn whether any of the other parties was indeed participating to the protocol) While previous works proved the existence of CMPC under standard assumptions, their candidate CMPC protocols were exclusively of theoretical interest. In this work, we revisit the design of CMPC protocols and show that, perhaps surprisingly, this very strong security notion can be achieved essentially for free. More specifically, we show how to build a CMPC protocol out of a standard, state-of-the-art MPC protocol, where both the communication and the computation are the same than the original protocol, up to an additive factor independent of the size of the circuit. Along the way, we prove two variants of the UC theorem which greatly simplify the design and the security analysis of CMPC protocols.

Event date: 13 February to 15 February 2017
Submission deadline: 19 October 2016
Notification: 15 November 2016

In 2014, the orthogonalized integer representation is presented indepently by Dan Ding etc and Fukase etc to solve SVP respectively by genetic algorithm and sampling technique, and both work have achieved very good results. In this paper, we first study the probability distribution of the shortest vector with orthogonalized integer representations, and give a new enumeration method based on the representations, called orthognalized enumeration. Besides, we present a new BKZ method, called MBKZ, which alternately uses orthognalized enumeration and traditional enumeration. Our method has the obvious advantage in time complexity compared to the previous ones which achieved exponential speedups both in theory and in practice. Furthermore, a new technique of reducing enumeration space is described, we can't find a quantitative analysis about success probability but it is effective in practice.

Lewko and Waters introduced the computational hiding technique in Crypto'12. In their technique, two computational assumptions that achieve selective and co-selective security proofs lead to adaptive security of an encryption scheme. Later, pair encoding framework was introduced by Attrapadung in Eurocrypt'14. The pair encoding framework generalises the computational hiding technique for functional encryption (FE). It has been used to achieve a number of new FE schemes such as FE for regular languages and unbounded attribute based encryption allowing multi-use of attributes. Nevertheless, the generalised construction of Attrapadung's pair encoding for those schemes is adaptively secure only in composite order groups, which leads to efficiency loss. It remains a challenging task to explore constructions in prime order groups for gaining efficiency improvement, which leaves the research gap in the existing literature. In this work, we aim to address this drawback by proposing a new generalised construction for pair encodings in prime order groups. Our construction will lead to a number of new FE schemes in prime order groups, which have been previously introduced only in composite order groups by Attrapadung.

Apart from their numerous other benefits, online social networks (OSNs) allow users to jointly compute on each other’s data (e.g., profiles, geo-locations, medical records, etc.). Privacy issues naturally arise in this setting due to the sensitive nature of the exchanged information. Ideally, nothing about a user’s data should be revealed to the OSN provider or "non-friend" users, and even her "friends" should only learn the output of a joint computation. In this work we propose the first security framework to capture these strong privacy guarantees for general-purpose computation. We also achieve two additional attractive properties: users do not need to be online while their friends compute on their data, and any user value uploaded at the server can be repeatedly used in multiple computations. We formalize our framework in the setting of secure multi-party computation (MPC) and provide two instantiations: the first is a non-trivial adaptation of garbled circuits that converts inputs under different keys to ones under the same key, and the second is based on two-party mixed protocols and involves a novel two-party re-encryption module. We experimentally validate the efficiency of our instantiations using state-of-the-art tools for two concrete use-cases.

Fix a prime number $\ell$. Graphs of isogenies of degree a power of $\ell$ are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called $\mathfrak l$-isogenies, resolving that they are (almost) volcanoes in any dimension. Specializing to the case of principally polarizable abelian surfaces, we then exploit this structure to describe graphs of a particular class of isogenies known as $(\ell, \ell)$-isogenies: those whose kernels are maximal isotropic subgroups of the $\ell$-torsion for the Weil pairing. We use these two results to write an algorithm giving a path of computable isogenies from an arbitrary absolutely simple ordinary abelian surface towards one with maximal endomorphism ring, which has immediate consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.

Software-based cryptographic implementations can be vulnerable to side-channel analysis. Masking countermeasures rank among the most prevalent techniques against it, ensuring formally the protection vs. value-based leakages. However, its applicability is halted by two factors. First, a masking countermeasure involves a computational overhead that can render implementations inefficient. Second, physical effects such as glitches and distance-based leakages can cause the reduction of the security order in practice, rendering the masking protection less effective. This paper, attempts to address both factors. In order to reduce the computational cost, we implement a high-throughput, bitsliced, 2nd-order masked implementation of the PRESENT cipher, using assembly in ARM Cortex-M4. The implementation outperforms the current state of the art and is capable of encrypting a 64-bit block of plaintext in 6,532 cycles (excluding RNG), using 1,644 bytes of data RAM and 1,552 bytes of code memory. Second, we analyze experimentally the effectiveness of masking in ARM devices, i.e. we examine the effects of distance-based leakages on the security order of our implementation. We confirm the theoretical model behind distance leakages for the first time in ARM-based architectures.

This paper presents high-throughput assembly implementations of PRESENT, PRINCE and KATAN64 ciphers for the ATtiny family of AVR microcontrollers. We report throughput records, achieving the speed of 2967 clock cycles per block encryption for PRESENT, 1803 cycles for PRINCE and 23671 cycles for KATAN64. In addition, we offer insight into the `slicing' techniques used for high throughput and their application to lightweight cryptographic implementations. We also demonstrate the speed-memory tradeoff by constructing high-throughput implementations with large memory requirements.