International Association
for Cryptologic Research

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.

Correlated oblivious transfer (COT) is a crucial building block for secure multi-party computation (MPC) and can be generated efficiently via OT extension. Recent works based on the pseudorandom correlation generator (PCG) paradigm presented a new way to generate random COT correlations using only communication sublinear to the output length. However, due to their high computational complexity, these protocols are only faster than the classical IKNP-style OT extension under restricted network bandwidth.

In this paper, we propose new COT protocols in the PCG paradigm that achieve unprecedented performance. With $50$ Mbps network bandwidth, our maliciously secure protocol can produce one COT correlation in $22$ nanoseconds. More specifically, our results are summarized as follows:

- We propose a semi-honest COT protocol with sublinear communication and linear computation. This protocol assumes primal-LPN and is built upon a recent VOLE protocol with semi-honest security by Schoppmann et al. (CCS 2019). We are able to apply various optimizations to reduce its communication cost by roughly $15\times$, not counting a one-time setup cost that diminishes as we generate more COTs.

- We strengthen our COT protocol to malicious security with no loss of efficiency. Among all optimizations, our new protocol features a new checking technique that ensures correctness and consistency essentially for free. In particular, our maliciously secure protocol is only $1-3$ nanoseconds slower for each COT.

- We implemented our protocols, and the code will be publicly available at EMP-toolkit. We observe at least $9\times$ improvement in running time compared to the state-of-the-art protocol by Boyle et al. (CCS 2019) in both semi-honest and malicious settings under any network faster than $50$ Mbps.

With this new record of efficiency for generating COT correlations, we anticipate new protocol designs and optimizations will flourish on top of our protocol.

In 2012, Lyubashevsky introduced a framework for obtaining efficient digital signatures relying on lattice assumptions. Several works attempted to make this approach compliant with the coding theory setting, unsuccessfully. Recently, Song et al. proposed another adaptation of this framework, using denser and permuted secret keys, claiming immunity against existing attacks. This paper describes an efficient attack against Song et al. signature scheme. We show that it is possible to fully recover the secret key from a very limited number of signatures. As an example, it requires 32 signatures and 2 hours to recover the secret key of the parameter set targeting 80 bits of security. The attack affects both proposed parameter sets, and discourages patching such an approach.

In recent years, the conventional power grid system has been streamlined towards Smart grid infrastructure that empowers two-way communication between the consumers and the utility providers. This however also makes the grid more susceptible towards faults as well as physical and cyber attacks. In this work, we propose a Physically Unclonable Function (PUF) and Blockchain based detection and prevention mechanism to secure the Smart grid system against such faults and adversarial threats. In this context, we discuss a recently proposed Manipulation of demand via IoT (MadIoT) attacks, False Data Injection Attacks (FDIA) via Smart meters and Electric Fault Attacks (EFA) on Smart grid which can lead to localized blackout, falsified load forecasting, imbalance in demand-response, generator tripping, frequency instability and loss of equipment. To detect these threats and to trace back to the source of such attacks, we inspect the potential of the promising blockchain technology which gives a mechanism to authenticate and ensure the integrity of real power consumption information. However, the blockchain needs to be augmented with a root-of-trust, to bind the Smart meter with a unique hardware fingerprint. This can be achieved through Physically Unclonable Functions (PUFs) which is considered to be an unconventional cryptographic primitive and used for keyless authentication. The proposed PUF based authentication scheme would further prevent the system from injection of any false data by an illegitimate Smart meter that aids to false power estimation. The novelty of the proposed work is to blend these two technologies in developing a robust and secure framework which detects and prevents all of the above mentioned security vulnerabilities and can be easily integrated with the Smart grid infrastructure. Finally an end-to-end demonstration of the attack has been presented using MATLAB and Power World simulator and the proposed framework has been prototyped using commercial off-the-shelf products such as Raspberry Pi and Artix 7 FPGA along with an in-house blockchain simulator.

Dynamic group signatures (DGS) enable a user to generate a signature on behalf of a group of users, allowing a prospective user to join via an appropriate join protocol. A natural security requirement in the dynamic setting is to permit an adversary to concurrently perform join protocol executions. To date, most of DGS schemes do not provide the efficient concurrent join protocols in their security analysis, because of the need to use knowledge extractors. Also, DGS schemes have to provide efficient batch verifications for practical applications such as Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication, where a large number of group signatures should be verified in a very short time. In this paper, we propose a new practical DGS scheme that supports not only efficient concurrent joins but also batch verifications. The concurrent security is proven by showing that our join protocols are simulated without any knowledge extractor in security analysis. To do this, we introduce a modified Pointcheval-Sanders (PS) problem that can guarantee efficiently checking equality of discrete logarithms. In terms of efficiency, when considering a type-3 pairing, our DGS scheme has the advantages that the signature generation and verification are faster and especially our batch verification is at least 7 times faster in case of verifying 100 signatures, compared to other comparable pairing-based DGS schemes in the literature.

Differential analysis is an important cryptanalytic technique on block ciphers. In one form, this measures the probability of occurrence of the differences between certain inputs vectors and the corresponding outputs vectors. For this analysis, the constituent S-boxes of Block cipher need to be studied carefully. In this direction, we derive further cryptographic properties of inverse function, especially higher-order differential properties here. This improves certain results of Boukerrou et al [ToSC 2020(1)]. We prove that inverse function defined over $\mathbb F_{2^n}$ has an error (bias) in its second-oder differential spectrum with probability $\frac{1}{2^{n-2}}$, and that error occurs in more than one places. To the best of our knowledge, this result was not known earlier. Further, for the first time, we analyze the Gowers uniformity norm of S-boxes which is also a measure of resistance to higher order approximations. Finally, the bounds related to the nonlinearity profile of multiplicative inverse function are derived using both Gowers $U_3$ norm and Walsh--Hadamard spectrum. Some of our findings provide slightly improved bounds over the work of Carlet [IEEE-IT, 2008]. All our results might have implications towards non-randomness of a block cipher where the inverse function is used as a primitive.

Simon's algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by presenting precise query estimates for the different use cases of Simon's algorithm in cryptanalysis, and shows that Simon's algorithm requires in most cases little more than $n$ queries to succeed.

Authentication continues to be a challenge for legacy real-time communications networks involving low-speed buses interconnecting resource-limited devices. A commercial vehicle network is such a network which does not change much over the years due to safety standards and regulations in the transportation domain. The SAE J1939 incorporating the ISO 11898- 1 specification for the data link and physical layers of the standard CAN and CAN-flexible data rate (CAN-FD) handles communication among electronic control units (ECUs). The SAE J1939 is susceptible to attacks such as replay, masquerading and man-in-the-middle. This paper presents a formal analysis of the existing authentication protocols for the SAE J1939 and identifies limitation, especially man-in-the-middle attack. To mitigate the attack, we propose two new authentication protocols. One pass authentication protocol is proposed for computationally restricted nodes, and for the nodes that support public key operations, a certificateless signature-based authentication protocol is proposed which is based on certificateless key insulated manageable signature scheme (CL-KIMS). The security of the new protocol suite and the signature scheme is formally analysed in the random oracle model. We use the Tamarin tool to verify mutual authentication, session key security, known key secrecy and forward security of the proposed protocols. Performance comparison shows that compared with the existing protocol suite, the new protocol suite is computation and communication efficient with robust security. Our simulation study in Matlab 2018a reveals that the key exchange protocols in the new protocol suite are efficient regarding consumption of lesser total message delay than its counterpart.