International Association
for Cryptologic Research

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.

Fault-tolerant distributed systems move the trust in a single party to a majority of parties participating in the protocol. This makes blockchain based crypto-currencies possible: they allow parties to agree on a total order of transactions without a trusted third party. To trust a distributed system, the security of the protocol and the correctness of the implementation must be indisputable.

We present the first machine checked proof that guarantees both safety and liveness for a consensus algorithm. We verify a Proof of Stake (PoS) Nakamoto-style blockchain (NSB) protocol, using the foundational proof assistant Coq. In particular, we consider a PoS NSB in a synchronous network with a static set of corrupted parties. We define execution semantics for this setting and prove chain growth, chain quality, and common prefix which together implies both safety and liveness.

In the context of secure computation, protocols with security against covert adversaries ensure that any misbehavior by malicious parties will be detected by the honest parties with some constant probability. As such, these protocols provide better security guarantees than passively secure protocols and, moreover, are easier to construct than protocols with full security against active adversaries. Protocols that, upon detecting a cheating attempt, allow the honest parties to compute a certificate that enables third parties to verify whether an accused party misbehaved or not are called publicly verifiable.

In this work, we present the first generic compilers for constructing two-party protocols with covert security and public verifiability from protocols with passive security. We present two separate compilers, which are both fully blackbox in the underlying protocols they use. Both of them only incur a constant multiplicative factor in terms of bandwidth overhead and a constant additive factor in terms of round complexity on top of the passively secure protocols they use.

The first compiler applies to all two-party protocols that have no private inputs. This class of protocols covers the important class of preprocessing protocols that are used to setup correlated randomness among parties. We use our compiler to obtain the first secret-sharing based two-party protocol with covert security and public verifiability. Notably, the produced protocol achieves public verifiability essentially for free when compared with the best known previous solutions based on secret-sharing that did not provide public verifiability

Our second compiler constructs protocols with covert security and public verifiability for arbitrary functionalities from passively secure protocols. It uses our first compiler to perform a setup phase, which is independent of the parties' inputs as well as the protocol they would like to execute.

Finally, we show how to extend our techniques to obtain multiparty computation protocols with covert security and public verifiability against arbitrary constant fractions of corruptions.

The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently unstructured'' (such as fixed-length SHA-2) should suffice. Finally, for some special interactive protocols, it is known how to (1) isolate a concrete security property of a hash function that suffices to instantiate Fiat-Shamir and (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors.

In this work, we abandon this methodology and ask whether Fiat-Shamir truly requires a cryptographic hash function. Perhaps surprisingly, we show that in two of its most common applications --- building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-p or bit decomposition. In some cases, we make idealized assumptions about the interactive protocol (i.e., we invoke the generic group model), while in others, we argue soundness in the plain model. At a high level, the security of each resulting non-interactive protocol derives from hard problems already implicit in the original interactive protocol.

On the other hand, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope that this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation.

In this paper we study multivariate public key signature schemes with "ultra"-short signatures. In order to do so, we consider that signing and verifying a signature could require about 1 minute of computation on a modern personal computer. Despite the fact that this time is way bigger than the time required by general purpose multivariate-based signature schemes, such as Quartz or GeMMS, it enables us to reach ultra-short signature length, for instance, around 70 bits long signatures for a security of 80 bits. Two main issues arise when one wants to build a signature scheme with ultra-short signatures: avoiding the birthday paradox attack and having the ability to sign arbitraly long messages, this paper gives ways to overcome both.

In a first part, we describe the attacks against multivariate public key signature and use them to compute the minimal parameters that an ultra-short signature scheme would have. In a second part, we give an explicit example of such an ultra-short signature scheme using HFE-like algorithms. In the end, we give parameters for several level of security: 80, 90, 100 bits and the classic 128, 192, and 256 bits; for each of them, we propose different choices of finite fields.

Differential cryptanalysis is an important technique to evaluate the security of block ciphers. There exists several generalisations of differential cryptanalysis and it is also used in combination with other cryptanalysis techniques to improve the attack complexity. Usefulness of Machine learning in differential cryptanalysis is introduced by Gohr in 2019 to attack the lightweight block cipher SPECK. In this paper, we present a framework to combine the classical differential distinguisher and machine learning (ML) based differential distinguisher. We propose a novel technique to construct differential-ML distinguisher which provides better results with reduced data complexity. This technique is demonstrated on lightweight block ciphers SPECK & SIMON where 96% & 99% (or more) success rate is achieved for distinguishing the 6-round SPECK and 9-round SIMON respectively.

In this paper, we propose EM side-channel attacks with carefully constructed ciphertext on Kyber, a lattice-based key encapsulation mechanism, which is a candidate of NIST Post-Quantum Cryptography standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require a lower number of traces and avoid the need for template attacks. We practically evaluate our methods using both a clean reference implementation of Kyber and the ARM-optimized pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret-key with between eight and 960 traces (or 184 traces for recovering 98% of the secret-key), depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

We introduce a new cryptographic primitive, a lossy correlation-intractable hash function, and use it to soundly instantiate the Fiat-Shamir transform for the general interactive sumcheck protocol, assuming sub-exponential hardness of the Learning with Errors (LWE) problem. By combining this with the result of Choudhuri et al. (STOC 2019), we show that $\#\mathsf{SAT}$ reduces to end-of-metered line, which is a $\mathsf{PPAD}$-complete problem, assuming the sub-exponential hardness of LWE.

The Hamming Quasi-Cyclic (HQC) proposal is a promising candidate in the second round of the NIST Post-Quantum cryptography Standardization project. It features small public key sizes, precise estimation of its decryption failure rates and contrary to most of the code-based systems, its security does not rely on hiding the structure of an error-correcting code. In this paper, we propose the first power side-channel attack on the Key Encapsulation Mechanism (KEM) version of HQC. Our attack utilizes a power side-channel to build an oracle that outputs whether the BCH decoder in HQC's decryption algorithm corrects an error for a chosen ciphertext. Based on the decoding algorithm applied in HQC, it is shown how to design queries such that the output of the oracle allows to retrieve a large part of the secret key. The remaining part of the key can then be determined by an algorithm based on linear algebra. It is shown in experiments that less than 10000 measurements are sufficient to successfully mount the attack on the HQC reference implementation running on an ARM Cortex-M4 microcontroller.