International Association
for Cryptologic Research

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

Unification techniques have been proven to be useful for formal analysis of cryptographic systems. In this paper, we introduce a new unification problem called local XOR unification, motivated by formal analysis of security of modes of operation. The goal in local XOR unification is to find a substitution making two terms equivalent modulo the theory of exclusive-or, but each variable is only allowed to be mapped to a term from a given set of terms. We present two versions of the local XOR unification problem, and give algorithms to solve them, proving soundness, completeness and termination.

We present the first non-interactive zero-knowledge argument system for QMA with multi-theorem security. Our protocol setup constitutes an additional improvement and is constructed in the malicious designated-verifier (MDV-NIZK) model (Quach, Rothblum, and Wichs, EUROCRYPT 2019), where the setup consists of a trusted part that includes only a common uniformly random string and an untrusted part of classical public and secret verification keys, which even if sampled maliciously by the verifier, the zero knowledge property still holds. The security of our protocol is established under the Learning with Errors Assumption.

Our main technical contribution is showing a general transformation that compiles any sigma protocol into a reusable MDV-NIZK protocol, using NIZK for NP. Our technique is classical but works for quantum protocols and allows the construction of a reusable MDV-NIZK for QMA.

Superlight clients enable the verification of proof-of-work-based blockchains by checking only a small representative number ofblock headers instead of all the block headers as done in simplified pay-ment verification (SPV). Such clients can be embedded within otherblockchains by implementing them as smart contracts, allowing for cross-chain verification. One such interesting instance is the consumption ofBitcoin data within Ethereum by implementing a Bitcoin superlightclient in Solidity. While such theoretical constructions have demonstratedsecurity and efficiency in theory, no practical implementation exists. Inthis work, we put forth the first practical Solidity implementation ofa superlight client which implements the NIPoPoW superblocks pro-tocol. Contrary to previous work, our Solidity smart contract achievessufficient gas-efficiency to allow a proof and counter-proof to fit withinthe gas limit of a block, making it practical. We provide extensive ex-perimental measurements for gas consumption. The optimizations thatenable gas-efficiency heavily leverage a novel technique which we termhash-and-resubmit, which almost completely eliminates persistent stor-age requirements, the most expensive operation of smart contracts interms of gas. Instead, the contract asks contesters to resubmit data andchecks their veracity by hashing it. Other optimizations include off-chainmanipulation of proofs in order to remove expensive look-up structures,and the usage of an optimistic schema. We show that such techniquescan be used to bring down gas costs significantly and may be of indepen-dent interest. Lastly, our implementation allows us to calculate concretecryptoeconomic parameters for the superblocks NIPoPoWs protocol andin particular to make recommendations about the monetary value of thecollateral parameters. We provide such parameter recommendations overa variety of liveness settings.

Traditional threshold cryptosystems have decentralized core cryptographic primitives like key generation, decryption and signatures. Most threshold cryptosystems, however, rely on special purpose protocols that cannot easily be integrated into more complex multiparty protocols.

In this work, we design and implement decentralized versions of lattice-based and elliptic-curve-based public-key cryptoystems using generic secure multiparty computation (MPC) protocols. These are standard cryptosystems, so we introduce no additional work for encrypting devices and no new assumptions beyond those of the generic MPC framework. Both cryptosystems are also additively homomorphic, which allows for secure additions directly on ciphertexts. By using generic MPC techniques, our multiparty decryption protocols compute secret-shares of the plaintext, whereas most special-purpose cryptosystems either do not support decryption or must reveal the decryptions in the clear. Our method allows complex functions to be securely evaluated after decryption, revealing only the results of the functions and not the plaintexts themselves.

To improve performance, we present a novel oblivious elliptic curve multiplication protocol and a new noise-masking technique which may be of independent interest. We implemented our protocols using the SCALE-MAMBA secure multiparty computation platform, which provides security against malicious adversaries and supports arbitrary numbers of participants.

Efficient zero-knowledge (ZK) proofs for arbitrary boolean or arithmetic circuits have recently attracted much attention. Existing solutions suffer from either significant prover overhead (superlinear running time and/or high memory usage) or relatively high communication complexity (at least $\kappa$ bits per gate, for computational security parameter $\kappa$ and boolean circuits). We show here a new protocol for constant-round interactive ZK proofs that simultaneously allows for a highly efficient prover and low communication. Specifically:

- The prover in our protocol has linear running time and, perhaps more importantly, memory usage linear in the memory needed to evaluate the circuit non-cryptographically. This allows our proof system to scale easily to very large circuits.

- For circuits of size C over an arbitrary finite field and a statistical security parameter $\rho$, the communication complexity of our protocol is roughly 3B + 1 elements per gate, where B = 1 for large fields and $B = \rho/\log C$ for small fields.

Using 5 threads and a 50 Mbps network, our ZK protocol $(\rho = 40,\kappa = 128)$ runs at a rate of $0.54 \mus$/gate for a boolean circuit with 10 billion gates, using only 400 MB of memory and communicating 9 bits/gate. This is roughly an order of magnitude faster than prior work.