The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large-scale deployments are still yet to come due to various challenges, including the heavy computation and communication (particularly broadcast) overhead in their adversarial cases. In this paper, we propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear computation and communication per-node cost with the help of a common coin, even in the face of the maximal amount of Byzantine nodes. Moreover, our protocol is secure against adaptive adversaries, which can corrupt less than half of all nodes. The key to our improvements lies in delegating the most costly operations to an Any-Trust group together with a set of techniques for adaptive security. This group is randomly sampled and consists of a small number of individuals. The population only trusts that at least one member in the group is honest, without knowing which one. Moreover, we present a generic transformer that enables us to efficiently deploy a conventional distributed protocol like our DKG, even when the participants have different weights. Additionally, we introduce an extended broadcast channel based on a blockchain and data dispersal network (such as IPFS), enabling reliable broadcasting of arbitrary-size messages at the cost of constant-size blockchain storage. Our DKG leads to a fully practical instantiation of Filecoin's checkpointing mechanism, in which all validators of a Proof-of-Stake (PoS) blockchain periodically run DKG and threshold signing to create checkpoints on Bitcoin, to enhance the security of the PoS chain. In comparison with the recent checkpointing approach of Babylon (Oakland, 2023), ours enjoys a significantly smaller cost of Bitcoin transaction fees. For $2^{12}$ validators, our cost is merely 0.4\% of that incurred by Babylon's approach.

A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal construction for a primitive can be constructed from a robust combiner for the primitive in many cases. Although robust combiners and universal constructions for classical cryptography are widely studied, robust combiners and universal constructions for quantum cryptography have not been explored so far. In this work, we define robust combiners and universal constructions for several quantum cryptographic primitives including one-way state generators, public-key quantum money, quantum bit commitments, and unclonable encryption, and provide constructions of them. On a different note, it was an open problem how to expand the plaintext length of unclonable encryption. In one of our universal constructions for unclonable encryption, we can expand the plaintext length, which resolves the open problem.

We show that the Nikooghadam-Shahriari-Saeidi authentication and key agreement scheme [J. Inf. Secur. Appl., 76, 103523 (2023)] cannot resist impersonation attack, not as claimed. An adversary can impersonate the RFID reader to cheat the RFID tag. The drawback results from its simple secret key invoking mechanism. We also find it seems difficult to revise the scheme due to the inherent flaw.

India is the largest democracy by population and has one of the largest deployments of e-voting in the world for national elections. However, the e-voting machines used in India are not end-to-end (E2E) verifiable. The inability to verify the tallying integrity of an election by the public leaves the outcome open to disputes. E2E verifiable e-voting systems are commonly regarded as the most promising solution to address this problem, but they had not been implemented or trialed in India. It was unclear whether such systems would be usable and practical to the Indian people. Previous works such as Helios require a set of tallying authorities (TAs) to perform the decryption and tallying operations, but finding and managing TAs can prove difficult. This paper presents a TA-free E2E verifiable online voting system based on the DRE-ip protocol. In collaboration with the local authority of New Town, Kolkata, India, we conducted an online voting trial as part of the 2022 Durga Puja festival celebration, during which residents of New Town were invited to use mobile phones to vote for their favourite pujas (festival decorations) in an E2E verifiable manner. 543 participants attended the Durga Puja trial and 95 of them provided feedback by filling in an anonymous survey after voting. Based on the voter feedback, participants generally found the system easy to use. This was the first time that an E2E online voting system had been built and tested in India, suggesting its feasibility for non-statutory voting scenarios.

Non-invasive fault injection attacks have emerged as significant threats to a spectrum of microelectronic systems ranging from commodity devices to high-end customized processors. Unlike their invasive counterparts, these attacks are more affordable and can exploit system vulnerabilities without altering the hardware physically. Furthermore, certain non-invasive fault injection strategies allow for remote vulnerability exploitation without the requirement of physical proximity. However, existing studies lack extensive investigation into these attacks across diverse target platforms, threat models, emerging attack strategies, assessment frameworks, and mitigation approaches. In this paper, we provide a comprehensive overview of contemporary research on non-invasive fault injection attacks. Our objective is to consolidate and scrutinize the various techniques, methodologies, target systems susceptible to the attacks, and existing mitigation mechanisms advanced by the research community. Besides, we categorize attack strategies based on several aspects, present a detailed comparison among the categories, and highlight research challenges with future direction. By underlining and discussing the landscape of cutting-edge, non-invasive fault injection, we hope more researchers, designers, and security professionals examine the attacks further and take such threats into consideration while developing effective countermeasures.

In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over large hidden rings using homomorphic encryption through modular multiplications. Initially designed for key encapsulation mechanism (KEM), HPPK ensures security through homomorphic encryption of public polynomials over concealed rings. This paper extends its application to a digital signature scheme. The framework of HPPK KEM can not be directly applied to the digital signatures dues to the different nature of verification procedure compared to decryption procedure. Thus, in order to use the core ideas of the HPPK KEM scheme in the framework of digital signatures, the authors introduce an extension of the Barrett reduction algorithm. This extension transforms modular multiplications over hidden rings into divisions in the verification equation, conducted over a prime field. The extended algorithm non-linearly embeds the signature into public polynomial coefficients, employing the floor function of big integer divisions. This innovative approach overcomes vulnerabilities associated with linear relationships of earlier MPPK DS schemes. The security analysis reveals exponential complexity for both private key recovery and forged signature attacks, taking into account that the bit length of the rings is twice that of the prime field size. The effectiveness of the proposed Homomorphic Polynomial Public Key Digital Signature (HPPK DS) scheme is illustrated through a practical toy example, showcasing its intricate functionality and enhanced security features.

SPHINCS+ is a signature scheme included in the first NIST post-quantum standard, that bases its security on the underlying hash primitive. As most of the runtime of SPHINCS+ is caused by the evaluation of several hash- and pseudo-random functions, instantiated via the hash primitive, offloading this computation to dedicated hardware accelerators is a natural step. In this work, we evaluate different architectures for hardware acceleration of such a hash primitive with respect to its use-case and evaluate them in the context of SPHINCS+. We attach hardware accelerators for different hash primitives (SHAKE256 and Asconxof for both full and round-reduced versions) to CPU interfaces having different transfer speeds. We show, that for most use-cases, data transfer determines the overall performance if accelerators are equipped with FIFOs.

In this short note, we present a simplified (but slower) version Clapoti of Clapotis, whose full description will appear later. Let 𝐸/𝔽_𝑞 be an elliptic curve with an effective primitive orientation by a quadratic imaginary order 𝑅 ⊂ End(𝐸). Let 𝔞 be an invertible ideal in 𝑅. Clapoti is a randomized polynomial time algorithm in 𝑂 ((log Δ_𝑅 + log 𝑞)^𝑂(1) ) operations to compute the class group action 𝐸 ↦ 𝐸_𝔞 ≃ 𝐸/𝐸[𝔞].

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ̸ = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search. In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(·), there exists of a circuit of size $2^{4n/5+o(n)}$ that solves the t(·)-bounded Kolmogorov complexity problem on every instance. Our algorithm is black-box in the description of the Universal Turing Machine employed in the definition of Kolmogorov Complexity, and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity problem of Liu and Pass (FOCS’20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC’91). We additionally demonstrate that no such black-box algorithm can have sub-exponential circuit size. Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 2^{4n/5+o(n)}; as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function.

How to achieve distributed differential privacy (DP) without a trusted central party is of great interest in both theory and practice. Recently, the shuffle model has attracted much attention. Unlike the local DP model in which the users send randomized data directly to the data collector/analyzer, in the shuffle model an intermediate untrusted shuffler is introduced to randomly permute the data, which have already been randomized by the users, before they reach the analyzer. The most appealing aspect is that while shuffling does not explicitly add more noise to the data, it can make privacy better. The privacy amplification effect in consequence means the users need to add less noise to the data than in the local DP model, but can achieve the same level of differential privacy. Thus, protocols in the shuffle model can provide better accuracy than those in the local DP model. What looks interesting to us is that the architecture of the shuffle model is similar to private aggregation, which has been studied for more than a decade. In private aggregation, locally randomized user data are aggregated by an intermediate untrusted aggregator. Thus, our question is whether aggregation also exhibits some sort of privacy amplification effect? And if so, how good is this ``aggregation model'' in comparison with the shuffle model. We conducted the first comparative study between the two, covering privacy amplification, functionalities, protocol accuracy, and practicality. The results as yet suggest that the new shuffle model does not have obvious advantages over the old aggregation model. On the contrary, protocols in the aggregation model outperform those in the shuffle model, sometimes significantly, in many aspects.

We present a three-party protocol that can protect both Transformer parameters and user data during the inference phase. For each feedforward inference process, our protocol only introduces permutation computation of input and output data on the user side. Our protocol, Secure Transformer Inference Protocol (STIP), can be applied to real-world services like ChatGPT.

Verification of program safety is often reducible to proving the unsatisfiability (i.e., validity) of a formula in Satisfiability Modulo Theories (SMT): Boolean logic combined with theories that formalize arbitrary first-order fragments. Zero-knowledge (ZK) proofs allow SMT formulas to be validated without revealing the underlying formulas or their proofs to other parties, which is a crucial building block for proving the safety of proprietary programs. Recently, Luo et al. (CCS 2022) studied the simpler problem of proving the unsatisfiability of pure Boolean formulas, but it does not support safety proofs generated by SMT solvers. This work presents ZKSMT, a novel framework for proving the validity of SMT formulas in ZK. We design a virtual machine (VM) tailored to efficiently represent the verification process of SMT validity proofs in ZK. Our VM can support the vast majority of popular theories when proving program safety while being complete and sound. To demonstrate this, we instantiate the commonly used theories of equality and linear integer arithmetic in our VM with theory-specific optimizations for proving them in ZK. ZKSMT achieves high practicality even when running on realistic SMT formulas generated by Boogie, a common tool for software verification. It achieves a three-order-of-magnitude improvement compared to a baseline that executes the proof verification code in a general ZK system.

Post-compromise security (PCS) has been a core goal of end-to-end encrypted messaging applications for many years, both in one-to-one continuous key agreement (CKA) and for groups (CGKA). At its essence, PCS relies on a compromised party to perform a key update in order to `self-heal'. However, due to bandwidth constraints, receive-only mode, and various other environmental demands of the growing number of use cases for such CGKA protocols, a group member may not be able to issue such updates. In this work, we address the issue of devices functioning in limited mode through the introduction of guardianship, where a designated guardian can perform key updates on the behalf of its paired edge device. We introduce a Guardianship PCS (GPCS) security, and provide an associated security experiment. We investigate various architectural designs in the pursuit of GPCS, provide constructions and security analyses, and describe trade-offs.

This paper describes Biscuit, a new multivariate-based signature scheme derived using the MPC-in-the-Head (MPCitH) approach. The security of Biscuit is related to the problem of solving a set of structured quadratic algebraic equations. These equations are highly compact and can be evaluated using very few multiplications (one multiplication per equation). The core of Biscuit is a rather simple MPC protocol for secure multiplications using standard optimized multiplicative triples. This paper also includes several improvements toward the initial version of Biscuit submitted to the NIST PQC standardization process for additional signature schemes. Notably, we introduce a new hypercube variant of Biscuit, refine the security analysis with recent third-party attacks, and present a new AVX2 implementation of Biscuit.

In this paper, we consider to generalize NIZK by empowering a prover to share a witness in a fine-grained manner with verifiers. Roughly, the prover is able to authorize a verifier to obtain extra information of witness, i.e., besides verifying the truth of the statement, the verifier can additionally obtain certain function of the witness from the accepting proof using a secret functional key provided by the prover. To fulfill these requirements, we introduce a new primitive called \emph{non-interactive zero-knowledge functional proofs (fNIZKs)}, and formalize its security notions. We provide a generic construction of fNIZK for any $\textsf{NP}$ relation $\mathcal{R}$, which enables the prover to share any function of the witness with a verifier. For a widely-used relation about set membership proof (implying range proof), we construct a concrete and efficient fNIZK, through new building blocks (set membership encryption and dual inner-product encryption), which might be of independent interest.

Widespread efforts to subvert acccess to strong cryptography has renewed interest in steganography, the practice of embedding sensitive messages in mundane cover messages. Recent efforts at provably secure steganography have only focused on text-based generative models and cannot support other types of models, such as diffusion models, which are used for high-quality image synthesis. In this work, we initiate the study of securely embedding steganographic messages into the output of image diffusion models. We identify that the use of variance noise during image generation provides a suitable steganographic channel. We develop our construction, Pulsar, by building optimizations to make this channel practical for communication. Our implementation of Pulsar is capable of embedding $\approx 275$-$542$ bytes (on average) into a single image without altering the distribution of the generated image, all in the span of $\approx 3$ seconds of online time on a laptop. In addition, we discuss how the results of Pulsar can inform future research into diffusion models. Pulsar shows that diffusion models are a promising medium for steganography and censorship resistance.

We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since [Lamport et al, 82] that BA under honest majority (let alone secure computation) would not be possible without messages-authentication. But as further highlighted by [Borcherding, 96], messages-authentication cannot not simply be implemented with digital signatures, without a bulletin-board of public keys. So the bulletin-board PKI setup and the messages-authentication model seem very close: this raizes the question whether there is a separation between them. In the bulletin-board PKI setup, the most communication-efficient synchronous BA is the one of [Boyle-Cohen-Goel, Podc'21 \& J. Cryptol.'24], which has $O(n.\text{polylog}(n))$ bit complexity, $f<n(1/3-\epsilon)$ resilience and tolerates an adversary which cannot adaptively corrupt after the setup. Our main upper-bound is a BA (and also a VBA) in this same model with strictly better parameters: {quasi-optimal} resilience $f<n(1/2-\epsilon)$, with an expected bit complexity of communications which is {linear} in $n$, and tolerance to an {adaptive} rushing adversary (but which unavoidably cannot remove messages sent). As [BCG'21], they have constant expected latency. All previous BAs or VBAs achieving the same metrics as our upper bound, are either in the static adversary model: Sleepy [Pass-Shi, Asiacrypt'17], Snow White [Daian-Pass-Shi, FC'19], or assume more than a bare PKI setup: (i) The model of Thunderella [Pass-Shi, EC'17], Algorand [Gilad et al, SOSP'17], Praos [David et al, EC'18], [Goyal et al, FC'21] and [Momose et al, CCS'22 and CCS'23] assumes a public random seed which is unpredictable until strictly after all players published on the bulletin board; (ii) [Abraham et al, Podc'19] assume a trusted entity which honestly samples the keys of all players; (iii) All known implementations of the setups (i) and (ii), as well as the setup of [Blum et al, TCC'20], require interactions, furthermore in the form of BAs. (iv) [Garay-Kiayas-Shen '23] assume that honest players work more than the adversary, or, [Eckey-Faust-Loss et al '17 '22] at least as fast. Of independent interest, our tool is a very simple non-interactive mechanism which {sets-up a self-sortition function from non-interactive publications on the bulletin board}, and still, guarantees an honest majority in every committee up to probability exponentially small in both $\epsilon$ and in the multicast complexity. We provide the following further results: {- Optimality.} We show that resilience up to a tight honest majority $f<n/2$ is impossible for any multicast-based adaptively secure BA with subquadratic communication, whatever the setup. {- Separation.} We show impossibility of subquadratic multicast-based BA in the messages-authentication model. Our model for this lower bound is even stronger, since it onboards other assumptions at least as strong as all popular implications of a bulletin-board PKI setup: {secure channels}, {a (possibly structured) random string}, {NIZK}. {- Partial synchrony.} Given that the multicast lower-bound holds a fortiori, and that the upper-bound adapts seamlessly (for $f<n(1/3-\epsilon)$), the separation also holds. We show a second separation, which holds for general BAs, non-necessarily multicast-based: any partially-synchronous BA in the messages-authentication model, if it has linear message complexity, then it has latency at least {logarithmic in $f$}. {- Extension to VBA.} We extend to VBA the logarithmic latency lower bound. This is the first communication lower bound for randomized VBA to our knowledge. It shows that the separation under partial synchrony also holds for VBA. Along the way, we close the characterization of [Civit et al, Podc'23] of validity conditions in authenticated consensus, by apparently new results on VBA: both BA and VBA are infeasible under partial synchrony beyond $f<n/3$, whatever the setup; whereas synchronous VBA is feasible up to $f=n-1$ (contrary to BA).

Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs. As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs. We show that applying qsiO to a program immediately achieves best-possible copy protection. Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection. Finally, we construct qsiO relative to an efficient quantum oracle.

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. These protocols have found applications in blockchain technology, leading to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others assume partial or bounded synchronous networks. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that uses a secure Hash function to generate beacons and pairwise secure channels. HashRand has a per-node communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=160$ nodes, HashRand produces 1 beacon every second, which is at least 4x higher than Spurt. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 122k txns per second over a WAN at $n=40$ nodes.

The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance. In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum cryptography, with its hiccups due to the novelty of underlying assumptions, has become the perfect use case for FSS. This paper aims to reboot research on FSS with practical use in mind: Our framework for FSS includes ``fine-grained'' security definitions (that assume a powerful, but bounded adversary e.g: can break $128$-bit of security, but not $256$-bit). As an application, we show new FSS constructions for the post-quantum setting. We show that FSS are equivalent to standard, provably secure digital signatures that do not require rewinding or programming random oracles, and that this implies lattice-based FSS. Our main construction is an FSS version of SPHINCS, which required building FSS versions of all its building blocks: WOTS, XMSS, and FORS. In the process, we identify and provide generic solutions for two fundamental issues arising when deriving a large number of private keys from a single seed, and when building FSS for Hash-and-Sign-based signatures.

The Internet Key Exchange version 2 (IKEv2) (RFC 7296) is a component of IPsec used to authenticate two parties (the initiator and responder) to each other and to establish a set of security parameters for the communications. The security parameters include secret keys to encrypt and authenticate data as well as the negotiation of a set of cryptographic algorithms. The core documentation uses exclusively Diffie-Hellman exchanges to agree the security information. However, this is not a quantum-secure option due to the ability of Shor's algorithm to break the security assumption underlying the Diffie-Hellman. A post-quantum solution is to include a preshared key in the exchange, as proposed by the extension RFC 8784; assuming that this preshared key has sufficient entropy, the keys created in the IKEv2 exchange will be resistant to a quantum computer. In this paper, we investigate the security claims of RFC 8784 using formal verification methods. We find that keys created using the preshared key are secret from an adversary. However, certain authentication properties of the protocol that are weakened under the assumption that Diffie-Hellman is insecure are not recovered using the preshared key.

This paper introduces a novel approach to enhancing cryp- tographic security. It proposes the use of one-time message sharing com- bined with Physically Unclonable Functions (PUF) to securely exchange keys and generate an S-subbyte-box for encryption. This innovative tech- nique aims to elevate the security standards of cryptographic applica- tions.

As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known countermeasures heralded to be durable against side-channel attacks are: “masking” and “hiding”. In that dichotomous picture, of particular note are successful single-trace attacks on some of the NIST’s PQC then-candidates, which worked to the detriment of the former: “masking”. In this paper, we cast an eye over the latter: “hiding”. Hiding proves to be durable against both side-channel attacks and another equally robust type of attacks called “fault injection attacks”, and hence is deemed an auspicious countermeasure to be implemented. Mathematically, the hiding method is fundamentally based on random permutations. There has been a cornucopia of studies on generating random permutations. However, those are not tied to implementation of the hiding method. In this paper, we propose a reliable and efficient verification of permutation implementation, through employing Fisher–Yates’ shuffling method. We introduce the concept of an 𝑛-th order permutation and explain how it can be used to verify that our implementation is more efficient than its previous-gen counterparts for hiding countermeasures.

Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-off : supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (which diminishes performance). We present Dora, a concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.

A recent preprint [ePrint 2023/1475] suggests the use of polynomials over a tropical algebra to construct a digital signature scheme "based on" the problem of factoring such polynomials, which is known to be NP‑hard. This short note presents two very efficient forgery attacks on the scheme, bypassing the need to factorize tropical polynomials and thus demonstrating that security in fact rests on a different, empirically easier problem.

In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting. We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

In the attacker models of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA), the opponent has access to a noisy version of the internal behavior of the hardware. Since the end of the nineties, many works have shown that this type of attacks constitutes a serious threat to cryptosystems implemented in embedded devices. In the state-of-the-art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (either SCA or FIA). The main known counter-measure against SCA is masking; it makes the complexity of SCA growing exponentially with its order d. The most general version of masking is based on error correcting codes. It has the advantage of offering in principle a protection against both types of attacks (SCA and FIA), but all the functions implemented in the algorithm need to be masked accordingly, and this is not a simple task in general. We propose a particular version of such construction that has several advantages: it has a very low computation complexity, it offers a concrete protection against both SCA and FIA, and finally it allows flexibility: being not specifically dedicated to AES, it can be applied to any block cipher with any S-boxes. In the state-of-art, masking schemes all come with pros and cons concerning the different types of complexity (time, memory, amount of randomness). Our masking scheme concretely achieves the complexity of the best known scheme, for each complexity type

Given a set of matrices $\mathbf{A} := \{A_0, \dotsc, A_{k-1}\}$, and a matrix $M$ guaranteed to be the product of some ordered subset of $\mathbf{L}\subset\mathbf{A}$, can $\mathbf{L}$ be efficiently recovered? We begin by observing that the answer is positive under some assumptions on $\mathbf{A}$. Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based upon this problem. We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.

Secure multi-party computation (MPC) enables (joint) computations on sensitive data while maintaining privacy. In real-world scenarios, asymmetric trust assumptions are often most realistic, where one somewhat trustworthy entity interacts with smaller clients. We generalize previous two-party computation (2PC) protocols like MUSE (USENIX Security'21) and SIMC (USENIX Security'22) to the three-party setting (3PC) with one malicious party, avoiding the performance limitations of dishonest-majority inherent to 2PC. We introduce two protocols, Auxiliator and Socium, in a machine learning (ML) friendly design with a fast online phase and novel verification techniques in the setup phase. These protocols bridge the gap between prior 3PC approaches that considered either fully semi-honest or malicious settings. Auxiliator enhances the semi-honest two-party setting with a malicious helper, significantly improving communication by at least two orders of magnitude. Socium extends the client-malicious setting with one malicious client and a semi-honest server, achieving substantial communication improvement by at least one order of magnitude compared to SIMC. Besides an implementation of our new protocols, we provide the first open-source implementation of the semi-honest 3PC protocol ASTRA (CCSW'19) and a variant of the malicious 3PC protocol SWIFT (USENIX Security'21).

Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been determined are few: An example of such a function is the two-input AND function where $(2\log_2 3)$-bit communication is optimal. In this paper, we provide new upper and lower bounds for several concrete functions. For lower bounds, we introduce a novel approach using combinatorial objects called abstract simplicial complexes to represent PSM protocols. Our method is suitable for obtaining non-asymptotic explicit lower bounds for concrete functions. By deriving lower bounds and constructing concrete protocols, we show that the optimal communication complexity for the equality and majority functions with three input bits are $3\log_2 3$ bits and $6$ bits, respectively. We also derive new lower bounds for the $n$-input AND function, three-valued comparison function, and multiplication over finite rings.

A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals: 1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner. This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.

We introduce a new notion called ${\cal Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in {\cal Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$. By fine-tuning ${\cal Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of ${\cal Q}$-secure pseudorandom isometries (PRI) for different interesting settings of ${\cal Q}$. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.

Among secure multi-party computation protocols, linear secret sharing schemes often do not rely on cryptographic assumptions and are among the most straightforward to explain and to implement correctly in software. However, basic versions of such schemes either limit participants to evaluating linear operations involving private values or require those participants to communicate synchronously during a computation phase. A straightforward, information-theoretically secure extension to such schemes is presented that can evaluate arithmetic sum-of-products expressions that contain multiplication operations involving non-zero private values. Notably, this extension does not require that participants communicate during the computation phase. Instead, a preprocessing phase is required that is independent of the private input values (but is dependent on the number of factors and terms in the sum-of-products expression).

Motivated by the fact that broadcast is an expensive, but useful, resource for the realization of multi-party computation protocols (MPC), Cohen, Garay, and Zikas (Eurocrypt 2020), and subsequently Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021), and, Damgård, Ravi, Siniscalchi and Yakoubov (Eurocrypt 2023), focused on 𝘴𝘰-𝘤𝘢𝘭𝘭𝘦𝘥 𝘣𝘳𝘰𝘢𝘥𝘤𝘢𝘴𝘵 𝘰𝘱𝘵𝘪𝘮𝘢𝘭 𝘔𝘗𝘊. In particular, the authors focus on two-round MPC protocols (in the CRS model), and give tight characterizations of which security guarantees are achievable if broadcast is available in the first round, the second round, both rounds, or not at all. This work considers the natural question of characterizing broadcast optimal MPC in the plain model where no set-up is assumed. We focus on four-round protocols, since four is known to be the minimal number of rounds required to securely realize any functionality with black-box simulation. We give a complete characterization of which security guarantees, (namely selective abort, selective identifiable abort, unanimous abort and identifiable abort) are feasible or not, depending on the exact selection of rounds in which broadcast is available.

It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this conceptually simple contribution by instantiating RB under various assumptions to get AB under the same assumptions. Using this framework we obtain the first asynchronous AB with sub-quadratic communication and optimal corruption threshold $t < n/3$, and the first network agnostic AB which is optimistically responsive. The latter result is secure in a relaxed synchronous model where parties locally decide timeouts and do not have synchronized clocks. Finally, we provide asynchronous ABs with covert security and mixed adversary structures.

We study the security of a fundamental family of succinct interactive arguments in the standard model, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner (``BCS'', 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments. Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on the security of this protocol. Prior analyses incur large overheads, or assume restrictive properties of the underlying PCP. Our second result concerns an interactive variant of the BCS succinct non-interactive argument, which here we call IBCS, realized with any public-coin interactive oracle proof (IOP) and any vector commitment. We establish the first security bounds for the IBCS protocol. Prior works rely upon this protocol without proving its security; our result closes this gap. Finally, we study the capabilities and limitations of succinct arguments based on vector commitments. We show that a generalization of the IBCS protocol, which we call the \emph{Finale protocol}, is secure when realized with any \emph{public-query} IOP (a notion that we introduce) that satisfies a natural ``random continuation sampling'' (RCS) property. We also show a partial converse: if the Finale protocol satisfies the RCS property (which in particular implies its security), then so does the underlying public-query IOP.

Homomorphic encryption (HE) has gained broad attention in recent years as it allows computations on encrypted data enabling secure cloud computing. Deploying HE presents a notable challenge since it introduces a performance overhead by orders of magnitude. Hence, most works target accelerating server-side operations on hardware platforms, while little attention has been given to client-side operations. In this paper, we present a novel design methodology to implement and accelerate the client-side HE operations on area-constrained hardware. We show how to design an optimized floating-point unit tailored for the encoding of complex values. In addition, we introduce a novel hardware-friendly algorithm for modulo-reduction of floating-point numbers and propose various concepts for achieving efficient resource sharing between modular ring and floating-point arithmetic. Finally, we use this methodology to implement an end-to-end hardware accelerator, Aloha-HE, for the client-side operations of the CKKS scheme. In contrast to existing work, Aloha-HE supports both encoding and encryption and their counterparts within a unified architecture. Aloha-HE achieves a speedup of up to 59x compared to prior hardware solutions.

$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood. In this work, we study the problems on rotations of $\mathbb{Z}^n$ by exploiting the symmetry property. We introduce a randomization framework that can be roughly viewed as `applying random automorphisms’ to the output of an oracle, without accessing the automorphism group. Using this framework, we obtain new reduction results for rotations of $\mathbb{Z}^n$. First, we present a reduction from $\mathbb{Z}$LIP to $\mathbb{Z}$SCVP. Here $\mathbb{Z}$SCVP is the problem of finding the shortest characteristic vectors, which is a special case of CVP where the target vector is a deep hole of the lattice. Moreover, we prove a reduction from $\mathbb{Z}$SVP to $\gamma$-$\mathbb{Z}$SVP for any constant $\gamma = O(1)$ in the same dimension, which implies that $\mathbb{Z}$SVP is as hard as its approximate version for any constant approximation factor. Second, we investigate the problem of finding a nontrivial automorphism for a given lattice, which is called LAP. Specifically, we use the randomization framework to show that $\mathbb{Z}$LAP is as hard as $\mathbb{Z}$LIP. We note that our result can be viewed as a $\mathbb{Z}^n$-analogue of Lenstra and Silverberg's result in [JoC2017], but with a different assumption: they assume the $G$-lattice structure, while we assume the access to an oracle that outputs a nontrivial automorphism.

Memory tightness of reductions in cryptography, in addition to the standard tightness related to advantage and running time, is important when the underlying problem can be solved efficiently with large memory, as discussed in Auerbach, Cash, Fersch, and Kiltz (CRYPTO 2017). Diemert, Geller, Jager, and Lyu (ASIACRYPT 2021) and Ghoshal, Ghosal, Jaeger, and Tessaro (EUROCRYPT 2022) gave memory-tight proofs for the multi-challenge security of digital signatures in the random oracle model. This paper studies the memory-tight reductions for _post-quantum_ signature schemes in the _quantum_ random oracle model. Concretely, we show that signature schemes from lossy identification are multi-challenge secure in the quantum random oracle model via memory-tight reductions. Moreover, we show that the signature schemes from lossy identification achieve more enhanced securities considering _quantum_ signing oracles proposed by Boneh and Zhandry (CRYPTO 2013) and Alagic, Majenz, Russel, and Song (EUROCRYPT 2020). We additionally show that signature schemes from preimage-sampleable functions achieve those securities via memory-tight reductions.

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-dependent information. Our first construction HintlessPIR eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the "hint" related computation to the server, leveraging a new concept of homomorphic encryption with composable preprocessing. We realize this concept on RLWE encryption schemes, and thanks to the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse across multiple executions. As a concrete application, we achieve very efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 3.7GB/s without requiring any client or server state. We additionally formalize the matrix vector multiplication protocol as LinPIR primitive, which may be of independent interests. In our second construction TensorPIR we reduce the communications of HintlessPIR from square root to cubic root in the database size. For this purpose we extend our HE with preprocessing techniques to composition of key-switching keys and the query expansion algorithm. We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications. This allows the server to do more complex processing using a more compact query under LWE. We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest. We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or database updates frequently. The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022). In the setting of anonymous queries we also improve on Spiral's communication.

Masking is a well-known and provably secure countermeasure against side-channel attacks. However, due to additional redundant computations, integrating masking schemes is expensive in terms of performance. The performance overhead of integrating masking countermeasures is heavily influenced by the design choices of a cryptographic algorithm and is often not considered during the design phase. In this work, we deliberate on the effect of design choices on integrating masking techniques into lattice-based cryptography. We select Scabbard, a suite of three lattice-based post-quantum key-encapsulation mechanisms (KEM), namely Florete, Espada, and Sable. We provide arbitrary-order masked implementations of all the constituent KEMs of the Scabbard suite by exploiting their specific design elements. We show that the masked implementations of Florete, Espada, and Sable outperform the masked implementations of Kyber in terms of speed for any order masking. Masked Florete exhibits a $73\%$, $71\%$, and $70\%$ performance improvement over masked Kyber corresponding to the first-, second-, and third-order. Similarly, Espada exhibits $56\%$, $59\%$, and $60\%$ and Sable exhibits $75\%$, $74\%$, and $73\%$ enhanced performance for first-, second-, and third-order masking compared to Kyber respectively. Our results show that the design decisions have a significant impact on the efficiency of integrating masking countermeasures into lattice-based cryptography.

Physical attacks are serious threats to cryptosystems deployed in the real world. In this work, we propose a microarchitectural end-to-end attack methodology on generic lattice-based post-quantum key encapsulation mechanisms to recover the long-term secret key. Our attack targets a critical component of a Fujisaki-Okamoto transform that is used in the construction of almost all lattice-based key encapsulation mechanisms. We demonstrate our attack model on practical schemes such as Kyber and Saber by using Rowhammer. We show that our attack is highly practical and imposes little preconditions on the attacker to succeed. As an additional contribution, we propose an improved version of the plaintext checking oracle, which is used by almost all physical attack strategies on lattice-based key-encapsulation mechanisms. Our improvement reduces the number of queries to the plaintext checking oracle by as much as 39% for Saber and approximately 23% for Kyber768. This can be of independent interest and can also be used to reduce the complexity of other attacks.

We show an explicit construction of an efficiently decodable family of $n$-dimensional lattices whose minimum distances achieve $\Omega(\sqrt{n} / (\log n)^{\varepsilon+o(1)})$ for $\varepsilon>0$. It improves upon the state-of-the-art construction due to Mook-Peikert (IEEE Trans.\ Inf.\ Theory, no. 68(2), 2022) that provides lattices with minimum distances $\Omega(\sqrt{n/ \log n})$. These lattices are construction-D lattices built from a sequence of BCH codes. We show that replacing BCH codes with subfield subcodes of Garcia-Stichtenoth tower codes leads to a better minimum distance. To argue on decodability of the construction, we adapt soft-decision decoding techniques of Koetter-Vardy (IEEE Trans.\ Inf.\ Theory, no.\ 49(11), 2003) to algebraic-geometric codes.

Secure Multiparty Computation (MPC) protocols enable secure evaluation of a circuit by several parties, even in the presence of an adversary who maliciously corrupts all but one of the parties. These MPC protocols are constructed using the well-known secret-sharing-based paradigm (SPDZ and SPD$\mathbb{Z}_{2^k}$), where the protocols ensure security against a malicious adversary by computing Message Authentication Code (MAC) tags on the input shares and then evaluating the circuit with these input shares and tags. However, this tag computation adds a significant runtime overhead, particularly for machine learning (ML) applications with computationally intensive linear layers, such as convolutions and fully connected layers. To alleviate the tag computation overhead, we introduce CompactTag, a lightweight algorithm for generating MAC tags specifically tailored for linear layers in ML. Linear layer operations in ML, including convolutions, can be transformed into Toeplitz matrix multiplications. For the multiplication of two matrices with dimensions T1 × T2 and T2 × T3 respectively, SPD$\mathbb{Z}_{2^k}$ required O(T1 · T2 · T3) local multiplications for the tag computation. In contrast, CompactTag only requires O(T1 · T2 + T1 · T3 + T2 · T3) local multiplications, resulting in a substantial performance boost for various ML models. We empirically compared our protocol to the SPD$\mathbb{Z}_{2^k}$ protocol for various ML circuits, including ResNet Training-Inference, Transformer Training-Inference, and VGG16 Training-Inference. SPD$\mathbb{Z}_{2^k}$ dedicated around 30% of its online runtime for tag computation. CompactTag speeds up this tag computation bottleneck by up to 23×, resulting in up to 1.47× total online phase runtime speedups for various ML workloads.

In LWE based cryptosystems, using small (polynomially large) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs "simulation security": the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Rényi divergence based analyses that are sufficient for game-based but not simulation security. In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially large modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.

Envelope encryption is a method to encrypt data with two distinct keys in its basic form. Data is first encrypted with a data-encryption key, and then the data-encryption key is encrypted with a key-encryption key. Despite its deployment in major cloud services, as far as we know, envelope encryption has not received any formal treatment. To address this issue, we first formalize the syntax and security requirements of envelope encryption in the symmetric-key setting. Then, we show that it can be constructed by combining encryptment and authenticated encryption with associated data (AEAD). Encryptment is one-time AEAD satisfying that a small part of a ciphertext works as a commitment to the corresponding secret key, message, and associated data. Finally, we show that the security of the generic construction is reduced to the security of the underlying encryptment and AEAD.

We construct a new post-quantum cryptosystem which consists of enhancing CSIDH and similar cryptosystems by adding a full level $N$ structure. We discuss the size of the isogeny graph in this new cryptosystem which consists of components which are acted on by the ray class group for the modulus $N$. We conclude by showing that, if we can efficiently find rational isogenies between elliptic curves, then we can efficiently find rational isogenies that preserve the level structure. We show that one can reduce the group action problem for the ray class group to the group action problem for the ideal class group. This reduces the security of this new cryptosystem to that of the original one

For any prime number $p$, we provide two classes of linear codes with few weights over a $p$-ary alphabet. These codes are based on a well-known generic construction (the defining-set method), stemming on a class of monomials and a class of trinomials over finite fields. The considered monomials are Dembowski-Ostrom monomials $x^{p^{\alpha}+1}$, for a suitable choice of the exponent $\alpha$, so that, when $p>2$ and $n\not\equiv 0 \pmod{4}$, these monomials are planar. We study the properties of such monomials in detail for each integer $n$ greater than two and any prime number $p$. In particular, we show that they are $t$-to-one, where the parameter $t$ depends on the field $\mathbb{F}_{p^n}$ and it takes the values $1, 2$ or $p+1$. Moreover, we give a simple proof of the fact that the functions are $\delta$-uniform with $\delta \in \{1,4,p\}$. This result describes the differential behaviour of these monomials for any $p$ and $n$. For the second class of functions, we consider an affine equivalent trinomial to $x^{p^{\alpha}+1}$, namely, $x^{p^{\alpha}+1}+\lambda x^{p^{\alpha}}+\lambda^{p^{\alpha}}x$ for $\lambda\in \mathbb{F}_{p^n}^*$. We prove that these trinomials satisfy certain regularity properties, which are useful for the specification of linear codes with three or four weights that are different than the monomial construction. These families of codes contain projective codes and optimal codes (with respect to the Griesmer bound). Remarkably, they contain infinite families of self-orthogonal and minimal $p$-ary linear codes for every prime number $p$. Our findings highlight the utility of studying affine equivalent functions, which is often overlooked in this context.

A $t$-out-of-$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a well-formed ciphertext. Existing threshold decryption systems are not secure when these parties are rational actors: an adversary can offer to pay the parties for their key shares. The problem is that a quorum of $t$ parties, working together, can sell the adversary a decryption key that reveals nothing about the identity of the traitor parties. This provides a risk-free profit for the parties since there is no accountability for their misbehavior --- the information they sell to the adversary reveals nothing about their identity. This behavior can result in a complete break in many applications of threshold decryption, such as encrypted mempools, private voting, and sealed-bid auctions. In this work we show how to add accountability to threshold decryption systems to deter this type of risk-free misbehavior. Suppose a quorum of $t$ or more parties construct a decoder algorithm $D(\cdot)$ that takes as input a ciphertext and outputs the corresponding plaintext or $\bot$. They sell $D$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace $D$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to $D$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder $D$ in the first place. Our starting point is standard (non-threshold) traitor tracing, where $n$ parties each holds a secret key. Every party can decrypt a well-formed ciphertext on its own. However, if a subset of parties ${\cal J} \subseteq [n]$ collude to create a pirate decoder $D(\cdot)$ that can decrypt well-formed ciphertexts, then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder $D$. Traitor tracing received much attention over the years and multiple schemes have been developed. In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset ${\cal J} \subseteq [n]$ of $t$ or more parties can collude to create a pirate decoder $D(\cdot)$. This problem has recently become quite important due to the real-world deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several non-threshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption settings requires new cryptographic techniques. We present a number of constructions for traitor tracing for threshold decryption, and note that much work remains to explore the large design space.

We present a deterministic synchronous protocol for binary Byzantine Agreement against a corrupt minority with adaptive $O(n\cdot f)$ communication complexity, where $f$ is the exact number of corruptions. Our protocol improves the previous best-known deterministic Byzantine Agreement protocol developed by Momose and Ren (DISC 2021), whose communication complexity is quadratic, independent of the exact number of corruptions. Our approach combines two distinct primitives that we introduce and implement with $O(n\cdot f)$ communication, Reliable Voting, and Weak Byzantine Agreement. In Reliable Voting, all honest parties agree on the same value only if all honest parties start with that value, but there is no agreement guarantee in the general case. In Weak Byzantine Agreement, we achieve agreement, but validity requires that the inputs to the protocol satisfy certain properties. Our Weak Byzantine Agreement protocol is an adaptation of the recent Cohen et al. protocol (OPODIS 2022), in which we identify and address various issues.

Active fault injection is a credible threat to real-world digital systems computing on sensitive data. Arguing about security in the presence of faults is non-trivial, and state-of-the-art criteria are overly conservative and lack the ability of fine-grained comparison. However, comparing two alternative implementations for their security is required to find a satisfying compromise between security and performance. In addition, the comparison of alternative fault scenarios can help optimize the implementation of effective countermeasures. In this work, we use quantitative information flow analysis to establish a vulnerability metric for hardware circuits under fault injection that measures the severity of an attack in terms of information leakage. Potential use cases range from comparing implementations with respect to their vulnerability to specific fault scenarios to optimizing countermeasures. We automate the computation of our metric by integrating it into a state-of-the-art evaluation tool for physical attacks and provide new insights into the security under an active fault attacker.

We propose a new method to encode the problems of optimizing S-box implementations into SAT problems. By considering the inputs and outputs of gates as Boolean functions, the fundamental idea of our method is representing the relationships between these inputs and outputs according to their algebraic normal forms. Based on this method, we present several encoding schemes for optimizing S-box implementations according to various criteria, such as multiplicative complexity, bitslice gate complexity, gate complexity, and circuit depth complexity. The experimental results of these optimization problems show that, compared to the encoding method proposed in FSE 2016, which represents these relationships between Boolean functions by their truth tables, our new encoding method can significantly reduce accelerate the subsequent solving process by 2-100 times for the majority of instances. To further improve the solving efficiency, we propose several strategies to eliminate the redundancy of the derived equation system and break the symmetry of the solution space. We apply our method in the optimizations of the S-boxes used in Ascon, ICEPOLE, PRIMATEs, Keccak/Ketje/Keyak, Joltik/Piccolo, LAC, Minalpher, Prøst, and RECTANGLE. We achieve some new improved implementations and narrow the range of the optimal values for different optimization criteria of these S-boxes.

There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al. (CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.

This paper presents MQ on my Mind (MQOM), a digital signature scheme based on the difficulty of solving multivariate systems of quadratic equations (MQ problem). MQOM has been submitted to the NIST call for additional post-quantum signature schemes. MQOM relies on the MPC-in-the-Head (MPCitH) paradigm to build a zero-knowledge proof of knowledge (ZK-PoK) for MQ which is then turned into a signature scheme through the Fiat-Shamir heuristic. The underlying MQ problem is non-structured in the sense that the system of quadratic equations defining an instance is drawn uniformly at random. This is one of the hardest and most studied problems from multivariate cryptography which hence constitutes a conservative choice to build candidate post-quantum cryptosystems. For the efficient application of the MPCitH paradigm, we design a specific MPC protocol to verify the solution of an MQ instance. Compared to other multivariate signature schemes based on non-structured MQ instances, MQOM achieves the shortest signatures (6.3-7.8 KB) while keeping very short public keys (few dozen of bytes). Other multivariate signature schemes are based on structured MQ problems (less conservative) which either have large public keys (e.g. UOV) or use recently proposed variants of these MQ problems (e.g. MAYO).

The LowMC family of SPN block cipher proposed by Albrecht et al. was designed specifically for MPC-/FHE-/ZKP-friendly use cases. It is especially used as the underlying block cipher of PICNIC, one of the alternate third-round candidate digital signature algorithms for NIST post-quantum cryptography standardization. The security of PICNIC is highly related to the difficulty of recovering the secret key of LowMC from a given plaintext/ciphertext pair, which raises new challenges for security evaluation under extremely low data complexity. In this paper, we improve the attacks on LowMC under low data complexity, i.e. 1 or 2 chosen plaintext/ciphertext pairs. For the difference enumeration attack with 2 chosen plaintexts, we propose new algebraic methods to better exploit the nonlinear relation inside the introduced variables based on the attack framework proposed by Liu et al. at ASIACRYPT 2022. With this technique, we significantly extend the number of attack rounds for LowMC with partial nonlinear layers and improve the success probability from around 0.5 to over 0.9. The security margin of some instances can be reduced to only 3/4 rounds. For the key-recovery attack using a single plaintext, we adopt a different linearization strategy to reduce the huge memory consumption caused by the polynomial methods for solving multivariate equation systems. The memory complexity reduces drastically for all 5-/6-round LowMC instances with full nonlinear layers at the sacrifice of a small factor of time complexity. For 5-round LowMC instances with a block size of 129, the memory complexity decreases from $2^{86.46}$ bits to $2^{48.18}$ bits while the time complexity even slightly reduces. Our results indicate that the security for different instances of LowMC under extremely low data complexity still needs further exploration.

Central Bank Digital Currencies refer to the digitization of lifecycle's of central bank money in a way that meets first of a kind requirements for transparency in transaction processing, interoperability with legacy or new world, and resilience that goes beyond the traditional crash fault tolerant model. This comes in addition to legacy system requirements for privacy and regulation compliance, that may differ from central bank to central bank. This paper introduces a novel framework for Central Bank Digital Currency settlement that outputs a system of record---acting a a trusted source of truth serving interoperation, and dispute resolution/fraud detection needs---, and brings together resilience in the event of parts of the system being compromised, with throughput comparable to crash-fault tolerant systems. Our system further exhibits agnosticity of the exact cryptographic protocol adopted for meeting privacy, compliance and transparency objectives, while ensuring compatibility with the existing protocols in the literature. For the latter, performance is architecturally guaranteed to scale horizontally. We evaluated our system's performance using an enhanced version of Hyperledger Fabric, showing how a throughput of >100K TPS can be supported even with computation-heavy privacy-preserving protocols are in place.

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC '09; Brakerski–Vaikuntanathan, FOCS '11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee, STOC '13; Boneh et al., Eurocrypt '14], only accommodate circuits up to a *predetermined* depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: - Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size. - Based on the *evasive circular* LWE assumption, a stronger variant of the recently proposed *evasive* LWE assumption [Wee, Eurocrypt '22; Tsabary, Crypto '22], we construct a full-fledged ABE scheme for circuits of unbounded depth and size. Our LFE, 1-key FE, and reusable garbling schemes achieve optimal succinctness (up to polynomial factors in the security parameter). Their ciphertexts and input encodings have sizes linear in the input length, while function digest, secret keys, and garbled circuits have constant sizes independent of circuit parameters (for Boolean outputs). In fact, this gives the first constant-size garbled circuits without relying on indistinguishability obfuscation. Our ABE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.

With the widespread development of database systems, data security has become crucial when it comes to sharing among users and servers. A straightforward approach involves using searchable encryption to ensure the confidentiality of shared data. However, in certain scenarios, varying user tiers are granted disparate data searching privileges, and administrators need to restrict the searchability of ciphertexts to select users exclusively. To address this issue, public key encryption with authorized keyword search (PEAKS) was proposed, wherein solely authorized users possess the ability to conduct targeted keyword searches. Nonetheless, it is vulnerable to resist quantum computing attacks. As a result, research focusing on authorizing users to search for keywords while achieving quantum security is far-reaching. In this paper, we propose a lattice-based variant of PEAKS (L-PEAKS) that enables keyword dataset authorization for outsourced data management. Unlike existing schemes, our design incorporates identity-based encryption (IBE) to overcome the bottleneck of public key management. Besides, we utilize several lattice sampling algorithms to defend against attacks from quantum adversaries. Specifically, each authorized user must obtain a search privilege from an authority. The authority distributes an authorized token to the user within a specific time period, and the user generates a trapdoor for any authorized keywords. Our scheme is proven to be secure against IND-sID-CKA and T-EUF security in a quantum setting. We also conduct comprehensive evaluations on a commodity machine to assess completeness and provide theoretical complexity comparisons with existing state-of-the-art schemes.

Parallel repetition refers to a set of valuable techniques used to reduce soundness error of probabilistic proofs while saving on certain efficiency measures. Parallel repetition has been studied for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). In this paper we initiate the study of parallel repetition for probabilistically checkable proofs (PCPs). We show that, perhaps surprisingly, parallel repetition of a PCP can increase soundness error, in fact bringing the soundness error to one as the number of repetitions tends to infinity. This "failure" of parallel repetition is common: we find that it occurs for a wide class of natural PCPs for NP-complete languages. We explain this unexpected phenomenon by providing a characterization result: the parallel repetition of a PCP brings the soundness error to zero if and only if a certain "MIP projection" of the PCP has soundness error strictly less than one. We show that our characterization is tight via a suitable example. Moreover, for those cases where parallel repetition of a PCP does bring the soundness error to zero, the aforementioned connection to MIPs offers preliminary results on the rate of decay of the soundness error. Finally, we propose a simple variant of parallel repetition, called consistent parallel repetition (CPR), which has the same randomness complexity and query complexity as the plain variant of parallel repetition. We show that CPR brings the soundness error to zero for every PCP (with non-trivial soundness error). In fact, we show that CPR decreases the soundness error at an exponential rate in the repetition parameter.

In this paper we revisit the problem of erasing sensitive data from memory and registers during return from a cryptographic routine. While the problem and related attacker model is fairly easy to phrase, it turns out to be surprisingly hard to guarantee security in this model when implementing cryptography in common languages such as C/C++ or Rust. We revisit the issues surrounding zeroization and then present a principled solution in the sense that it guarantees that sensitive data is erased and it clearly defines when this happens. We implement our solution as extension to the formally verified Jasmin compiler and extend the correctness proof of the compiler to cover zeroization. We show that the approach seamlessly integrates with state-of-the-art protections against microarchitectural attacks by integrating zeroization into Libjade, a cryptographic library written in Jasmin with systematic protections against timing and Spectre-v1 attacks. We present benchmarks showing that in many cases the overhead of zeroization is barely measurable and that it stays below 2% except for highly optimized symmetric crypto routines on short inputs.

Boolean Searchable Symmetric Encryption (BSSE) enables users to perform retrieval operations on the encrypted data while sup- porting complex query capabilities. This paper focuses on addressing the storage overhead and privacy concerns associated with existing BSSE schemes. While Patel et al. (ASIACRYPT’21) and Bag et al. (PETS’23) introduced BSSE schemes that conceal the number of single keyword re- sults, both of them suffer from quadratic storage overhead and neglect the privacy of search and access patterns. Consequently, an open ques- tion arises: Can we design a storage-efficient Boolean query scheme that effectively suppresses leakage, covering not only the volume pattern for singleton keywords, but also search and access patterns? In light of the limitations of existing schemes in terms of storage over- head and privacy protection, this work presents a novel solution called SESAME. It realizes efficient storage and privacy preserving based on Bloom filter and functional encryption. Moreover, we propose an en- hanced version, SESAME+, which offers improved search performance. By rigorous security analysis on the leakage functions of our schemes, we provide a formal security proof. Finally, we implement our schemes and demonstrate that SESAME+ achieves superior search efficiency and reduced storage overhead.

We demonstrate that a passive network attacker can opportunistically obtain private RSA host keys from an SSH server that experiences a naturally arising fault during signature computation. In prior work, this was not believed to be possible for the SSH protocol because the signature included information like the shared Diffie-Hellman secret that would not be available to a passive network observer. We show that for the signature parameters commonly in use for SSH, there is an efficient lattice attack to recover the private key in case of a signature fault. We provide a security analysis of the SSH, IKEv1, and IKEv2 protocols in this scenario, and use our attack to discover hundreds of compromised keys in the wild from several independently vulnerable implementations.

Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson (JACM'91), zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments. In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action (Eurocrypt’22). We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We consider three representations: arithmetic circuits, rank-1 constraint systems and branching programs. This work gives the first attempt at constructing a post-quantum generic proof system from isogeny assumptions (the group action DDH problem). Though the resulting proof systems are linear in the circuit size, they possess interesting features such as non-interactivity, statistical zero-knowledge, and online-extractability.

In 2012, Ding, Xie and Lin designed a key exchange protocol based on Ring-LWE problem, called the DXL key exchange protocol, which can be seen as an extended version of the Diffie-Hellman key exchange. In this protocol, Ding et al. achieved key exchange between the communicating parties according to the associativity of matrix multiplications, that is, $(x^T\cdot A)\cdot y = x^T\cdot (A\cdot y)$, where $x,y$ are column vectors and $A$ is a square matrix. However, the DXL key exchange protocol cannot resist key reuse attacks. At ESORICS 2022, Qin et al. proposed a method that an adversary can recover the reused private key after forging the public keys for several times. Nevertheless, Qin et al.'s method leads to a lot of redundant operations. In this paper, we improve Qin et al.'s method to a more general case and propose an effective approach to combine signal leakage attacks with depth first search. Compared with state-of-the-art result appeared at ESORICS 2022, the number of reused private key have been decreased from 29 to 10. In other words, if the number of reuses exceeds 10, the private key will be restored. Moreover, we validate the effectiveness of the results through experiments.

The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0). In this paper, we study various algebraic properties of this map. We consider $\chi_n$ (through vectorial isomorphism) as a univariate polynomial. We show that it is a power function if and only if $n=1,3$. We furthermore compute bounds on the sparsity and degree of these univariate polynomials, and the number of different univariate representations. Secondly, we compute the number of monomials of given degree in the inverse of $\chi_n$ (if it exists). This number coincides with binomial coefficients. Lastly, we consider $\chi_n$ as a polynomial map, to study whether the same rule ($y_i = x_i + (x_{i+1}+1)x_{i+2}$) gives a bijection on field extensions of $\mathbb{F}_2$. We show that this is not the case for extensions whose degree is divisible by two or three. Based on these results, we conjecture that this rule does not give a bijection on any extension field of $\mathbb{F}_2$.

Several key exchange protocols based on tropical circulant matrices were proposed in the last two years. In this paper, we show that protocols offered by M. Durcheva [M. I. Durcheva. TrES: Tropical Encryption Scheme Based on Double Key Exchange. In: Eur. J. Inf. Tech. Comp. Sci. 2.4 (2022), pp. 11–17], by B. Amutha and R. Perumal [B. Amutha and R. Perumal. Public key exchange protocols based on tropical lower circulant and anti-circulant matrices. In: AIMS Math. 8.7 (2023), pp. 17307–17334.], and by H. Huang, C. Li, and L. Deng [H. Huang, C. Li, and L. Deng. Public-Key Cryptography Based on Tropical Circular Matrices. In: Appl. Sci. 12.15 (2022), p. 7401] are insecure.

Private Set Intersection Cardinality(PSI-CA) is a type of secure two-party computation. It enables two parties, each holding a private set, to jointly compute the cardinality of their intersection without revealing any other private information about their respective sets. In this paper, we manage to break two PSI-CA protocols by recovering the specific intersection items in polynomial time. Among them, the PSI-CA protocol proposed by De Cristofaro et al. in 2012 is the most popular PSI-CA protocol based on the Google Scholar search results and it is still deemed one of the most efficient PSI-CA protocols. In this paper, we also propose several solutions to these protocols' security problems.

This works introduces Basefold, a new $\textit{field-agnostic}$ Polynomial Commitment Scheme (PCS) for multilinear polynomials that has $O(\log^{2}(n))$ verifier costs and $O(n \log n)$ prover time. An important application of a multilinear PCS is constructing Succinct Non-interactive Arguments (SNARKs) from multilinear polynomial interactive oracle proofs (PIOPs). Furthermore, field-agnosticism is a major boon to SNARK efficiency in applications that require (or benefit from) a certain field choice. Our inspiration for Basefold is the Fast Reed-Solomon Interactive-Oracle Proof of Proximity (FRI IOPP), which leverages two properties of Reed-Solomon (RS) codes defined over "FFT-friendly'' fields: $O(n \log n)$ encoding time, and a second property that we call foldability. We first introduce a generalization of the FRI IOPP that works over any foldable linear code in linear time. Second, we construct a new family of linear codes which we call $\textit{random foldable codes}$, that are a special type of punctured Reed-Muller codes, and prove tight bounds on their minimum distance. Unlike RS codes, our new codes are foldable and have $O(n \log n)$ encoding time over ${any}$ sufficiently large field. Finally, we construct a new multilinear PCS by carefully interleaving our IOPP with the classical sumcheck protocol, which also gives a new multilinear PCS from FRI. Basefold is 2-3 times faster than prior multilinear PCS constructions from FRI when defined over the same finite field. More significantly, using Hyperplonk (Eurocrypt, 2022) as a multilinear PIOP backend for apples-to-apples comparison, we show that Basefold results in a SNARK that has better concrete efficiency across a range of field choices than with any prior multilinear PCS in the literature. Hyperplonk with Basefold has a proof size that is more than $10$ times smaller than Hyperplonk with Brakedown and its verifier is over $30$ times faster for circuits with more than $2^{20}$ gates. Compared to FRI, Hyperplonk with Basefold retains efficiency over any sufficiently large field. For illustration, with Basefold we can prove ECDSA signature verification over the secp256k1 curve more than $20$ times faster than Hyperplonk with FRI and the verifier is also twice as fast. Proofs of signature verification have many useful applications, including offloading blockchain transactions and enabling anonymous credentials over the web.

Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world can lead to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, has been proven to exhibit superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with domain separation. But the main reason for this is an artifact of the idealized model used in the proof, in particular, that (in the random-function-ideal world) $\mathsf{XoP}$ might hit a trivially bad event (outputting $\mathbf{0}$), which does not occur in the real/domain-separated world. Motivated by this, we put forth the analysis of such primitives in an updated ideal world, which we call the {\it fine-tuned} setting, where the above artifact is eliminated. We provide fine-tuned (and enhanced) security analyses for $\mathsf{XoP}$ and $\mathsf{XoP}$-based MACs: $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$, and demonstrate how the transition to the fine-tuned setting can also yield better privacy/authentication tradeoff in authenticated encryption via the generic composition of encryption and MAC. Our analyses demonstrate that the security of $\mathsf{XoP}$-based and $\mathsf{XoP2}$-based constructions are, in fact, far more similar than what was previously proven. Our security proofs rely on a fine-tuned and extended version of Mirror theory for both lower and upper bounds, which yields more versatile and improved security proofs. Of independent interest, this extension allows us to prove the multi-user MAC security of $\mathsf{nEHtM}$ in the nonce-misuse model, while the previous analysis only applied to the multi-user PRF security in the nonce-respecting model. As a side note, we also point out (and fix) a flaw in the original analysis of Chen et al. [CRYPTO'23].

When outsourcing a database to an untrusted remote server, one might want to verify the integrity of contents while accessing it. To solve this, Blum et al. [FOCS `91] propose the notion of memory checking. Memory checking allows a user to run a RAM program on a remote server, with the ability to verify integrity of the storage with small local storage. In this work, we define and initiate the formal study of memory checking for Parallel RAMs (PRAMs). The parallel RAM model is very expressive and captures many modern architectures such as multi-core architectures and cloud clusters. When multiple clients run a PRAM algorithm on a shared remote server, it is possible that there are concurrency issues that cause inconsistencies. Therefore, integrity verification is even more desirable property in this setting. Assuming only the existence of one-way functions, we construct an online memory checker (one that reports faults as soon as they occur) for PRAMs with $O(\log N)$ simulation overhead in both work and depth. In addition, we construct an offline memory checker (one that reports faults only after a long sequence of operations) with amortized $O(1)$ simulation overhead in both work and depth. Our constructions match the best known simulation overhead of the memory checkers in the standard single-user RAM setting. As an application of our parallel memory checking constructions, we additionally construct the first maliciously secure oblivious parallel RAM (OPRAM) with polylogarithmic overhead.

Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that both Sahai’s construction for SS-NIZK (in the CRS model) and the Fiat-Shamir transformation (in the QROM) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.

Integral, impossible-differential (ID), and zero-correlation (ZC) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most automatic tools regarding integral, ZC, and ID attacks have focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP) model based on satisfiability for finding ID, ZC, and integral distinguishers. This new model can be extended to a unified CP model for finding full key recovery attacks. However, it has limitations, including determining the contradiction location beforehand and a cell-wise model unsuitable for weakly aligned ciphers like Ascon and PRESENT. They also deferred developing a CP model for the partial-sum technique in key recovery as future work. In this paper, we enhance Hadipour et al.'s method in several ways. First, we remove the limitation of determining the contradiction location in advance. Second, we show how to extend the distinguisher model to a bit-wise model, considering the internal structure of S-boxes and keeping the model based on satisfiability. Third, we introduce a CP model for the partial-sum technique for the first time. To show the usefulness and versatility of our approach, we apply it to various designs, from strongly aligned ones like ForkSKINNY and QARMAv2 to weakly aligned ones such as Ascon and PRESENT, yielding significantly improved results. To mention a few of our results, we improve the integral distinguisher of QARMAv2-128 (resp. QARMAv2-64) by 7 (resp. 5) rounds, and the integral distinguisher of ForkSKINNY by 1 round, only thanks to our cell-wise distinguishe modelings. By using our new bit-wise modeling, our tool can find a group of $2^{155}$ 5-round ID and ZC distinguishers for Ascon in only one run, taking a few minutes on a regular laptop. The new CP model for the partial-sum technique enhances integral attacks on all SKINNY variants, notably improving the best attack on SKINNY-$n$-$n$ in the single-key setting by 1 round. We also enhance ID attacks on ForkSKINNY and provide the first analysis of this cipher in a limited reduced-round setting. Our methods are generic and applicable to other block ciphers.

Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties. In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations. 1. We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties. 2. Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state- of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties. 3. We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party. Our implementation will be made public.

In this paper, we introduce Oblivious Homomorphic Encryption (OHE) which provably separates the computation spaces of multiple clients of a fully homomorphic encryption (FHE) service while keeping the evaluator blind about whom a result belongs. We justify the importance of this strict isolation property of OHE by showing an attack on a recently proposed key-private cryptocurrency scheme. Our two OHE constructions are based on a puncturing function where the evaluator can effectively mask ciphertexts from rogue and potentially colluding clients. In the first construction OHE1, we show that this can be im- plemented via an FHE scheme (with key privacy and weak wrong-key decryption properties) plus an anonymous commitment scheme. The second construction OHE2, for flexibility of primitive choice, achieves this via a combination of a standard FHE scheme, an encryption scheme with key privacy and weak wrong-key decryption, and an anonymous commitment scheme. OHE can be used to provide provable anonymity to cloud applications, single server implementations of anonymous messaging as well as account-based cryptocurrencies.

The idea of balancing the side-channel leakage in software was proposed more than a decade ago. Just like with other hiding-based countermeasures, the goal is not to hide the leakage completely but to significantly increase the effort required for the attack. Previous approaches focused on two directions: either balancing the Hamming weight of the processed data or deriving the code by using stochastic leakage profiling. In this brief, we build upon these results by proposing a novel approach that combines the two directions. We provide the theory behind our encoding scheme backed by experimental results on a 32-bit ARM Cortex-M4 microcontroller. Our results show that such a combination gives better side-channel resistance properties than each of the two methods separately.

This paper presents full round distinguishing and key recovery attacks on lightweight block cipher SAND-2 with 64-bit block size and 128-bit key size, which appears to be a mixture of the AND-Rotation-XOR (AND-RX) based ciphers SAND and ANT. However, the security arguments against linear and some other attacks are not fully provided. In this paper, we find that the combination of a SAND-like nibble-based round function and ANT-like bit-based permutations will cause dependencies and lead to iterative linear and differential trails with high probabilities. By exploiting these, full round distinguishing attacks on SAND-2 work with $2^{46}$ queries for linear and $2^{58.60}$ queries for differential in the single-key setting. Then, full round key recovery attacks are also mounted, which work with the time complexity $2^{48.23}$ for linear and $2^{64.10}$ for differential. It should be noted that the dependency observed in this paper only works for SAND-2 and will not threaten SAND and ANT. From the point of designers, our attacks show the risk of mixing the parts of different designs, even though each of them is well-studied to be secure.

We show that the Yang et al.'s key agreement scheme [Future Gener. Comput. Syst., 145, 415-428 (2023)] is flawed. (1) There are some inconsistent computations, which should be corrected. (2) The planned route of a target vehicle is almost exposed. The scheme neglects the basic requirement for bit-wise XOR, and tries to encrypt the route by the operator. The negligence results in some trivial equalities. (3) The scheme is insecure against impersonation attack launched by the next roadside unit.

Many secure computation schemes and protocols (such as numerous variants of secure multi-party computation and homomorphic encryption) have favorable performance characteristics when they are used to evaluate addition and scalar multiplication operations on private values that can be represented as ring elements. A purely algebraic argument (with no references to any specific protocol or scheme) can be used to show that the ability to perform these operations is sufficient to implement any univariate map that operates on private values when that map's domain is finite. Such implementations of univariate maps can be composed in sequence any number of times. Other forms of composition for such implementations can be realized by using multiplication operations involving ring elements, but it is possible that these can be substituted with scalar multiplication operations within certain secure computation workflows.

Motivated by applications in anonymous reputation systems and blockchain governance, we initiate the study of predicate aggregate signatures (PAS), which is a new primitive that enables users to sign multiple messages, and these individual signatures can be aggregated by a combiner, preserving the anonymity of the signers. The resulting PAS discloses only a brief description of signers for each message and provides assurance that both the signers and their description satisfy the specified public predicate. We formally define PAS and give a construction framework to yield a logarithmic size signature, and further reduce the verification time also to logarithmic. We also give several instantiations for several concrete predicates that may be of independent interest. To showcase its power, we also demonstrate its applications to multiple settings including multi-signatures, aggregate signatures, threshold sig- natures, (threshold) ring signatures, attribute-based signatures, etc, and advance the state of the art in all of them.

In the design of an identity-based encryption (IBE) scheme, the primary security assumptions center around quadratic residues, bilinear mappings, and lattices. Among these approaches, one of the most intriguing is introduced by Clifford Cocks and is based on quadratic residues. However, this scheme has a significant drawback: a large ciphertext to plaintext ratio. A different approach is taken by Zhao et al., who design an IBE still based on quadratic residues, but with an encryption process reminiscent of the Goldwasser-Micali cryptosystem. In the following pages, we will introduce an elementary method to accelerate Cocks' encryption process and adapt a space-efficient encryption technique for both Cocks' and Zhao et al.'s cryptosystems.

In Crypto 94, Chor, Fiat, and Naor first introduced the traitor tracing (TT) systems, which aim at helping content distributors identify pirates. Since its introduction, many traitor tracing schemes have been proposed. However, we observe until now almost all the traitor tracing systems using probabilistic public key (and secret key) encryption as the the content distribution algorithm, they do not consider this basic fact: the malicious encrypter can plant some trapdoor in the randomness of the ciphertexts and later he can use this trapdoor or the delegation of the trapdoor to construct decoding pirates, He can sell them to the black market and get his own benefits. At first sight, this new attack model is too strong to capture the real attack scenarios. But we think it is valuable at least for the following two reasons: (1) Note in many modern content distribution systems, there are at least existing three different roles: { the content provider, the content distributer and the content consumer. In this framework, the encrypter is not necessarily the content provider (or content owner). It can be a malicious employee in the content provider corporation, it can also be the malicious content distributer or its malicious employee}. In all these cases, the encrypter has its own benefits and has the potential intention to plant some trapdoor in the randomness for generating ciphertexts. (2) Also note in the related work, there is a conclusion that traitor tracing and differential privacy can have directly influence on each other, while differential privacy (DP) is at the heart of constructing modern privacy preserving systems. But if we consider this new insider attacker (the encrypter), at least some part arguments on the relationship between traitor tracing and differential privacy need more consideration. Therefore in this paper we carefully describe this new insider attacker and investigate thoroughly on its effect. Our main research results are the following: (1) We show that many existing public key traitor tracing systems with probabilistic encryption algorithm are failing to work correctly when facing this malicious encrypter.They are including the BSW, BW, GKSW, LCZ and BZ traitor tracing systems. Furthermore, we conclude that most of the existing traitor tracing systems using probabilistic encryption algorithm can not resist this attack. (2) When considering the insider attacker (the encrypter), if the traitor tracing schemes using probabilistic encryption algorithms, the conclusion on tight relationship between traitor tracing and differential privacy may need more consideration. (3) By employing the technique of hash function, we show how to design TT+ system which can resist this type of attack based on the existing traitor tracing system. Compared with the old traitor tracing system, our new proposal does not add much overhead and thus is practical too.

In this paper, we analyze the Espresso cipher from a related key chosen IV perspective. More precisely, we explain how one can obtain Key-IV pairs such that Espresso's keystreams either have certain identical bits or are shifted versions of each other. For the first case, we show how to obtain such pairs after $2^{32}$ iterations, while for the second case, we present an algorithm that produces such pairs in $2^{28}$ iterations. Moreover, we show that by making a minor change in the padding used during the initialization phase, it can lead to a more secure version of the cipher. Specifically, changing the padding increases the complexity of our second attack from $2^{28}$ to $2^{34}$. Finally, we show how related IVs can accelerate brute force attacks, resulting in a faster key recovery. Although our work does not have any immediate implications for breaking the Espresso cipher, these observations are relevant in the related-key chosen IV scenario.

We present a new method for doing multi-party private set intersection against a malicious adversary, which reduces the total communication cost to $ O(nl\kappa) $. Additionally, our method can also be used to build a multi-party Circuit-PSI without payload. Our protocol is based on Vector-OLE(VOLE) and oblivious key-value store(OKVS). To meet the requirements of the protocol, we first promote the definition of VOLE to a multi-party version. After that, we use the new primitive to construct our protocol and prove that it can tolerate all-but-two malicious corruptions. Our protocol follows the idea of [RS21], where each party encodes the respective set as a vector, uses VOLE to encrypt the vector, and finally construct an OPRF to get the result. When it comes to multi-party situation, we have to encrypt several vectors at one time. As a result, the VOLE used in [RS21] and follow-up papers is not enough, that brings our idea of an multi-party VOLE.

In this paper, inspired by the work of Beyne and Rijmen at CRYPTO 2022, we explore the accurate probability of $d$-differential in the fixed-key model. The theoretical foundations of our method are based on a special matrix $-$ quasi-$d$-differential transition matrix, which is a natural extension of the quasidifferential transition matrix. The role of quasi-$d$-differential transition matrices in polytopic cryptananlysis is analogous to that of correlation matrices in linear cryptanalysis. Therefore, the fixed-key probability of a $d$-differential can be exactly expressed as the sum of the correlations of its quasi-$d$-differential trails. Then we revisit the boomerang attack from a perspective of 3-differential. Different from previous works, the probability of a boomerang distinguisher can be exactly expressed as the sum of the correlations of its quasi-$3$-differential trails without any assumptions in our work. In order to illustrate our theory, we apply it to the lightweight block cipher GIFT. It is interesting to find the probability of every optimal 3-differential characteristic of an existing 2-round boomerang is zero, which can be seen as an evidence that the security of block ciphers adopting half-round key XOR might be overestimated previously to some extent in differential-like attacks.

GLS254 is an elliptic curve defined over a finite field of characteristic 2; it contains a 253-bit prime order subgroup, and supports an endomorphism that can be efficiently computed and helps speed up some typical operations such as multiplication of a curve element by a scalar. That curve offers on x86 and ARMv8 platforms the best known performance for elliptic curves at the 128-bit security level. In this paper we present a number of new results related to GLS254: - We describe new efficient and complete point doubling formulas (2M+4S) applicable to all ordinary binary curves. - We apply the previously described (x,s) coordinates to GLS254, enhanced with the new doubling formulas. We obtain formulas that are not only fast, but also complete, and thus allow generic constant-time usage in arbitrary cryptographic protocols. - Our strictly constant-time implementation multiplies a point by a scalar in 31615 cycles on an x86 Coffee Lake, and 77435 cycles on an ARM Cortex-A55, improving previous records by 13% and 11.7% on these two platforms, respectively. - We take advantage of the completeness of the formulas to define some extra operations, such as canonical encoding with (x, s) compression, constant-time hash-to-curve, and signatures. Our Schnorr signatures have size only 48 bytes, and offer good performance: signature generation in 18374 cycles, and verification in 27376 cycles, on x86; this is about four times faster than the best reported Ed25519 implementations on the same platform. - The very fast implementations leverage the carryless multiplication opcodes offered by the target platforms. We also investigate performance on CPUs that do not offer such an operation, namely a 64-bit RISC-V CPU (SiFive-U74 core) and a 32-bit ARM Cortex-M4 microcontroller. While the achieved performance is substantially poorer, it is not catastrophic; on both platforms, GLS254 signatures are only about 2x to 2.5x slower than Ed25519.

The Crossbred algorithm is one of the algorithms for solving a system of polynomial equations, proposed by Joux and Vitse in 2017. It has been implemented in Fukuoka MQ challenge, which is related to the security of multivariate crytography, and holds several records. A framework for estimating the complexity has already been provided by Chen et al. in 2017. However, it is generally unknown which parameters are actually available. This paper investigates how to select available parameters for the Crossbred algorithm. As a result, we provide formulae that give an available parameter set and estimate the complexity of the Crossbred algorithm.

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.

In this paper, we introduce the subfield bilinear collision problem and use it to construct an identification protocol and a signature scheme. This construction is based on the MPC-in-the-head paradigm and uses the Fiat-Shamir transformation to obtain a signature.

Computing the distance between two non-normalized vectors $\mathbfit{x}$ and $\mathbfit{y}$, represented by $\Delta(\mathbfit{x},\mathbfit{y})$ and comparing it to a predefined public threshold $\tau$ is an essential functionality used in privacy-sensitive applications such as biometric authentication, identification, machine learning algorithms ({\em e.g.,} linear regression, k-nearest neighbors, etc.), and typo-tolerant password-based authentication. Tackling a widely used distance metric, {\sc Nomadic} studies the privacy-preserving evaluation of cosine similarity in a two-party (2PC) distributed setting. We illustrate this setting in a scenario where a client uses biometrics to authenticate to a service provider, outsourcing the distance calculation to two computing servers. In this setting, we propose two novel 2PC protocols to evaluate the normalising cosine similarity between non-normalised two vectors followed by comparison to a public threshold, one in the semi-honest and one in the malicious setting. Our protocols combine additive secret sharing with function secret sharing, saving one communication round by employing a new building block to compute the composition of a function $f$ yielding a binary result with a subsequent binary gate. Overall, our protocols outperform all prior works, requiring only two communication rounds under a strong threat model that also deals with malicious inputs via normalisation. We evaluate our protocols in the setting of biometric authentication using voice, and the obtained results reveal a notable efficiency improvement compared to existing state-of-the-art works.

MAYO is a popular high-calorie condiment as well as an auspicious candidate in the ongoing NIST competition for additional post-quantum signature schemes achieving competitive signature and public key sizes. In this work, we present high-speed implementations of MAYO using the AVX2 and Armv7E-M instruction sets targeting recent x86 platforms and the Arm Cortex-M4. Moreover, the main contribution of our work is showing that MAYO can be even faster when switching from a bitsliced representation of keys to a nibble-sliced representation. While the bitsliced representation was primarily motivated by faster arithmetic on microcontrollers, we show that it is not necessary for achieving high performance on Cortex-M4. On Cortex-M4, we instead propose to implement the large matrix multiplications of MAYO using the Method of the Four Russians (M4R), which allows us to achieve better performance than when using the bitsliced approach. This results in up to 21% faster signing. For AVX2, the change in representation allows us to implement the arithmetic much faster using shuffle instructions. Signing takes up to 3.2x fewer cycles and key generation and verification enjoy similar speedups. This shows that MAYO is competitive with lattice-based signature schemes on x86 CPUs, and a factor of 2-6 slower than lattice-based signature schemes on Cortex-M4 (which can still be considered competitive).

We prove that two variants of the Fujisaki-Okamoto (FO) transformations are selective opening secure (SO) against chosen-ciphertext attacks in the quantum random oracle model (QROM), assuming that the underlying public-key encryption scheme is one-way secure against chosen-plaintext attacks (OW-CPA). The two variants we consider are $\mathsf{FO}^{\not{\bot}}$ (Hofheinz, Hövelmanns, and Kiltz, TCC 2017) and $\mathsf{U}^{\not{\bot}}_\mathsf{m}$ (Jiang et al., CRYPTO 2018). This is the first correct proof in the QROM. The previous work of Sato and Shikata (IMACC 2019) showed the SO security of $\mathsf{FO}^{\not{\bot}}$ in the QROM. However, we identify a subtle gap in their work. To close this gap, we propose a new framework that allows us to adaptively reprogram a QRO with respect to multiple queries that are computationally hard to predict. This is a property that can be easily achieved by the classical ROM, but is very hard to achieve in the QROM. Hence, our framework brings the QROM closer to the classical ROM. Under our new framework, we construct the first tightly SO secure PKE in the QROM using lossy encryption. Our final application is proving $\mathsf{FO}^{\not{\bot}}$ and $\mathsf{U}^{\not{\bot}}_\mathsf{m}$ are bi-selective opening (Bi-SO) secure in the QROM. This is a stronger SO security notion, where an adversary can additionally corrupt some users' secret keys.

Deep learning-based profiling side-channel analysis has gained widespread adoption in academia and industry due to its ability to uncover secrets protected by countermeasures. However, to exploit this capability, an adversary must have access to a clone of the targeted device to obtain profiling measurements and know secret information to label these measurements. Non-profiling attacks avoid these constraints by not relying on secret information for labeled data. Instead, they attempt all key guesses and select the most successful one. Deep learning approaches form the foundation of several non-profiling attacks, but these methods often suffer from high computational complexity and limited performance in practical applications. This work explores the performance of multi-output regression (MOR) models in side-channel analysis. We start with the recently proposed multi-output regression (MOR) approach for non-profiling side-channel analysis. Then, we significantly improve its performance by updating the 1) loss function, 2) distinguisher, and 3) employing a novel concept of validation set to reduce overfitting. We denote our approach as MORE - Multi-Output Regression Enhanced, which emphasizes significantly better attack performance than MOR. Our results demonstrate that combining the MORE methodology, ensembles, and data augmentation presents a potent strategy for enhancing non-profiling side-channel attack performance and improving the reliability of distinguishing key candidates.

Weightwise degree-d functions are Boolean functions that take the values of a function of degree at most d on each set of fixed Hamming weight. The class of weightwise affine functions encompasses both the symmetric functions and the Hidden Weight Bit Function (HWBF). The good cryptographic properties of the HWBF, except for the nonlinearity, motivates to investigate a larger class with functions that share the good properties and have a better nonlinearity. Additionally, the homomorphic friendliness of symmetric functions exhibited in the context of hybrid homomorphic encryption and the recent results on homomorphic evaluation of Boolean functions make this class of functions appealing for efficient privacy-preserving protocols. In this article we realize the first study on weightwise degree-d functions, focusing on weightwise affine and weightwise quadratic functions. We show some properties on these new classes of functions, in particular on the subclass of cyclic weightwise functions. We provide balanced constructions and prove nonlinearity lower bounds for all cyclic weightwise affine functions and for a family of weightwise quadratic functions. We complement our work with experimental results, they show that other cyclic weightwise linear functions than the HWBF have better cryptographic parameters, and considering weightwise quadratic functions allows to reach higher algebraic immunity and substantially better nonlinearity.

The need for energy optimizations in modern systems forces CPU vendors to provide Dynamic Voltage Frequency Scaling (DVFS) interfaces that allow software to control the voltage and frequency of CPU cores. In recent years, the accessibility of such DVFS interfaces to adversaries has amounted to a plethora of fault attack vectors. In response, the current countermeasures involve either restricting access to DVFS interfaces or including additional compiler-based checks that let the DVFS fault occur but prevent an adversary from weaponizing it. However, such countermeasures are overly restrictive because (1) they prevent benign, non-SGX processes from utilizing DVFS, and (2) rely upon a less practical threat model than what is acceptable for Intel SGX. In this work, we hence put forth a new countermeasure perspective. We reason that all DVFS fault attacks are helped by system design decisions that allow an adversary to search through the entire space of frequency/voltage pairs which lead to DVFS faults on the victim system. Using this observation, we classify such frequency/voltage pairs causing DVFS faults as unsafe system states. We then develop a kernel module level countermeasure (in non-SGX execution context) that polls core frequency/voltage pairs to detect when the system is in an unsafe state, and force it back into a safe state. Our countermeasure completely prevents DVFS faults on three Intel generation CPUs: Sky Lake, Kaby Lake R, and Comet Lake, while allowing accessibility of DVFS features to benign non-SGX executions (something which prior works fail to achieve). Additionally, we also put forth the notion of maximal safe state, allowing our countermeasure to be implemented both as microcode (on the micro-architecture level) and as model-specific register (on the hardware level), as opposed to prior countermeasures which can not be implemented at the hardware level. Finally, we evaluate the overhead of our kernel module's execution on SPEC2017, observing an minuscule overhead of 0.28%.

Large transformer-based models have realized state- of-the-art performance on lots of real-world tasks such as natural language processing and computer vision. However, with the increasing sensitivity of the data and tasks they handle, privacy has become a major concern during model deployment. In this work, we focus on private inference in two-party settings, where one party holds private inputs and the other holds the model. We introduce BumbleBee, a fast and communication-friendly two-party private transformer inference system. Our contributions are three-fold: Firstly, we present optimized homomorphic encryption-based proto- cols that enable the multiplication of large matrices with 80 – 90% less communication cost than existing methods. Secondly, we offer a general method for designing efficient and accurate protocols for non-linear activation functions in transformers. Our activation protocols have demonstrated speed and reduced the communication overhead by 80 – 95% over two existing methods. Finally, we conducted intensive benchmarks on several large transformer models. Results show that BumbleBee is more than one order of magnitude faster than Iron (NeurIPS22).

In STOC 2019 Canetti et al. showed how to soundly instantiate the Fiat-Shamir transform assuming that prover and verifier have access to the key of a 𝑐𝑜𝑟𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛 𝑖𝑛𝑡𝑟𝑎𝑐𝑡𝑎𝑏𝑙𝑒 ℎ𝑎𝑠ℎ 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑓𝑜𝑟 𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑙𝑦 𝑠𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠. The transform requires the starting protocol to be a special 3-round public-coin scheme that Canetti et al. call 𝑡𝑟𝑎𝑝𝑑𝑜𝑜𝑟 𝑠𝑖𝑔𝑚𝑎-𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙. One downside of the Canetti et al. approach is that the key of the hash function can be used only once (or a pre-determined bounded number of times). That is, each new zero-knowledge proof requires a freshly generated hash key (i.e., a freshly generated setup). This is in contrast to what happens with the standard Fiat-Shamir transform, where the prover, having access to the same hash function (modeled as a random-oracle), can generate an unbounded number of proofs that are guaranteed to be zero-knowledge and sound. As our main contribution, we extend the results of Canetti et al., by proposing a multi-theorem protocol that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Our construction is presented in the form of a compiler, that follows the Fiat-Shamir paradigm, which takes as input any trapdoor sigma-protocol for the NP-language $L$ and turns it into a non-interactive zero-knowledge protocol that satisfies the properties we mentioned. To be best of our knowledge, ours is the first compiler that follows the Fiat-Shamir paradigm to obtain a multi-theorem adaptive NIZK relying on correlation intractable hash functions.

Oblivious RAM (ORAM) is a general-purpose technique for hiding memory access patterns. This is a fundamental task underlying many secure computation applications. While known ORAM schemes provide optimal asymptotic complexity, despite extensive efforts, their concrete costs remain prohibitively expensive for many interesting applications. The current state-of-the-art practical ORAM schemes are suitable only for somewhat small memories (Square-Root ORAM or Path ORAM). This work presents a novel concretely efficient ORAM construction based on recent breakthroughs in asymptotic complexity of ORAM schemes (PanORAMa and OptORAMa). We bring these constructions to the realm of practically useful schemes by relaxing the restriction on constant local memory size. Our design provides a factor of at least $6$ to $8$ improvement over an implementation of the original Path ORAM for a set of reasonable memory sizes (e.g., 1GB, 1TB) and with the same local memory size. To our knowledge, this is the first practical implementation of an ORAM based on the full hierarchical ORAM framework. Prior to our work, the belief was that hierarchical ORAM-based constructions were inherently too expensive in practice. We implement our design and provide extensive evaluation and experimental results.

Differential-Linear (DL) cryptanalysis is a well known cryptanalytic technique that combines differential and linear cryptanalysis. Over the years, multiple techniques were proposed to increase its strength and applicability. Two relatively recent ones are: The partitioning technique by Leurent and the use of neutral bits adapted by Beierle et al. to DL cryptanalysis. In this paper we compare these techniques and discuss the possibility of using them together to achieve the best possible DL attacks. We study the combination of these two techniques and show that in many cases they are indeed compatible. We demonstrate the strength of the combination in two ways. First, we present the first DL attack on 4-round Xoodyak and an extension to 5-round in the related key model. We show that the attacks are possible only by using these two techniques simultaneously. In addition, using the combination of the two techniques we improve a DL attack on 9-round DES. We show that the partitioning technique mainly reduces the time complexity, and the use of neutral bits mainly reduces the data complexity, while the combination of them reduces both the time and data complexities.

Post-quantum cryptographic (PQC) algorithms, especially those based on the learning with errors (LWE) problem, have been subjected to several physical attacks in the recent past. Although the attacks broadly belong to two classes -- passive side-channel attacks and active fault attacks, the attack strategies vary significantly due to the inherent complexities of such algorithms. Exploring further attack surfaces is, therefore, an important step for eventually securing the deployment of these algorithms. Also, it is important to test the robustness of the already proposed countermeasures in this regard. In this work, we propose a new fault attack on side-channel secure masked implementation of LWE-based key-encapsulation mechanisms (KEMs) exploiting fault propagation. The attack typically originates due to an algorithmic modification widely used to enable masking, namely the Arithmetic-to-Boolean ($\mathtt{A2B}$) conversion. We exploit the data dependency of the adder carry chain in $\mathtt{A2B}$ and extract sensitive information, albeit masking (of arbitrary order) being present. As a practical demonstration of the exploitability of this information leakage, we show key recovery attacks of Kyber, although the leakage also exists for other schemes like Saber. The attack on Kyber targets the decapsulation module and utilizes Belief Propagation (BP) for key recovery. To the best of our knowledge, it is the first attack exploiting an algorithmic component introduced to ease masking rather than only exploiting the randomness introduced by masking to obtain desired faults (as done by Delvaux). Finally, we performed both simulated and electromagnetic (EM) fault-based practical validation of the attack for an open-source first-order secure Kyber implementation running on an STM32 platform.

Sponge based constructions have gained significant popularity for designing lightweight authenticated encryption modes. Most of the authenticated ciphers following the Sponge paradigm can be viewed as variations of the Transform-then-permute construction. It is known that a construction following the Transform-then-permute paradigm provides security against any adversary having data complexity $D$ and time complexity $T$ as long as $DT \ll 2^{b-r}$. Here, $b$ represents the size of the underlying permutation, while $r$ pertains to the rate at which the message is injected. The above result demonstrates that an increase in the rate leads to a degradation in the security of the constructions, with no security guaranteed to constructions operating at the full rate, where $r=b$. This present study delves into the exploration of whether adding some auxiliary states could potentially improve the security of the Transform-then-permute construction. Our investigation yields an affirmative response, demonstrating that a special class of full rate Transform-then-permute with additional states, dubbed frTtP+, can indeed attain security when operated under a suitable feedback function and properly initialized additional state. To be precise, we prove that frTtP+ provides security as long as $D \ll 2^{s/2}$ and $T \ll 2^{s}$, where $s$ denotes the size of the auxiliary state in terms of bits. To demonstrate the applicability of this result, we show that the construction $Orange-Zest_{mod}$ belongs to this class, thereby obtaining the desired security. In addition, we propose a family of full-rate Transform-then-permute construction with a Beetle-like feedback function, dubbed \textsf{fr-Beetle}, which also achieves the same level of security.