International Association
for Cryptologic Research

In CRYPTO 2019, Gohr opens up a new direction for cryptanalysis. He successfully applied deep learning to differential cryptanalysis against the NSA block cipher SPECK32/64, achieving higher accuracy than traditional differential distinguishers. Until now, one of the mainstream research directions is increasing the training sample size and utilizing different neural networks to improve the accuracy of neural distinguishers. This conversion mindset may lead to a huge number of parameters, heavy computing load, and a large number of memory in the distinguishers training process. However, in the practical application of cryptanalysis, the applicability of the attacks method in a resource-constrained environment is very important. Therefore, we focus on the cost optimization and aim to reduce network parameters for differential neural cryptanalysis.

In this paper, we propose two cost-optimized neural distinguisher improvement methods from the aspect of data format and network structure, respectively. Firstly, we obtain a partial output difference neural distinguisher using only 4-bits training data format which is constructed with a new advantage bits search algorithm based on two key improvement conditions. In addition, we perform an interpretability analysis of the new neural distinguishers whose results are mainly reflected in the relationship between the neural distinguishers, truncated differential, and advantage bits. Secondly, we replace the traditional convolution with the depthwise separable convolution to reduce the training cost without affecting the accuracy as much as possible. Overall, the number of training parameters can be reduced by less than 50\% by using our new network structure for training neural distinguishers. Finally, we apply the network structure to the partial output difference neural distinguishers. The combinatorial approach have led to a further reduction in the number of parameters (approximately 30\% of Gohr's distinguishers for SPECK).

Wi-Fi is a wireless communication technology that has been around since the late nineties. Nowadays, it is the most adopted wireless short-range communication technology in various IoT (Internet of Things) applications and on many wireless AI (Artificial Intelligent) systems. Although Wi-Fi security has significantly improved throughout the past years, it is still having some limitations. Some vulnerabilities still exist allowing attackers to generate different types of attacks. These attacks can breach the authentication, confidentiality, and data integrity of Wi-Fi systems. At the same time, many vulnerabilities have been fixed or patched, and the attacks that were relying on those vulnerabilities would fail on modern Wi-Fi systems. Therefore, it is important for security engineers, in general, and for wireless intelligent system designers, in particular, to be aware of the existing vulnerabilities and feasible attacks on modern Wi-Fi systems and their respective countermeasures. That would help them to not have to look back and care about attacks that can no longer be generated on today’s Wi-Fi systems. In this light, we devote this paper to extensively review the attacks on Wi-Fi. We group the attacks into feasible and unfeasible. Also, for each attack, we discuss the possible countermeasures to mitigate it.

We present a protocol called $\mathsf{cq}$ for checking the values of a committed polynomial $f(X)\in \mathbb{F}_{

Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it. Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, rationally sound with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a rationally sound secret reconstruction protocol if (1) shares are authenticated or (2) half of all players may form a coalition.

A family of block ciphers parametrized by an optimal quasigroup is proposed in this paper. The proposed cipher uses sixteen $4\times 4$ bits S-boxes as an optimal quasigroup of order 16. Since a maximum of $16!$ optimal quasigroups of order 16 can be formed, the family consists of $C^{16!}_1$ cryptosystems. All the sixteen S-boxes have the highest algebraic degree and are optimal with the lowest linearity and differential characteristics. Therefore, these S-boxes are secure against linear and differential attacks. The proposed cipher is analyzed against various attacks, including linear and differential attacks, and we found it to be resistant to these attacks. The proposed cipher is implemented in C++, compared its performance with existing quasigroup based block ciphers, and we found that our proposal is more efficient than existing quasigroup based proposals. We also evaluated our cipher using various statistical tests of the NIST-STS test suite, and we found it to pass these tests. We also established in this study that the randomness of our cipher is almost the same as that of the AES-128.

Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances.

In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.

In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.

In this work we present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets or one high threshold secret with a total communication complexity of just $O(\lambda n^2)$ words. Bingo requires a public key infrastructure and a powers-of-tau setup. Using Bingo's packed secret sharing, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time. Using this agreement protocol in combination with Bingo, we obtain an adaptively secure high threshold asynchronous distributed key generation (ADKG) of standard field element secrets that uses $O(\lambda n^3)$ expected words and constant expected time. To the best of our knowledge, Bingo is the first ADKG to have an adaptive security proof and have the same asymptotic complexity of the best known ADKG's that only have non-adaptive security proofs.

This paper introduces SuperNova, a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set (e.g., EVM, RISC-V). A distinguishing aspect of SuperNova is that the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step. This is a stark departure from prior works that employ universal circuits where the cost of proving a program step is proportional at least to the sum of sizes of circuits representing each supported instruction—even though a particular program step invokes only one of the supported instructions. Naturally, SuperNova can support a rich instruction set without affecting the per-step proving costs. SuperNova achieves its cost profile by building on Nova, a prior high-speed recursive proof system, and leveraging its internal building block, folding schemes, in a new manner. We formalize SuperNova’s approach as a way to realize non-uniform IVC, a generalization of IVC. Furthermore, SuperNova’s prover costs and the recursion overhead are the same as Nova’s, and in fact, SuperNova is equivalent to Nova for machines that support a single instruction.

The One-Way to Hiding (O2H) Lemma is a central component of proofs of chosen-ciphertext attack (CCA) security of practical public-key encryption schemes using variants of the Fujisaki-Okamoto (FO) transform in the Quantum Random Oracle Model (QROM). Recently, Kuchta et al. (EUROCRYPT ’20) introduced a new QROM proof technique, called Measure-Rewind-Measure (MRM), giving an improved variant of the O2H lemma, with a new security reduction that does not suffer from a square-root advantage security loss as in the earlier work of Bindel et al. (TCC ’19).However, the FO transform QROM CCA security reduction based on the improved MRM O2H lemma still requires an injectivity assumption on the underlying CPA-secure determinstic public-key encryption scheme. In particular, the tightness of the concrete security reduction relies on a sufficiently small injectivity bound, and obtaining such bounds for concrete schemes was left as an open problem by Kuchta et al. (EUROCRYPT ’20). In this paper, we address the above problem by deriving concrete bounds on the injectivity of the deterministic CPA-secure variant of CRYSTALS-Kyber, the public-key encryption scheme selected for standardisation by the NIST Post-Quantum Cryptograpy (PQC) standardisation process. We evaluate our bounds numerically for the CRYSTALS-Kyber parameter sets, and show that the effect of injectivity on the tightness of the QROM CCA security of the Fujisaki-Okamoto transformed Kyber KEM is negligible, i.e. allows for a tight QROM CCA security reduction. Consequently, we give tightest QROM CCA security bounds to date for a simplified ‘single hashing’ variant of Kyber CCAKEM against attacks with low quantum circuit depth. Our bounds apply for all the Kyber parameter sets, based on the hardness of the Module Learning with Errors (MLWE) problem.

A critical aspect for the practical use of non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model is the demand for a trusted setup, i.e., a trusted generation of the CRS. Recently, motivated by its increased use in real-world applications, there has been a growing interest in concepts that allow to reduce the trust in this setup. In particular one demands that the zero-knowledge and ideally also the soundness property hold even when the CRS generation is subverted. One important line of work in this direction is the so-called updatable CRS for NIZK by Groth et al. (CRYPTO’18). The basic idea is that everyone can update a CRS and there is a way to check the correctness of an update. This guarantees that if at least one operation (the generation or one update) have been performed honestly, the zero-knowledge and the soundness properties hold. Later, Lipmaa (SCN’20) adopted this notion of updatable CRS to quasi-adaptive NIZK (QA-NIZK) arguments. In this work, we continue the study of CRS-updatable QA-NIZK and analyse the most efficient asymmetric QA-NIZKs by González et al. (ASIACRYPT’15) in a setting where the CRS is fully subverted and propose an updatable version of it. In contrast to the updatable QA- NIZK by Lipmaa (SCN’20) which represents a symmetric QA-NIZK and requires a new non-standard knowledge assumption for the subversion zero-knowledge property, our technique to construct updatable asymmetric QA-NIZK is under a well-known standard knowledge assumption, i.e., the Bilinear Diffie-Hellman Knowledge of Exponents assumption. Furthermore, we show the knowledge soundness of the (updatable) asymmetric QA-NIZKs, an open problem posed by Lipmaa, which makes them compatible with modular zk-SNARK frameworks such as LegoS- NARK by Campanelli et al. (ACM CCS’19).

To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain multiple outputs. In particular, the set of parties participating changes over time, i.e., at different points in time different sets of parties evaluate a function over their private inputs. To this end, we propose the notion of an online trusted third party that allows to prove the security of SMPC protocols implementing online functionalities or online algorithms, respectively. We show that any online functionality can be implemented perfectly secure in the presence of a semi-honest adversary, if strictly less than 1/2 of the parties participating are corrupted. We show that the same result holds in the presence of a malicious adversary if it corrupts strictly less than 1/3 of the parties and always allows the corrupted parties to arrive and provide input. Note, this is the corrected and extended version of the work presented in [24].

In [BS22], the authors proposed a lattice based hash function that is useful for building zero-knowledge proofs with superior performance. In this short note we analysis the underlying lattice problem with the classic shortest vector problem, and show that 2 out of 15 proposed parameter sets for this hash function do not achieve the claimed security.

In general, digital signatures can be used to prove authenticity for as long as the signature scheme is not broken and the signing key is kept secret. While this "long-lived" authenticity might be useful in some scenarios, it is inherently undesirable for certain types of sensitive communication, for instance, whistleblowing. A particular concern in this case is that the communication could be leaked in the future, which might lead to potential retaliation and extortion. Therefore, a natural question to ask is whether it is possible to design a signature scheme that allows the signers to prove authenticity for a limited period of time, and then afterwards be able to deny having signed any messages in the first place. We argue that this could offer a desirable degree of protection to the signers through deniability against future leaks. This also reduces the incentives for criminals to obtain leaked communications for the sole purpose of blackmailing.

This paper introduces the concept of digital signature with key extraction (DSKE). In such schemes, signers can have plausible deniability by demonstrating that a group of recipients can collectively extract the signing key, while, within a certain threshold, the signature deterministically proves message authenticity. We give a formal definition of DSKE, as well as two provably secure constructions, one based on hash-based digital signatures and the other based on polynomial commitments. Later, we propose a forward-forgeable signature construction, GroupForge, by combining DSKE constructions with Merkle trees and timestamps to have a "short-lived" signature with extractable sets that can act as deniable groups under a fixed public key. Finally, we demonstrate that GroupForge can replace Keyforge in the non-attributable email protocol of Specter, Park, and Green (USENIX Sec '21), hence eliminating the need to continuously disclose outdated private keys.

Logic locking/obfuscation secures hardware designs from untrusted entities throughout the globalized semiconductor supply chain. Machine learning (ML) recently challenged the security of locking: such attacks successfully captured the locking-induced, structural design modifications to decipher obfuscated gates. Although routing obfuscation eliminates this threat, more recent attacks exposed new vulnerabilities, like link formation, breaking such schemes. Thus, there is still a need for advanced, truly learning-resilient locking solutions.

Here we propose IsoLock, a provably-secure locking scheme that utilizes isomorphic structures which ML models and other structural methods cannot discriminate. Unlike prior work, IsoLock’s security promise neither relies on re-synthesis nor on dedicated sub-circuits. Instead, IsoLock introduces isomorphic key-gate structures within the design via systematic routing obfuscation. We theoretically prove the security of IsoLock against modeling attacks. Further, we lock ISCAS-85 and ITC-99 benchmarks and launch state-of-the-art ML attacks, SCOPE and MuxLink, as well as the Redundancy and SAAM attacks, which only decipher an average of 0–6% of the key, well confirming the resilience of IsoLock. All in all, IsoLock is proposed to break the cycle of “cat and mouse” in locking and attack studies, through a provably-secure locking approach against structural ML attacks.

Code-based cryptography relies, among other things, on the hardness of the Decoding Problem. If the search version is well understood, both from practical and theoretical standpoints, the decision version has been less studied in the literature. Until the work of Brakerski et al. (Eurocrypt 2019), no worst-case to average-case reduction was even known, and most reductions focus on the plain unstructured Decoding Problem. In the world of Euclidean lattices though, the situation is rather different and many reductions exist, both for unstuctured and structured versions of the underlying problems. For the latter versions, a powerful tool called the O(H)CP framework has been introduced by Peikert et al. (STOC 2017) and has proved itself very useful as a black box inside reductions. In this work, we adapt this technique to the coding-theoretic setting, and give a new worst-case hardness of the decision Decoding Problem, as well as a new (average-case) search-to-decision reduction. We then turn to the structured version and explain why this is not as straightforward as for Euclidean lattices. If we fail to give a search-to-decision reduction in this case, we believe that our work opens the way towards new reductions for structured codes given that the O(H)CP framework proved itself to be so powerful in lattice–based cryptography. Furthermore, we also believe that this technique could be extended to codes endowed with other metrics, such as the rank metric, for which no search-to-decision reduction is known.

We present a faster dual lattice attack on the Learning with Errors (LWE) problem, based on ideas from coding theory. Basically, it consists of revisiting the most recent dual attack of \cite{Matzov22} and replacing modulus switching by a decoding algorithm. This replacement achieves a reduction from small LWE to plain LWE with a very significant reduction of the secret dimension. We also replace the enumeration part of this attack by betting that the secret is zero on the part where we want to enumerate it and iterate this bet over other choices of the enumeration part. We estimate the complexity of this attack by making the optimistic, but realistic guess that we can use polar codes for this decoding task. We show that under this assumption the best attacks on Kyber and Saber can be improved by 1 and 6 bits.

The Permuted Kernel Problem (PKP) asks to find a permutation which makes an input matrix an element of the kernel of some given vector space. The literature exhibits several works studying its hardness in the case of the input matrix being mono-dimensional (i.e., a vector), while the multi-dimensional case has received much less attention and, de facto, only the case of a binary ambient finite field has been studied. The Subcode Equivalence Problem (SEP), instead, asks to find a permutation so that a given linear code becomes a subcode of another given code. At the best of our knowledge, no algorithm to solve the SEP has ever been proposed. In this paper we study the computational hardness of solving these problems. We first show that, despite going by different names, PKP and SEP are exactly the same problem. Then we consider the state-of-the-art solver for the mono-dimensional PKP (namely, the KMP algorithm), generalize it to the multi-dimensional case and analyze both the finite and the asymptotic regimes. We further propose a new algorithm, which can be thought of as a refinement of KMP. In the asymptotic regime our algorithm becomes slower than existing solutions but, in the finite regime (and for parameters of practical interest), it achieves competitive performances. As an evidence, we show that it is the fastest algorithm to attack several recommended instances of cryptosystems based on PKP. As a side-effect, given the already mentioned equivalence between PKP and SEP, all the algorithms we analyze in this paper can be used to solve instances of this latter problem.

The verification of computations performed by an untrusted server is a cornerstone for delegated computations, especially in multi- clients setting where inputs are provided by different parties. As- suming a common secret between clients, a garbled circuit offers the attractive property to ensure the correctness of a result computed by the untrusted server while keeping the input and the function private. Yet, this verification can be guaranteed only once. Based on the notion of multi-key homomorphic encryption (MKHE), we propose RMC-PVC a multi-client verifiable computation proto- col, able to verify the correctness of computations performed by an untrusted server for inputs (encoded for a garbled circuit) provided by multiple clients. Thanks to MKHE, the garbled circuit is reusable an arbitrary number of times. In addition, each client can verify the computation by its own. Compared to a single-key FHE scheme, the MKHE usage in RMC-PVC allows to reduce the workload of the server and thus the response delay for the client. It also enforce the privacy of inputs, which are provided by different clients.

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with $n$ addressable locations, Duoram can perform a sequence of $m$ arbitrarily interleaved reads and writes using just $O(m\lg n)$ words of communication, compared with Floram's $O(m \sqrt{n})$ words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just $O(m)$ words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

Password security relies heavily on the choice of password by the user but also on the one-way hash functions used to protect stored passwords. To compensate for the increased computing power of attackers, modern password hash functions like Argon2, have been made more complex in terms of computational power and memory requirements. Nowadays, the computation of such hash functions is performed usually by the server (or authenticator) instead of the client. Therefore, constrained Internet of Things devices cannot use such functions when authenticating users. Additionally, the load of computing such functions may expose servers to denial of service attacks. In this work, we discuss client-side hashing as an alternative. We propose Clipaha, a client-side hashing scheme that allows using high-security password hashing even on highly constrained server devices. Clipaha is robust to a broader range of attacks compared to previous work and covers important and complex usage scenarios. Our evaluation discusses critical aspects involved in client-side hashing. We also provide an implementation of Clipaha in the form of a web library and benchmark the library on different systems to understand its mixed JavaScript and WebAssembly approach's limitations. Benchmarks show that our library is 50\% faster than similar libraries and can run on some devices where previous work fails.