International Association
for Cryptologic Research

Event date: 11 February to 13 February 2021
Submission deadline: 14 September 2020
Notification: 12 November 2020

We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for large enough dimensions $\ell$. The algorithm implies polynomial-time attacks against blind signatures such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as the one from GJKR (when concurrent executions are allowed), and multisignatures such as CoSI and the two-round version of MuSig.

Conflict-free Replicated Data Types (CRDTs) are abstract data types that support developers when designing and reasoning about distributed systems with eventual consistency guarantees. In their core they solve the problem of how to deal with concurrent operations, in a way that is transparent for developers. However in the real world, distributed systems also suffer from other relevant problems, including security and privacy issues and especially when participants can be untrusted.

In this paper we present the first formal cryptographic treatment of CRDTs, as well as proposals for secure implementations. We start by presenting a security notion that is compatible with standard definitions in cryptography. We then describe new privacy-preserving CRDT protocols that can be used to help secure distributed cloud-backed applications, including NoSQL geo-replicated databases. Our proposals are based on standard CRDTs, such as sets and counters, augmented with cryptographic mechanisms that allow operations to be performed on encrypted data.

Our proposals are accompanied with formal security proofs and implement and integrate them in AntidoteDB, a geo-replicated NoSQL database that leverages CRDTs for its operations. Experimental evaluations based on the Danish Shared Medication Record dataset (FMK) exhibit the tradeoffs that our different proposals make and show that they are ready to be used in practical applications.

Sharding is considered one of the most promising approaches to solve the scalability issue of permissionless blockchains. In a sharding design, participants are split into groups, called shards, and each shard only executes part of the workloads. Despite its wide adoption in permissioned systems, where participants are fixed and known to everyone, transferring such success to permissionless blockchains is challenging, as it is difficult to allocate participants to different shards uniformly. Specifically, in a permissionless network, participants may join and leave the system at any time, and there can be a considerable number of Byzantine participants.

This paper focuses on the shard allocation protocols designed for permissionless networks. We start from formally defining the shard allocation protocol, including its syntax, correctness properties, and performance metrics. Then, we apply this framework to evaluate the shard allocation subprotocols of seven state-of-the-art sharded blockchains. Our evaluation shows that none of them is fully correct or achieves satisfactory performance. We attribute these deficiencies to their redundant security assumptions and their extreme choices between two performance metrics: self-balance and operability. We further prove a fundamental trade-off between these two metrics, and prove that shard allocation should be non-memoryless in order to parametrise this trade-off. Non-memorylessness specifies that each shard allocation does not only rely on the current and the incoming system states, but also previous system states. Based on these insights, we propose WORMHOLE, a non-memoryless shard allocation protocol that minimises security assumptions and allows parametrisation between self-balance and operability. We formally prove WORMHOLE’s correctness, and show that WORMHOLE outperforms existing shard allocation protocols.

Generating randomness collectively has been a long standing problem in distributed computing. It plays a critical role not only in the design of state-of-the-art BFT and blockchain protocols, but also for a range of applications far beyond this field. We present RandRunner, a random beacon protocol with a unique set of guarantees that targets a realistic system model. Our design avoids the necessity of a (Byzantine fault-tolerant) consensus protocol and its accompanying high complexity and communication overhead. We achieve this by introducing a novel extension to verifiable delay functions (VDFs) in the RSA setting that does not require a trusted dealer or distributed key generation (DKG) and only relies on well studied cryptographic assumptions. This design allows RandRunner to tolerate adversarial or failed leaders while guaranteeing safety and liveness of the protocol despite possible periods of asynchrony.

Grover’s search algorithm allows a quantum adversary to find a k-bit secret key of a block cipher by making O(2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the T-depth of its circuit implementation (time) and the number of qubits used by the circuit (space). Since the AES S-box is the only component which requires T-gates in the quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low T-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose seven methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular,one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its T-depth.

Attribute-based encryption (ABE) is a promising type of cryptosystem achieving fine-grained access control on encrypted data. Revocable attribute-based encryption (RABE) is an extension of ABE that provides revocation mechanisms when user's attributes change, key exposure, and so on. In this paper, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from lattices, which support flexible threshold access policies on multi-valued attributes, achieving user-level and attribute-level user revocation, respectively. Specifically, the revocation list is defined and embedded into the ciphertext by the message sender to revoke a user in the user-level revocable scheme or revoke some attributes of a certain user in the attribute-level revocable scheme. We also discuss how to outsource decryption and reduce the workload for the end user. Our schemes are proved to be secure in the standard model, assuming the hardness of the learning with errors (LWE) problem.

Recently, research on deep learning based side-channel analysis (DLSCA) has received a lot of attention. Deep learning-based profiling methods similar to template attacks as well as non-profiling-based methods similar to differential power analysis have been proposed. DLSCA methods have been proposed for targets to which masking schemes or jitter-based hiding schemes are applied. However, most of them are methods for finding the secret key, except for methods for preprocessing, and there are no studies on the target to which the dummy-based hiding schemes or shuffling schemes are applied. In this paper, we propose a DLSCA for detecting dummy operations. In the previous study, dummy operations were detected using the method called BCDC, but there is a disadvantage in that it is impossible to detect dummy operations for commercial devices such as an IC card. We consider the detection of dummy operations as a multi-label classification problem and propose a deep learning method based on CNN to solve it. As a result, it is possible to successfully perform detection of dummy operations on an IC card, which was not possible in the previous study.

The 2020 election is being held to fill the three IACR Director positions currently held by Masayuki Abe, Tancrède Lepoint, and Moti Yung, whose 3-year terms are ending.

Nominations are due by September 24, 2020.
Information about nomination is available at https://iacr.org/elections/2020/announcement.html.

Revelio (CVCBT 2019) is a proof of reserves protocol for MimbleWimble-based cryptocurrencies which provides privacy to a cryptocurrency exchange by hiding the exchange-owned outputs in a larger anonymity set of unspent outputs. A drawback of Revelio is that the proof size scales linearly in the size of the anonymity set. To alleviate this, we design RevelioBP, a Bulletproofs-based proof of reserves protocol with proof sizes which scale logarithmically in the size of the anonymity set. This improvement allows us to use the set of all UTXOs as the anonymity set, resulting in better privacy for the exchange. On the downside, the higher proof generation and verification time of RevelioBP than that of Revelio might affect practical deployment of RevelioBP. Through implementation of RevelioBP, we quantitatively analyse trade-offs in design of MimbleWimble proofs of reserves in terms of scalability and performance. We conclude that unless proof size is a concern for exchanges, Revelio is a marginally better choice for proof of reserves. On the other hand, if an exchange is willing to pay in terms of proof generation time, RevelioBP offers proof sizes significantly smaller than Revelio.

Electromagnetic Fault Injection (EMFI) is a well-known technique for performing fault injection attacks. While such attacks may be easy demonstrated in a laboratory condition, the applicability of them to real-life environments is required to understand how concerned about EMFI designers of systems should be. This work targets a recent (2019) automotive ECU, and analyzes the target microcontroller used in laboratory conditions, and then transitions the attack to a real-world “in-situ” attack.

The specific work appears relevant to several devices in the MPC55xx and MPC56xx series, which are automotive-focused PowerPC devices.

Recently, He et al. proposed an anonymous authentication for wireless body area networks and prove that their scheme is secure in the random oracle model. In this paper, we cryptanalysis the He et al.’s scheme and design an attack model against their scheme, in which adversary replaces a user’s public key with a value of his choice and prove a key replacement attack besides client anonymity. Thus, their scheme is insecure and not suitable for implementing a secure WBAN system. Further, we point out a solution to improve their scheme.

The outbreak of coronavirus disease 2019 (covid-19) is imposing a severe worldwide lock-down. Contact tracing based on smartphones' applications (apps) has emerged as a possible solution to trace contagions and enforce a more sustainable selective quarantine. However, a massive adoption of these apps is required to reach the critical mass needed for effective contact tracing. As an alternative, geo-location technologies in next generation networks (e.g., 5G) can enable Mobile Operators (MOs) to perform passive tracing of users' mobility and contacts with a promised accuracy of down to one meter. To effectively detect contagions, the identities of positive individuals, which are known only by a Governmental Authority (GA), are also required. Note that, besides being extremely sensitive, these data might also be critical from a business perspective. Hence, MOs and the GA need to exchange and process users' geo-locations and infection status data in a privacy-preserving manner. In this work, we propose a privacy-preserving protocol that enables multiple MOs and the GA to share and process users' data to make only the final users discover the number of their contacts with positive individuals. The protocol is based on existing privacy-enhancing strategies that guarantee that users' mobility and infection status are only known to their MOs and to the GA, respectively. From extensive simulations, we observe that the cost to guarantee total privacy (evaluated in terms of data overhead introduced by the protocol) is acceptable, and can also be significantly reduced if we accept a negligible compromise in users' privacy.

We present CanDID, a platform for practical, user-friendly realization of decentralized identity, the idea of empowering end users with management of their own credentials.

While decentralized identity promises to give users greater control over their private data, it burdens users with management of private keys, creating a significant risk of key loss. Existing and proposed approaches also presume the spontaneous availability of a credential-issuance ecosystem, creating a bootstrapping problem. They also omit essential functionality, like resistance to Sybil attacks and the ability to detect misbehaving or sanctioned users while preserving user privacy.

CanDID addresses these challenges by issuing credentials in a user-friendly way that draws securely and privately on data from existing, unmodified web service providers. Such legacy compatibility similarly enables CanDID users to leverage their existing online accounts for recovery of lost keys. Using a decentralized committee of nodes, CanDID provides strong confidentiality for user's keys, real-world identities, and data, yet prevents users from spawning multiple identities and allows identification (and blacklisting) of sanctioned users.

We present the CanDID architecture and its technical innovations and report on experiments demonstrating its practical performance.

We show two new results about instantiability of the classical random-oracle-model encryption transforms for upgrading ``weak'' trapdoor permutations and encryption to ``strong'' chosen-ciphertext (CCA) secure encryption, namely the OAEP trapdoor permutation based (Bellare and Rogaway, EUROCRYPT 1994) and Fujasaki Okamoto (FO) hybrid-encryption (EUROCRYPT 1998) transforms: - First, we propose a slight tweak to FO so that achieves the same goal in the RO model, but it is not ``admissible'' in the sense of Brzuska et al. (TCC 2015) and thus their uninstantiability result does not apply. We then show this modified transform is fully instantiable using extractable hash functions. - Second, we show that OAEP is partially instantiable using extractability assumptions on the round function when trapdoor permutation is partially one-way. This improves the prior work by Cao et al. (PKC 2020) who showed weaker results. This shed light on ``why'' RSA-OAEP may be secure whereas there exists one-way trapdoor permutations for which the OAEP transform fails (Shoup, J. Cryptology 2002).

ABSTRACT In 2017, D. Ezhilmaran & V. Muthukumaran (E&M [1]) have proposed key agreement protocols based on twisted conjugacy search problem in Near – ring and they have claimed that one can extend 3 party key agreement protocol (3PKAP) to any number of parties. Unfortunately their protocol is not an extension of 3PKAP and we present this weakness in this paper. We also show that their proposed 3PKAP is practically infeasible. Their protocol is not extendable to large number of parties like in banking system where number of parties is high. To overcome this problem we present an improved (or corrected) version of 3PKAP and for better understanding we extend it into 4PKAP with improvements in terms of number of passes, rounds, time complexity and run time.

KEYWORDS Data communication, Key agreement, Near – ring, Twisted Conjugacy Search Problem (TCSP)

String search finds occurrences of patterns in a larger text. This general problem occurs in various application scenarios, f.e. Internet search, text processing, DNA analysis, etc. Using somewhat homomorphic encryption with SIMD packing, we provide an efficient string search protocol that allows to perform a private search in outsourced data with minimal preprocessing. At the base of the string search protocol lies a randomized homomorphic equality circuit whose depth is independent of the pattern length. This circuit not only improves the performance but also increases the practicality of our protocol as it requires the same set of encryption parameters for a wide range of patterns of different lengths. This constant depth algorithm is about 10 times faster than the prior work. It takes about 5 minutes on an average laptop to find the positions of a string with at most 50 UTF-32 characters in a text with 1000 characters. In addition, we provide a method that compresses the search results, thus reducing the communication cost of the protocol. For example, the communication complexity for searching a string with 50 characters in a text of length 10000 is about 347 KB and 13.9 MB for a text with 1000000 characters.

Secure, efficient execution of AES is an essential requirement for most computing platforms. Dedicated Instruction Set Extensions (ISEs) are often included for this purpose. RISC-V is a (relatively) new ISA that lacks such a standardised ISE. We survey the state-of-the-art industrial and academic ISEs for AES, implement and evaluate five different ISEs, one of which is novel, and make recommendations for standardisation. We consider the side-channel security implications of the ISE designs, demonstrating how an implementation of one candidate ISE can be hardened against DPA-style attacks. We also explore how the proposed standard Bit-manipulation extension to RISC-V can be harnessed for efficient implementation of AES-GCM. Our work supports the ongoing RISC-V cryptography extension standardisation process.

The post holder will work with Prof. Mark Ryan, Dr Flavio Garcia and Dr David Oswald on the EPSRC project ‘User-controlled hardware security anchors: evaluation and designs’, part of the EPSRC/NCSC Research Institute in Hardware Security and Embedded Systems (RISE). Many modern processors are equipped with hardware extensions that allow one to set up a "trusted execution environment" (TEE). This allows programs to run securely, with protection from other programs or operating system software running on the processor. TEEs are an attractive way to provide software implementations (e.g. for user authentications) with security similar to pure hardware realisation. There is a variety of TEE-supporting hardware extensions, with a similar variety of security assumptions, threat models, and potential attack vectors. The project has two parts. The first part is to evaluate actual and potential TEE systems, and point out security weaknesses. The second part is to devise ways of using TEEs in applications, focusing on user authentication applications. HP Labs (formerly known as Hewlett Packard) is a partner on the project and is actively involved in the research. Therefore, the successful applicant will have the opportunity of working with colleagues from HP Labs. The successful candidate will be based at the School of Computer Science as part of the Centre for Cyber Security and Privacy and will be working closely with Professor Mark Ryan. The centre is recognised by NCSC and EPSRC as an Academic Centre of Excellence in Cyber Security Research.

Closing date for applications:

Contact: Mark Ryan

More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=200001T9&tz=GMT%2B01%3A00&tzname=Europe%2FLondon

Thanks to a collaborative project between The Applied Cryptography Group at ETH Zurich and the London-based startup Crypto Quantique, there are openings for Cryptography researchers with both institutions. The project is funded by Eureka Eurostars.

The Project Crypto Quantique’s role is to develop a novel Key Provisioning Architecture (KPA) for the generation, distribution, and certification of cryptographic keys used by lnternet of Things (IoT) devices and cloud services. The aim is to build a quantum-driven security platform by combining the KPA with cryptographic keys generated through quantum tunnelling behaviour in semiconductor devices. The Applied Cryptography Group’s main role in the project is to lead an investigation of how to transition Crypto Quantique’s KPA to use post-quantum cryptographic algorithms in the KPA protocols. They will also assist Crypto Quantique in conducting formal security analysis of the constituent protocols currently used in the KPA, and in developing and analysing new cryptographic protocols where necessary.

How to Apply? We look forward to receiving your online application with the following documents: CV; list of scientific publications; pointers to relevant software development projects, if applicable; contact details for 3 referees.

If you would like to apply for a role at Crypto Quantique, please use this link where the CQ team look forward to reviewing your CV: https://bit.ly/2Ot5OSc

If you would like to apply for the role with ETH Zurich please apply online at: https://bit.ly/3j88Vgs

Closing date for applications:

Contact: Kenny Paterson (kenny.paterson@inf.ethz.ch) or Christian Saade (csaade@cryptoquantique.com)

More information: https://jobs.ethz.ch/job/view/3159?mw_source=ethz_aem