International Association
for Cryptologic Research

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.

In 2013, Tao et al. introduced the ABC Simple Matrix Encryption Scheme, a multivariate public key encryption scheme. The scheme boasts great efficiency in encryption and decryption, though it suffers from very large public keys. It was quickly noted that the original proposal, utilizing square matrices, suffered from a very bad decryption failure rate. As a consequence, the designers later published updated parameters, replacing the square matrices with rectangular matrices and altering other parameters to avoid the cryptanalysis of the original scheme presented in 2014 by Moody et al.

In this work, we show that making the matrices rectangular, while decreasing the decryption failure rate, actually, and ironically, diminishes security. We show that the combinatorial rank methods employed in the original attack of Moody et al. can be enhanced by the same added degrees of freedom that reduce the decryption failure rate. Moreover, and quite interestingly, if the decryption failure rate is still reasonably high, as exhibited by the proposed parameters, we are able to mount a reaction attack to further enhance the combinatorial rank methods. To our knowledge this is the first instance of a reaction attack creating a significant advantage in this context.

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with an attribute vector and a receiver holding a secret-key associated to a predicate vector can recover the message from the ciphertext if the inner product between the attribute and predicate vectors is non-zero. The main focus is to hide messages in most of the existing NIPEs and the associated attribute is trivially included in the ciphertext. In this work, we investigate the design of NIPEs that are capable of hiding attributes along with messages and secure against active adversaries. In particular, we describe a generic ransformation of an attribute-hiding chosen-ciphertext attack (CCA) secure NIPE from an inner product functional encryption (IPFE) and a quasi-adaptive non-interactive zero-knowledge (QANIZK) proof system. This leads us to a set of attribute-hiding NIPEs (AHNIPE) with security based on several assumptions such as plain Decisional Diffie-Hellman (DDH), Learning With Errors (LWE) and Decision Composite Reciprocity (DCR). Furthermore, we build a more efficient and concrete construction of a CCA secure AHNIPE the security of which can be based on DDH and Kernel Matrix Diffie-Hellman (KerMDH) assumptions. As DDH implies the computational KerMDH assumption, the latter construction achieves a CCA secure AHNIPE from minimal assumption to date. We explore a few applications of AHNIPE. More specifically, we show that AHNIPE directly implies an anonymous identity-based revocation (IBR) scheme. Consequently, we get the first CCA secure IBR solely based on plain DDH assumption in the standard model, improving the security of any previous anonymous CCA secure IBR scheme which is proven secure relying on pairing-based assumptions in the random oracle model. Moreover, we add a tracing algorithm to our anonymous IBR scheme to convert it into an efficient anonymous trace and revoked scheme with CCA security.

Chameleon-hashes are collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash can be found. Recently, Derler et al. (PKC '20) introduced the notion of fully collision-resistant chameleon-hashes. Full collision-resistance requires the intractability of finding collisions, even with full-adaptive access to a collision-finding oracle. Their construction combines simulation-sound extractable (SSE) NIZKs with perfectly correct IND-CPA secure public-key encryption (PKE) schemes.

We show that, instead of perfectly correct PKE, non-interactive commitment schemes are sufficient. For the first time, this gives rise to efficient instantiations from plausible post-quantum assumptions and thus candidates of chameleon-hashes with strong collision-resistance guarantees and long-term security guarantees. On the more theoretical side, our results relax the requirement to not being dependent on public-key encryption.

Event date: 11 December 2020
Submission deadline: 2 October 2020
Notification: 23 October 2020

**Senior Cryptography Researchers have a responsibility to help grow NCC Group Cryptography Services. They will be key contributors to project delivery and research (we have an entire division dedicated to Research and your bonus includes doing research during company hours) at NCC Group Cryptography Services. **Activities and Responsibilities (include): • Delivery of consultancy projects within Cryptography Services • Research and tool development in Cryptography Services • External delivery of client-facing and public speaking events in Cryptography Services • Assistance with sales support for Cryptography Services • Mentoring and leadership for staff at NCC Group **Skills and Experience: Blockchain Security experience is a requirement. The amount of experience with this is flexible. Minimum of five (5) years of experience in Cryptography disciplines with focus areas including some of the following: • Cryptographic Analysis and Review • Elliptic Curve Cryptography • Finite Field Cryptography • Symmetric Cryptography and Hashes • Post-quantum Cryptography • Cryptanalysis of Novel Cryptosystems • Implementation Review of Cryptographic Primitives • Key Management Design and Implementation Review

Closing date for applications:

Contact: Danielle Owen

More information: https://nccgroup.wd3.myworkdayjobs.com/NCC_Group/job/USA-Remote---Eastern-Time/Senior-Cryptography-Researcher_R3223

We are looking for a PhD student and a Post-Doc in the area of (applied crypto) and/or side-channels.

The PhD post can be in any (fun) area of crypto; the candidate will be supervised by Elisabeth Oswald, and as co-supervisors A. Roy and E. Andreeva are potentially available.

The Post-Doc is related to ERC funding and therefore will work in the area of side channels; our areas of interest here are techniques for secure software development, and RISC-V.

Both posts are available immediately. The salary is around 32k per annum for the PhD student and 35k upwards (depending on prior experience) for the Post-Doc. Further information about the group is under www.cybersecurityresearch.at

Closing date for applications:

Contact: Elisabeth Oswald (firstname.lastname@aau.at)

More information: http://www.cybersecurityresearch.at