Post-quantum Cryptography (PQC) has reached the verge of standardization competition, with Kyber as a winning candidate. In this work, we demonstrate practical backdoor insertion in Kyber through kleptrography. The backdoor can be inserted using classical techniques like ECDH or post-quantum Classic Mceliece. The inserted backdoor targets the key generation procedure where generated output public keys subliminally leak information about the secret key to the owner of the backdoor. We demonstrate first practical instantiations of such attack at the protocol level by validating it on TLS 1.3.

Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or efficacy, and the ad hoc solutions for identifying the intended key deployed in practice can be inefficient and, in some cases, vulnerable to practical attacks. We provide the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.

{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure $k$-nearest neighbour computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. Using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al.

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity assumption (being expensive to instantiate) and the Decisional Diffie-Hellman assumption, incurring a high latency (more than 100s with a failure threshold of 16). Moreover, the security of DYX+ ADKG is based on the random oracle model (ROM) which takes hash function as an ideal function; assuming the existence of random oracle is a strong assumption, and up to now, we cannot find any theoretically-sound implementation. Furthermore, the ADKG protocol needs public key infrastructure (PKI) to support the trustworthiness of public keys. The strong models (ROM and PKI) further limit the applicability of DYX+ ADKG, as they would add extra and strong assumptions to underlying threshold cryptosystems. For instance, if the original threshold cryptosystem works in the standard model, then the system using DYX+ ADKG would need to use ROM and PKI. In this paper, we design and implement a modular ADKG protocol that offers improved efficiency and stronger security guarantees. We explore a novel and much more direct reduction from ADKG to the underlying blocks, reducing the computational overhead and communication rounds of ADKG in the normal case. Our protocol works for both the low-threshold and high-threshold scenarios, being secure under the standard assumption (the well-established discrete logarithm assumption only) in the standard model (no trusted setup, ROM, or PKI).

It is an involutory (self-reciprocal) quagmire 4 cipher. Furthermore, it is isomorphic to a Beaufort. Explicit keys and transformations are provided.

Many applications of blind signatures (notably in blockchains) require the resulting signatures to be compatible with the existing system. This makes schemes that produce Schnorr signatures (now being standardized and supported by major cryptocurrencies like Bitcoin) desirable. Unfortunately, the existing blind-signing protocol has been shown insecure when users can open signing sessions concurrently (Eurocrypt'21). On the other hand, only allowing sequential sessions opens the door to denial-of-service attacks. We present the first practical, concurrently secure blind-signing protocol for Schnorr signatures, using the standard primitives NIZK and PKE and assuming that Schnorr signatures themselves are unforgeable. We cast our scheme as a generalization of blind and partially blind signatures: we introduce the notion of predicate blind signatures, in which the signer can define a predicate that the blindly signed message must satisfy. We provide proof-of-concept implementations and benchmarks for various choices of primitives and scenarios, including blindly signing Bitcoin transactions conditioned on certain properties.

Fault injection attacks have caused implementations to behave unexpectedly, resulting in a spectacular bypass of security features and even the extraction of cryptographic keys. Clearly, developers want to ensure the robustness of the software against faults and eliminate production weaknesses that could lead to exploitation. Several fault simulators have been released that promise cost-effective evaluations against fault attacks. In this paper, we set out to discover how suitable such tools are, for a developer who wishes to create robust software against fault attacks. We found four open-source fault simulators that employ different techniques to navigate faults, which we objectively compare and discuss their benefits and drawbacks. Unfortunately, none of the four open-source fault simulators employ artificial intelligence (AI) techniques. However, AI was successfully applied to improve the fault simulation of cryptographic algorithms, though none of these tools is open source. We suggest improvements to open-source fault simulators inspired by the AI techniques used by cryptographic fault simulators.

In this work, we introduce a lightweight communication-efficient multi-key approach suitable for the Federated Averaging rule. By combining secret-key RLWE-based HE, additive secret sharing and PRFs, we reduce approximately by a half the communication cost per party when compared to the usual public-key instantiations, while keeping practical homomorphic aggregation performances. Additionally, for LWE-based instantiations, our approach reduces the communication cost per party from quadratic to linear in terms of the lattice dimension.

The biometric system has become the desired alternative to a knowledge-based authentication system. An authentication system does not provide uniqueness, as a single user can create multiple registrations with different identities for authentication. Biometric authentication identifies users based on physical traits (fingerprint, iris, face, voice), which allows the system to detect multiple authentications from the same user. The biometric templates must be encrypted or hidden to preserve users' privacy. Moreover, we need a system to perform the matching process over encrypted data without decrypting templates to preserve the users' privacy. For the euclidean distance-based matching process, centralized server-based authentication leads to possible privacy violations of biometric templates since the power of computing inner product value over any two encrypted templates allows the server to retrieve the plain biometric template by computing a few inner products. To prevent this, we considered a decentralized system called collective authority, which is a part of a public network. The collective authority computes the collective public key with contributions from all nodes in the collective authority. It also performs a matching process over encrypted biometric templates in a decentralized manner where each node performs partial matching. Then the leader of the collective authority combines it to get the final value. We further provide a lattice-based verification system for each operation. Every time a node performs some computations, it needs to provide proof of the correctness of the computation, which is publicly verifiable. We finally make the system dynamics using Shamir's secret sharing scheme. In dynamic collective authority, only $k$ nodes out of the total $n$ nodes are required to perform the matching process. We further show that the security of the proposed system relies on the security of the underlying encryption scheme and the secret sharing scheme.

Blockchain exposes all users’ transaction data to the public, including account balances, asset holdings, trading history, etc. Such data exposure leads to potential security and personal privacy risks that restrict blockchain from broader adoption. Although some existing projects focus on single-chain confidential payment, no existing cross-chain system supports private transactions yet, which is incompatible with privacy regulations such as GDPR. Also, current confidential payment systems require users to pay high extra fees. However, a private and anonymous protocol encrypting all transaction data raises concerns about malicious and illegal activities since the protocol is difficult to audit. We need to balance privacy and auditability in blockchain. We propose an auditable and affordable protocol for cross-chain and single-chain transactions. This protocol leverages zero-knowledge proofs to encrypt transactions and perform validation without disclosing sensitive users' data. To meet regulations, each auditor from an auditing committee will have an encrypted secret share of the transaction data. Auditors may view the private transaction data only if a majority of the committee agrees to decrypt the data. We employ a ZK-rollup scheme by processing multiple transactions in batches, which reduces private transaction costs to 90\% lower compared with solutions without ZK-rollup. We implemented the proposed scheme using Zokrates and Solidity and evaluated the protocol on the Ethereum test network, and the total one-to-one private transactions cost only 5 seconds. We also proved the security of the protocol utilizing the standard real/ideal world paradigm.

Differential cryptanalysis is a block cipher analysis technology that infers a key by using the difference characteristics. Input differences can be distinguished using a good difference characteristic, and this distinguishing task can lead to key recovery. Artificial neural networks are a good solution for distinguishing tasks. For this reason, recently, neural distinguishers have been actively studied. We propose a distinguisher based on a quantum-classical hybrid neural network by utilizing the recently developed quantum neural network. To our knowledge, we are the first attempt to apply quantum neural networks for neural distinguisher. The target ciphers are simplified ciphers (S-DES, S-AES, S-PRESENT-[4]), and a quantum neural distinguisher that classifies the input difference from random data was constructed using the Pennylane library. Finally, we obtained quantum advantages in this work: improved accuracy and reduced number of parameters. Therefore, our work can be used as a quantum neural distinguisher with high reliability for simplified ciphers.

Facebook introduced message franking to enable users to report abusive content verifiably in end-to-end encrypted messaging. Grubbs et al. formalized the underlying primitive called compactly committing authenticated encryption with associated data (ccAEAD) and presented schemes with provable security. Dodis et al. proposed a core building block called encryptment and presented a generic construction of ccAEAD with encryptment and standard AEAD. This paper first proposes to use a tweakable block cipher instead of AEAD for the generic construction of Dodis et al. In the security analysis of the proposed construction, its ciphertext integrity is shown to require a new but feasible assumption on the ciphertext integrity of encryptment. Then, this paper formalizes remotely keyed ccAEAD (RK ccAEAD) and shows that the proposed construction works as RK ccAEAD. Finally, the confidentiality of the proposed construction as RK ccAEAD is shown to require a new variant of confidentiality for encryptment. The problem of remotely keyed encryption was posed by Blaze in 1996. It is now related to the problem of designing a cryptographic scheme using a trusted module and/or with leakage resiliency.

Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years. Here we introduce Jolt, a novel attack targeting signature scheme implementations. Our attack exploits faulty signatures gained by injecting faults during signature generation. By using the signature verification primitive, we correct faulty signatures and, in the process deduce bits of the secret signing key. Compared to recent attacks that exploit single bit biases in the nonce that require $2^{45}$ signatures, our attack requires less than a thousand faulty signatures for a $256$-bit (EC)DSA. The performance improvement is due to the fact that our attack targets the secret signing key, which does not change across signing sessions. We show that the proposed attack also works on Schnorr and RSA signatures with minor modifications. We demonstrate the viability of Jolt by running experiments targeting TLS handshakes in common cryptographic libraries such as WolfSSL, OpenSSL, Microsoft SymCrypt, LibreSSL, and Amazon s2n. On our target platform, the online phase takes less than 2 hours to recover $192$ bits of a $256$-bit ECDSA key, which is sufficient for full key recovery. We note that while RSA signatures are protected in popular cryptographic libraries, OpenSSL remains vulnerable to double fault injection. We have also reviewed their Federal Information Processing Standard (FIPS) hardened versions which are slightly less efficient but still vulnerable to our attack. We found that (EC)DSA signatures remain largely unprotected against software-only faults, posing a threat to real-life deployments such as TLS, and potentially other security protocols such as SSH and IPSec. This highlights the need for a thorough review and implementation of faults checking in security protocol implementations.

Symbolic computations with the usage of bipartite algebraic graphs A(n, F_q) and A(n, F_q[x_1, x_2, ..., x_n]) were used for the development of various cryptographic algorithms because the length of their minimal cycle (the girth) tends to infinity when n is growing. It motivates studies of graphs A(n, K) defined over arbitrary integrity ring K. We show that the cycle indicator of A(n, K), i. e. maximal value of minimal cycles through the given vertex is >2n. We justify that the girth indicator of line [0,0,..., 0]$ of $A(n, K)$ is > 2n and the girth indicator of point (0,0, ..., 0) of this graph is at least 2n. From this result instantly follows that the girth of known edge transitive graphs D(n, K) defined over integrity ring K is at least 2[(n+5)]/2. We consider some inequalities defined in terms of a girth, a diameter and the girth indicator of homogeneous algebraic graphs and formulate some conjectures.

This paper illustrates that masking the torsion point images does not guarantee Castryck-Decru attack does not apply. Our experiments over SIDH primes hint that any square root concerning the Weil pairing on the masked public key helps to recover Bob's private key via the Castryck-Decru attack.

Recently, F.Ivanov, E.Krouk and V.Zyablov proposed new cryptosystem based of Generalized Reed--Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message-recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret key of Ivanov-Krouk-Zyablov cryptosystem can successfully recovered in polynomial time with a linear-algebra based attack and a square-based attack.

In 2009, Lyubashevsky proposed a lattice-based signature scheme by applying the Fiat-Shamir transformation and proved its security under the generalized compact knapsack (GCK) problem. This scheme has a simple structure but has large signature and key sizes due to the security requirement of their security reduction. Dilithium, which was submitted to the NIST Post-Quantum Cryptography standardization and selected as one of the final candidates, is an improvement of the Lyubashevsky's signature scheme and decreases key and signature sizes by modifying the form of a public key and including additional steps in key generation, signing, and verification algorithms. Thus, Dilithium has a more complex structure to implement compared to the Lyubashevsky's scheme. To combine the strength of both signature schemes, we modify the Lyubashevsky's signature scheme and present a new security proof that removes their security requirement. As a result, we propose a simple and practical GCKSign signature scheme based on the hardness of a new GCK assumption, called target-modified one-wayness of GCK function. The signature size of our signature scheme decreases 40 percent, the sum of signature and public key sizes decreases 25 percent, and the secret key size decreases 90 percent for the NIST security level III, compared to Dilithium. Furthermore, by the simplicity of our structure, the key generation, signing, and verification algorithms of our scheme run 2.4$\times$, 1.7$\times$, and 2.0$\times$ faster than those of Dilithium, respectively.

NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes. In this work, we propose a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes nearly all existing drawbacks. NTRU+ is constructed based on two new generic transformations: $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ (a variant of the Fujisaki-Okamoto transform). $\mathsf{ACWC}_{2}$ is used to easily achieve worst-case correctness error, while $\overline{\mathsf{FO}}^{\perp}$ is used to achieve chosen-ciphertext security without re-encryption. Both $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are defined using a randomness-recovery algorithm and an encoding method. In particular, our simple encoding method, the semi-generalized one-time pad (SOTP), allows us to sample a message from a natural bit-string space with an arbitrary distribution. We provide four parameter sets for NTRU+ and present implementation results using NTT-friendly rings over cyclotomic trinomials.

We propose a REinforced modified Dual-Ouroboros based on Gabidulin codes, shortly called REDOG. This is a code-based cryptosystem based on the well-known rank metric codes, Gabidulin codes. The public key sizes of REDOG are 14KB, 33KB, 63KB at the security levels of 128, 192, 256 bits respectively. There is no decoding failure in decryption. REDOG is IND-CPA. As a new result, we give the performance results of implementing REDOG including the time for Key generation, encryption, and decryption for each security level.

A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient. In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no $2$-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.

Primal attack, BKW attack, and dual attack are three well-known attacks to LWE. To build efficient post-quantum cryptosystems in practice, the structured variants of LWE (i.e. MLWE/RLWE) are often used. Some efforts have been spent on addressing concerns about additional vulnerabilities introduced by algebraic structures and no effective attack method based on ideal lattices or module lattices has been proposed so far; these include refining primal attack and BKW attack to MLWE/RLWE. It is thus an interesting problem to consider how to enhance the dual attack against LWE with the rich algebraic structure of MLWE (including RLWE). In this paper, we present the first attempt to this problem by observing that each short vector found by BKZ generates another n − 1 vectors of the same length automatically and all of these short vectors can be used to distinguish. To this end, an interesting property which indicates the rotations are consistent with certain linear transformations is proved, and a new kind of intersection lattice is constructed with some tricks. Moreover, we notice that coefficient vectors of different rotations of the same polynomial are near-orthogonal in high-dimensional spaces. This is validated by extensive experiments and is treated as an extension to the assumption under the original dual attack against LWE. Taking Newhope512 as an example, we show that by our enhanced dual attack method, the required blocksize and time complexity (in both classical and quantum cases) all decrease. It is remarked that our improvement is not significant and its limitation is also touched on. Our results do not reveal a severe security problem for MLWE/RLWE compared to that of a general LWE, this is consistent with the findings by the previous work for using primal and BKW attacks to MLWE/RLWE.

On the Internet of Connected Vehicles, a vehicle has to communicate bi-directionally with several devices for establishing a shared network for inter-vehicle and intra-vehicle connectivity. These connection protocols are commonly structured to connect all the individual components with an implicit degree of trust, which is supposed to protect the whole system from unauthorized users. Technologies like Automotive Ethernet tend to increase security by reducing the implicit trust within the local network devices. However, the lack of individual security protocols in vehicle-to-vehicle communication still keeps the possession of vulnerability to hacks, external attacks, and further disruption. This is where Zero Trust Architecture can become a reliable technology for the exchange of information in between vehicles. Zero trust is a security system that means no one is trusted by default and verification is required from anyone or any device willing to get connected to the intra-vehicle network. In this paper, we have scoped the preliminary and most vital step of this system: verifying the owner identity of a vehicle with zero trust manner. Our approach involves recognizing vehicle license plates and utilizing the license information for retrieving the vehicle owner details to establish trust before allowing connection to the network. Our proposed methodology operates with 85\% to 99\% accuracy on the license recognition part within recognizable distances using PyTesseract OCR. Reliability to the zero trust solution is gained through necessary information retrieved using GET and POST requests to and from the corresponding driving license information databases.

In the seminal work published by Gohr in CRYPTO 2019, neural networks were successfully exploited to perform differential attacks on Speck32/64, the smallest member in the block cipher family Speck. The deep learning aided key-recovery attack by Gohr achieves considerable improvement in terms of time complexity upon the state-of-the-art result from the conventional cryptanalysis method. A further question is whether the advantage of deep learning aided attacks can be kept on large-state members of Speck and other primitives. Since there are several key points in Gohr’s key-recovery frameworks that seem not fit for large-state ciphers, this question stays open for years. This work provides an answer to this question by proposing a deep learning aided multi-stage key-recovery framework. To apply this key-recovery framework on large-state members of Speck, multiple neural distinguishers (NDs) are trained and carefully combined into groups. Employing the groups of NDs under the multi-stage key-recovery framework, practical attacks are designed and trialed. Experimental results show the effectiveness of the framework. The practical attacks are then extended into theoretical attacks that cover more rounds. To do that, multi-round classical differentials (CDs) are used together with the NDs. To find the CDs’ neutral bits to boost signals from the distinguishers, an efficient algorithm is proposed. As a result, considerable improvement in terms of both time and data complexity of differential key-recovery attacks on round-reduced Speck with the largest, i.e., the 128-bit state, is obtained. Besides, efficient differential attacks are achieved on round-reduced Speck with 96-bit and 64-bit states. Since most real-world block ciphers have a state size of no less than 64 bits, this work paves the way for performing cryptanalysis using deep learning on more block ciphers. The code is available at https://github.com/AI-Lab-Y/NAAF.

Digital Identities are playing an essential role in our digital lives. Today, most Digital Identities are based on central architectures. Central Digital Identity providers control and know our data and thereby our Identity. Self Sovereign Identities are based on decentralized data storage and data exchange architecture, where the user is in sole control of his data and identity. Most of the issued credentials need the possibility of revocation. For a centrally managed Digital Identity system, revocation is not a problem. In decentral architectures, revocation is more challenging. Revocation can be done with different methods e.g. list based, cryptographic accumulators and with credential updates. A revocation method must be privacy preserving and must scale. This paper gives an overview of the available revocation methods, including a survey to define requirements, assess revocation groups against the requirements, highlights shortcomings of the methods and introduces a new revocation method called Linked Validity Verifiable Credentials.

Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets ($\ge2^{24}$, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset $\log N$ times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires $\frac{1}{6}\log N$ passes.

An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without changing the public key or the threshold. We give several definitions for this notion achieving different levels of security. We observe that certain natural constructions for an ATS cannot be proactively refreshed because the secret key generated at setup is needed for accountability. We then construct three types of ATS schemes with proactive refresh. The first is a generic construction that is efficient when the number of signers is small. The second is a hybrid construction that performs well for a large number of signers and satisfies a strong security definition. The third is a collection of very practical constructions derived from ATS versions of the Schnorr and BLS signature schemes; however these practical constructions only satisfy our weaker notion of security.

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we show that in the presence of $n - 1$ corrupt parties, no unreactive primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with fairness. We show more generally that for $t > \frac{n}{2}$, in the presence of $t$ malicious parties, no unreactive primitive of cardinality $t$ is complete for realizing an arbitrary $n$-party functionality with fairness. We complement this result by noting that $(t+1)$-wise fair exchange is complete for realizing an arbitrary $n$-party functionality with fairness. In order to prove our results, we utilize the primitive of fair coin tossing and the notion of predictability. While this notion has been considered in some form in past works, we come up with a novel and non-trivial framework to employ it, one that readily generalizes from the setting of two parties to multiple parties, and also to the setting of unreactive functionalities.

The Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project. Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher. On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.

We conduct a security analysis of the e-voting protocol used for the largest political election using e-voting in the world, the 2022 French legislative election for the citizens overseas. Due to a lack of system and threat model specifications, we built and contributed such specifications by studying the French legal framework and by reverse-engineering the code base accessible to the voters. Our analysis reveals that this protocol is affected by two design-level and implementation-level vulnerabilities. We show how those allow a standard voting server attacker and even more so a channel attacker to defeat the election integrity and ballot privacy due to 6 attack variants. We propose and discuss 5 fixes to prevent those attacks. Our specifications, the attacks, and the fixes were acknowledged by the relevant stakeholders during our responsible disclosure. Our attacks are in the process of being prevented with our fixes for future elections. Beyond this specific protocol, we draw general conclusions and lessons from this instructive experience where an e-voting protocol meets the real-world constraints of a large-scale and political election.

A Universal Circuit (UC) is a Boolean circuit of size $\Theta(n \log n)$ that can simulate any Boolean function up to a certain size $n$. Valiant (STOC'76) provided the first two UC constructions of asymptotic sizes $\sim5 n\log n$ and $\sim4.75 n\log n$, and today's most efficient construction of Liu et al. (CRYPTO'21) has size $\sim3n\log n$. Evaluating a public UC with a secure Multi-Party Computation (MPC) protocol allows efficient Private Function Evaluation (PFE), where a private function is evaluated on private data. Previously, most UC constructions have only been developed for circuits consisting of 2-input gates. In this work, we generalize UCs to simulate circuits consisting of ($\rho\rightarrow\omega$)-Lookup Tables (LUTs) that map $\rho$ input bits to $\omega$ output bits. Our LUT-based UC (LUC) construction has an asymptotic size of $1.5\rho\omega n \log \omega n$ and improves the size of the UC over the best previous UC construction of Liu et al. (CRYPTO'21) by factors 1.12$\times$ - $2.18\times$ for common functions. Our results show that the greatest size improvement is achieved for $\rho=3$ inputs, and it decreases for $\rho>3$. Furthermore, we introduce Varying Universal Circuits (VUCs), which reduce circuit size at the expense of leaking the number of inputs $\rho$ and outputs $\omega$ of each LUT. Our benchmarks demonstrate that VUCs can improve over the size of the LUC construction by a factor of up to $1.45\times$.

The quantum resistance Key Encapsulation Mechanism (PQC-KEM) design aims to replace cryptography in legacy security protocols. It would be nice if PQC-KEM were faster and lighter than ECDH or DH for easy migration to legacy security protocols. However, it seems impossible due to the temperament of the secure underlying problems in a quantum environment. Therefore, it makes reason to determine the threshold of the scheme by analyzing the maximum bandwidth the legacy security protocol can adapt. We specified the bandwidth threshold at 1,244 bytes based on IKEv2 (RFC7296), a security protocol with strict constraints on payload size in the initial exchange for secret key sharing. We propose TiGER that is an IND-CCA secure KEM based on RLWE(R). TiGER has a ciphertext (1,152bytes) and a public key (928 bytes) smaller than 1,244 bytes, even at the AES256 security level. To our knowledge, TiGER is the only scheme with such an achievement. Also, TiGER satisfies security levels 1, 3, and 5 of NIST competition. Based on reference implementation, TiGER is 1.7-2.6x faster than Kyber and 2.2-4.4x faster than LAC.

Security and privacy issues with centralized exchange services have motivated the design of atomic swap protocols for decentralized trading across currencies. These protocols follow a standard blueprint similar to the 2-phase commit in databases: (i) both users first lock their coins under a certain (cryptographic) condition and a timeout; (ii-a) the coins are swapped if the condition is fulfilled; or (ii-b) coins are released after the timeout. The quest for these protocols is to minimize the requirements from the scripting language supported by the swapped coins, thereby supporting a larger range of cryptocurrencies. The recently proposed universal atomic swap protocol [IEEE S&P’22] demonstrates how to swap coins whose scripting language only supports the verification of a digital signature on a transaction. However, the timeout functionality is cryptographically simulated with verifiable timelock puzzles, a computationally expensive primitive that hinders its use in battery-constrained devices such as mobile phones. In this state of affairs, we question whether the 2-phase commit paradigm is necessary for atomic swaps in the first place. In other words, is it possible to design a secure atomic swap protocol where the timeout is not used by (at least one of the two) users? In this work, we present LightSwap, the first secure atomic swap protocol that does not require the timeout functionality (not even in the form of a cryptographic puzzle) by one of the two users. LightSwap is thus better suited for scenarios where a user, running an instance of LightSwap on her mobile phone, wants to exchange coins with an online exchange service running an instance of LightSwap on a computer. We show how LightSwap can be used to swap Bitcoin and Monero, an interesting use case since Monero does not provide any scripting functionality support other than linkable ring signature verification.

A Feistel Network (FN) based block cipher relies on a Substitution Box (S-Box) for achieving the non-linearity. S-Box is carefully designed to achieve optimal cryptographic security bounds. The research of the last three decades shows that considerable efforts are being made on the mathematical design of an S-Box. To import the exact cryptographic profile of an S-Box, the designer focuses on the Affine Equivalent (AE) or Extended Affine (EA) equivalent S-Box. In this research, we argue that the Robustness of surjective mappings is invariant under AE and not invariant under EA transformation. It is proved that the EA equivalent of a surjective mapping does not necessarily contribute to the Robustness against the Differential Cryptanalysis (DC) in the light of Seberry's criteria. The generated EA equivalent S-Box(es) of DES and other $6 \times 4$ mappings do not show a good robustness profile compared to the original mappings. This article concludes that a careful selection of affine permutation parameters is significant during the design phase to achieve high Robustness against DC and Differential Power Analysis (DPA) attacks.

Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some certification authority. We propose a generic and efficient compiler that transforms any linear secret sharing based honest-majority MPC protocol into one with input authentication. Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For $n$-party honest majority MPC protocols with abort security where each party has $\ell$ inputs, our compiler incurs $O(n\log \ell)$ communication overall and a computational overhead of $O(\ell)$ group exponentiations per party (the corresponding overheads for the most efficient existing solution are $O(n^2)$ and $O(\ell n)$). Finally, for a corruption threshold $t<n/3$, our compiler preserves the stronger identifiable abort security of the underlying MPC protocol. No existing solution for authenticated MPC achieves this regardless of the corruption threshold. Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment.

In 1993 Bernstein and Vazirani proposed a quantum algorithm for the Bernstein-Vazirani problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1x_1+\cdots + a_nx_n \pmod 2$ with respect to a secret string $x = x_1\dots x_n \in \{0,1\}^n$, where $a_1,\dots,a_n \in \{0,1\}$, find $x$. We give a quantum algorithm for a new problem called the oracle subset product problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1^{x_1}\cdots a_n^{x_n}$ with respect to a secret string $x = x_1\dots x_n\in\{0,1\}^n$, where $a_1,\dots,a_n\in \mathbb Z$, find $x$. Similar to the Bernstein-Vazirani algorithm, it is a quantum algorithm for a problem that is originally polynomial time solvable by classical algorithms; and that the advantage of the algorithm over classical algorithms is that it only makes one call to the function instead of $n$ calls.

The tech industry is currently making the transition from Web 2.0 to Web 3.0, and with this transition, authentication and authorization have been reimag- ined. Users can now sign in to websites with their unique public/private key pair rather than generating a username and password for every site. How- ever, many useful features, like role-based access control, dynamic resource owner privileges, and expiration tokens, currently don’t have efficient Web 3.0 solutions. Our solution aims to provide a flexible foundation for resource providers to implement the aforementioned features on any blockchain through a two-step process. The first step, authorization, creates an on-chain asset which is to be presented as an access token when interacting with a resource. The second step, authentication, verifies ownership of an asset through querying the blockchain and cryptographic digital signatures. Our solution also aims to be a multi-chain standard, whereas current Web 3.0 sign-in standards are limited to a single blockchain.

This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform. At the heart of our proposal is a new approach, Hypercube-MPCitH, to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with $N$ parties can be repeated $D$ times using parallel composition to reach the same soundness as a protocol run with $N^D$ parties. However, the former comes with $D$ times higher communication costs, often mainly contributed by the usage of $D$ `auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating $N^D$ shares, arranged into a $D$-dimensional hypercube of side $N$ containing only one `auxiliary' state. We derive from this hypercube $D$ sharings of size $N$ which are used to run $D$ instances of an $N$ party MPC protocol. Hypercube-MPCitH leads to a protocol with $1/N^D$ soundness error, requiring $N^D$ offline computation, but with only $N\cdot D$ online computation, and only $1$ `auxiliary'. As the (potentially offline) share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition. Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 8.1x improvement in global runtime and a 30x improvement in online runtime for their shortest signatures size (8,481 Bytes). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6,784 Bytes for 26 ms offline and 5,689 Bytes for 320 ms offline. For NIST security level 1, online signature cost is around 3 million cycles ($<$1 ms on commodity processors), regardless of signature size.

In this paper, we examine one of the public key exchange protocols proposed in [M. I. Durcheva. An application of different dioids in public key cryptography. In AIP Conference Proceedings, vol. 1631, pp 336-343. AIP, 2014] which uses max-times and min-times algebras. We discuss properties of powers of matrices over these algebras and introduce a fast attack on this protocol. This preprint has not undergone peer review (when applicable) or any post-submission improvements or corrections. The Version of Record of this article is published in Indian Journal of Pure and Applied Mathematics, and is available online at https://doi.org/10.1007/s13226-023-00469-0.

As end-to-end encrypted messaging services become widely adopted, law enforcement agencies have increasingly expressed concern that such services interfere with their ability to maintain public safety. Indeed, there is a direct tension between preserving user privacy and enabling content moderation on these platforms. Recent research has begun to address this tension, proposing systems that purport to strike a balance between the privacy of ''honest'' users and traceability of ''malicious'' users. Unfortunately, these systems suffer from a lack of protection against malicious or coerced service providers. In this work, we address the privacy vs. content moderation question through the lens of pre-constrained cryptography [Ananth et al., ITCS 2022]. We introduce the notion of set pre-constrained (SPC) group signatures that guarantees security against malicious key generators. SPC group signatures offer the ability to trace users in messaging systems who originate pre-defined illegal content (such as child sexual abuse material), while providing security against malicious service providers. We construct concretely efficient protocols for SPC group signatures, and demonstrate the real-world feasibility of our approach via an implementation. The starting point for our solution is the recently introduced Apple PSI system, which we significantly modify to improve security and expand functionality.

Popular Ethereum wallets (like MetaMask) entrust centralized infrastructure providers (e.g., Infura) to run the consensus client logic on their behalf. As a result, these wallets are light-weight and high-performant, but come with security risks. A malicious provider can mislead the wallet by faking payments and balances, or censoring transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but are concretely inefficient, often with asymptotically \emph{linear} bootstrapping complexity. This poses a dilemma between decentralization and performance. We design, implement, and evaluate a new proof-of-stake (PoS) \emph{superlight} client with concretely efficient and asymptotically \emph{logarithmic} bootstrapping complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree of PoS epochs. The verifier enrolls the provers in a bisection game, in which honest provers are destined to win once an adversarial Merkle tree is challenged at sufficient depth. We provide an implementation for mainnet Ethereum: compared to the state-of-the-art light client construction of Ethereum, our client improves time-to-completion by $9\times$, communication by $180\times$, and energy usage by $30\times$ (when bootstrapping after $10$ years of consensus execution). As an important additional application, our construction can be used to realize trustless cross-chain bridges, in which the superlight client runs within a smart contract and takes the role of an on-chain verifier. We prove our construction is secure and show how to employ it for other PoS systems such as Cardano (with fully adaptive adversary), Algorand, and Snow White.

A good differential is a start for a successful differential attack. However, a differential might be invalid, i.e., there is no right pair following the differential, due to some contradictions in the conditions imposed by the differential. This paper presents a novel and handy method for searching and verifying differential trails from an algebraic perspective. From this algebraic perspective, exact Boolean expressions of differentials over a cryptographic primitive can be conveniently established, which allows for the convenient verification of a given differential trail. This verification process can be naturally formulated as a Boolean satisfiability problem (SAT). To demonstrate the power of our new tool, we apply it to Gimli, Ascon, and Xoodoo. For Gimli, we improve the efficiency of searching for a valid 8-round colliding differential trail compared to the previous MILP model (CRYPTO 2020). Based on this differential trail, a practical semi-free-start collision attack on the intermediate 8-round Gimli-Hash is thus successfully mounted. For Ascon, we check several differential trails reported at FSE 2021. Specifically, we find that a 4-round differential used in the forgery attack on Ascon-128’s iteration phase has been proven invalid. As a consequence, the corresponding forgery attack is also invalid. For Xoodoo, as an independent interest, we develop a SAT-based automatic search toolkit called XoodooSat to search for 3- and 4-round differential trail cores of Xoodoo. Our toolkit finds two more 3-round differential trail cores of weight 48 that were missed by the designers which enhance the security analysis of Xoodoo. Then, we verify tens of thousands of 3-round differential trails and two 4-round differential trails extended from the so-called differential trail cores. We find that all these differential trails are valid, which effectively demonstrates that there are no contradictions in the conditions imposed by the round differentials of the DTs in the trail core.

In this paper we introduce the differential meet-in-the-middle framework, a new cryptanalysis technique for symmetric primitives. Our new cryptanalysis method combines techniques from both meet-in-the- middle and differential cryptanalysis. As such, the introduced technique can be seen as a way of extending meet-in-the-middle attacks and their variants but also as a new way to perform the key recovery part in differential attacks. We apply our approach to SKINNY-128-384 in the single-key model and to AES-256 in the related-key model. Our attack on SKINNY-128-384 permits to break 25 out of the 56 rounds of this variant and improves by two rounds the previous best known attacks. For AES-256 we attack 12 rounds by considering two related keys, thus outperforming the previous best related-key attack on AES-256 with only two related keys by 2 rounds.

Adopting Post-Quantum Cryptography (PQC) in network protocols is a challenging subject. Larger PQC public keys and signatures can significantly slow the Transport Layer Security (TLS) protocol. In this context, KEMTLS is a promising approach that replaces the handshake signatures by using PQC Key Encapsulation Mechanisms (KEMs), which have, in general, smaller sizes. However, for broad PQC adoption, hybrid cryptography has its advantages over PQC-only approaches, mainly about the confidence in the security of existing cryptographic schemes. This work brings hybrid cryptography to the KEMTLS and KEMTLS-PDK protocols. We analyze different network conditions and show that the penalty when using Hybrid KEMTLS over PQC-only KEMTLS is minor under certain security levels. We also compare Hybrid KEMTLS with a hybrid version of PQTLS. Overall, the benefits of using hybrid protocols outweigh the slowdown penalties in higher security parameters, which encourages its use in practice.

The study of symmetric structures based on quasigroups is relatively new and certain gaps can be found in the literature. In this paper, we want to fill one of these gaps. More precisely, in this work we study substitution permutation networks based on quasigroups that make use of permutation layers that are non-linear relative to the quasigroup operation. We prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of mounting a differential attack against this type of substitution permutation network is the same as attacking another symmetric structure based on $\mathbb{G}$. The resulting structure is interesting and new, and we hope that it will form the basis for future secure block ciphers.

Indistinguishability Obfuscation $(i\mathcal{O})$ is a highly versatile primitive implying a myriad advanced cryptographic applications. Up until recently, the state of feasibility of $i\mathcal{O}$ was unclear, which changed with works (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai Eurocrypt 2022) showing that $i\mathcal{O}$ can be finally based upon well-studied hardness assumptions. Unfortunately, one of these assumptions is broken in quantum polynomial time. Luckily, the line work of Brakerski et al. Eurocrypt 2020, Gay-Pass STOC 2021, Wichs-Wee Eurocrypt 2021, Brakerski et al. ePrint 2021, Devadas et al. TCC 2021 simultaneously created new pathways to construct $i\mathcal{O}$ with plausible post-quantum security from new assumptions, namely a new form of circular security of LWE in the presence of leakages. At the same time, effective cryptanalysis of this line of work has also begun to emerge (Hopkins et al. Crypto 2021). It is important to identify the simplest possible conjectures that yield post-quantum $i\mathcal{O}$ and can be understood through known cryptanalytic tools. In that spirit, and in light of the cryptanalysis of Hopkins et al., recently Devadas et al. gave an elegant construction of $i\mathcal{O}$ from a fully-specified and simple-to-state assumption along with a thorough initial cryptanalysis. Our work gives a polynomial-time distinguisher on their "final assumption" for their scheme. Our algorithm is extremely simple to describe: Solve a carefully designed linear system arising out of the assumption. The argument of correctness of our algorithm, however, is nontrivial. We also analyze the "T-sum" version of the same assumption described by Devadas et. al. and under a reasonable conjecture rule out the assumption for any value of $T$ that implies $i\mathcal{O}$.

Existing threshold signature schemes come in two flavors: (i) fully private, where the signature reveals nothing about the set of signers that generated the signature, and (ii) accountable, where the signature completely identifies the set of signers. In this paper we propose a new type of threshold signature, called TAPS, that is a hybrid of privacy and accountability. A TAPS signature is fully private from the public's point of view. However, an entity that has a secret tracing key can trace a signature to the threshold of signers that generated it. A TAPS makes it possible for an organization to keep its inner workings private, while ensuring that signers are accountable for their actions. We construct a number of TAPS schemes. First, we present a generic construction that builds a TAPS from any accountable threshold signature. This generic construction is not efficient, and we next focus on efficient schemes based on standard assumptions. We build two efficient TAPS schemes (in the random oracle model) based on the Schnorr signature scheme. We conclude with a number of open problems relating to efficient TAPS.

Fully Homomorphic Encryption (FHE) is a technique that allows computation on encrypted data. It has the potential to drastically change privacy considerations in the cloud, but high computational and memory overheads are preventing its broad adoption. TFHE is a promising Torus-based FHE scheme that heavily relies on bootstrapping, the noise-removal tool invoked after each encrypted logical/arithmetical operation. We present FPT, a Fixed-Point FPGA accelerator for TFHE bootstrapping. FPT is the first hardware accelerator to heavily exploit the inherent noise present in FHE calculations. Instead of double or single-precision floating-point arithmetic, it implements TFHE bootstrapping entirely with approximate fixed-point arithmetic. Using an in-depth analysis of noise propagation in bootstrapping FFT computations, FPT is able to use noise-trimmed fixed-point representations that are up to 50% smaller than prior implementations that prefer floating-point or integer FFTs. FPT is built as a streaming processor inspired by traditional streaming DSPs: it instantiates directly cascaded high-throughput computational stages, with minimal control logic and routing networks. We explore different throughput-balanced compositions of streaming kernels with a user-configurable streaming width in order to construct a full bootstrapping pipeline. Our proposed approach allows 100% utilization of arithmetic units and requires only a small bootstrapping key cache, enabling an entirely compute-bound bootstrapping throughput of 1 BS / 35$\mu$s. This is in stark contrast to the established classical CPU approach to FHE bootstrapping acceleration, which is typically constrained by memory and bandwidth. FPT is fully implemented and evaluated as a bootstrapping FPGA kernel for an Alveo U280 datacenter accelerator card. FPT achieves two to three orders of magnitude higher bootstrapping throughput than existing CPU-based implementations, and 2.5$\times$ higher throughput compared to recent ASIC emulation experiments.

Decentralized anonymous payment schemes may be exploited for illicit activities, such as money laundering, bribery and blackmail. To address this issue, several regulatory friendly decentralized anonymous payment schemes have been proposed. However, most of these solutions lack restrictions on the regulator’s authority, which could potentially result in power abuse and privacy breaches. In this paper, we present a decentralized anonymous payment scheme with collaborative regulation (DAPCR). Unlike existing solutions, DAPCR reduces the risk of power abuse by distributing regulatory authority to two entities: Filter and Supervisor, neither of which can decode transactions to access transaction privacy without the assistance of the other one. Our scheme enjoys three major advantages over others: ① Universality, achieved by using zk-SNARK to extend privacy-preserving transactions for regulation. ② Collab orative regulation, attained by adding the ring signature with controllable linkability to the transaction. ③ Efficient aggregation of payment amounts, achieved through amount tags. As a key technology for realizing collaborative regulation in DAPCR, the ring signature with controllable linkability (CLRS) is proposed, where a user needs to specify a linker and an opener to generate a signature. The linker can extract pseudonyms from signatures and link signatures submitted by the same signer based on pseudonyms, without leaking the signer’s identity. The opener can recover the signer’s identity from a given pseudonym. The experimental results reflect the efficiency of DAPCR. The time overhead for transaction generation is 1231.2 ms, representing an increase of less than 50 % compared to ZETH. Additionally, the time overhead for transaction verification is only 1.2 ms.

Rollup technology today promises long-term solutions to the scalability of the blockchain. Among a thriving ecosystem, Consensys has launched the Linea zkEVM Rollup network for Ethereum. At a high level, the Ethereum blockchain can be seen as a state machine and its state transition can be arithmetized carefully. Linea's prover protocol uses this arithmetization, along with transactions on layer two in order to compute a cryptographic proof that the state transition is performed correctly. The proof is then sent over to the Ethereum layer, where the smart contract (verifier contract) on Ethereum checks the proof and accepts the state transition if the proof is valid. The interaction between layer two and Ethereum is costly, which imposes substantial limitations on the proof size. Therefore, Linea's prover aims to compress the proof via cryptographic tools such as list polynomial commitments (LPCs), polynomial interactive oracle proofs (PIOPs), and Succinct Non-Interactive Arguments of Knowledge (SNARKs). We introduce Wizard-IOP, a cryptographic tool for handling a wide class of queries (such as range checks, scalar products, permutations checks, etc.) needed to ensure the correctness of the executions of the state machines efficiently and conveniently. Another cryptographic tool is the Arcane compiler, which outputs standard PIOPs and is employed by Wizard-IOP to make different queries homogeneous. After applying Arcane, all the queries constitute evaluation queries over the polynomials. We then apply the Unique Evaluation compiler (UniEval), which receives the output of the Arcane and provides us with a PIOP that requires only a single evaluation check. At this point, we employ Vortex, a list polynomial commitment (LPC) scheme to convert the resulting PIOP into an argument of knowledge. Since the proof size may not still be sufficiently succinct, we apply different techniques such as self-recursion, standard recursion, and proof aggregations. The security of different components and steps will be discussed in separate papers as we advance on the final design of the Linea prover.

The security of several cryptosystems rests on the trust assumption that a certain fraction of the parties are honest. This trust assumption has enabled a diverse of cryptographic applications such as secure multiparty computation, threshold encryption, and threshold signatures. However, current and emerging practical use cases suggest that this paradigm of one-person-one-vote is outdated. In this work, we consider {\em weighted} cryptosystems where every party is assigned a certain weight and the trust assumption is that a certain fraction of the total weight is honest. This setting can be translated to the standard setting (where each party has a unit weight) via virtualization. However, this method is quite expensive, incurring a multiplicative overhead in the weight. We present new weighted cryptosystems with significantly better efficiency. Specifically, our proposed schemes incur only an {\em additive} overhead in weights. \begin{itemize} \item We first present a weighted ramp secret-sharing scheme where the size of the secret share is as short as $O(w)$ (where $w$ corresponds to the weight). In comparison, Shamir's secret sharing with virtualization requires secret shares of size $w\cdot\lambda$, where $\lambda=\log |\mathbb{F}|$ is the security parameter. \item Next, we use our weighted secret-sharing scheme to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our secret sharing scheme and incur only an additive overhead in the weights. \end{itemize} Our weighted secret-sharing scheme is based on the Chinese remainder theorem. Interestingly, this secret-sharing scheme is {\em non-linear} and only achieves statistical privacy. These distinct features introduce several technical hurdles in applications to MPC and threshold cryptosystems. We resolve these challenges by developing several new ideas.

In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices. To mitigate this issue, Bolboceanu et al (Asiacrypt 2019) defined q-Order-LWE over any order (modulo q) in a number field and based its hardness on worst-case hard problems of ideal lattices of the same order, but restricted to invertible ideals. Orders generalize the ring of integers to non-Dedekind domains. In a subsequent work in 2021, they proved a non-effective ``ideal-clearing" lemma for q-Order-LWE for any q that is co-prime to index of the order in the ring of integers. This work can be shown to give an efficient reduction from any ideal of the same order. However, this requires factorization of arbitrary integers, namely the norm of the given ideal. In this work we give a novel approach to proving the ``ideal-clearing" lemma for q-Order-LWE by showing that all ideals I of an order are principal modulo qI, for any q that is co-prime to index of the order in the ring of integers. Further, we give a rather simple (classical) randomized algorithm to find a generator for this principal ideal, which makes our hardness reduction (from all ideals of the order) not require any further quantum steps on top of the quantum Gaussian sampling of the original Regev reduction. This also removes the ``known factorization" requirement on q for the original RLWE hardness result of Peikert et al. Finally, we recommend a ``twisted'' cyclotomic field as an alternative for the cyclotomic field used in NIST PQC algorithm CRYSTALS-Kyber, as it leads to a more efficient implementation and is based on hardness of ideals in a non-Dedekind domain following Dedekind index theorem.

The hash function Romulus-H is a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose double block-length (DBL) construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. Therefore, the security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been studied with only a few other block ciphers, like IDEA and AES. However, Romulus-H uses Hirose DBL with the SKINNY block cipher where only very little analysis has been published so far. In this work, we present the first practical analysis of Romulus-H. We propose a new framework for finding collisions in hash functions based on the Hirose DBL construction. This is in contrast to previous work that only focused on free-start collisions. Our framework is based on the idea of joint differential characteristics which capture the relationship between the two block cipher calls in the Hirose DBL construction. To identify good joint differential characteristics, we propose a combination of MILP and CP models. Then, we use these characteristics in another CP model to find collisions. Finally, we apply this framework to Romulus-H and find practical collisions of the hash function for 10 out of 40 rounds and practical semi-free-start collisions for up to 14 rounds.

As of 28 January 2022, Filecoin is ranked as the first capitalized storage-oriented cryptocurrency. In this system, miners dedicate their storage space to the network and verify transactions to earn rewards. Nowadays, Filecoin's network capacity has surpassed 15 exbibytes. In this paper, we propose three temporary block withholding attacks to challenge Filecoin's expected consensus (EC). Specifically, we first deconstruct EC following old-fashioned methods (which have been widely developed since 2009) to analyze the advantages and disadvantages of EC's design. We then present three temporary block withholding schemes by leveraging the shortcomings of EC. We build Markov Decision Process (MDP) models for the three attacks to calculate the adversary's gains. We develop Monte Carlo simulators to mimic the mining strategies of the adversary and other miners and indicate the impacts of the three attacks on expectation. As a result, we show that our three attacks have significant impacts on Filecoin's mining fairness and transaction throughput. For instance, when honest miners who control more than half the global storage power assemble their tipsets after the default transmission cutoff time, an adversary with 1% of the global storage power is able to launch temporary block withholding attacks without a loss in revenue, which is rare in existing blockchains. Finally, we discuss the implications of our attacks and propose several countermeasures to mitigate them.

We investigate the security of the NIST Lightweight Crypto Competition’s Finalists against side-channel attacks. We start with a mode-level analysis that allows us to put forward three candidates (As- con, ISAP and Romulus-T) that stand out for their leakage properties and do not require a uniform protection of all their computations thanks to (expensive) implementation-level countermeasures. We then implement these finalists and evaluate their respective performances. Our results confirm the interest of so-called leveled implementations (where only the key derivation and tag generation require security against differential power analysis). They also suggest that these algorithms differ more by their qualitative features (e.g., two-pass designs to improve confidentiality with decryption leakage vs. one-pass designs, flexible overheads thanks to masking vs. fully mode-level, easier to implement, schemes) than by their quantitative features, which all improve over the AES and are quite sensitive to security margins against cryptanalysis.

In this work, we introduce the random fault model - a more advanced fault model inspired by the random probing model, where the adversary can fault all values in the algorithm but the probability for each fault to occur is limited. The new adversary model is used to evaluate the security of side-channel and fault countermeasures such as Boolean masking, error detection techniques, error correction techniques, multiplicative tags, and shuffling methods. The results of the security analysis reveal new insights both in the novel random fault model as well as in the established random probing model including: shuffling masked implementations does not significantly improve the random probing security over regular masking; error correction providing little security when faults target more bits (versus the significant improvement when using error detection); and the order in which masking and duplication are applied providing a trade-off between random probing and fault security. Moreover, the results also explain the experimental results from CHES 2022 and find weaknesses in the shuffling method from SAMOS 2021.

We present a candidate sequential function for a VDF protocol to be used within the Ethereum ecosystem. The new function, called MinRoot, is an optimized iterative algebraic transformation and is a strict improvement over competitors VeeDo and Sloth++. We analyze various attacks on sequentiality and suggest weakened versions for public scrutiny. We also announce bounties on certain research directions in cryptanalysis.

Threshold Fully Homomorphic Encryption (ThFHE) enables arbitrary computation over encrypted data while keeping the decryption key distributed across multiple parties at all times. ThFHE is a key enabler for threshold cryptography and, more generally, secure distributed computing. Existing ThFHE schemes inherently require highly inefficient parameters and are unsuitable for practical deployment. In this paper, we take the first step towards making ThFHE practically usable by (i) proposing a novel ThFHE scheme with a new analysis resulting in significantly improved parameters; (ii) and providing the first practical ThFHE implementation benchmark based on Torus FHE. • We propose the first practical ThFHE scheme with a polynomial modulus-to-noise ratio that supports practically efficient parameters while retaining provable security based on standard quantum-safe assumptions. We achieve this via a novel Rényi divergence-based security analysis of our proposed threshold decryption mechanism. • We present an optimized software implementation of a Torus-FHE based instantiation of our proposed ThFHE scheme that builds upon the existing Torus FHE library and supports (distributed) decryption on highly resource-constrained ARM-based handheld devices. Along the way, we implement several extensions to the Torus FHE library, including a Torus-based linear integer secret sharing subroutine to support ThFHE key sharing and distributed decryption for any threshold access structure. We illustrate the efficacy of our proposal via an end-to-end use case involving encrypted computations over a real medical database, and distributed decryptions of the computed result on resource-constrained ARM-based handheld devices.

The task of ensuring the required level of security of information systems in the adversary models with additional data obtained through side channels (a striking example of implementing threats in such a model is a differential power analysis) has become increasingly relevant in recent years. An effective protection method against side-channel attacks is masking all intermediate variables used in the algorithm with random values. At the same time, many algorithms use masking of different kinds, for example, Boolean, byte-wise, and arithmetic; therefore, a problem of switching between masking of different kinds arises. Switching between Boolean and arithmetic masking is well studied, while no solutions have been proposed for switching between masking of other kinds. This article recalls the requirements for switching algorithms and presents algorithms for switching between block-wise and arithmetic masking, which includes the case of switching between byte-wise and arithmetic masking.

The $\mathcal{S}_{leeve}$ construction proposed by Chaum et al. (ACNS'21) introduces an extra security layer for digital wallets by allowing users to generate a "back up key" securely nested inside the secret key of a signature scheme, i.e., ECDSA. The "back up key", which is secret, can be used to issue a "proof of ownership", i.e., only the real owner of this secret key can generate a single proof, which is based on the WOTS+ signature scheme. The authors of $\mathcal{S}_{leeve}$ proposed the formal technique for a single proof of ownership, and only informally outlined a construction to generalize it to multiple proofs. This work identifies that their proposed construction presents drawbacks, i.e., varying of signature size and signing/verifying computation complexity, limitation of linear construction, etc. Therefore we introduce WOTSwana, a generalization of $\mathcal{S}_{leeve}$, which is, more concretely, a more general scheme, i.e., an extra security layer that generates multiple proofs of ownership, and put forth a thorough formalization of two constructions: (1) one given by a linear concatenation of numerous WOTS+ private/public keys, and (2) a construction based on tree like structure, i.e., an underneath Merkle tree whose leaves are WOTS+ private/public key pairs. Furthermore, we present the security analysis for multiple proofs of ownership, showcasing that this work addresses the early mentioned drawbacks of the original construction. In particular, we extend the original security definition for $\mathcal{S}_{leeve}$. Finally, we illustrate an alternative application of our construction, by discussing the creation of an encrypted group chat messaging application.

On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish honest users from bots or attackers. In this work, we focus on designing an anonymous token protocol between a client and an issuer (also a verifier) that enables the issuer to support its fraud detection mechanisms while preserving users' privacy. This is done by allowing the issuer to embed a hidden (from the client) metadata bit into the tokens. We first study an existing protocol from CRYPTO 2020 which is an extension of Privacy Pass from PoPETs 2018; that protocol aimed to provide support for a hidden metadata bit, but provided a somewhat restricted security notion. We demonstrate a new attack, showing that this is a weakness of the protocol, not just the definition. In particular, the metadata bit hiding is weak in the setting where the attacker can redeem some tokens and get feedback on whether the bit extraction succeeded. We then revisit the formalism of anonymous tokens with private metadata bit, consider the more natural notion, and design a scheme which achieves it. In order to design this new secure protocol, we base our construction on algebraic MACs instead of PRFs. Our security definitions capture a realistic threat model where adversaries could, through direct feedback or side channels, learn the embedded bit when the token is redeemed. Finally, we compare our protocol with one of the CRYPTO 2020 protocols. We obtain 20% more efficient performance.

Private comparison schemes constructed on homomorphic encryption offer the noninteractive, output expressive and parallelizable features, and have advantages in communication bandwidth and performance. In this paper, we propose cuXCMP, which allows negative and float inputs, offers fully output expressive feature, and is more extensible and practical compared to XCMP (AsiaCCS 2018). Meanwhile, we introduce several memory-centric optimizations of the constant term extraction kernel tailored for CUDA-enabled GPUs. Firstly, we fully utilize the shared memory and present compact GPU implementations of NTT and INTT using a single block; Secondly, we fuse multiple kernels into one AKS kernel, which conducts the automorphism and key switching operation, and reduce the grid dimension for better resource usage, data access rate and synchronization. Thirdly, we precisely measure the IO latency and choose an appropriate number of CUDA streams to enable concurrent execution of independent operations, yielding a constant term extraction kernel with perfect latency hide, i.e., CTX. Combining these approaches, we boost the overall execution time to optimum level and the speedup ratio increases with the comparison scales. For one comparison, we speedup the AKS by 23.71×, CTX by 15.58×, and scheme by 1.83× (resp., 18.29×, 11.75×, and 1.42×) compared to C (resp., AVX512) baselines, respectively. For 32 comparisons, our CTX and scheme implementations outperform the C (resp., AVX512) baselines by 112.00× and 1.99× (resp., 81.53× and 1.51×).

Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions. In this work, we provide both negative and positive results for publicly verifiable quantum money. **In the first part, we give a general theorem, showing that a certain natural class of quantum money schemes from lattices cannot be secure. We use this theorem to break the recent quantum money scheme of Khesin, Lu, and Shor. **In the second part, we propose a framework for building quantum money and quantum lightning we call invariant money which abstracts some of the ideas of quantum money from knots by Farhi et al.(ITCS'12). In addition to formalizing this framework, we provide concrete hard computational problems loosely inspired by classical knowledge-of-exponent assumptions, whose hardness would imply the security of quantum lightning, a strengthening of quantum money where not even the bank can duplicate banknotes. **We discuss potential instantiations of our framework, including an oracle construction using cryptographic group actions and instantiations from rerandomizable functional encryption, isogenies over elliptic curves, and knots.

For avoding the attacks from quantum computing (QC), this study applies the post-quantum cryptography (PQC) methods without hidden subgroups to the security of vehicular communications. Due the mainstream technologies of PQC methods (i.e. lattice-based cryptography methods), the standard digital signature methods including Dilithium and Falcon have been discussed and compared. This study uses a queueing model to analyze the performance of these standard digital signature methods for selection decision-making.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.

RAGHAV is a 64-bit block cipher proposed by Bansod in 2021. It supports 80-, and 128-bit secret keys. The designer evaluated its security against typical attack, such as differential cryptanalysis, linear cryptanalysis, and so on. On the other hand, it has not been reported the security of RAGHAV against higher order differential attack, which is one of the algebraic attacks. In this paper, we applied higher order differential cryptanalysis to RAGHAV. As a results, we found a new full-round higher order characteristic of RAGHAV using 1-st order differential. Exploiting this characteristic, we also show that the full-round of RAGHAV is attackable by distinguishing attack with 2 chosen plaintexts.

Sharing a secret efficiently amongst a group of participants is not easy since there is always an adversary / eavesdropper trying to retrieve the secret. In secret sharing schemes, every participant is given a unique share. When the desired group of participants come together and provide their shares, the secret is obtained. For other combinations of shares, a garbage value is returned. A threshold secret sharing scheme was proposed by Shamir and Blakeley independently. In this (n,t) threshold secret sharing scheme, the secret can be obtained when at least $t$ out of $n$ participants contribute their shares. This paper proposes a novel algorithm to reveal the secret only to the subsets of participants belonging to the access structure. This scheme implements totally generalized ideal secret sharing. Unlike threshold secret sharing schemes, this scheme reveals the secret only to the authorized sets of participants, not any arbitrary set of users with cardinality more than or equal to $t$. Since any access structure can be realized with this scheme, this scheme can be exploited to implement various access priorities and access control mechanisms. A major advantage of this scheme over the existing ones is that the shares being distributed to the participants is totally independent of the secret being shared. Hence, no restrictions are imposed on the scheme and it finds a wider use in real world applications.

The recent advent of cloud computing and IoT has made it imperative to store huge amount of data in the cloud servers. Enormous amount of data is also stored in the servers of big organizations. In organizations, it is not desirable for every member to have equal privileges to access the stored data. Threshold secret sharing schemes are widely used for implementing such access control mechanisms. The access privileges of the members also vary from one data packet to another. While implementing such dynamic access structures using threshold secret sharing schemes, the key management becomes too complex to be implemented in real time. Furthermore, the storage of the users’ access privileges requires exponential space (O($2^n$)) and its implementation requires exponential time. In this paper, the algorithms proposed to tackle the problems of priority based access control and authentication require a space complexity of O($n^2$) and a time complexity of O($n$), where n is the number of users. In the practical scenario, such space can easily be provided on the servers and the algorithms can run smoothly in real time.

Off-chain payment channels were introduced as one of the solutions to the blockchain scalability problem. The channels shape a network, where parties have to lock funds for their creation. A channel is expected to route a limited number of transactions before it becomes unbalanced, when all of the funds are devoted to one of the parties. Since an on-chain transaction is often necessary to establish, rebalance, or close a channel, the off-chain network is bounded to the throughput of the blockchain. In this paper, we propose a mathematical model to formulate limitation on the throughput of an off-chain payment network. As a case study, we show the limitation of the Lightning Network, in comparison with popular banking systems. Our results show that theoretically, the throughput of the Lightning Network can reach the order of 10000 transactions per second, close to the average throughput of centralized banking systems.

Classic McEliece is a code based encryption scheme and candidate of the NIST post quantum contest. Implementing Classic McEliece on smart card chips is a challenge, because those chips have only a very limited amount of RAM. Decryption is not an issue because the cryptogram size is short and the decryption algorithm can be implemented using very few RAM. However key generation is a concern, because a large binary matrix must be inverted. In this paper, we show how key generation can be done on smart card chips with very little RAM resources. This is accomplished by modifying the key generation algorithm and splitting it in a security critical part and a non security critical part. The security critical part can be implemented on the smart card controller. The non critical part contains the matrix inversion and will be done on a connected host.

Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space. In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We design the first such zero-knowledge system with sublinear communication complexity (when the underlying $\textsf{NP}$ relation uses non-trivial space) and provide evidence why existing techniques are unlikely to improve the communication complexity in this setting. Namely, for every NP relation that can be verified in time T and space S by a RAM program, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\widetilde{O}(T)$ and space $\widetilde{O}(S)$, the verifier runs in time $\widetilde{O}(T/S+S)$ and space $\widetilde{O}(1)$ and the communication is $\widetilde{O}(T/S)$, where $\widetilde{O}()$ ignores polynomial factors in $\log T$ and $\kappa$ is the security parameter. As our construction is public-coin, we can apply the Fiat-Shamir heuristic to make it non-interactive with sample communication/computation complexities. Furthermore, we give evidence that reducing the proof length below $\widetilde{O}(T/S)$ will be hard using existing symmetric-key based techniques by arguing the space-complexity of constant-distance error correcting codes.

BLS signatures have fast aggregated signature verification but slow individual signature verification. We propose a three part optimisation that dramatically reduces CPU time in large distributed system using BLS signatures: First, public keys should be given on both source groups $\mathbb{G}_1$ and $\mathbb{G}_2$, with a proof-of-possession check for correctness. Second, aggregated BLS signatures should carry their particular aggregate public key in $\mathbb{G}_2$, so that verifiers can do both hash-to-curve and aggregate public key checks in $\mathbb{G}_1$. Third, individual non-aggregated BLS signatures should carry short Chaum-Pedersen DLEQ proofs of correctness, so that verifying individual signatures no longer requires pairings, which makes their verification much faster. We prove security for these optimisations. The proposed scheme is implemented and benchmarked to compare with classic BLS scheme.

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.

The desirable encryption scheme possesses high PRF security, high efficiency, and the ability to produce variable-length outputs. Since designing dedicated secure PRFs is difficult, a series of works was devoted to building optimally secure PRFs from the sum of independent permutations (SoP), Encrypted Davies-Meyer (EDM), its Dual (EDMD), and the Summation-Truncation Hybrid (STH) for variable output lengths, which can be easily instantiated from existing permutations. For increased efficiency, reducing the number of operations in established primitives has been gaining traction: Mennink and Neves pruned EDMD to FastPRF, and Andreeva et al. introduced ForkCiphers, which take an n-bit input, process it through a reduced-round permutation, fork it into two states, and feed each of them into another reduced-round permutation to produce a 2n-bit output. The constructions above can be used in secure variable-length modes or generalizations such as MultiForkCiphers. In this paper, we suggest a framework of those constructions in terms of the three desiderata: we span the spectrum of (1) output length vs. PRF security, (2) full vs. round-reduced primitives, and (3) fixed- vs. variable-length outputs. From this point of view, we identify remaining gaps in the spectrum and fill them with the proposal of several highly secure and efficient fixed- and variable-output-length PRFs. We fork SoP and STH to ForkPRF and ForkSTH, extend STH to the variable-output-length construction STHCENC, which bridges the gap between CTR mode and CENC,and propose ForkCENC, ForkSTHCENC, ForkEDMD, as well as ForkEDM-CTR as the variable-output-length and round-reduced versions of CENC, STH, FastPRF, and FastPRF's dual, respectively. Using recent results on Patarin's general Mirror Theory, we have proven that almost all our proposed PRFs are optimally secure under the assumption that the permutations are pairwise independent and random and STH achieves the optimal security depending on the output length. Our constructions can be highly efficient in practice. We propose efficient instantiations from round-reduced AES and back it with the cryptanalysis lessons learned from existing earlier analysis of AES-based primitives.

We design and implement a simple zero-knowledge argument protocol for $\mathsf{NP}$ whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography. Our protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damg$\mathring{a}$rd and Ishai (CRYPTO 2006). It can be viewed as a simple zero-knowledge interactive PCP based on ``interleaved'' Reed-Solomon codes. This paper is an extended version of the paper published in CCS 2017 and features a tighter analysis, better implementation along with formal proofs. For large verification circuits, the Ligero prover remains competitive against subsequent works with respect to the prover’s running time, where our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously. Our protocol is attractive not only for very large verification circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage with $2^{-40}$ soundness error, the communication complexity is roughly 35KB. The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For $2^{-40}$ soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. With our refined analysis the Ligero system's proof lengths and prover's running times are better than subsequent post-quantum ZK-SNARKs for small to moderately large circuits.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. has briefly noticed this issue, we present the first comprehensive study of correctness in UC PAKE. Our contributions are four-fold: 1. We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE; 2. We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable; 3. We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible; 4. Finally, we show how to naturally incorporate correctness by changing the model — we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party. In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.

Accountability is a well-established and widely used security concept that allows for obtaining undeniable cryptographic proof of misbehavior, thereby incentivizing honest behavior. There already exist several general purpose accountability frameworks for formal game-based security analyses. Unfortunately, such game-based frameworks do not support modular security analyses, which is an important tool to handle the complexity of modern protocols. Universal composability (UC) models provide native support for modular analyses, including re-use and composition of security results. So far, accountability has mainly been modeled and analyzed in UC models for the special case of MPC protocols, with a general purpose accountability framework for UC still missing. That is, a framework that among others supports arbitrary protocols, a wide range of accountability properties, handling and mixing of accountable and non-accountable security properties, and modular analysis of accountable protocols. To close this gap, we propose AUC, the first general purpose accountability framework for UC models, which supports all of the above, based on several new concepts. We exemplify AUC in three case studies not covered by existing works. In particular, AUC unifies existing UC accountability approaches within a single framework.

Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency that allows users to atomically exchange coins. While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting (which also degrades fungibility and leads to high transaction fees), do not support atomic swaps across a wide range of currencies, or come with incomplete security proofs. To overcome these limitations, we introduce Sweep-UC (Read as Sweep Ur Coins.), the first fair exchange protocol that simultaneously is efficient, minimizes scripting, and is compatible with a wide range of currencies (more than the state of the art). We build Sweep-UC from modular sub-protocols and give a rigorous security analysis in the UC framework. Many of our tools and security definitions can be used in standalone fashion and may serve as useful components for future constructions of fair exchange.

ARIA is a block cipher proposed by Kwon et al. at ICISC 2003, and it is widely used as the national standard block cipher in the Republic of Korea. In this study, we identify some flaws in the quantum rebound attack on 7-round ARIA-DM proposed by Dou et al., and we reveal that the limit of this attack is up to 5-round. Our revised attack applies not only to ARIA-DM but also to ARIA-MMO and ARIA-MP among the PGV models, and it is valid for all key lengths of ARIA. Moreover, we present dedicated quantum rebound attacks on 7-round ARIA-Hirose and ARIA-MJH for the first time. These attacks are only valid for the 256-bit key length of ARIA because they are constructed using the degrees of freedom in the key schedule. All our attacks are faster than the generic quantum attack in the cost metric of time–space tradeoff.

Fruit is a small-state stream cipher designed for securing communications among resource-constrained devices. The design of Fruit was first known to the public in 2016. It was later improved as Fruit-80 in 2018 and becomes the latest and final version among all versions of the Fruit stream ciphers. In this paper, we analyze the Fruit-80 stream cipher. We found that Fruit-80 generates identical keystreams from certain two distinct pairs of key and IV. Such pair of key and IV pairs is known as a slid pair. Moreover, we discover that when two pairs of key and IV fulfill specific characteristics, they will generate identical keystreams. This shows that slid pairs do not always exist arbitrarily in Fruit-80. We define specific rules which are equivalent to the characteristics. Using the defined rules, we are able to automate the searching process using an MILP solver, which makes searching of the slid pairs trivial.

Data privacy concerns are increasing significantly in the context of Internet of Things, cloud services, edge computing, artificial intelligence applications, and other applications enabled by next generation networks. Homomorphic Encryption addresses privacy challenges by enabling multiple operations to be performed on encrypted messages without decryption. This paper comprehensively addresses homomorphic encryption from both theoretical and practical perspectives. The paper delves into the mathematical foundations required to understand fully homomorphic encryption (FHE). It consequently covers design fundamentals and security properties of FHE and describes the main FHE schemes based on various mathematical problems. On a more practical level, the paper presents a view on privacy-preserving Machine Learning using homomorphic encryption, then surveys FHE at length from an engineering angle, covering the potential application of FHE in fog computing, and cloud computing services. It also provides a comprehensive analysis of existing state-of-the-art FHE libraries and tools, implemented in software and hardware, and the performance thereof.

In this paper, we reconsider the security for CRYSTALS-Dilithium, a lattice-based post-quantum signature scheme standardized by NIST. In their documentation, the authors proved that the security of the signature scheme can be based on the hardness of the following three assumptions: MLWE, MSIS and SelfTargetMSIS. While the first two are standard lattice assumptions with hardness well studied, the authors claimed that the third assumption SelfTargetMSIS can be estimated by the hardness of MSIS (and further into SIS). However, we point out that this is in fact not the case. We give a new algorithm for solving SelfTargetMSIS, by both experimental results and asymptotic complexities, we prove that under specific parameters, solving SelfTargetMSIS might be faster than MSIS. Although our algorithm does not propose a real threat to parameters used in Dilithium, we successfully show that solving SelfTargetMSIS cannot be turned into solving MSIS or MISIS. Furthermore, we define a new variant of MISIS, called sel-MISIS, and show that solving SelfTargetMSIS can only be turned into solving sel-MISIS. We believe that in order to fully understand the concrete hardness of SelfTargetMSIS and prevent potential attacks to Dilithium, the hardness of this new problem needs to be further studied.

We present novel protocols to compute SQL-like join operations on secret shared database tables with non-unique join keys. Previous approaches to the problem had the restriction that the join keys of both the input tables must be unique or had quadratic overhead. Our work lifts this restriction, allowing one or both of the secret shared input tables to have an unknown and unbounded number of repeating join keys while achieving efficient $O(n\log n)$ asymptotic communication/computation and $O(\log n)$ rounds of interaction, independent of the multiplicity of the keys. We present two join protocols, \ProtoUni and \ProtoDup. The first, \ProtoUni is optimized for the case where one table has a unique primary key while the second, \ProtoDup is for the more general setting where both tables contain duplicate keys. Both protocols require $O(n \log n)$ time and $O(\log n)$ rounds to join two tables of size $n$. Our framework for computing joins requires an efficient sorting protocol and generic secure computation for circuits. We concretely instantiate our protocols in the honest majority three-party setting. Our join protocols are built around an efficient method to compute structured aggregations over a secret shared input vector $\V\in \mathbb{D}^n$. If the parties have another secret-shared vector of control bits $\B \in \{0, 1\}^n$ to partition $\V$ into sub-vectors (that semantically relates to the join operations). A structured aggregation computes a secret shared vector $\V'\in \mathbb{D}^n$ where every sub-vector $(\V_b,...,\V_e)$ (defined by the control bits) is aggregated as $\V_i'=\V_b\op...\op \V_i$ for $i\in \{b,...,e\}$ according to some user-defined operator $\op$. Critically, the $b,e$ indices that partition the vector are secret. It's trivial to compute aggregations by sequentially processing the input vector and control bits. This would require $O(n)$ rounds and would be very slow due to network latency. We introduce Aggregation Trees as a general technique to compute aggregations in $O(\log n)$ rounds. For our purpose of computing joins, we instantiate $\op \in$ \textsf{\{copy previous value, add\}}, but we believe that this technique is quite powerful and can find applications in other useful settings.

We initiate the study of streaming functional encryption (sFE) which is designed for scenarios in which data arrives in a streaming manner and is computed on in an iterative manner as the stream arrives. Unlike in a standard functional encryption (FE) scheme, in an sFE scheme, we (1) do not require the entire data set to be known at encryption time and (2) allow for partial decryption given only a prefix of the input. More specifically, in an sFE scheme, we can sequentially encrypt each data point $x_i$ in a stream of data $x = x_1\ldots x_n$ as it arrives, without needing to wait for all $n$ values. We can then generate function keys for streaming functions which are stateful functions that take as input a message $x_i$ and a state $\mathsf{st}_i$ and output a value $y_i$ and the next state $\mathsf{st}_{i+1}$. For any $k \leq n$, a user with a function key for a streaming function $f$ can learn the first $k$ output values $y_1\ldots y_k$ where $(y_i, \mathsf{st}_{i+1}) = f(x_i, \mathsf{st}_i)$ and $\mathsf{st}_1 = \bot$ given only ciphertexts for the first $k$ elements $x_1\ldots x_k$. In this work, we introduce the notion of sFE and show how to construct it from FE. In particular, we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from a compact, secure FE scheme for $\mathsf{P/Poly}$, where our security notion for sFE is similar to standard FE security except that we require all function queries to be made before the challenge ciphertext query. Furthermore, by combining our result with the FE construction of Jain, Lin, and Sahai (STOC, 2022), we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from the polynomial hardness of well-studied assumptions.

In this work, we put forward the notion of ``efficiently testable circuits'' and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set. Our technical contribution is a compiler that transforms any circuit $C$ into a testable circuit $(\widehat{C}, \widehat{T})$ for which we can detect arbitrary tampering with all wires in $\widehat{C}$. The notion of a testable circuit is weaker or incomparable to existing notions of tamper-resilience, which aim to detect or even correct for errors introduced by tampering during every query, but our new notion is interesting in several settings, and we achieve security against much more general tampering classes -- like tampering with all wires -- with very modest overhead. Concretely, starting from a circuit $C$ of size $n$ and depth $d$, for any $L$ (think of $L$ as a small constant, say $L=4$), we get a testable $(\widehat{C}, \widehat{T})$ where $\widehat{C}$ is of size $\approx 12n$ and depth $d+\log(n)+L\cdot n^{1/L}$. The test set $\widehat{T}$ is of size $4\cdot 2^L$. The number of extra input and output wires (i.e., pins) we need to add for the testing is $3+L$ and $2^L$, respectively.

The paper " An energy and area efficient, all digital entropy source compatible with modern standards based on jitter pipelining", by Peetermans and Verbauwhede, IACR Transactions on Cryptographic Hardware and Embedded Systems, Aug. 2022, 88-109, suggests a pipelined TRNG design and a stochastic model for it. The stochastic model is shown to be inadequate and other problems of the TRNG design are identified. Possible fixes for the problems are considered.

We propose and analyze LowMS, a new rank-based key encapsulation mechanism (KEM). The acronym stands for Loidreau with Multiple Syndromes, since our work combines the cryptosystem of Loidreau (presented at PQCrypto 2017) together with the multiple syndrome approach, that allows to reduce parameters by sending several syndromes with the same error support in one ciphertext. Our scheme is designed without using ideal structures. Considering cryptosystems without such an ideal structure, like the FrodoKEM cryptosystem, is important since structure allows to compress objects, but gives reductions to specific problems whose security may potentially be weaker than for unstructured problems. For 128 bits of security, we propose parameters with a public key size of 4,6KB and a ciphertext size of 1,1KB. To the best of our knowledge, our scheme is the smallest among all existing unstructured post-quantum lattice or code-based algorithms, when taking into account the sum of the public key size and the ciphertext size. In that sense, our scheme is for instance about 4 times shorter than FrodoKEM. Our system relies on the hardness of the Rank Support Learning problem, a well-known variant of the Rank Syndrome Decoding problem, and on the problem of indistinguishability of distorted Gabidulin codes, i.e. Gabidulin codes multiplied by an homogeneous matrix of given rank. The latter problem was introduced by Loidreau in his paper.

We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step. We implemented our sorting protocol with different optimizations and achieved concretely fast performance. For example, sorting one million items with 32-bit keys and 32-bit values takes less than 2 seconds with semi-honest security and about 3.5 seconds with malicious security. Finding the heavy hitters among hundreds of thousands of 256-bit values takes only a few seconds, compared to close to an hour in previous work.

This paper presents the first functional encryption (FE) scheme for the attribute-weighted sum (AWS) functionality that supports the uniform model of computation. In such an FE scheme, encryption takes as input a pair of attributes (x,z) where the attribute x is public while the attribute z is private. A secret key corresponds to some weight function f, and decryption recovers the weighted sum f(x)z. This is an important functionality with a wide range of potential real life applications, many of which require the attribute lengths to be flexible rather than being fixed at system setup. In the proposed scheme, the public attributes are considered as binary strings while the private attributes are considered as vectors over some finite field, both having arbitrary polynomial lengths that are not fixed at system setup. The weight functions are modeled as Logspace Turing machines. Prior schemes [Abdalla, Gong, and Wee, CRYPTO 2020 and Datta and Pal, ASIACRYPT 2021] could only support non-uniform Logspace. The proposed scheme is built in asymmetric prime-order bilinear groups and is proven adaptively simulation secure under the well-studied symmetric external Diffie-Hellman (SXDH) assumption against an arbitrary polynomial number of secret key queries both before and after the challenge ciphertext. This is the best possible level of security for FE as noted in the literature. As a special case of the proposed FE scheme, we also obtain the first adaptively simulation secure inner-product FE (IPFE) for vectors of arbitrary length that is not fixed at system setup. On the technical side, our contributions lie in extending the techniques of Lin and Luo [EUROCRYPT 2020] devised for payload hiding attribute-based encryption (ABE) for uniform Logspace access policies avoiding the so-called “one-use” restriction in the indistinguishability-based security model as well as the “three-slot reduction” technique for simulation-secure attribute-hiding FE for non-uniform Logspace devised by Datta and Pal [ASIACRYPT 2021] to the context of simulation-secure attribute-hiding FE for uniform Logspace.

We provide a $\Sigma$-protocol for proving that two values committed in different groups are equal. We study our protocol in Lyubashevsky's framework "Fiat-Shamir with aborts" (Asiacrypt’09) and offer concrete parameters for instantiating it. We explain how to use it to compose SNARKs with $\Sigma$-protocols, create efficient proofs of solvency on cryptocurrencies, and join of attributes across different anonymous credentials.

We introduce the first decentralized trusted setup protocols for constructing a powers-of-tau structured reference string. Facilitated by a blockchain platform, our protocols can run in a permissionless manner, with anybody able to participate in exchange for paying requisite transaction fees. The result is secure as long as any single party participates honestly. We introduce several protocols optimized for different sized powers-of-tau setups and using an on-chain or off-chain data availability model to store the resulting string. We implement our most efficient protocol on top of Ethereum, demonstrating practical concrete performance numbers.

This paper analyses the lightweight, sponge-based NAEAD mode $\textsf{ISAP}$, one of the finalists of the NIST Lightweight Cryptography (LWC) standardisation project, that achieves high-throughput with inherent protection against differential power analysis (DPA). We observe that $\textsf{ISAP}$ requires $256$-bit capacity in the authentication module to satisfy the NIST LWC security criteria. In this paper, we study the analysis carefully and observe that this is primarily due to the collision in the associated data part of the hash function which can be used in the forgery of the mode. However, the same is not applicable to the ciphertext part of the hash function because a collision in the ciphertext part does not always lead to a forgery. In this context, we define a new security notion, named $\textsf{2PI+}$ security, which is a strictly stronger notion than the collision security, and show that the security of a class of encrypt-then-hash based MAC type of authenticated encryptions, that includes $\textsf{ISAP}$, reduces to the $\textsf{2PI+}$ security of the underlying hash function used in the authentication module. Next we investigate and observe that a feed-forward variant of the generic sponge hash achieves better $\textsf{2PI+}$ security as compared to the generic sponge hash. We use this fact to present a close variant of $\textsf{ISAP}$, named $\textsf{ISAP+}$, which is structurally similar to $\textsf{ISAP}$, except that it uses the feed-forward variant of the generic sponge hash in the authentication module. This improves the overall security of the mode, and hence we can set the capacity of the ciphertext part to $192$ bits (to achieve a higher throughput) and yet satisfy the NIST LWC security criteria.

We introduce a modification of the Russian standardized AEAD MGM mode — an MGM2 mode, for which a nonce is not encrypted anymore before using it as an initial counter value. For the new mode we provide security bounds regarding security notions in the nonce-misuse setting (MRAE-integrity and CPA-resilience). The obtained bounds are even better than the bounds obtained for the original MGM mode regarding standard security notions.

Continuous authentication has been proposed as a complementary security mechanism to password-based authentication for computer devices that are handled directly by humans, such as smart phones. Continuous authentication has some privacy issues as certain user features and actions are revealed to the authentication server, which is not assumed to be trusted. Wei et al. proposed in 2021 a privacy-preserving protocol for behavioral authentication that utilizes homomorphic encryption. The encryption prevents the server from obtaining sampled user features. In this paper, we show that the Wei et al. scheme is insecure regarding both an honest-but-curious server and an active eavesdropper. We present two attacks. The first attack enables the authentication server to obtain the secret user key, plaintext behavior template and plaintext authentication behavior data from encrypted data. The second attack enables an active eavesdropper to restore the plaintext authentication behavior data from the transmitted encrypted data.

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $n$, where $n$ is the integer whose factorization is sought. The algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or $\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus.

Two main secondary constructions of bent functions are the direct and indirect sum methods. We show that the direct sum, under more relaxed conditions compared to those in \cite{PolujanandPott2020}, can generate bent functions provably outside the completed Maiorana-McFarland class ($\mathcal{MM}^\#$). We also show that the indirect sum method, though imposing certain conditions on the initial bent functions, can be employed in the design of bent functions outside $\mathcal{MM}^\#$. Furthermore, applying this method to suitably chosen bent functions we construct several generic classes of homogenous cubic bent functions (considered as a difficult problem) that might posses additional properties (namely without affine derivatives and/or outside $\mathcal{MM}^\#$). Our results significantly improve upon the best known instances of this type of bent functions given by Polujan and Pott \cite{PolujanandPott2020}, and additionally we solve an open problem in \cite[Open Problem 5.1]{PolujanandPott2020}. More precisely, we show that one class of our homogenous cubic bent functions is non-decomposable (inseparable) so that $h$ under a non-singular transform $B$ cannot be represented as $h(xB)=f(y)\oplus g(z)$. Finally, we provide a generic class of vectorial bent functions strongly outside $\mathcal{MM}^\#$ of relatively large output dimensions, which is generally considered as a difficult task.

With the emergence of decentralized systems, spearheaded by blockchains, threshold cryptography has seen unprecedented adoption. Just recently, the trustless distribution of threshold keys over an unreliable network has started to become practical. The next logical step is ensuring the security of these keys against persistent adversaries attacking the system over long periods of time. In this work, we tackle this problem and give two practical constructions for Asynchronous Proactive Secret Sharing. Our first construction uses recent advances in asynchronous protocols and achieves a communication complexity of $O(n^3)$ where $n$ is the total number of nodes in the network. The second protocol builds upon the first and uses sortition to drive down the communication complexity to $O(c n^2)$. Here, $c$ is a tunable parameter that controls the expected size of the sharing committee chosen using the existing random coin. Additionally, we identify security flaws in prior work and ensure that our protocols are secure by giving rigorous proofs. Moreover, we introduce a related notion which we term Asynchronous Refreshable Secret Sharing — a functionality that also re-randomizes the secret itself. Finally, we demonstrate the practicability of our constructions by implementing them in Rust and running large-scale, geo-distributed benchmarks.

User attributes can be authenticated by an attribute-based anonymous credential while keeping the anonymity of the user. Most attribute-based anonymous credential schemes are designed specifically for either multi-use or single-use. In this paper, we propose a unified attribute-based anonymous credential system, in which users always obtain the same format of credential from the issuer. The user can choose to use it for an efficient multi-use or single-use show proof. It is a more user-centric approach than the existing schemes. Technically, we propose an interactive approach to the credential issuance protocol using a two-party computation with an additive homomorphic encryption. At the same time, it keeps the security property of impersonation resilience, anonymity, and unlinkability. Apart from the interactive protocol, we further design the show proofs for efficient single-use credentials which maintain the user anonymity.

Extending work leveraging program obfuscation to instantiate random-oracle-based transforms (e.g., Hohenberger et al., EUROCRYPT 2014, Kalai et al., CRYPTO 2017), we show that, using obfuscation and other assumptions, there exist standard-model hash functions that suffice to instantiate the classical RO-model encryption transforms OAEP (Bellare and Rogaway, EUROCRYPT 1994) and Fujisaki-Okamoto (CRYPTO 1999, J. Cryptology 2013) for specific public-key encryption (PKE) schemes to achieve IND-CCA security. Our result for Fujisaki-Okamoto employs a simple modification to the scheme. Our instantiations do not require much stronger assumptions on the base schemes compared to their corresponding RO-model proofs. For example, to instantiate low-exponent RSA-OAEP, the assumption we need on RSA is sub-exponential partial one-wayness, matching the assumption (partial one-wayness) on RSA needed by Fujisaki et al. (J. Cryptology 2004) in the RO model up to sub-exponentiality. For the part of Fujisaki-Okamoto that upgrades public-key encryption satisfying indistinguishability against plaintext checking attack to IND-CCA, we again do not require much stronger assumptions up to sub-exponentiality. We obtain our hash functions in a unified way, extending a technique of Brzuska and Mittelbach (ASIACRYPT 2014). We incorporate into their technique: (1) extremely lossy functions (ELFs), a notion by Zhandry (CRYPTO 2016), and (2) multi-bit auxiliary-input point function obfuscation (MB-AIPO). While MB-AIPO is impossible in general (Brzuska and Mittelbach, ASIACRYPT 2014), we give plausible constructions for the special cases we need, which may be of independent interest.

Multi-party quantum computation (MPQC) allows a set of parties to securely compute a quantum circuit over private quantum data. Current MPQC protocols rely on the fact that the network is synchronous, i.e., messages sent are guaranteed to be delivered within a known fixed delay upper bound, and unfortunately completely break down even when only a single message arrives late. Motivated by real-world networks, the seminal work of Ben-Or, Canetti and Goldreich (STOC'93) initiated the study of multi-party computation for classical circuits over asynchronous networks, where the network delay can be arbitrary. In this work, we begin the study of asynchronous multi-party quantum computation (AMPQC) protocols, where the circuit to compute is quantum. Our results completely characterize the optimal achievable corruption threshold: we present an $n$-party AMPQC protocol secure up to $t<n/4$ corruptions, and an impossibility result when $t\geq n/4$ parties are corrupted. Remarkably, this characterization differs from the analogous classical setting, where the optimal corruption threshold is $t<n/3$.

Numerous security vulnerability assessment techniques urge precise and fast finite state machines (FSMs) extraction from the design under evaluation. Sequential logic locking, watermark insertion, fault-injection assessment of a System-ona- Chip (SoC) control flow, information leakage assessment, and reverse engineering at gate-level abstraction, to name a few, require precise FSM extraction from the synthesized netlist of the design. Unfortunately, no reliable solutions are currently available for fast and precise extraction of FSMs from the highly unstructured gate-level netlist for effective security evaluation. The major challenge in developing such a solution is precise recognition of FSM state flip-flops in a netlist having a massive collection of flip-flops. In this paper, we propose FSMx-Ultra, a framework for extracting FSMs from extremely unstructured gate-level netlists. FSMx-Ultra utilizes state-of-the-art graph theory concepts and algorithms to distinguish FSM state registers from other registers and then constructs gate-level state transition graphs (STGs) for each identified FSM state register using automatic test pattern generation (ATPG) techniques. The results of our experiments on 14 open-source benchmark designs illustrate that FSMx-Ultra can recover all FSMs quickly and precisely from synthesized gate-level netlists of diverse complexity and size utilizing various state encoding schemes.