International Association
for Cryptologic Research

Arbiter Physically Unclonable Function (APUF), while being relatively lightweight, is extremely vulnerable to modeling attacks. Hence, various compositions of APUFs such as XOR APUF and Lightweight Secure PUF have been proposed to be secure alternatives. Previous research has demonstrated that PUF compositions have two major challenges to overcome: vulnerability against modeling and statistical attacks, and lack of reliability. In this paper, we introduce a multiplexer based composition of APUFs, denoted as MPUF, to simultaneously overcome these challenges. In addition to the basic MPUF design, we propose two MPUF variants namely cMPUF and rMPUF to improve robustness against cryptanalysis and reliability based modeling attack, respectively. The rMPUF demonstrates enhanced robustness against reliability based modeling attack, while even the well-known XOR APUF, otherwise robust to machine learning based modeling attacks, has been modeled using the same technique with linear data and time complexities. The rMPUF can provide a good trade-off between security and hardware overhead while maintaining a significantly higher reliability level than any practical XOR APUF instance. Moreover, MPUF variants are the first APUF compositions, to the best of our knowledge, that can achieve Strict Avalanche Criterion without any additional hardware. Finally, we validate our theoretical findings using Matlab-based simulations of MPUFs.

Inner product encryption (IPE) is a new cryptographic primitive initially proposed by Abdalla et al. in 2015. IPE can be classified into public-key IPE and secret-key IPE. The currently proposed PK-IPE schemes can-not resist the following collusion attack: an invalid user that holds no private key can ”buy” a combined key generated from multiple collusion adversaries, and the user can use this private key to decrypt a ciphertext. Furthermore, the user should not let the collusion adversaries know the ciphertext, and the collusion adversaries should not let the user learn their private keys. We present a new PK-IPE to resist such collusion attack. Our PK-IPE is proven secure under the selective-vector chosen-plaintext attack model. We formalize a selective vector collusion attack model to prove that our scheme is secure under this model.

Attribute-Based Encryption (ABE) is a special type of public key encryption that allows users to share sensitive data efficiently through fine-grained access control. The security involved in existing ABE systems is currently insufficient. These systems are usually built on the Decisional Bilinear Diffie-Hellman (DBDH) assumption or the q-type DBDH assumption, which is stronger than the DBDH assumption. However, once the DBDH assumption is unsecure, all concerned ABEs become vulnerable to threats. To address this problem, the $k$-BDH assumption family proposed by Benson et al. is adopted. Any assumption in the $k$-BDH assumption family is associated with parameter $k$ and becomes strictly weaker as $k$ increased. We propose a framework to implement Ciphertext-Policy Attribute Based Encryption (CP-ABE) under the arbitrary assumption in the $k$-BDH assumption family. When the $k'$-BDH assumption in the $k$-BDH assumption family becomes unsecure, where $k'$-BDH is the assumption on which our ABE relies, the scheme can be shifted to rely on the $l'$-BDH assumption instead, where $l'>k'$. This condition guarantees security as the underlying assumption of our scheme becomes weaker. In addition, we define the formal security model of our schemes and prove the security of CP-ABE in the selective attribute model.

We give a theoretical treatment of ratcheting, lifting it from a technique used in secure messaging protocols to a cryptographic primitive. To allow a modular treatment, we decouple the creation of keys from their use. We define ratcheted key exchange and give a protocol proven to achieve it. We then define ratcheted encryption and show how to achieve it generically from ratcheted key exchange and standard encryption.

Realistic secure processors, including those built for academic and commercial purposes, commonly realize an “attested execution” abstraction. Despite being the de facto standard for modern secure processors, the “attested execution” abstraction has not received adequate formal treatment. We provide formal abstractions for “attested execution” secure processors and rigorously explore its expressive power. Our explorations show both the expected and the surprising.

On one hand, we show that just like the common belief, attested execution is extremely powerful, and allows one to realize powerful cryptographic abstractions such as stateful obfuscation whose existence is otherwise impossible even when assuming virtual blackbox obfuscation and stateless hardware tokens. On the other hand, we show that surprisingly, realizing composable two-party computation with attested execution processors is not as straightforward as one might anticipate. Specifically, only when both parties are equipped with a secure processor can we realize composable two-party computation. If one of the parties does not have a secure processor, we show that composable two-party computation is impossible. In practice, however, it would be desirable to allow multiple legacy clients (without secure processors) to leverage a server’s secure processor to perform a multi-party computation task. We show how to introduce minimal additional setup assumptions to enable this. Finally, we show that fair multi-party computation for general functionalities is impossible if secure processors do not have trusted clocks. When secure processors have trusted clocks, we can realize fair two-party computation if both parties are equipped with a secure processor; but if only one party has a secure processor (with a trusted clock), then fairness is still impossible for general functionalities.

We present Tesla# (pronounced "Tesla Sharp"), a digital signature scheme based on the RLWE assumption that continues a recent line of proposals of lattice-based digital signature schemes originating in work by Lyubashevsky as well as by Bai and Galbraith. It improves upon all of its predecessors in that it attains much faster key pair generation, signing, and verification, outperforming most (conventional or lattice-based) signature schemes on modern processors. We propose a selection of concrete parameter sets, including a high-security instance that aims at achieving post-quantum security. Based on these parameters, we present a full-fledged software implementation protected against timing and cache attacks that supports two scheme variants: one providing 128 bits of classical security and another providing 128 bits of post-quantum security.

The linear complexity and $k$-error linear complexity of sequences are important measures of the strength of key-streams generated by stream ciphers. The counting function of a sequence complexity measure gives the number of sequences with given complexity measure value and it is useful to determine the expected value and variance of a given complexity measure of a family of sequences. Fu et al. studied the distribution of $2^n$-periodic binary sequences with 1-error linear complexity in their SETA 2006 paper and peoples have strenuously promoted the solving of this problem from $k=2$ to $k=4$ step by step. Unfortunately, it still remains difficult to obtain the solutions for larger $k$ and the counting functions become extremely complex when $k$ become large. In this paper, we define an equivalent relation on error sequences. We use a concept of \textit{cube fragment} as basic modules to construct classes of error sequences with specific structures. Error sequences with the same specific structures can be represented by a single \textit{symbolic representation}. We introduce concepts of \textit{trace}, \textit{weight trace} and \textit{orbit} of sets to build quantitative relations between different classes. Based on these quantitative relations, we propose an algorithm to automatically generate symbolic representations of classes of error sequences, calculate \textit{coefficients} from one class to another and compute \textit{multiplicity} of classes defined based on specific equivalence on error sequences. This algorithm can efficiently get the number of sequences with given $k$-error linear complexity. The time complexity of this algorithm is $O(2^{k\log k})$ in the worst case which does not depend on the period $2^n$.

Side-channel attacks put the security of the implementations of cryptographic algorithms under threat. Secret information can be recovered by analyzing the physical measurements acquired during the computations and using key recovery distinguishing functions to guess the best candidate. Several generic and model based distinguishers have been proposed in the literature. In this work we describe two contributions that lead to better performance of side-channel attacks in challenging scenarios. First, we describe how to transform the physical leakage traces into a new space where the noise reduction is near-optimal. Second, we propose a new generic distinguisher that is based upon minimal assumptions. It approaches a key distinguishing task as a problem of classification and ranks the key candidates according to the separation among the leakage traces. We also provide experiments and compare their results to those of the Correlation Power Analysis (CPA). Our results show that the proposed method can indeed reach better success rates even in the presence of significant amount of noise.

Converting a Boolean mask to an arithmetic mask, and vice versa, is often required in implementing side-channel resistant instances of cryptographic algorithms that mix Boolean and arithmetic operations. In this paper, we describe a method for converting a Boolean mask to an arithmetic mask that runs in constant time for a fixed order. We propose explicit algorithms for a second-order secure Boolean-to-arithmetic mask conversion that uses 24 instructions and for a third-order secure mask conversion that uses 56 instructions. We show that our solution is more efficient than previously proposed methods for any choice of masking-scheme order, typically by several orders of magnitude.

A covering system of congruences can be defined as a set of congruence relations of the form: $\{r_1 \pmod{m_1}, r_2 \pmod{m_2}, \dots, r_t \pmod{m_t}\}$ for $m_1, \dots, m_t \in \mathbb{N}$ satisfying the property that for every integer $k$ in $\mathbb{Z}$, there exists at least an index $i \in \{1, \dots, t\}$ such that $k \equiv r_i \pmod{m_i}$. First, we show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact \mbox{$n$-covers}, we present a novel uniformly randomized scalar multiplication algorithm with built-in protections against various types of side-channel attacks. This algorithm can be an alternative to Coron's scalar blinding technique for elliptic curves, in particular when the choice of a particular finite field tailored for speed compels to use a large random factor.

Smart metering, smart parking, health, environment monitoring, and other applications drive the deployment of the so-called Internet of Things (IoT). Whilst cost and energy efficiency are the main factors that con- tribute to the popularity of commercial devices in the IoT domain, secu- rity features are increasingly desired. Security features typically guarantee authenticity of devices and/or data, as well as confidentiality of data in transit. Our study finds that whilst cryptographic algorithms for confi- dentiality and authenticity are supported in hardware on a popular class of devices, there is no adequate support for random number generation available. We show how to passively manipulate the on-board source for randomness, and thereby we can completely undermine the security pro- vided by (otherwise) strong cryptographic algorithms, with devastating results.

For encryption schemes, key dependent message (KDM) security requires that ciphertexts preserve secrecy even when the encrypt messages may depend on the secret keys. While KDM security has been extensively studied for public-key encryption (PKE), it receives much less attention in the setting of identity-based encryption (IBE). In this work, we focus on the KDM security for IBE. Our results are threefold. \begin{itemize} \item We propose an exquisite structure-preserving PKE-to-IBE transformation via indistinguishability obfuscation and puncturable PRF. This transformation establishes a connection between PKE and IBE in general. In particular, it provides a liberal interface for transferring the KDM security results (either positive or negative) from PKE to IBE, though in the selective-identity sense.

\item On the positive side, we present two constructions that achieve KDM security in the adaptive-identity sense for the first time. One is generically built from identity-based hash proof system (IB-HPS) with homomorphic property, which indicates that the IBE schemes of Gentry (Eurocrypt 2006), Coron (DCC 2009), Chow et al. (CCS 2010) are actually KDM-secure in the multiple-key setting. The other is built from indistinguishability obfuscation and a new notion named puncturable unique signature, which is bounded KDM-secure in the single-key setting.

\item On the negative side, we separate $n$-circular security (which is a prototypical case of KDM security) from the standard IND-CPA/CCA security for IBE by giving a counterexample based on differing-inputs obfuscation and a new notion named puncturable IBE. \end{itemize}

We study the Sign_then_Encrypt, Commit_then_Encrypt_and_Sign, and Encrypt_then_Sign paradigms in the context of two cryptographic primitives, namely designated confirmer signatures and signcryption. Our study identifies weaknesses in those paradigms which impose the use of expensive encryption (as a building block) in order to meet a reasonable security level. Next, we propose some optimizations which annihilate the found weaknesses and allow consequently cheap encryption without compromising the overall security. Our optimizations further enjoy verifiability, a property profoundly needed in many real-life applications of the studied primitives.

The 3rd annual TCC Test of Time Award, is awarded to the article Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology by Ueli Maurer, Renato Renner, and Clemens Holenstein, that was published in TCC 2004.

This work received the test of time award for introducing the security notion of "indifferentiability", that had a significant impact on both the theory of cryptography and the design of practical cryptosystems.

The award will be presented on Tuesday Nov 1 at TCC 2016-B in Beijing.

Event date: 26 February 2017
Submission deadline: 1 December 2016
Notification: 21 January 2017

Event date: 1 January to 31 January 2018
Submission deadline: 22 March 2017

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

A successful candidate will explore research topics such as developing consensus protocols that allow for scalable and efficient distributed ledgers, resisting de-facto centralisation, and coming up with ledgers for a diverse set of applications that nevertheless achieve some notion of interoperability.

We expect candidates to have a PhD in Computer Science or a related field, and a strong track record in systems and network security, distributed systems, or similar topics. The position is available starting September 2016 (but the start date is negotiable) and will last for two years, with the possibility to extend by another 6-12 months.

Closing date for applications: 26 November 2016

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

More information: http://bit.ly/2dO72Yz

We are looking for post-docs (2 positions) to join our group. Candidates should have completed (or close to completing) a PhD in computer science, mathematics, or a related discipline. He/she should have solid experience in public key cryptography and provable security.

Successful candidates are expected to contribute to one of the following topics:

- accountable anonymous credentials

- applications of blockchain technology

- searchable encryption

- lattice-based cryptography

The post has a flexible starting date. The initial appointment will be for 12 months, with a strong possibility for further appointment.

Review of applications will start immediately until the positions are filled.

Closing date for applications: 1 March 2017

Contact: Man Ho Allen Au (http://www.comp.polyu.edu.hk/~csallen/)

Email: csallen (at) comp.polyu.edu.hk

We present a methodology to evaluate a Discrete Fourier Transform (DFT) on data which has been encrypted using a Somewhat Homomorphic Encryption (SHE) scheme, which is over 200 times faster than other methods. The technique utilizes the fact that the entire DFT algorithm is an algebraic operation over the underlying ring of the SHE scheme (for a suitably chosen ring). We then go on to show that the same technique can be used to perform homomorphic operations on encryptions of approximations to arbitrary complex numbers, which dramatically simplifies earlier methodologies.

Man-in-the-middle attacks in TLS due to compromised CAs have been mitigated by log-based PKI enhancements such as Certificate Transparency. However, these log-based schemes do not offer sufficient incentives to logs and monitors, and do not offer any actions that domains can take in response to CA misbehavior. We propose IKP, a blockchain-based PKI enhancement that offers automatic responses to CA misbehavior and incentives for those who help detect misbehavior. IKP’s decentralized nature and smart contract system allows open participation, offers incentives for vigilance over CAs, and enables financial recourse against misbehavior. We demonstrate through a game theoretic model and through an Ethereum prototype implementation that the incentives and increased deterrence offered by IKP are technically and economically viable.