International Association
for Cryptologic Research

The video of Phil Rogaway's IACR Distinguished Lecture at Asiacrypt 2015 has been posted to the IACR YouTube page. Slides are available at the Asiacrypt 2015 website.

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. In this paper, we extend the formal model of PRNG with input defined by Dodis et al. at CCS 2013 to deal with partial leakage of sensitive information. The resulting security notion, termed leakage-resilient robust PRNG with input, encompasses all the previous notions, but also allows the adversary to continuously get some leakage on the manipulated data. Dodis et al. also proposed an efficient construction, based on simple operations in a finite field and a classical deterministic pseudo-random generator PRG. Here, we analyze this construction with respect to our new stronger security model, and prove that with a stronger PRG, it also resists leakage. We show that this stronger PRG can be obtained by tweaking some existing constructions based on AES. We also propose a new instantiation which may be better in specific cases. Eventually, we show that the resulting scheme remains quite efficient in spite of its new security properties. It can thus be recommended in contexts where side-channel resistance is required.

The strength of ECC lies in the hardness of elliptic curve discrete logarithm problem (ECDLP) and the hight level security with significantly smaller keys. Thus, using smaller key sizes is a gain in term of speed, power, bandwidth, and storage. Point multiplication is the most common operation in ECC and the most used method to compute it is Montgomery Algorithm. This paper describes an area-efficient hardware implementation of Elliptic Curve Cryptography (ECC) over $GF(2^m)$. We used the Montgomery modular multiplication method for low cost implementation. Then, to accelerate the elliptic curve point multiplication, we firstly adopted projective coordinates, and then we reduced the number of multiplication block used, so we have a gain at area occupation and execution time. We detailed our optimized hardware architecture and we prove that it outperform existing ones regarding area, power, and energy consumption. Our hardware implementation, on a Xilinx virtex 5 ML 50 FPGA, used only 9670 Slices achieving maximum frequency of 221 MHz, it computed scalar multiplication in only 2.58 $\mu$s. FPGA implementations represent generally the first step to obtain faster ASIC implementations.Further, we implemented our design on an ASIC CMOS 45 nm technology, it uses 0.121 $mm^2$ of area cell, it runs at a frequency of 990 MHz and consumes 39(mW).\\ \textbf{Keywords:} Elliptic Curves Cryptosystems(ECC), RSA, ASIC, Discrete Logarithm (DL), Elliptic Curves Discrete Logarithm Problems (ECDLP), memory resources.

Random and pseudorandom number generators (RNG and PRNG) are used for many purposes including cryptographic, modeling and simulation applications. For such applications a generated bit sequence should mimic true random, i.e., by definition, such a sequence could be interpreted as the result of the flips of a “fair” coin with sides that are labeled “0” and “1”. It is known that the Shannon entropy of this process is 1 per letter, whereas for any other stationary process with binary alphabet the Shannon entopy is stricly less than 1. On the other hand, the entropy of the PRNG output should be much less than 1 bit (per letter), but the output sequence should look like truly random. We describe random processes for which those, in a first glance contradictory properties, are valid. More precisely, it is shown that there exist binary-alphabet random processes whose entropy is less than 1 bit (per letter), but a frequency of occurrences of any word $|u|$ goes to $2^{- |u|}$, where $|u|$ is the length of $u$. In turn, it gives a possibility to construct RNG and PRNG which possess theoretical guarantees. This, in turn, is important for applications such as those in cryptography.

Proxy re-encryption (PRE) allows a semi-trusted proxy to transform a ciphertext for Alice into a ciphertext of the same message for Bob. The traditional security notion of PRE focuses on preventing the proxy with the re-encryption key learning anything about the encrypted messages. However, such a basic security requirement is clearly not enough for many scenarios where the proxy can collude with Bob. A desirable security goal is therefore to prevent a malicious proxy colluding with Bob to re-delegate Alice’s decryption right. In 2005, Ateniese, Fu, Green and Hohenberger first proposed this intriguing problem called non-transferability, in the sense that the only way for Bob to transfer Alice’s decryption capability is to expose his own secret key. It captures the notion that Bob cannot collude with the proxy and transfer Alice’s decryption right without compromising his own decryption capability. However, over the last decade, no solutions have achieved this property.

In this paper, we positively resolve this open problem. In particular, we give the first construction of nontransferable proxy re-encryption where the attacker is allowed to obtain one pair of keys consisting of Bob’s secret key and the corresponding re-encryption key. Using indistinguishability obfuscation and k-unforgeable authentication as main tools, our scheme is provably secure in the standard model. The essential idea behind our approach is to allow Bob’s secret key to be evoked in the process of decrypting Alice’s ciphertext while hiding the fact that only Bob could decrypt it by the obfuscated program. In addition, we also show a negative result: a CPA secure proxy re-encryption scheme with “error-freeness” property cannot be non-transferable.

The TVLA procedure using the t-test has become a popular leakage detection method. To protect against environmental fluctuation in laboratory measurements, we propose a paired t-test to improve the standard procedure. We take advantage of statistical matched-pairs design to remove the environmental noise effect in leakage detection. Higher order leakage detection is further improved with a moving average method. We compare the proposed test with standard t-test on synthetic data and physical measurements. Our results show that the proposed tests are robust to environmental noise.

The ENS Crypto Group is looking for Post-Docs on Privacy-Preserving Cryptographic Protocols.

The candidate should have strong experience in provable security, in order to be involved in one of the ongoing research projects (see the web page of the group: https://crypto.di.ens.fr).

Possible topics are (but not limited to):

• Functional Encryption
• Lattice-based Cryptography
• Secure Multi-Party Computation
• Zero-Knowledge Proofs

To apply, please send by e-mail the following documents:

• Curriculum vitae with publication list
• Reference letters
• Research statement

Closing date for applications: 31 March 2016

Contact: David Pointcheval, david(dot)pointcheval(at)ens(dot)fr

More information: https://crypto.di.ens.fr

Low-latency key exchange (LLKE) protocols allow for the transmission of cryptographically protected payload data without requiring the prior exchange of messages of a cryptographic key exchange protocol, while providing perfect forward secrecy. The LLKE concept was first realized by Google in the QUIC protocol, and a low-latency mode is currently under discussion for inclusion in TLS 1.3.

In LLKE two keys are generated, typically using a Diffie-Hellman key exchange. The first key is a combination of an ephemeral client share and a long-lived server share. The second key is computed using an ephemeral server share and the same ephemeral client share.

In this paper, we propose (relatively) simple, novel security models, which catch the intuition behind known LLKE protocols; namely that the first (respectively, second) key should remain indistinguishable from a random value, even if the second (respectively, first) key is revealed. We call this property strong key independence. We also give the first constructions of LLKE which are provably secure in these models, based on the generic assumption that secure non-interactive key exchange (NIKE) exists.

In many communication scenarios it is not sufficient to protect only the content of the communication, it is necessary to also protect the identity of communicating parties. Various protocols and technologies have been proposed to offer such protection, for example, anonymous proxies, mix-networks, or onion routing. The protocol that offers the strongest anonymity guarantees, namely unconditional sender and recipient untraceability, is the Dining Cryptographer (DC) protocol proposed by Chaum in 1988. Unfortunately the strong anonymity guarantees come at the price of limited performance and scalability and multiple issues that make deployment complicated in practice.

In this paper we address one of those issues, namely slot reservation. We propose footprint scheduling as a new technique for participants to negotiate communication slots without losing anonymity and at the same time hiding the number of actively sending users. Footprint scheduling is at the same time simple, efficient and yields excellent results, in particular in very dynamic networks with a frequently changing set of participants and frequently changing activity rate.

Many hardware and software pairing implementations can be found in the literature and some pairing friendly parameters are given. However, depending on the situation, it could be useful to generate other nice parameters (e.g. resistance to subgroup attacks, larger security levels, database of pairing friendly curves). The main purpose of this paper is to describe explicitly and exhaustively what should be done to generate the best possible parameters and to make the best choices depending on the implementation context (in terms of pairing algorithm, ways to build the tower field, $\mathbb{F}_{p^{12}}$ arithmetic, groups involved and their generators, system of coordinates).

We focus on low level implementations, assuming that $\mathbb{F}_p$ additions have a significant cost compared to other $\mathbb{F}_p$ operations. However, the results obtained are still valid in the case where $\mathbb{F}_p$ additions can be neglected. We also explain why the best choice for the polynomials defining the tower field $\mathbb{F}_{p^{12}}$ is only depending on the value of the BN parameter $u$ modulo small integers like $12$ as a nice application of old elementary arithmetic results. Moreover, we use this opportunity to give some new improvements on $\mathbb{F}_{p^{12}}$ arithmetic (in a pairing context) in terms of $\mathbb{F}_p$-addition allowing to save around $10\%$ of them depending on the context.

In this report we describe our efforts in analysing log files produced by the Estonian i-voting system in the KOV2013, EP2014 and RK2015 elections in combination with other information available, so as to detect attacks against the i-voting system, detect system malfunctions and study voter behaviour.

In this paper, we present a hybrid encryption scheme that is chosen ciphertext secure in the quantum random oracle model. Our scheme is a combination of an asymmetric and a symmetric encryption scheme that are secure in a weak sense. It is a slight modification of the Fujisaki-Okamoto transform that is secure against classical adversaries. In addition, we modify the OAEP-cryptosystem and prove its security in the quantum random oracle model based on the existence of a partial-domain one-way injective function secure against quantum adversaries.

Secure two party computation (2PC) is a well-studied problem with many real world applications. Due to Cleve's result on general impossibility of fairness, however, the state-of-the-art solutions only provide security with abort. We investigate fairness for 2PC in presence of a trusted Arbiter, in an optimistic setting where the Arbiter is not involved if the parties act fairly. Existing fair solutions in this setting are by far less efficient than the fastest unfair 2PC.

We close this efficiency gap by designing protocols for fair 2PC with covert and malicious security that have competitive performance with the state-of-the-art unfair constructions. In particular, our protocols only requires the exchange of a few extra messages with sizes that only depend on the output length; the Arbiter's load is independent of the computation size; and a malicious Arbiter can only break fairness, but not covert/malicious security even if he colludes with a party. Finally, our solutions are designed to work with the state-of-the-art optimizations applicable to garbled circuits and cut-and-choose 2PC such as free-XOR, half-gates, and the cheating-recovery paradigm.

PRINCE is a modern involutive lightweight block cipher proposed by Rechberger in Asiacrypt 2012[6], then PRINCE has been widely used in many constrained devices. PRINCE uses the FX construction, in which one part of the cipher is considered as core cipher and remaining parts are used for whitenings before and after the core. Farzaech et al. gave the security evaluations of PRINCEcore against biclique and differential cryptanalysis, respectively[10]. They presented an independent-biclique attack on the full version with computational complexity 2^62.72 and data complexity 2^40 . Inspired from their work, by better selections of differential characteristics in the biclique construction, we give another balanced biclique attack on PRINCEcore with lower computation complexity and data complexity than previous results in [10]. The computational complexity and data complexity of our attack is 2^62.67 and 2^32, respectively. Then, we first illustrate a star-based biclique attack on PRINCEcore. The computational complexity of star-based biclique attack is 2^63.02 and the required data is only a single plaintext-ciphertext pair. This is the optimal data complexity among the existing results of full round attack on PRINCEcore.

We remark that the experimental demonstrations of Shor's algorithm in the past decades are falsely claimed and flawed, because they had used too less qubits in the first quantum register to accomplish the step of Continued Fraction Expansion in Shor's algorithm. More worse, the amount of qubits used in some experiments are too less to represent all residues modulo n, which means that the number n cannot be truly involved in the related computations.

This work proposes substantial algorithmic enhancements to the SPEA attack of Schlosser et al. by adding cryptographic post-processing, and improved signal processing to the photonic measurement phase. Our improved approach provides three crucial benefits: (1) For some SBox/SRAM configurations the original SPEA method is unable to identify a unique key, and terminates with up to 2^48 key candidates; using our new solver we are able to find the correct key regardless of the respective SBox/SRAM configuration. (2) Our methods reduce the number of required (complex photonic) measurements by an order of magnitude, thereby shortening the duration of the attack significantly. (3) Due to the unavailability of the attack equipment of Schlosser et al. we additionally developed a novel Photonic Emission Simulator which we matched against the real equipment of the original SPEA work. With this simulator we were able to verify our enhanced SPEA attack by a full AES recovery which uses only a small number of photonic measurements.

Deniable encryption, first introduced by Canetti et al. (CRYPTO 1997), allows a sender and/or receiver of encrypted communication to produce fake but authentic-looking coins and/or secret keys that ``open'' the communication to a different message. Here we initiate its study for the more general case of functional encryption (FE), as introduced by Boneh et al. (TCC 2011), wherein a receiver in possession of a key k can compute from any encryption of a message x the value F(k,x) according to the scheme's functionality F. Our results are summarized as follows:

We put forth and motivate the concept of deniable FE, for which we consider two models. In the first model, as previously considered by O'Neill et al. (CRYPTO 2011) in the case of identity-based encryption, a receiver gets assistance from the master authority to generate a fake secret key. In the second model, there are ``normal'' and ``deniable'' secret keys, and a receiver in possession of a deniable secret key can produce a fake but authentic-looking normal key on its own. This parallels the ``multi-distributional'' model of deniability previously considered for public-key encryption.

In the first model, we show that any FE scheme for the general circuit functionality (as several recent candidate construction achieve) can be converted into an FE scheme having receiver deniability, without introducing any additional assumptions. In addition we show an efficient receiver deniable FE for Boolean Formulae from bilinear maps. In the second (multi-distributional) model, we show a specific FE scheme for the general circuit functionality having receiver deniability. This result additionally assumes differing-inputs obfuscation and relies on a new technique we call delayed trapdoor circuits. To our knowledge, a scheme in the multi-distributional model was not previously known even in the simpler case of identity-based encryption.

Finally, we show that receiver deniability for FE implies some form of simulation security, further motivating study of the latter and implying optimality of our results.

Auctions and elections are seemingly disjoint research fields. Nevertheless, we observe that similar cryptographic primitives are used in both fields. For instance, mixnets, homomorphic encryption, and trapdoor bit-commitments, have been used by state-of-the-art schemes in both fields. These developments have appeared independently. For example, the adoption of mixnets in elections preceded a similar adoption in auctions by over two decades. In this paper, we demonstrate a relation between auctions and elections: we present a generic construction for auctions from election schemes. Moreover, we show that the construction guarantees secrecy and verifiability, assuming the underlying election scheme satisfies secrecy and verifiability. We demonstrate the applicability of our work by deriving an auction scheme from the Helios election scheme. Our results inaugurate the unification of auctions and elections, thereby facilitating the advancement of both fields.

A notion of the graph of minimal distances of bent functions is introduced. It is an undirected graph ($V$, $E$) where $V$ is the set of all bent functions in $2k$ variables and $(f, g) \in E$ if the Hamming distance between $f$ and $g$ is equal to $2^k$ (it is the minimal possible distance between two different bent functions). The maximum degree of the graph is obtained and it is shown that all its vertices of maximum degree are quadratic. It is proven that a subgraph of the graph induced by all functions affinely equivalent to Maiorana---McFarland bent functions is connected.

Self-updatable encryption (SUE) is a new kind of public-key encryption, motivated by cloud computing, which enables anyone (i.e. cloud server with no access to private keys) to update a past ciphertext to a future ciphertext by using a public key. The main applications of SUE is revocable-storage attribute-based encryption (RS-ABE) that provides an efficient and secure access control to encrypted data stored in cloud storage. In this setting, there is a new threat such that a revoked user still can access past ciphertexts given to him by a storage server. RS-ABE solves this problem by combining user revocation and ciphertext updating functionalities. The mechanism was designed with semantic security (CPA).

We have noticed, however, that when anyone can contribute ciphertexts (as this is a public key setting), and when clients have access to some ciphertexts (encrypted data) at storage servers (since we do not exclude this possibility), then, when in order to retrieve plaintexts they employ decryption service (i.e., probe crypto servers in the cloud), this service may be sensitive to Chosen Ciphertext Attacks (CCA) when the adversary plays as a client. Next notice that when considering CCA, the RS-ABE functionality, by definition, allows certain malleability, namely, updating of messages by anyone (e.g., storage servers) over time. This seems, at first, anathema to this security notion, and this has to be dealt with!

Here, we propose the first SUE and RS-ABE schemes, secure against a relevant form of CCA, which allows ciphertexts submitted by attackers to decryption servers. Due to the fact that some ciphertexts are easily derived from others, we employ a different notion of CCA which avoids easy challenge related messages (we note that this type of idea was employed in other contexts before). Specifically, we define "time extended challenge" (TEC) CCA security for SUE which excludes ciphertexts that are easily derived from the challenge (over time periods) from being queried on (namely, once a challenge is decided by an adversary, no easy modification of this challenge to future and past time periods is allowed to be queried upon). We then propose an efficient SUE scheme with such CCA security, and we also define similar CCA security for RS-ABE and present an RS-ABE scheme with this CCA security.