International Association
for Cryptologic Research

At Crypto 2015, Blondeau \textit{et al.} showed a known-key analysis on the full \texttt{PRESENT} lightweight block cipher. Based on some of the best differential distinguishers, they introduced a meet in the middle (MitM) layer to pre-add the differential distinguisher, which extends the number of attacked rounds on \texttt{PRESENT} from 26 rounds to full rounds without reducing differential probability.

In this paper, we generalize their method and present a generic distinguisher on a kind of permutations called \texttt{PRESENT}-like permutations. This generic distinguisher is divided into two phases. The first phase is a truncated differential distinguisher with strong bias, which describes the unbalancedness of the output collision on some fixed bits, given the fixed input in some bits, and we take advantage of the strong relation between truncated differential probability and capacity of multidimensional linear approximation to derive the best differential distinguishers. The second phase is the meet-in-the-middle layer, which is pre-added to the truncated differential to propagate the differential properties as far as possible. Different with Blondeau \textit{et al.}'s work, we extend the MitM layers on a 64-bit internal state to states with any size, and we also give a concrete bound to estimate the attacked rounds of the MitM layer.

As an illustration, we apply our technique to all versions of \texttt{SPONGENT} permutations. In the truncated differential phase, as a result we reach one, two or three rounds more than the results shown by the designers. In the meet-in-the-middle phase, we get up to 11 rounds to pre-add to the differential distinguishers. Totally, we improve the previous distinguishers on all versions of \texttt{SPONGENT} permutations by up to 13 rounds.

In PKC 2014, Dachman-Soled showed a construction of a chosen ciphertext (CCA) secure public key encryption (PKE) scheme based on a PKE scheme which simultaneously satisfies a security property called weak simulatability and (standard model) plaintext awareness (sPA1) in the presence of multiple public keys. It is not well-known if plaintext awareness for the multiple keys setting is equivalent to the more familiar notion of that in the single key setting, and it is typically considered that plaintext awareness is a strong security assumption (because to achieve it we have to rely on a "knowledge"-type assumption). In Dachman-Soled's construction, the underlying PKE scheme needs to be plaintext aware in the presence of $2k+2$ public keys.

The main result in this work is to show that the strength of plaintext awareness required in the Dachman-Soled construction can be somehow "traded" with the strength of a "simulatability" property of other building blocks. Furthermore, we also show that we can "separate" the assumption that a single PKE scheme needs to be both weakly simulatable and plaintext aware in her construction. Specifically, in this paper we show two new constructions of CCA secure key encapsulation mechanisms (KEMs): Our first scheme is based on a KEM which is chosen plaintext (CPA) secure and plaintext aware only under the $2$ keys setting, and a PKE scheme satisfying a "slightly stronger" simulatability than weak simulatability, called \emph{trapdoor simulatability} (introduced by Choi et al. ASIACRYPT 2009). Our second scheme is based on a KEM which is $1$-bounded CCA secure (Cramer et al. ASIACRYPT 2007) and plaintext aware only in the \emph{single} key setting, and a trapdoor simulatable PKE scheme. Our results add new recipes for constructing CCA secure PKE/KEM from general assumptions (that are incomparable to those used by Dachman-Soled), and in particular show interesting trade-offs among building blocks with those used in Dachman-Soled's construction.

Tweakable blockcipher (TBC) is a powerful tool to design authenticated encryption schemes as illustrated by Minematsu's Offset Two Rounds (OTR) construction. It considers an additional input, called tweak, to a standard blockcipher which adds some variability to this primitive. More specifically, each tweak is expected to define a different, independent pseudo-random permutation.

In this work we focus on OTR's way to instantiate a TBC and show that it does not achieve such a property for a large amount of parameters. We indeed describe collisions between the input masks derived from the tweaks and explain how they result in practical attacks against this scheme, breaking privacy, authenticity, or both, using a single encryption query, with advantage at least 1/4.

We stress however that our results do not invalidate the OTR construction as a whole but simply prove that the TBC's input masks should be designed differently.

We introduce a novel notion of smooth (-verifier) non- interactive zero-knowledge proofs (NIZK) which parallel the familiar notion of smooth projective hash functions (SPHF). We also show that the recent single group element quasi-adaptive NIZK (QA-NIZK) of Jutla and Roy (CRYPTO 2014) for linear subspaces can be easily extended to be computationally smooth. One important distinction of the new notion from SPHFs is that in a smooth NIZK the public evaluation of the hash on a language member using the projection key does not require the witness of the language member, but instead just requires its NIZK proof.

This has the remarkable consequence that in the Gennaro-Lindell paradigm of designing universally-composable password-authenticated key-exchange (UC-PAKE) protocols, if one replaces the traditionally employed SPHFs with the novel smooth QA-NIZK, one gets highly efficient UC-PAKE protocols that are secure even under dynamic corruption. The new notion can be seen as capturing the essence of the recent UC-PAKE protocol of Jutla and Roy (AsiaCrypt 2015) which is secure under dynamic corruption but uses intricate dual-system arguments.

This simpler and modular design methodology allows us to give the first single-round asymmetric UC-PAKE protocol, which is also secure under dynamic corruption in the erasure model. Previously, all asymmetric UC-PAKE protocols required at least two rounds. In fact, our protocol just requires each party to send a single message asynchronously. In addition, the protocol has short messages, with each party sending only four group elements. Moreover, the server password file needs to store only one group element per client. The protocol employs asymmetric bilinear pairing groups and is proven secure in the random oracle model and under the standard bilinear pairing assumption SXDH.

Recommendation systems become popular in our daily life. It is well known that the more the release of users’ personal data, the better the quality of recommendation. However, such services raise serious privacy concerns for users. In this paper, focusing on matrix factorization-based recommendation systems, we propose the first privacy-preserving matrix factorization using fully homomorphic encryption. On inputs of encrypted users' ratings, our protocol performs matrix factorization over the encrypted data and returns encrypted outputs so that the recommendation system knows nothing on rating values and resulting user/item profiles. It provides a way to obfuscate the number and list of items a user rated without harming the accuracy of recommendation, and additionally protects recommender's tuning parameters for business benefit and allows the recommender to optimize the parameters for quality of service. To overcome performance degradation caused by the use of fully homomorphic encryption, we introduce a novel data structure to perform computations over encrypted vectors, which are essential operations for matrix factorization, through secure 2-party computation in part. With the data structure, the proposed protocol requires dozens of times less computation cost over those of previous works. Our experiments on a personal computer with 3.4 GHz 6-cores 64 GB RAM show that the proposed protocol runs in 1.5 minutes per iteration. It is more efficient than Nikolaenko et al.'s work proposed in CCS 2013, in which it took about 170 minutes on two servers with 1.9 GHz 16-cores 128 GB RAM.

Event date: 5 September to 7 September 2016

There is a vacancy for a postdoctoral fellow position at the Department of Informatics, Selmer Center for secure and reliable communications. The position is for a period of 4 years and is connected to the project Modern Methods and Tools for Theoretical and Applied Cryptology (CryptoWorld) funded by the Norwegian Research Council. For more information and to apply for the position see https://www.jobbnorge.no/en/available-jobs/job/122732/postdoctoral-fellow-within-cryptology

Closing date for applications: 31 March 2016

Contact: Professor Tor Helleseth, phone (+47) 55584160, email: Tor.Helleseth (at) uib.no

More information: https://www.jobbnorge.no/en/available-jobs/job/122732/postdoctoral-fellow-within-cryptology

Reporting to the Director of Security and Data Sciences, the Engineer is responsible for the following:

• Conduct research on advanced ethical hacking, penetration testing, reverse engineering.
• Conduct assessment on network infrastructure, web and mobile security.
• Assisting in IT security enforcement and enhancement.
• Design secure application testing approaches, integrate quality assurance testings with security functionalities.
• Candidate with strong programming background will also be involved in security tool/signature development.
• Design and implement preventive security controls, application code review and analysis, code scanning and testing tools, web application scanning and penetration tests.
• Manage vendor and service provider on security tools and technologies project engagement and delivery.

Requirements

• Bachelor’s degree or above in Computer Science, Electrical Engineering or other relevant disciplines with a minimum of 5 years of experience in security assessment. Candidates with less experience will also be considered for the Engineer level.
• Experience in financial industry is preferred but not mandatory.
• Demonstrate wide working knowledge of application security.
• Experience in application development life cycle, application testing and code scanning, with exposure in penetration test, finding exploits, vulnerabilities, unauthorized access, or other malicious activities in computer systems.
• Proficient in English, spoken and written.
• High integrity and professional work practice.
• Appreciation of people and cultures of different countries.

Closing date for applications: 15 March 2016

Contact: charlenechoo (at) astri.org

More information: http://www.astri.org/careers/work-at-astri/jobs/senior-engineerengineer-cyber-security-assessment-multiple-openings-4

Event date: 3 May to 5 May 2016

A postdoc position is opened by The Université Libre de Bruxelles and the company Hipperos in the domain of Secured Real-Time Operating System. The aim of the research is to propose measures to introduce security in the architecture of a modern Real-Time Operating System (RTOS) in the sense of allowing Multiple Levels of Security. This means both the security of the RTOS itself related to the authentication of the kernel, updates, drivers, services, ... as well as the secure management of applications (registration of a new application, update and upgrade of applications and execution of applications) and the security of data inside applications. The researcher would study the HIPPEROS (http://hipperos.com) architecture and propose, based on the state-of-the-art of secure operating systems, how to smoothly integrate such an architecture in the existing development process of HIPPEROS. The researcher will implement the proposed architecture in the operating system.

Status: Two years Marie Curie postdoc grant

Expected starting date: September 2016

Location: University of Brussels (ULB), Belgium

Interested applicants should:

• Hold a Ph.D. degree or equivalent in Computer Science or Computer Engineering or a closely related area
• Have solid background on real-time systems
• Have good programming skills (in C)
• Have a good publication record
• Demonstrate an excellent level of spoken and written English. Knowledge of French is a plus.

Closing date for applications: 15 March 2016

Contact: Applications should be sent latest by March 15, 2016 to joel.goossens (at) ulb.ac.be

In this paper, we study the side-channel resistance of the implementation of the ECDSA signature scheme in Android's standard cryptographic library. We show that, for elliptic curves over prime fields, one can recover the secret key very efficiently on smartphones using electromagnetic side-channel and well-known lattice reduction techniques. We experimentally show that elliptic curve operations (doublings and additions) can be distinguished in a multi-core CPU clocking over the giga-hertz. We then extend the standard lattice attack on ECDSA over prime fields to binary Koblitz curves. This is the first time that such an attack is described on Koblitz curves. These curves, which are also available in Bouncy Castle, allow very efficient implementations using the Frobenius operation. This leads to signal processing challenges since the number of available points are reduced. We investigate practical side-channel, showing the concrete vulnerability of such implementations. In comparison to previous works targeting smartphones, the attacks presented in the paper benefits from discernible architectural features, like specific instructions computations or memory accesses.

We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks. We demonstrate full extraction of ECDSA secret signing keys from OpenSSL and CoreBitcoin running on iOS devices, and partial key leakage from OpenSSL running on Android and from iOS's CommonCrypto. These non-intrusive attacks use a simple magnetic probe placed in proximity to the device, or a power probe on the phone's USB cable. They use a bandwidth of merely a few hundred kHz, and can be performed cheaply using an audio card and an improvised magnetic probe.

With the impending threat of quantum computers, Post-Quantum Cryptography schemes have emerged as suitable replacements for today's public-key cryptography schemes. We present a method for key compression in quantum-resistant isogeny-based cryptosystems, which reduces storage and transmission costs of per-party public information by a factor of two, with no effect on security. We achieve this reduction by associating a canonical choice of elliptic curve to each $j$-invariant, and representing elements on the curve as linear combinations with respect to a canonical choice of basis. This method of compressing public information can be applied to numerous isogeny-based protocols, such as key exchange, zero-knowledge identification, and public-key encryption. We performed personal computer and ARM implementations of the key exchange with compression and decompression in C and provided timing results, showing the computational cost of key compression and decompression at various security levels. Our results show that isogeny-based cryptosystems achieve by far the smallest possible key sizes among all existing families of post-quantum cryptosystems at practical security levels; e.g. 3073-bit public keys at the quantum 128-bit security level, comparable to (non-quantum) RSA key sizes.With the impending threat of quantum computers, Post-Quantum Cryptography schemes have emerged as suitable replacements for today's public-key cryptography schemes. We present a method for key compression in quantum-resistant isogeny-based cryptosystems, which reduces storage and transmission costs of per-party public information by a factor of two, with no effect on security. We achieve this reduction by associating a canonical choice of elliptic curve to each $j$-invariant, and representing elements on the curve as linear combinations with respect to a canonical choice of basis. This method of compressing public information can be applied to numerous isogeny-based protocols, such as key exchange, zero-knowledge identification, and public-key encryption. We performed personal computer and ARM implementations of the key exchange with compression and decompression in C and provided timing results, showing the computational cost of key compression and decompression at various security levels. Our results show that isogeny-based cryptosystems achieve by far the smallest possible key sizes among all existing families of post-quantum cryptosystems at practical security levels; e.g. 3073-bit public keys at the quantum 128-bit security level, comparable to (non-quantum) RSA key sizes.

We construct an algorithm that permits a large group of individuals to reach consensus on a random number, without having to rely on any third parties. The algorithm works with high probability if there are less than 50% colluding parties in the group. We describe also some modifications and generalizations of the algorithm.

How to securely run untrusted software? A typical answer is to try to isolate the actual effects this software might have. Such counter-measures can take the form of memory segmentation, sandboxing or virtualisation. Besides controlling potential damage this software might do, such methods try to prevent programs from peering into other running programs' operation and memory.

As programs, no matter how many layers of indirection in place, are really being run, they consume resources. Should this resource usage be precisely monitored, malicious programs might be able to communicate in spite of software protections.

We demonstrate the existence of such a covert channel bypassing isolations techniques and IPC policies. This covert channel that works over all major consumer OSes (Windows, Linux, MacOS) and relies on exploitation of the process table. We measure the bandwidth of this channel and suggest countermeasures.

Goldwasser and Rothblum (TCC '07) prove that statistical indistinguishability obfuscation (iO) cannot exist if the obfuscator must maintain perfect correctness (under a widely believed complexity theoretic assumption: $\mathcal{NP} \not\subseteq \mathcal{SZK}\subseteq\mathcal{AM}\cap\mathbf{co}\mathcal{AM}$). However, for many applications of iO, such as constructing public-key encryption from one-way functions (one of the main open problems in theoretical cryptography), approximate correctness is sufficient. It had been unknown thus far whether statistical approximate iO (saiO) can exist.

We show that saiO does not exist, even for a minimal correctness requirement, if $\mathcal{NP} \not\subseteq \mathcal{AM}\cap\mathbf{co}\mathcal{AM}$, and if one-way functions exist. A simple complementary observation shows that if one-way functions do not exist, then average-case saiO exists. Technically, previous approaches utilized the behavior of the obfuscator on evasive functions, for which saiO always exists. We overcome this barrier by using a PRF as a ``baseline'' for the obfuscated program.

We broaden our study and consider relaxed notions of security for iO. We introduce the notion of correlation obfuscation, where the obfuscations of equivalent circuits only need to be mildly correlated (rather than statistically indistinguishable). Perhaps surprisingly, we show that correlation obfuscators exist via a trivial construction for some parameter regimes, whereas our impossibility result extends to other regimes. Interestingly, within the gap between the parameters regimes that we show possible and impossible, there is a small fraction of parameters that still allow to build public-key encryption from one-way functions and thus deserve further investigation.

The fresh re-keying scheme is a countermeasure designed to protect low-cost devices against side-channel attacks. In this paper, we present a new birthday-type attack based on a refined reduction to Ring-LPN with a reducible polynomial. Compared with the previous research, our algorithm significantly reduces the time complexity in the 128-bit leakage model—with an SNR equal to 8 and at most $2^{20}$ traces, for instance, the key can be recovered using $2^{41.99}$ bit-operations.

The scatter-gather technique is a commonly-implemented approach to prevent cache-based timing attacks. In this paper we show that scatter-gather is not constant-time. We implement a cache timing attack against the scatter-gather implementation used in the modular exponentiation routine in OpenSSL version 1.0.2f. Our attack exploits cache-bank conflicts on the Sandy Bridge microarchitecture. We have tested the attack on an Intel Xeon E5-2430 processor. For 4096-bit RSA our attack can fully recover the private key after observing 16,000 decryptions.

The International Association for Cryptologic Research and cryptographers all over the world congratulate Whitfield Diffie and Martin Hellman for their 2015 ACM Turing Award.

Their work laid the foundation for the vibrant research field of public-key cryptography, established cryptology as a discipline of its own, and protects the daily communication and businesses of billions of people today.

We are proud of their achievement and thrilled to stand on their shoulders.

The International Association for Cryptologic Research
Christian Cachin, President

Several pairing-based cryptographic protocols are recently proposed with a wide variety of new novel applications including the ones in emerging technologies like cloud computing, internet of things (IoT), e-health systems and wearable technologies. There have been however a wide range of incorrect use of these primitives. The paper of Galbraith, Paterson, and Smart (2006) pointed out most of the issues related to the incorrect use of pairing-based cryptography. However, we noticed that some recently proposed applications still do not use these primitives correctly. This leads to unrealizable, insecure or too inefficient designs of pairing-based protocols. We observed that one reason is not being aware of the recent advancements on solving the discrete logarithm problems in some groups. The main purpose of this article is to give an understandable, informative, and an up-to-date recipe for the correct use of pairing-based cryptography. We thereby deliberately avoid most of the technical details and rather give special emphasis on the importance of the correct use of bilinear maps by realizing secure cryptographic protocols. We list a collection of some recent papers having wrong security assumptions or realizability/efficiency issues. Finally, we give a compact and up-to-date recipe of the correct use of pairings.