International Association
for Cryptologic Research

Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances are built over finite fields of large characteristic and their security relies on the fact the embedding field of the underlying curve is relatively large. How large is debatable. The aim of our work is to sustain the claim that the combination of degree 3 embedding and too small finite fields obviously does not provide enough security. As a computational example, we solve the DLP on a 170-bit MNT curve, by exploiting the pairing embedding to a 508-bit, degree-3 extension of the base field.

Considering that access to information is one of the most important aspects of modern society, the actions of certain governments or internet providers to control or, even worse, deny access for their citizens/users to selected data sources has lead to the implementation of new communication protocols. TOR is such a protocol, in which the path between the original source and destination is randomly generated using a network of globally connected routers and, by doing so, the client is not identified as actually accessing the resource. However, if the ISP knows that the first hop is part of TOR or if it can identify the contents of the exchanged packages as being TOR packages, by using advanced detection algorithms, it can still perform it’s denial policies. These types of detection are circumvented by the usage of bridges (TOR routers which aren’t publicly known) and pluggable transports (content changing protocols, in order to pass through as innocent-looking traffic). The development of a didactic pluggable transport in a simulated TOR network is the main purpose of this paper, in order to investigate the current state of the art of TOR development and analysis.

The list of papers accepted to Crypto 2016 is now available online. Crypto will be held August 14-18 in Santa Barbara.

We consider the task of secure multi-party computation of arithmetic circuits over a finite field. Unlike Boolean circuits, arithmetic circuits allow natural computations on integers to be expressed easily and efficiently. In the strongest setting of malicious security with a dishonest majority — where any number of parties may deviate arbitrarily from the protocol — most existing protocols require expensive public-key cryptography for each multiplication in the preprocessing stage of the protocol, which leads to a high total cost.

We present a new protocol that overcomes this limitation by using oblivious transfer to perform secure multiplications in general finite fields with reduced communication and computation. Our protocol is based on an arithmetic view of oblivious transfer, with careful consistency checks and other techniques to obtain malicious security at a cost of less than 6 times that of semi-honest security. We describe a highly optimized implementation together with experimental results for up to five parties. By making extensive use of parallelism and SSE instructions, we improve upon previous runtimes for MPC over arithmetic circuits by more than 200 times.

The Number Theoretic Transform (NTT) provides efficient algorithms for cyclic and nega-cyclic convolutions, which have many applications in computer arithmetic, e.g., for multiplying large integers and large degree polynomials. It is commonly used in cryptographic schemes that are based on the hardness of the Ring Learning With Errors (R-LWE) problem to efficiently implement modular polynomial multiplication. We present a new modular reduction technique that is tailored for the special moduli required by the NTT. Based on this reduction, we speed up the NTT and propose faster, multi-purpose algorithms. We present two implementations of these algorithms: a portable C implementation and a high-speed implementation using assembly with AVX2 instructions. In comparison to state-of-the-art implementations of the NTT using the same parameters, our C and assembly implementations achieve factor-1.90 and factor-1.25 speedups, respectively. To demonstrate the improved efficiency in an application example, we benchmarked the algorithms in the context of the R-LWE key exchange protocol that has recently been proposed by Alkim, Ducas, Poppelmann and Schwabe. In this case, our C and assembly implementations compute the full key exchange 1.40 and 1.34 times faster, respectively. These results are achieved with full protection against timing attacks.

(Sequential) Aggregate signature schemes enable a group of users $u_1, \dots, u_k$ with messages $m_1, \dots, m_k$ to produce a single signature $\Sigma$ which states the integrity and authenticity of all the messages $m_1, \dots, m_k$. The length of the signature $\Sigma$ is thereby significantly shorter than a concatenation of individual signatures. Therefore, aggregate signatures can improve the efficiency of numerous applications, e.g. the BGPsec protocol of Internet routing and the development of new efficient aggregate signature schemes is an important task for cryptographic research. On the other hand, multivariate cryptography offers a huge variety of practical signature schemes. However, there is a lack of multivariate signature schemes with special properties such as aggregate signature schemes. In this paper, we propose a technique to extend the HFEv- signature scheme to a sequential aggregate signature scheme. By doing so, we create the first multivariate signature scheme of this kind. Our scheme is very efficient and offers compression rates that outperform current lattice-based constructions for practical parameters.

In this paper, we propose a guess and determine attack against some variants of the π-Cipher family of authenticated ciphers. This family of ciphers is a second-round candidate of the CAESAR competition. More precisely, we show a key recovery attack with time complexity little higher than 24^ω, and low data complexity, against variants of the cipher with ω-bit words, when the internal permutation is reduced to 2.5 rounds. In particular, this gives an attack with time complexity 2^72 against the variant π16-Cipher096 (using 16-bit words) reduced to 2.5 rounds, while the authors claim 96 bits of security with 3 rounds in their second-round submission. Therefore, the security margin for this variant of π-Cipher is very limited. The attack can also be applied to lightweight variants that are not included in the CAESAR proposal, and use only two rounds. The lightweight variants π16-Cipher096 and π16-Cipher128 claim 96 bits and 128 bits of security respectively, but our attack can break the full 2 rounds with complexity 2^72. Finally, the attack can be applied to reduced versions of two more variants of π-Cipher that were proposed in the first-round submission with 4 rounds: π16-Cipher128 (using 16-bit words) and π32-Cipher256 (using 32-bit words). The attack on 2.5 rounds has complexity 2^72 and 2^137 respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.

Certificateless encryption (CLE) alleviates the heavy certificate management in traditional public key encryption and the key escrow problem in the ID-based encryption simultaneously. Current CLE schemes assumed that the user’s secret key is absolutely secure. Unfortunately, this assumption is too strong in case the CLE is deployed in the hostile setting and the leakage of secret key is inevitable. In this paper, we present a new concept called an certificateless key insulated encryption scheme (CL-KIE). We argue that this is an important cryptographic primitive that can be used to achieve key-escrow free and key-exposure resilience. We also present an efficient CL-KIE scheme based on bilinear pairing. After that, the security of our scheme is proved under the Bilinear Diffie-Hellman assumption in the random oracle model. Certificateless encryption (CLE) alleviates the heavy certificate management in traditional public key encryption and the key escrow problem in the ID-based encryption simultaneously. Current CLE schemes assumed that the user’s secret key is absolutely secure. Unfortunately, this assumption is too strong in case the CLE is deployed in the hostile setting and the leakage of the secret key is inevitable. In this paper, we present a new concept called a certificateless key insulated encryption scheme (CL-KIE). We argue that this is an important cryptographic primitive that can be used to achieve key-escrow free and key-exposure resilience. We also present an efficient CL-KIE scheme based on bilinear pairing. After that, the security of our scheme is proved under the Bilinear DiffieHellman assumption in the random oracle model.

We present a new Identity-Based Encryption (IBE) scheme from a trapdoor subgroup of $\mathbb{Z}^*_{n}$ for an RSA modulus $n$. In a trapdoor subgroup of $\mathbb{Z}^*_{n}$, a subgroup order is hidden and can be used as a trapdoor. Our IBE scheme is efficient in both performance and space. Compared to practical pairing-based IBE schemes, ours is more efficient particularly in terms of computational performance. Following Naor's observation, we also suggest a new Public-Key Signature (PKS) scheme from a trapdoor subgroup of $\mathbb{Z}^*_{n}$. A favorable feature of our PKS scheme is that signing algorithm is exponentiation-free and requires only one modular inversion. This enables our PKS scheme to provide the fastest signing, compared to practical signature schemes such as RSA and ECDSA. We prove the security of our schemes in the random oracle model under new computational hardness problems that arguably hold in the trapdoor subgroup of $\mathbb{Z}^*_{n}$.

As flying, camera-bearing drones get smaller and lighter, they increasingly choke on the common ciphers as they interpret their commands, and send back their footage. New paradigm cryptography allows for minimum power, adjustable randomness security to step in, and enable this emerging technology to spy, follow, track, and detect. E.g.: to find survivors in a collapsed structure. We describe here a cryptographic premise where intensive computation is avoided, and security is achieved via non-complex processing of at-will size keys. The proposed approach is to increase the role of randomness, and to build ciphers that can handle any size key without choking on computation. Orthodox cryptography seeks to create a thorough mix between key bits and message bits, resulting in heavy-duty computation. Let’s explore simple, fast ciphers that allow their user to adjust the security of the ciphertext by determining how much randomness to use. We present “Walk in the Park” cipher where the “walk” may be described through the series of visited spots (the plaintext), or, equivalently through a list of the traversed walkways (ciphertext). The “walking park” being the key, determines security by its size. Yet, the length of the “walk” is determined by the size of the plaintext, not the size of the “park”. We describe a use scenario for the proposed cipher: a drone taking videos of variable sensitivity and hence variable required security – handled by the size of the “park”.

Constructing short signatures with tight security from standard assumptions is a long-standing open problem. We present an adaptively secure, short (and stateless) signature scheme, featuring a constant security loss relative to a conservative hardness assumption, Short Integer Solution (SIS), and the security of a concretely instantiated pseudorandom function (PRF). This gives a class of tightly secure short lattice signature schemes whose security is based on SIS and the underlying assumption of the instantiated PRF.

Our signature construction further extends to give a class of tightly and adaptively secure ``compact" Identity-Based Encryption (IBE) schemes, reducible with constant security loss from Regev's vanilla Learning With Errors (LWE) hardness assumption and the security of a concretely instantiated PRF. Our approach is a novel combination of a number of techniques, including Katz and Wang signature, Agrawal et al. lattice-based secure IBE, and Boneh et al. key-homomorphic encryption.

Our results, at the first time, eliminate the dependency between the number of adversary's queries and the security of short signature/IBE schemes in the context of lattice-based cryptography. They also indicate that tightly secure PRFs (with constant security loss) would imply tightly, adaptively secure short signature and IBE schemes (with constant security loss).

Noisy channels enable unconditionally secure multi-party computation even against parties with unbounded computational power. But inaccurate noise estimation and adversarially determined channel characteristics render known protocols insecure. Such channels are known as unreliable noisy channels. A large body of work in the last three decades has attempted to construct secure multi-party computation from unreliable noisy channels, but this previous work has not been able to deal with most parameter settings.

In this work, we study a form of unreliable noisy channels where the unreliability is one-sided, that we name elastic noisy channels: thus, in one form of elastic noisy channel, an adversarial receiver can increase the reception reliability unbeknown to the sender, but the sender cannot change the channel characteristic.

Our work shows feasibility results for a large set of parameters for the elastic binary symmetric channel, significantly improving upon the best results obtainable using prior techniques. In a key departure from existing approaches, we use a more elemental correlated private randomness as an intermediate cryptographic primitive that exhibits only a rudimentary essence of oblivious transfer. Toward this direction, we introduce new information-theoretic techniques that are potentially applicable to other cryptographic settings involving unreliable noisy channels.

Crepeau and Santha, in 1991, posed the question of reversibility of functionalities, that is, which functionalities when used in one direction, could securely implement the identical functionality in the reverse direction. Wolf and Wullschleger, in 2006, showed that oblivious transfer is reversible. We study the problem of reversibility among 2-party SFE functionalities, which also enable general multi-party computation, in the information-theoretic setting.

We show that any functionality that enables general multi-party computation, when used in both directions, is reversible. In fact, we show that any such functionality can securely realize oblivious transfer when used in an a priori fixed direction. This result enables secure computation using physical setups that parties can only use in a particular direction due to inherent asymmetries in them.

Garbled circuits (GC) are one of the main tools for secure two-party computation. One of the most promising techniques for efficiently achieving active-security in the context of GCs is the so called \emph{cut-and-choose} approach, which in the last few years has received many refinements in terms of the number of garbled circuits which need to be constructed, exchanged and evaluated.

In this paper we ask a simple question, namely \emph{how many garbled circuits are needed to achieve active security?} and we propose a novel protocol which achieves active security while using only a constant number of garbled circuits per evaluation in the amortized setting.

Electronic payment (e-payment) has been widely applied to electronic commerce and has especially attracted a large number of mobile users. However, current solutions often focus on protecting users' money security without concerning the issue of users' privacy leakage. In this paper, we propose AEP-M, a practical anonymous e-payment scheme specifically designed for mobile devices using TrustZone. On account of the limited resources on mobile devices and time constraints of electronic transactions, we construct our scheme based on efficient divisible e-cash system. Precisely, AEP-M allows users to withdraw a large coin of value $2^{n}$ at once, and then spend it in several times by dividing it without revealing users' identities to others, including banks and merchants. Users' payments cannot be linked either. AEP-M utilizes bit-decomposition technique and pre-computation to further increase the flexibility and efficiency of spending phase for mobile users. As a consequence, the frequent online spending process just needs at most $n$ exponentiations on elliptic curve on mobile devices. Moreover, we elaborately adapt AEP-M to TrustZone architecture for the sake of protecting users' money and critical data. The methods about key derivation and sensitive data management relying on a root of trust from SRAM Physical Unclonable Function (PUF) are presented. We implement a prototype system and evaluate AEP-M using Barreto-Naehrig (BN) curve with 128-bit security level. The security analysis and experimental results indicate that our scheme could meet the practical requirement of mobile users in respects of security and efficiency.

This paper deals with block ciphers embedding a trapdoor which consists to map a partition of the plaintext space to a partition of the ciphertext space. In a first part, this issue is reduced to the study of the S-boxes of the cipher satisfying a few criteria. Then, differential and linear properties of such S-boxes are assessed and an algorithm to build optimal S-boxes is provided. Finally, these primitives are used to design a small trapdoor cipher resistant to linear and differential cryptanalysis. This trapdoor allows to recover the $\kappa$-bit master key with only one plaintext/ciphertext pair and an effort of $2^{\frac{\kappa}{2}}$ encryptions.

We explore cryptographic primitives with low multiplicative complexity. This is motivated by recent progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where primitives from symmetric cryptography are needed and where linear computations are, compared to non-linear operations, essentially ``free''. Starting with the cipher design strategy ``LowMC'' from Eurocrypt 2015, a number of bit-oriented proposals have been put forward, focusing on applications where the multiplicative depth of the circuit describing the cipher is the most important optimization goal.

Surprisingly, albeit many MPC/FHE/ZK-protocols natively support operations in \GF{p} for large $p$, very few primitives, even considering all of symmetric cryptography, natively work in such fields. To that end, our proposal for both block ciphers and cryptographic hash functions is to reconsider and simplify the round function of the Knudsen-Nyberg cipher from 1995. The mapping $F(x) := x^3$ is used as the main component there and is also the main component of our family of proposals called ``MiMC''. We study various attack vectors for this construction and give a new attack vector that outperforms others in relevant settings.

Due to its very low number of multiplications, the design lends itself well to a large class of new applications, especially when the depth does not matter but the total number of multiplications in the circuit dominates all aspects of the implementation. With a number of rounds which we deem secure based on our security analysis, we report on significant performance improvements in a representative use-case involving SNARKs.

Quantifying the side channel security of implementations has been a significant research question for several years in academia but also among real world side channel practitioners. As part of security evaluations, efficient key rank estimation algorithms were devised, which in contrast to analyses based on subkey recovery, give a holistic picture of the security level after a side channel attack. However, it has been observed that outcomes of rank estimations show a huge spread in precisely the range of key ranks where enumeration could lead to key recovery. These observations raise the question whether this is because of insufficient rank estimation procedures, or, if this is an inherent property of the key rank. Furthermore, if this was inherent, how could key rank outcomes be translated into practically meaningful figures, suitable to analysing the risk that real world side channel attacks pose? This paper is a direct response to these questions. We experimentally identify the key rank distribution and show that it is independent of different distinguishers and signal-to-noise ratios. Then we offer a theoretical explanation for the observed key rank distribution and determine how many samples thereof are required for a robust estimation of some key parameters. We discuss how this can be naturally integrated into real world side channel evaluation practices. We conclude our research by connecting non-parametric order statistics, in particular percentiles, in a practically meaningful way with business goals.

Post-Doc DFG Research Training Group

UbiCrypt – Cryptography in Ubiquitous Computing

The Horst Görtz Institute for IT-Security (HGI) at Ruhr-University Bochum is one of Europe’s leading research centers in IT security. The DFG, or German Research Foundation, awarded more than €4 million to the HGI for the establishment of the interdisciplinary research training group “New Challenges for Cryptography in Ubiquitous Computing”. We are looking for candidates with an outstanding Ph.D. in the fields of computer science, electrical engineering, mathematics or related areas.

The research training group will study problems which are fundamental for securing the Internet of Things. The research is structured in three levels: cryptographic primitives, device and system level. The research topics range from cryptographic foundations such as fully homomorphic encryption for privacy in cloud computing, over security for medical implants to internet security solutions involving new national ID cards.

Beside the own research, the main task of the Post-Doc is to work with the UbiCrypt Ph.D. students, and to encourage collaboration between them. Thus, an interest in working with doctoral students and a broad interest in current research are required.

- Start: earliest possible (limitation: March 31, 2017)

- Competitive salary (TV-L 14)

- Application: Send your documents by June 1, 2016, to grako (at) hgi.rub.de

- Required documents: CV, certificates (Bachelor, Master/Diplom, Ph.D.), transcripts , motivation for applying (1 page), names of at least two people who can provide reference letters (email addresses are sufficient)

A group of internationally renowned researchers together with excellent funding provides an extremely interesting scientific environment. The HGI is known for its good working atmosphere.

Closing date for applications: 1 June 2016

More information: http://www.ubicrypt.hgi.rub.de/index.html.de

Applications are invited for the post of Lecturer (teaching focussed) in the Information Security Group at Royal Holloway, University of London.

The post holder will contribute to the creation and/or revision, delivery and assessment of postgraduate (MSc) and undergraduate teaching modules across a wide range of topics in the field of information/cyber security.

Applicants should have a Ph.D. in a relevant subject or equivalent and have a sound knowledge of information/cyber security. Applicants should be able to demonstrate an enthusiasm for teaching and communicating with diverse audiences, as well as show an awareness of contemporary issues relating to cyber security.

It should be noted that teaching post holders are permitted to spend 10% of their time following their research interests.

This is a five year teaching post, available from 1st September 2016. This post is based in Egham, Surrey, where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

Closing date for applications: 12 June 2016

Contact: For an informal discussion about the post, please contact Prof. Keith Mayes on keith.mayes (at) rhul.ac.uk .

The Human Resources Department can be contacted with queries by email at: recruitment (at) rhul.ac.uk.

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0516-161