International Association
for Cryptologic Research

High-assurance cryptography leverages methods from program verification and cryptography engineering to deliver efficient cryptographic software with machine-checked proofs of memory safety, functional correctness, cryptographic security, and side-channel protection. Traditionally, these guarantees are established under a sequential execution semantics. However, this semantics is not aligned with the behavior of modern processors that make use of speculative execution to improve performance. This mismatch, combined with the high-profile Spectre-style attacks that exploit speculative execution, may naturally cast doubts on the robustness of high-assurance cryptography guarantees. In this paper, we dispel these doubts by showing that the benefits of high-assurance cryptography extend to speculative execution, at the cost of a modest performance overhead. We build atop the Jasmin verification framework an end-to-end approach for proving properties of cryptographic software under speculative execution, and validate our approach experimentally with efficient, functionally correct, side-channel protected assembly implementations of ChaCha20 and Poly1305.

Higher-order masking countermeasures provide strong provable security against side-channel attacks at the cost of incurring significant overheads, which largely hinders its applicability. Previous works towards remedying cost mostly concentrated on ``local'' calculations, i.e., optimizing the cost of computation units such as a single AND gate or a field multiplication. This paper explores a complementary ``global'' approach, i.e., considering multiple operations in the masked domain as a batch and reducing randomness and computational cost via amortization. In particular, we focus on the amortization of $\ell$ parallel field multiplications for appropriate integer $\ell > 1$, and design a kit named {\it packed multiplication} for implementing such a batch. For $\ell+d\leq2^m$, when $\ell$ parallel multiplications over $\mathbb{F}_{2^{m}}$ with $d$-th order probing security are implemented, packed multiplication consumes $d^2+2\ell d + \ell$ bilinear multiplications and $2d^2 + d(d+1)/2$ random field variables, outperforming the state-of-the-art results with $O(\ell d^2)$ multiplications and $\ell \left \lfloor d^2/4\right \rfloor + \ell d$ randomness. To prove $d$-probing security for packed multiplications, we introduce some weaker security notions for multiple-inputs-multiple-outputs gadgets and use them as intermediate steps, which may be of independent interest. As parallel field multiplications exist almost everywhere in symmetric cryptography, lifting optimizations from ``local'' to ``global'' substantially enlarges the space of improvements. To demonstrate, we showcase the method on the AES Subbytes step, GCM and TET (a popular disk encryption). Notably, when $d=8$, our implementation of AES Subbytes in ARM Cortex M architecture achieves a gain of up to $33\%$ in total speeds and saves up to $68\%$ random bits than the state-of-the-art bitsliced implementation reported at ASIACRYPT~2018.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computers attacks like Shor and Grover algorithms. In this paper, we propose a method for designing post-quantum provable IND-CPA/IND-CCA2 public key cryptosystems based on polynomials over a non-commutative algebraic extension ring. The key ideas of our proposal is that (a) for a given non-commutative ring of rank-3 tensors, we can define polynomials and take them as the underlying work structure (b) we replace all numeric field arithmetic with GF(2^8) field operations. By doing so, it is easy to implement R-propped Diffie-Helman-like key exchange protocol and consequently ElGamal-like cryptosystems. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span or Roman’kov. The protocols have been proved to be semantically secure. Finally, we present numerical examples of the proposed R-Propped protocols.

First implemented in Bitcoin, Nakamoto Consensus (NC) is the most influential consensus protocol in cryptocurrencies despite all the alternative protocols designed afterward. Nevertheless, NC is trapped with a security-performance tradeoff, largely limiting the latter. In this paper, we propose NC-Max, a consensus protocol that breaks the throughput limit and enables the full utilization of the nodes' bandwidth in confirming transactions. In particular, after identifying the mechanism through which NC's security limits its performance, we decouple transaction synchronization from confirmation with a two-step mechanism, relieving the limits on the block size and the block interval. Further, we introduce an accurate dynamic difficulty adjustment mechanism to explore the real-time network condition and to adjust the protocol's throughput accordingly. We analyze the security of NC-Max, proving that it resists selfish mining and transaction withholding attacks better than NC does. Our performance evaluation shows that NC-Max not only fully exploits the nodes' bandwidth to confirm transactions, but also shortens the overall transaction confirmation latency by at least a factor of four compared to NC without compromising security.

Reducing the rounds of interaction in secure multiparty computation (MPC) protocols has been the topic of study of many works. One popular approach to reduce rounds is to construct *round compression compilers*. A round compression compiler is one that takes a highly interactive protocol and transforms it into a protocol with far fewer rounds. The design of round compression compilers has traditionally focused on preserving the security properties of the underlying protocol and in particular, not much attention has been given towards preserving their computational and communication efficiency. Indeed, the recent round compression compilers that yield round-optimal MPC protocols incur large computational and communication overhead.

In this work, we initiate the study of *efficiency-preserving* round compression compilers, i.e. compilers that translate the efficiency benefits of the underlying highly interactive protocols to the fewer round setting. Focusing on the honest majority setting (with near-optimal corruption threshold $\frac{1}{2} - \varepsilon$, for any $\varepsilon > 0$), we devise a new compiler that yields two round (i.e., round optimal) semi-honest MPC with similar communication efficiency as the underlying (arbitrary round) protocol. By applying our compiler on the most efficient known MPC protocols, we obtain a two-round semi-honest protocol based on one-way functions, with total communication (and per-party computation) cost $\widetilde{O}(s+n^4)$ -- a significant improvement over prior two-round protocols with cost $\widetilde{O}(n^\tau s+n^{\tau+1}d)$, where $\tau\geq 2$, $s$ is the size of the circuit computing the function and $d$ the corresponding depth. Our result can also be extended to handle malicious adversaries, either using stronger assumptions in the public key infrastructure (PKI) model, or in the plain model using an extra round.

An artifact of our approach is that the resultant protocol is ``unbalanced'' in the amount of computation performed by different parties. We give evidence that this is *necessary* in our setting. Our impossibility result makes novel use of the ``MPC-in-the-head" paradigm which has typically been used to demonstrate feasibility results.

We propose the first tightly secure and unbounded hierarchical identity-based encryption (HIBE) scheme based on standard assumptions. Our main technical contribution is a novel proof strategy that allows us to tightly randomize user secret keys for identities with arbitrary hierarchy depths using low entropy hidden in a small and hierarchy-independent master public key.

The notion of unbounded HIBE is proposed by Lewko and Waters (Eurocrypt 2011). In contrast to most HIBE schemes, an unbounded scheme does not require any maximum depth to be specified in the setup phase, and user secret keys or ciphertexts can be generated for identities of arbitrary depths with hierarchy-independent system parameters.

While all the previous unbounded HIBE schemes have security loss that grows at least linearly in the number of user secret key queries, the security loss of our scheme is only dependent on the security parameter, even in the multi-challenge setting, where an adversary can ask for multiple challenge ciphertexts. We prove the adaptive security of our scheme based on the Matrix Decisional Diffie-Hellman assumption in prime-order pairing groups, which generalizes a family of standard Diffie-Hellman assumptions such as k-Linear.

Bitcoin has introduced an open and decentralized consensus mechanism which in combination with an append-only ledger allows building so-called blockchain systems, often instantiated as permissionless cryptocurrencies. Bitcoin is surprisingly successful and its market capitalization has reached about 168 billion USD as of July 2020. Due to its high economic value, it became a lucrative target and the growing community has discovered various attacks, proposed promising improvements, and introduced contingency plans for handling catastrophic failures. Nonetheless, existing analysis and contingency plans are not formalized and are tailored only to handle a small specific subset of diverse attacks, and as such, they cannot resist unexpected emergency cases and it is hard to reason about their effectiveness and impact on the system. In this work, we provide a formalized framework to help evaluate a variety of attacks and their mitigations. The framework is based upon the universal composability (UC) framework to describe the attacker's power and the system's security goals. We propose the system in the context of Bitcoin and to the best of our knowledge, no similar work has been proposed previously. Besides, we demonstrate and evaluate our model with different case studies from the real world. Finally, we signal remaining challenges for the contingency plans and their formalization.

In EUROCRYPT '96, Aiello and Venkatesan proposed two candidates for $ 2n $-bit to $ 2n $-bit pseudorandom functions (PRFs), called Benes and modified Benes (or mBenes), based on $ n $-bit to $ n $-bit PRFs. While Benes is known to be secure up to $ 2^n $ queries (Patarin, AFRICACRYPT '08), the security of mBenes has only been proved up to $ 2^{n(1-\epsilon)} $ queries for all $ \epsilon > 0 $ by Patarin and Montreuil in ICISC '05. In this work, we show that the composition of a $ 2n $-bit hash function with mBenes is a secure variable input length (VIL) PRF up to $ 2^{n-2} $ queries (given appropriate hash function bounds). We extend our analysis with block ciphers as the underlying primitive and obtain two optimally secure VIL PRFs using block ciphers. The first of these candidates requires $ 6 $ calls to the block cipher. The second candidate requires just $ 4 $ calls to the block cipher, but here the proof is based on Patarin's mirror theory. Further, we instantiate the hash function with a PMAC+/LightMAC+ like hash, to get six candidates for deterministic message authentication codes with optimal security.

We present the first deep learning-based side-channel attack on AES-128 using far field electromagnetic emissions as a side channel. Our neural networks are trained on traces captured from five different Bluetooth devices at five different distances to target and tested on four other Bluetooth devices. We can recover the key from less than 10K traces captured in an office environment at 15 m distance to target even if the measurement for each encryption is taken only once. Previous template attacks required multiple repetitions of the same encryption. For the case of 1K repetitions, we need less than 400 traces on average at 15 m distance to target. This improves the template attack presented at CHES'2020 which requires 5K traces and key enumeration up to $2^{23}$.

This article gives a rigorous mathematical treatment of generalized and closed loop invariants (CLI) which extend the standard notion of (nonlinear) invariants used in the cryptanalysis of block ciphers. Employing the cycle structure of bijective S-box components, we precisely characterize the cardinality of both generalized and CLIs. We demonstrate that for many S-boxes used in practice quadratic invariants (especially useful for mounting practical attacks in cases when the linear layer is an orthogonal matrix) might not exist, whereas there are many quadratic invariants of generalized type (alternatively quadratic CLIs). In particular, it is shown that the inverse mapping $S(x)=x^{-1}$ over $GF(2^4)$ admits quadratic CLIs that additionally possess linear structures. The use of cycle structure is further refined through a novel concept of active cycle set, which turns out to be useful for defining invariants of the whole substitution layer. We present an algorithm for finding such invariants provided the knowledge about the cycle structure of the constituent S-boxes used.

Routing protocol for Low power and lossy network (RPL) is a standardized optimal protocol for routing in Internet of Things (IoT). The constrained wireless sensor network in IoT is characterized by lack of processing speed, low power and low memory. Sometimes various network attacks enabling the RPL network affect the network performance dismally. This leads to drastic variation in energy consumption at nodes and disturb the RPL network protocol structure. This leads to reduced processing speed and memory allocation in the network. We first illustrate the attacks and their impact in RPL network by simulation. To detect such attacks, we propose an Intrusion Detection System (IDS) scheme for RPL network based on trust computation. Trust based Neighbor notification IDS (TN-IDS) is a secure hierarchical distribution system which monitors the network intrusion and checks the performance of the network. The new TN-IDS system will track all nodes in the network and identify the malicious nodes. The activity list prepared by IDS indicates them to a sink node. This is achieved by introducing a distributed leader election algorithm to collect metrics related to the RPL network. Hence, the performance metrics of the RPL network together with TN-IDS module can identify the malicious node and isolate them.

Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations. Thus, unlike previous methods which focus on the propagation of the difference or $s$-difference, we redefine the impossible differentials and impossible $(s+1)$-polytopic transitions according to the propagation of state, which allow us to break through those limitations of the previous methods. Theoretically, we prove that traditional impossible differentials and impossible $(s+1)$-polytopic transitions are equivalent to part of our redefinitions, which have advantages from broader view. Technically, we renew the automatic search model and design an SAT-based tool to evaluate our redefined impossible differentials and impossible $(s+1)$-polytopic transitions efficiently. As a result, for GIFT64, we get the $6$-round impossible differentials which cannot be detected by all previous tools. For PRINTcipher, we propose the first modeling method for the key-dependent permutation and key-dependent S-box. For MISTY1, we derive 902 4-round impossible differentials by exploiting the differential property of S-boxes. For RC5, we present the first modeling method for the variable rotation and get 2.5-round impossible differentials for each version of it. More remarkable, our tool can be used to evaluate the security of given cipher against the impossible differentials, and we prove that there exists no 5-round 1 input active word and 1 output active word impossible differentials for AES-128 even consider the relations of 3-round keys. Besides, we also get the impossible $(s+1)$-polytopic transitions for PRINTcipher, GIFT64, PRESENT, and RC5, all of which can cover more rounds than their corresponding impossible differentials as far as we know.

We investigate the exact round complexity of secure multiparty computation (MPC) against *covert* adversaries who may attempt to cheat, but do not wish to be caught doing so. Covert adversaries lie in between semi-honest adversaries who follow protocol specification and malicious adversaries who may deviate arbitrarily.

Recently, two round protocols for semi-honest MPC and four round protocols for malicious-secure MPC were constructed, both of which are optimal. While these results can be viewed as constituting two end points of a security spectrum, we investigate the design of protocols that potentially span the spectrum.

Our main result is an MPC protocol against covert adversaries with variable round complexity: when the detection probability is set to the lowest setting, our protocol requires two rounds and offers same security as semi-honest MPC. By increasing the detecting probability, we can increase the security guarantees, with round complexity five in the extreme case. The security of our protocol is based on standard cryptographic assumptions.

We supplement our positive result with a negative result, ruling out *strict* three round protocols with respect to black-box simulation.

The CAP theorem says that no blockchain can be live under dynamic participation and safe under temporary network partitions. To resolve this availability-finality dilemma, we formulate a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. The finalized ledger falls behind the full ledger when the network partitions but catches up when the network heals. Gasper, the current candidate protocol for Ethereum 2.0's beacon chain, combines the finality gadget Casper FFG with the LMD GHOST fork choice rule and aims to achieve this property. However, we discovered an attack in the standard synchronous network model, highlighting a general difficulty with existing finality-gadget-based designs. We present a construction of provably secure ebb-and-flow protocols with optimal resilience. Nodes run an off-the-shelf dynamically available protocol, take snapshots of the growing available ledger, and input them into a separate off-the-shelf BFT protocol to finalize a prefix. We explore connections with flexible BFT and improve upon the state-of-the-art for that problem.

We consider the security of two of the most commonly used cryptographic primitives—message authentication codes (MACs) and pseudorandom functions (PRFs)—in a multi-user setting with adaptive corruption. Whereas is it well known that any secure MAC or PRF is also multi-user secure under adaptive corruption, the trivial reduction induces a security loss that is linear in the number of users. Our main result shows that black-box reductions from “standard” assumptions cannot be used to provide a tight, or even a linear-preserving, security reduction for adaptive multi-user secure deterministic stateless MACs and thus also PRFs. In other words, a security loss that grows with the number of users is necessary for any such black-box reduction.

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: SPIX and SpoC. We improve the number of rounds with respect to the previously known best results. We improve the techniques used for solving the inbound part and we relax the output conditions in order to extend the previous attacks.

The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

We propose a generic construction of 2-pass authenticated key exchange (AKE) scheme with explicit authentication from key encapsulation mechanism (KEM) and signature (SIG) schemes. We improve the security model due to Gjosteen and Jager [Crypto2018] to a stronger one. In the strong model, if a replayed message is accepted by some user, the authentication of AKE is broken. We define a new security notion named ''IND-mCPA with adaptive reveals'' for KEM. When the underlying KEM has such a security and SIG has unforgeability with adaptive corruptions, our construction of AKE equipped with counters as states is secure in the strong model, and stateless AKE without counter is secure in the traditional model. We also present a KEM possessing tight ''IND-mCPA security with adaptive reveals'' from the Computation Diffie-Hellman assumption in the random oracle model. When the generic construction of AKE is instantiated with the KEM and the available SIG by Gjosteen and Jager [Crypto2018], we obtain the first practical 2-pass AKE with tight security and explicit authentication. In addition, the integration of the tightly IND-mCCA secure KEM (derived from PKE by Han et al. [Crypto2019]) and the tightly secure SIG by Bader et al. [TCC2015] results in the first tightly secure 2-pass AKE with explicit authentication in the standard model.

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth.

In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (ePrint, 2020). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters' sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the $k$-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.'s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.'s scheme in the sense of the sizes of master public/secret keys.

The Department of Computer Science at the University of Surrey is seeking to recruit a full-time researcher to the Surrey Centre for Cyber Security.

The successful candidate will work on cyber security for Decentralisation in the Digital Economy through technologies such as Distributed Ledgers, and with a focus on self-sovereign identity and the human focused aspects of cyber security.

The project will concentrate on developing protocols and architectures for cyber security in decentralized systems for content provenance and content brokering, the initial scenarios to be considered by the project, and builds on Surrey’s previous work on Distributed Ledger Technologies. The project is within the new multidisciplinary and collaborative EPSRC DE Centre in the Decentralised Digital Economy led by Surrey.

The Department of Computer Science within the Faculty of Engineering and Physical Sciences has an international reputation for research and teaching. Security research in the department is focused within the Surrey Centre for Cyber Security, with Surrey recognized by the National Cyber Security Centre as an Academic Centre of Excellence in Cyber Security Research. Our research concentrates on protocol analysis, security verification, trusted computing, data privacy, access control, privacy preserving security, cryptography, distributed ledger technologies, digital forensics and human-centred computing.

The position offers the platform for the research fellow to work within a group and develop skills to become an independent researcher. The successful candidate will work under the direction of Professor Steve Schneider. The project is also collaborative with other Surrey research centres, with the University of Edinburgh and with the Digital Catapult.

We are looking for applicants that demonstrate strong research and analytical skills, have strong communication skills and enthusiasm for developing their own research ideas. Applicants should also have skills in software engineering for web applications, and an understanding of cyber security. Knowledge of Distributed Ledger Technologies would be an advantage

Closing date for applications:

Contact: Professor Steve Schneider: s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=035220

The 2020 TCC Test-of-Time Award goes to  Zuzana Trubini and Martin Hirt, for their TCC 2008 paper "Perfectly-Secure MPC with Linear Communication Complexity ". 

The award committee recognizes this paper “for introducing hyper-invertible matrices to perfectly secure multiparty computation, thus enabling significant efficiency improvements and, eventually, constructions with minimal communication complexity." 

The TCC Test of Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other areas of cryptography, theory, and beyond. The inaugural TCC Test of Time Award was given in TCC 2015 for papers published no later than TCC 2007.