## Papers updated in last 183 days (1561 results)

On the {\sf P/poly} Validity of the Agr17 FE Scheme

Functional encryption (FE) is a cutting-edge research topic in cryptography. The Agr17 FE scheme is a major scheme of FE area. This scheme had the novelty of “being applied for the group of general functions (that is, {\sf P/poly} functions) without IO”. It took the BGG+14 ABE scheme as a bottom structure, which was upgraded into a “partially hiding attribute” scheme, and combined with a fully homomorphic encryp-tion (FHE) scheme. However, the Agr17 FE scheme had a strange operation. For noise cancellation of FHE decryption stage, it used bulky “searching noise” rather than elegant “filtering”. It searched total modulus interval, so that the FHE modulus should be polynomially large. In this paper we discuss the {\sf P/poly} validity of the Agr17 FE scheme. First, we obtain the result that the Agr17 FE scheme is {\sf P/poly} invalid. More detailedly, when the Agr17 FE scheme is applied for the group of randomly chosen {\sf P/poly} Boolean functions, FHE modulus at the “searching” stage cannot be polynomially large. Our analysis is based on three restrictions of the BGG+14 ABE scheme: (1) The modulus of the BGG+14 ABE should be adapted to being super-polynomially large, if it is applied for the group of randomly chosen {\sf P/poly} functions. (2) The modulus of the BGG+14 ABE cannot be switched. (3) If the BGG+14 ABE is upgraded into a “partially hiding attribute” scheme, permitted operations about hidden part of the attribute can only be affine operations. Then, to check whether the {\sf P/poly} validity can be obtained by modifying the scheme, we consider two modified versions. The first modified version is controlling the FHE noise by repeatedly applying bootstrapping, and replacing a modular inner product with an arithmetic inner product. The second modified version is replacing the search for the modulus interval with the search for a public noise interval, hoping such noise interval polynomially large and tolerating the modulus which may be super-polynomially large. The first modified version may be {\sf P/poly} valid, but it is weaker. There is no evidence to support the {\sf P/poly} validity of the second modified version. We also present an additional conclusion that there is no evidence to support the {\sf P/poly} validity of the GVW15 PE scheme. Finally, we present our response to an argument that our work is unnecessary, and show that our work is quite valuable for any interpretation.

Dishonest Majority Multiparty Computation over Matrix Rings

The privacy-preserving machine learning (PPML) has gained growing importance over the last few years. One of the biggest challenges is to improve the efficiency of PPML so that the communication and computation costs of PPML are affordable for large machine learning models such as deep learning. As we know, linear algebra such as matrix multiplication occupies a significant part of the computation in deep learning such as deep convolutional neural networks (CNN). Thus, it is desirable to propose the MPC protocol specialized for the matrix operations. In this work, we propose a dishonest majority MPC protocol over matrix rings which supports matrix multiplication and addition. Our MPC protocol can be seen as a variant of SPDZ protocol, i.e., the MAC and global key of our protocol are vectors of length $m$ and the secret of our protocol is an $m\times m$ matrix. Compared to the classic SPDZ protocol, our MPC protocol reduces the communication complexity by at least $m$ times to securely compute a matrix multiplication. We also show that the communication complexity of our MPC protocol is asymptotically as good as [16] which also presented a dishonest majority MPC protocol specialized for matrix operations, i.e., the communication complexity of securely computing a multiplication gate is $O(m^2n^2\log q)$ in the preprocessing phase and $O(m^2n\log q)$ in the online phase. The share size and the number of multiplications of our protocol are reduced by around $50\%$ and $40\%$ of [16], respectively. However, we take a completely different approach. The protocol in [16] uses a variant of BFV scheme to embed a whole matrix into a single ciphertext and then treats the matrix operation as the entry-wise operation in the ciphertext while our approach resorts to a variant of vector linear oblivious evaluation (VOLE) called the subfield VOLE [33] which can securely compute the additive sharing of $v {\bf x}$ for $v\in \mathbb{F}_{q^b}, {\bf x}\in \mathbb{F}_q^a$ with sublinear communication complexity. Finally, we note that our MPC protocol can be easily extended to small fields.

On the Security of Succinct Interactive Arguments from Vector Commitments

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.

Scalable Equi-Join Queries over Encrypted Database

Secure join queries over encrypted databases, the most expressive class of SQL queries, have attracted extensive attention recently. The state-of-the-art JXT (Jutla et al. ASIACRYPT 2022) enables join queries on encrypted relational databases without pre-computing all possible joins. However, JXT can merely support join queries over two tables (in encrypted databases) with some high-entropy join attributes.
In this paper, we propose an equi-join query protocol over two tables dubbed JXT+, that allows the join attributes with arbitrary names instead of JXT requiring the identical name for join attributes. JXT+ reduces the query complexity from $O(\ell_1 \cdot \ell_2)$ to $O(\ell_1)$ as compared to JXT, where $\ell_1$ and $\ell_2$ denote the numbers of matching records in two tables respectively. Furthermore, we present JXT++, the \emph{first} equi-join queries across three or more tables over encrypted databases without pre-computation. Specifically, JXT++ supports joins of arbitrary attributes, i.e., all attributes (even low-entropy) can be candidates for join, while JXT requires high-entropy join attributes. In addition, JXT++ can alleviate sub-query leakage on three or more tables, which hides the leakage from the matching records of two-table join.
Finally, we implement and compare our proposed schemes with the state-of-the-art JXT. The experimental results demonstrate that both of our schemes are superior to JXT in search and storage costs. In particular, JXT+ (resp., JXT++) brings a saving of 49% (resp., 68%) in server storage cost and achieves a speedup of 51.7$\times$ (resp., 54.3$\times$) in search latency.

Arithmetic Tuples for MPC

Some of the most efficient protocols for Multi-Party Computation (MPC) use a two-phase approach where correlated randomness, in particular Beaver triples, is generated in the offline phase and then used to speed up the online phase. Recently, more complex correlations have been introduced to optimize certain operations even further, such as matrix triples for matrix multiplications. In this paper, our goal is to speed up the evaluation of multivariate polynomials and therewith of whole arithmetic circuits in the online phase. To this end, we introduce a new form of correlated randomness: arithmetic tuples. Arithmetic tuples can be fine tuned in various ways to the constraints of application at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups an arithmetic tuples based online phase outperforms state-of-the-art protocols based on Beaver triples.

Analysis on Sliced Garbling via Algebraic Approach

Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy~(Crypto~2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans~(Eurocrypt~2015).
Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa + O(1)$ bits for garbling AND gates.
Precisely they extended the idea of \emph{slicing} introduced by Rosulek and Roy to garble 3-input gates of the form $g(u,v,w) := u(v+w)$.
By setting $w = 0$, it can be used to garble AND gates with the improved communication costs.
However, in this paper, we observe that the scheme proposed by Ashur, Hazy, and Satish leaks information on the permute bits,
thereby allowing the evaluator to reveal information on the private inputs.
To be precise, we show that in their garbling scheme, the evaluator can compute the bits $\alpha$ and $\beta + \gamma$,
where $\alpha$, $\beta$, and $\gamma$ are the private permute bits of the input labels $A$, $B$, and $C$, respectively.

HierNet: A Hierarchical Deep Learning Model for SCA on Long Traces

Side-channel analysis (SCA) compromises the security of cryptographic devices by exploiting various side-channel leakages such as power consumption, electromagnetic (EM) emanations, or timing variations, posing a practical threat to the security and privacy of modern digital systems. In power or EM SCA, statistical or machine learning methods are employed to extract secret information from power/EM traces. In many practical scenarios, raw power/EM traces can span hundreds of thousands of features, with relevant leakages occurring over only a few small segments. Consequently, existing SCAs often select a small number of features before launching the attack, making their success highly dependent on the feasibility of feature selection. However, feature selection may not always be possible, such as in the presence of countermeasures like masking or jitters.
Several recent works have employed deep learning (DL) methods to conduct SCA on long raw traces, thereby reducing dependence on feature selection steps. However, these methods often perform poorly against various jitter-based countermeasures. While some of these methods have shown high robustness to jitter-based countermeasures on relatively shorter traces, we demonstrate in this work that their performance deteriorates as trace lengths increase. Based on these observations, we develop a hierarchical DL model for SCA on long traces that is robust against various countermeasures. The proposed model, HierNet, extracts information from long traces using a two-level information assimilation process. At the base level, a DL model with shift-invariance is employed to extract information from smaller trace segments. Subsequently, a top-level DL model integrates the outputs of the base model to generate the final output. The proposed model has been experimentally evaluated against various combinations of masking, random delay, and clock jitter countermeasures using traces with lengths exceeding $200K$ features. The results have been compared with three existing SCA benchmark models. They demonstrate HierNet's superiority in several scenarios, such as on long traces, against clock jitter countermeasures, and low training data scenarios. In particular, while other models fail to reach the guessing entropy $1$ using as many as $5K$ traces, HierNet achieves the same with fewer than or close to $10$ traces.

It's a Kind of Magic: A Novel Conditional GAN Framework for Efficient Profiling Side-channel Analysis (Extended Version)

Profiling side-channel analysis (SCA) is widely used to evaluate the security of cryptographic implementations under worst-case attack scenarios. This method assumes a strong adversary with a fully controlled device clone, known as a profiling device, with full access to the internal state of the target algorithm, including the mask shares. However, acquiring such a profiling device in the real world is challenging, as secure products enforce strong life cycle protection, particularly on devices that allow the user partial (e.g., debug mode) or full (e.g., test mode) control. This enforcement restricts access to profiling devices, significantly reducing the effectiveness of profiling SCA.
To address this limitation, this paper introduces a novel framework that allows an attacker to create and learn from their own white-box reference design without needing privileged access on the profiling device.
Specifically, the attacker first implements the target algorithm on a different type of device with full control. Since this device is a white box to the attacker, they can access all internal states and mask shares. A novel conditional generative adversarial network (CGAN) framework is then introduced to mimic the feature extraction procedure from the reference device and transfer this experience to extract high-order leakages from the target device. These extracted features then serve as inputs for profiled SCA. Experiments show that our approach significantly enhances the efficacy of black-box profiling SCA, matching or potentially exceeding the results of worst-case security evaluations. Compared with conventional profiling SCA, which has strict requirements on the profiling device, our framework relaxes this threat model and, thus, can be better adapted to real-world attacks.

LLRing: Logarithmic Linkable Ring Signatures with Transparent Setup

Linkable ring signatures are an important cryptographic primitive for anonymized applications, such as e-voting, e-cash and confidential transactions. To eliminate backdoor and overhead in a trusted setup, transparent setup in the discrete logarithm or pairing settings has received considerable attention in practice. Recent advances have improved the proof sizes and verification efficiency of linkable ring signatures with a transparent setup to achieve logarithmic bounds. Omniring (CCS '19) and RingCT 3.0 (FC '20) proposed linkable ring signatures in the discrete logarithm setting with logarithmic proof sizes with respect to the ring size, whereas DualDory (ESORICS '22) achieves logarithmic verifiability in the pairing setting. We make three novel contributions in this paper to improve the efficiency and soundness of logarithmic linkable ring signatures: (1) We identify an attack on DualDory that breaks its linkability. (2) To eliminate such an attack, we present a new linkable ring signature scheme in the pairing setting with logarithmic verifiability. (3) We also improve the verification efficiency of linkable ring signatures in the discrete logarithm setting, by a technique of reducing the number of group exponentiations for verification in Omniring by 50%. Furthermore, our technique is applicable to general inner-product relation proofs, which might be of independent interest. Finally, we empirically evaluate our schemes and compare them with the extant linkable ring signatures in concrete implementation.

Adaptor Signatures: New Security Definition and A Generic Construction for NP Relations

An adaptor signatures (AS) scheme is an extension of digital signatures that allows the signer to generate a pre-signature for an instance of a hard relation. This pre-signature can later be adapted to a full signature with a corresponding witness. Meanwhile, the signer can extract a witness from both the pre-signature and the signature. AS have recently garnered more attention due to its scalability and interoperability. Dai et al. [INDOCRYPT 2022] proved that AS can be constructed for any NP relation using a generic construction. However, their construction has a shortcoming: the associated witness is exposed by the adapted signature. This flaw poses limits the applications of AS, even in its motivating setting, i.e., blockchain, where the adapted signature is typically uploaded to the blockchain and is public to everyone.
To address this issue, in this work we augment the security definition of AS by a natural property which we call witness hiding. We then prove the existence of AS for any NP relation, assuming the existence of one-way functions. Concretely, we propose a generic construction of witness-hiding AS from signatures and a weak variant of trapdoor commitments, which we term trapdoor commitments with a specific adaptable message. We instantiate the latter based on the Hamiltonian cycle problem. Since the Hamiltonian cycle problem is NP-complete, we can obtain witness hiding adaptor signatures for any NP relation.

Eva: Efficient IVC-Based Authentication of Lossy-Encoded Videos

With the increasing spread of fake videos for misinformation, proving the provenance of an edited video (without revealing the original one) becomes critical. To this end, we introduce Eva, the first cryptographic protocol for authenticating lossy-encoded videos. Compared to previous cryptographic methods for image authentication, Eva supports significantly larger amounts of data that undergo complex transformations during encoding. We achieve this by decomposing repetitive and manageable components from video codecs, which can then be handled using Incrementally Verifiable Computation (IVC). By providing a formal definition and security model for proofs of video authenticity, we demonstrate the security of Eva under well-established cryptographic assumptions.
To make Eva efficient, we construct an IVC based on folding schemes that incorporate lookup arguments, resulting in a linear-time prover whose proofs can be compressed to a constant size. We further improve the performance of Eva through various optimizations, including tailored circuit design and GPU acceleration. The evaluation of our implementation shows that Eva is practical: for a $1$-minute HD ($1280 \times 720$) video encoded in H.264 at $30$ frames per second, Eva generates a proof in about $2.5$ hours on consumer-grade hardware at a speed of $5.5$ μs per pixel, surpassing previous cryptographic image authentication schemes that support arbitrary editing operations by more than an order of magnitude.

On the Viability of Open-Source Financial Rails: Economic Security of Permissionless Consensus

Bitcoin demonstrated the possibility of a financial ledger that operates without the need for a trusted central authority. However, concerns persist regarding its security and considerable energy consumption. We assess the consensus protocols that underpin Bitcoin’s functionality, questioning whether they can ensure economically meaningful security while maintaining a permissionless design that allows free entry of operators. We answer this affirmatively by constructing a protocol that guarantees economic security and preserves Bitcoin's permissionless design. This protocol's security does not depend on monetary payments to miners or immense electricity consumption, which our analysis suggests are ineffective. Our framework integrates economic theory with distributed systems theory, and highlights the role of the protocol's user community.

Actively Secure Polynomial Evaluation from Shared Polynomial Encodings

Many of the currently best actively secure Multi-Party Computation (MPC) protocols like SPDZ (Damgård et al., CRYPTO 2012) and improvements thereof use correlated randomness to speed up the time-critical online phase. Although many of these protocols still rely on classical Beaver triples, recent results show that more complex correlations like matrix or convolution triples lead to more efficient evaluations of the corresponding operations, i.e. matrix multiplications or tensor convolutions. In this paper, we address the evaluation of multivariate polynomials with a new form of randomness: polytuples. We use the polytuples to construct a new family of randomized encodings which then allow us to evaluate the given multivariate polynomial. Our approach can be fine-tuned in various ways to the constraints of applications at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups, a polytuples-based online phase outperforms state-of-the-art protocols based on Beaver triples.

Evolving Secret Sharing Made Short

Evolving secret sharing (Komargodski, Naor, and Yogev, TCC’16) generalizes the notion of secret sharing to the setting of evolving access structures, in which the share holders are added to the system in an online manner, and where the dealer does not know neither the access structure nor the maximum number of parties in advance. Here, the main difficulty is to distribute shares to the new players without updating the shares of old players; moreover, one would like to minimize the share size as a function of the number of players.
In this paper, we initiate a systematic study of evolving secret sharing in the computational setting, where the maximum number of parties is polynomial in the security parameter, but the dealer still does not know this value, neither it knows the access structure in advance. Moreover, the privacy guarantee only holds against computationally bounded adversaries corrupting an unauthorized subset of the players.
Our main result is that for many interesting, and practically relevant, evolving access structures (including graphs access structures, DNF and CNF formulas access structures, monotone circuits access structures, and threshold access structures), under standard hardness assumptions, there exist efficient secret sharing schemes with computational privacy and in which the shares are succinct (i.e., much smaller compared to the size of a natural computational representation of the evolving access structure).

An Efficient Hash Function for Imaginary Class Groups

This paper presents a new efficient hash function for imaginary class groups. Many class group based protocols, such as verifiable delay functions, timed commitments and accumulators, rely on the existence of an efficient and secure hash function, but there are not many concrete constructions available in the literature, and existing constructions are too inefficient for practical use cases.
Our novel approach, building on Wesolowski's initial scheme, achieves a 200 fold increase in computation speed, making it exceptionally practical for real-world applications. This optimisation is achieved at the cost of a smaller image of the hash function, but we show that the image is still sufficiently large for the hash function to be secure.

Untangling the Security of Kilian's Protocol: Upper and Lower Bounds

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr's protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr's protocol in the standard model is not fully understood.
In this paper we study Kilian's protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian's protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr's protocol, a precise understanding of the security of Kilian's protocol remains elusive. We contribute new insights via upper bounds and lower bounds.
- Upper bounds. We establish the tightest known bounds on the security of Kilian's protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian's protocol.
- Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian's protocol would imply improving the security analysis of Schnorr's protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian's protocol.

A Note on Gröbner Bases for Anemoi

This paper focuses on algebraic attacks on the $\mathsf{Anemoi}$ family of arithmetization-oriented permutations [Crypto '23]. We consider a slight variation of the naive modeling of the $\mathsf{CICO}$ problem associated to the primitive, for which we can very easily obtain a Gröbner basis and prove the degree of the associated ideal. For inputs in $\mathbb{F}_{q}^2$ when $q$ is an odd prime, we recover the same degree as conjectured for alternative polynomial systems used in other recent works [eprint/2024/250,eprint/2024/347]. Our approach can also be adapted to other settings which have not been studied there, i.e., even characteristic fields and inputs in $\mathbb{F}_{q}^{2\ell}$ for $\ell > 1$. Finally, we analyze the construction of the multiplication matrices associated to our Gröbner basis, showing that it can be achieved in a more efficient way than in the generic case.

Decryption Indistinguishability under Chosen Control Flow

Cryptographic primitives are often validated through rigorous security proofs, but insecure implementations or software-level attacks can compromise control flows, potentially undermining these guarantees. To address this issue, we introduce a new security notion, IND-CFA, which formalizes decryption security in the presence of adversarially controlled execution flows. Using this notion, we investigate the control flows under which a cryptographic scheme remains secure, providing insights into secure implementation practices. We revisit the Encrypt-then-MAC paradigm, underscoring the crucial role of operation sequencing in ensuring the security of authenticated encryption schemes built using this method. Additionally, we provide a detailed analysis of the Encode-then-Encipher (EtE) paradigm, a widely adopted approach for constructing robust AE schemes, revealing its vulnerability to adversarial control flows that can enable attackers to infer low-entropy values in the presence of multiple failure conditions.

SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra

Multiparty computation (MPC) is an important field of cryptography that deals with protecting the privacy of data, while allowing to do computation on that data. A key part of MPC is the parties involved having correlated randomness that they can use to make the computation or the communication between themselves more efficient, while still preserving the privacy of the data. Examples of these correlations include random oblivious transfer (OT) correlations, oblivious linear-function evaluation (OLE) correlations, multiplication triples (also known as Beaver triples) and one-time truth tables. Multi-point function secret sharing (FSS) has been shown to be a great building block for pseudo-random correlation generators. The main question is how to construct fast and efficient multi-point FSS schemes. Here we propose a natural generalization of the scheme of Boyle et al 2016 using a tree structure, a pseudorandom generator and systems of linear equations.
Our schemes SLAMP-FSS and SLAMPR-FSS are more efficient in the evaluation phase than other previously proposed multi-point FSS schemes while being also more flexible and being similar in other efficiency parameters.

$Shortcut$: Making MPC-based Collaborative Analytics Efficient on Dynamic Databases

Secure Multi-party Computation (MPC) provides a promising solution for privacy-preserving multi-source data analytics. However, existing MPC-based collaborative analytics systems (MCASs) have unsatisfying performance for scenarios with dynamic databases. Naively running an MCAS on a dynamic database would lead to significant redundant costs and raise performance concerns, due to the substantial duplicate contents between the pre-updating and post-updating databases.
In this paper, we propose $Shortcut$, a framework that can work with MCASs to enable efficient queries on dynamic databases that support data insertion, deletion, and update. The core idea of $Shortcut$ is to materialize previous query results and directly update them via our query result update (QRU) protocol to obtain current query results. We customize several efficient QRU protocols for common SQL operators, including Order-by-Limit, Group-by-Aggregate, Distinct, Join, Select, and Global Aggregate. These protocols are composable to implement a wide range of query functions. In particular, we propose two constant-round protocols to support data insertion and deletion. These protocols can serve as important building blocks of other protocols and are of independent interest. They address the problem of securely inserting/deleting a row into/from an ordered table while keeping the order. Our experiments show that $Shortcut$ outperforms naive MCASs for minor updates arriving in time, which captures the need of many realistic applications (e.g., insurance services, account data management). For example, for a single query after an insertion, $Shortcut$ achieves up to $186.8 \times$ improvement over those naive MCASs without our QRU protocols on a dynamic database with $2^{16} \sim 2^{20}$ rows, which is common in real-life applications.

On Multi-user Security of Lattice-based Signature under Adaptive Corruptions and Key Leakages

We consider the multi-user security under the adaptive corruptions and key leakages ($\rm{MU^{c\&l}}$ security) for lattice-based signatures. Although there exists an $\rm{MU^{c\&l}}$ secure signature based on a number-theoretic assumption, or a leakage-resilient lattice-based signature in the single-user setting, $\rm{MU^{c\&l}}$ secure lattice-based signature is not known.
We examine the existing lattice-based signature schemes from the viewpoint of $\rm{MU^{c\&l}}$ security, and find that the security of the Lyubashevsky's signature, which is proven to have the ordinary single-user security only, can be extended to the multi-user security even if we take the adaptive corruptions and the key leakages into account.
Our security proof in the multi-user setting makes use of the feature of the SIS problem so that a SIS instance is set to the public parameter and a reduction algorithm can set a public key with a secret key in order to answer a corruption query. We also show that the entropy of the secret key is kept under the bounded leakage with a high probability and then the leakage resilience of signature holds.

Interactive Line-Point Zero-Knowledge with Sublinear Communication and Linear Computation

Studies of vector oblivious linear evaluation (VOLE)-based zero-knowledge (ZK) protocols flourish in recent years. Such ZK protocols feature optimal prover computation and a flexibility for handling arithmetic circuits over arbitrary fields. However, most of them have linear communication, which constitutes a bottleneck for handling large statements in a slow network. The pioneer work AntMan (CCS'22), achieved sublinear communication for the first time within VOLE-based ZK, but lost the advantage of fast proving. In this work, we propose two new VOLE-based ZK constructions that achieve sublinear communication and linear computation, simultaneously. Let $\mathcal{C}$ be a circuit with size $S$, input size $n$, and depth $d$. In particular, our first ZK, specialized for layered circuits, has communication $O(n+d\log{S})$, while our second ZK can be used to prove general circuits and has communication $O(n+d\log{S}+d^2)$.
Our results are obtained by introducing the powerful sum-check techniques from the mature line of works on interactive proofs into the context of VOLE-based ZK for the first time. Reminiscent of the non-interactive line-point zero-knowledge proof system (ITC'21), we introduce an interactive line-point zero-knowledge (ILPZK) proof system, which closely connects with VOLE-based ZK protocols. In addition, our works also enrich the studies of ZK based on interactive proofs, with new interesting features (e.g., having information-theoretic UC-security, naturally supporting any field) achieved.

Hadamard Product Arguments and Their Applications

This paper introduces transparent and efficient arguments for Hadamard products between committed vectors from two source groups. For vectors of length $n$, the proofs consist of $\mathcal{O}(\log n)$ target group elements and $\mathcal{O}(1)$ additional elements. The verifier's workload is dominated by $\mathcal{O}(\log n)$ multi-exponentiations in the target group and $\mathcal{O}(1)$ pairings. We prove our security under the standard SXDH assumption. Additionally, we propose an aggregator for Groth16 pairing-based zk-SNARKs and a proof aggregation technique for the general case of the KZG pairing-based polynomial commitment scheme using our Hadamard product arguments. Both applications support logarithmic-sized aggregated proofs without requiring an additional trusted setup, significantly reducing the verifier’s pairing operations to $\mathcal{O}(1)$.

Carry Your Fault: A Fault Propagation Attack on Side-Channel Protected LWE-based KEM

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.

Provable Security of Linux-DRBG in the Seedless Robustness Model

This paper studies the provable security of the deterministic random bit generator~(DRBG) utilized in Linux 6.4.8, marking the first analysis of Linux-DRBG from a provable security perspective since its substantial structural changes in Linux 4 and Linux 5.17. Specifically, we prove its security up to $O(\min\{2^{\frac{n}{2}},2^{\frac{\lambda}{2}}\})$ queries in the seedless robustness model, where $n$ is the output size of the internal primitives and $\lambda$ is the min-entropy of the entropy source. Our result implies $128$-bit security given $n=256$ and $\lambda=256$ for Linux-DRBG. We also present two distinguishing attacks using $O(2^{\frac{n}{2}})$ and $O (2^{\frac{\lambda}{2}})$ queries, respectively, proving the tightness of our security bound.

New Secret Keys for Enhanced Performance in (T)FHE

Fully Homomorphic Encryption has known impressive improvements in the last 15 years, going from a technology long thought to be impossible to an existing family of encryption schemes able to solve a plethora of practical use cases related to the privacy of sensitive information.
Recent results mainly focus on improving techniques within the traditionally defined framework of GLWE-based schemes, but the recent CPU implementation improvements are mainly incremental.
To keep improving this technology, one solution is to modify the aforementioned framework, by using slightly different hardness assumptions.
In this paper, we identify two limitations with (T)FHE:
(i) there is no fine-grained control over the size of a GLWE secret key, which is traditionally composed of $k$ polynomials with $N=2^\alpha>1$ coefficients;
(ii) for security reasons one cannot use a noise variance smaller than a certain $\sigma_{\min}$ so, for all ciphertext modulus $q\in \mathbb{N}$, there exists an integer
$n_{\mathsf{plateau}}$ such that, with any secret key of size $k\cdot N \ge n_{\mathsf{plateau}}$, one cannot control their level of security, resulting in unnecessary big security levels.
To overcome the aforementioned limitations, we introduce two new types of secret keys for GLWE-based cryptosystems, that can be used separately or together.
We explain why these new secret keys are as secure as the traditional ones and we detail all the improvements that they bring to existing FHE algorithms alongside new algorithms especially efficient with these new keys.
We provide many comparisons with state-of-the-art TFHE techniques with traditional secret keys, and some benchmarks showing computational speed-ups between $1.3$ and $2.4$ while keeping the same level of security and failure probability (correctness).
Furthermore, the size of the key switching and bootstrapping keys is also reduced with this contribution by factors ranging from $1.5$ to $2.7$.

SmartZKCP: Towards Practical Data Exchange Marketplace Against Active Attacks

The trading of data is becoming increasingly important as it holds substantial value. A blockchain-based data marketplace can provide a secure and transparent platform for data exchange. To facilitate this, developing a fair data exchange protocol for digital goods has garnered considerable attention in recent decades. The Zero Knowledge Contingent Payment (ZKCP) protocol enables trustless fair exchanges with the aid of blockchain and zero-knowledge proofs. However, applying this protocol in a practical data marketplace is not trivial.
In this paper, several potential attacks are identified when applying the ZKCP protocol in a practical public data marketplace. To address these issues, we propose SmartZKCP, an enhanced solution that offers improved security measures and increased performance. The protocol is formalized to ensure fairness and secure against potential attacks. Moreover, SmartZKCP offers efficiency optimizations and minimized communication costs. Evaluation results show that SmartZKCP is both practical and efficient, making it applicable in a data exchange marketplace.

Masked Computation the Floor Function and its Application to the FALCON Signature

FALCON is candidate for standardization of the new Post Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers which is unusual in the cryptography field. While recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most noticeably how to protect the floor function. We propose in this work to complete the existing first trials of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proof in the probing model using the Non-Interference concepts.

IsoLock: Thwarting Link-Prediction Attacks on Routing Obfuscation by Graph Isomorphism

Logic locking/obfuscation secures hardware designs from untrusted entities throughout the globalized semiconductor supply chain. Machine learning (ML) recently challenged the security of locking: such attacks successfully captured the locking-induced, structural design modifications to decipher obfuscated gates. Although routing obfuscation eliminates this threat, more recent attacks exposed new vulnerabilities, like link formation, breaking such schemes. Thus, there is still a need for advanced, truly learning-resilient locking solutions.
Here we propose IsoLock, a provably-secure locking scheme that utilizes isomorphic structures which ML models and other structural methods cannot discriminate. Unlike prior work, IsoLock’s security promise neither relies on re-synthesis nor on dedicated sub-circuits. Instead, IsoLock introduces isomorphic key-gate structures within the design via systematic routing obfuscation. We theoretically prove the security of IsoLock against modeling attacks. Further, we lock ISCAS-85 and ITC-99 benchmarks and launch state-of-the-art ML attacks, SCOPE and MuxLink, as well as the Redundancy and SAAM attacks, which only decipher an average of 0–6% of the key, well confirming the resilience of IsoLock. All in all, IsoLock is proposed to break the cycle of “cat and mouse” in locking and attack studies, through a provably-secure locking approach against structural ML attacks.

MYao: Multiparty ``Yao'' Garbled Circuits with Row Reduction, Half Gates, and Efficient Online Computation

Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.
We present MYao, a new multiparty protocol for achieving a ``Yao'' garbled circuit, i.e., the garbled circuit size and online computation time are independent of the number of parties. The key innovation is that the parties collaboratively compute the PRF in MPC, which was previously believed to be inefficient. In this paper, we challenge this long-standing assumption by basing the garbled circuit construction on ``MPC-friendly'' PRFs. One of the highlights of our new technique is that we are able to achieve, for the first time, full row-reduction in multiparty garbled circuits. To achieve this optimization without increasing the number of rounds, we utilize free-XOR and half gates, presenting a new technique for choosing the keys, based on a naturally occurring relation between the 2 keys of the 2 half-gates.
MYao reduces the garbled circuit size by more than 90%, the total communication by more than 75%, and the online computation time by more than 10%, compared to all known solutions based on key-homomorphic PRFs, thus substantially improving the overall efficiency in both the offline and the online phases. Furthermore, MYao significantly improves over semi-honest BMR in online phase efficiency when the number of parties exceeds 80.

Kronos: A Secure and Generic Sharding Blockchain Consensus with Optimized Overhead

Sharding enhances blockchain scalability by dividing the network into shards, each managing specific unspent transaction outputs or accounts. As an introduced new transaction type, cross-shard transactions pose a critical challenge to the security and efficiency of sharding blockchains. Currently, there is a lack of a generic sharding blockchain consensus pattern that achieves both security and low overhead.
In this paper, we present Kronos, a secure sharding blockchain consensus achieving optimized overhead. In particular, we propose a new secure sharding blockchain consensus pattern, based on a buffer managed jointly by shard members. Valid transactions are transferred to the payee via the buffer, while invalid ones are rejected through happy or unhappy paths. Kronos is proved to achieve security with atomicity under malicious clients while maintaining optimal intra-shard overhead. Efficient rejection even requires no Byzantine fault tolerance (BFT) protocol execution in happy paths, and the cost in unhappy paths is still not higher than a two-phase commit. Besides, we propose secure cross-shard certification methods. Handling b transactions, Kronos is proved to achieve cross-shard communication with low cross-shard overhead O(n b \lambda) (n for the shard size and \lambda for the security parameter). Notably, Kronos imposes no restrictions on BFT and does not rely on timing assumptions, offering optional constructions in various modules. Kronos could serve as a universal framework for enhancing the performance and scalability of existing BFT protocols. Kronos supports generic models, including asynchronous networks, and can increase the throughput by several orders of magnitude.
We implement Kronos using two prominent BFT protocols: asynchronous Speeding Dumbo (NDSS'22) and partially synchronous Hotstuff (PODC'19). Extensive experiments (over up to 1000 AWS EC2 nodes across 4 AWS regions) demonstrate Kronos scales the consensus nodes to thousands, achieving a substantial throughput of 320 ktx/sec with 2.0 sec latency. Compared with the past solutions, Kronos outperforms, achieving up to a 12$\times$ improvement in throughput and a 50% reduction in latency when cross-shard transactions dominate the workload.

Powerformer: Efficient Privacy-Preserving Transformer with Batch Rectifier-Power Max Function and Optimized Homomorphic Attention

We propose an efficient non-interactive privacy-preserving Transformer inference architecture called Powerformer. Since softmax is a non-algebraic operation, previous studies have attempted to modify it to be HE-friendly, but these methods have encountered issues with accuracy degradation or prolonged execution times due to the use of multiple bootstrappings. We propose replacing softmax with a new ReLU-based function called the \textit{Batch Rectifier-Power max} (BRPmax) function without any unstable approximation methods, which outperforms even original BERT performance within BERT-Large model while requiring fewer levels, allowing it to operate with only a single bootstrapping. We also present a matrix multiplication algorithms specialized for attention block that reduce the number of key-switchings by 35% to 91% compared to existing state-of-the-art methods. We design clear end-to-end HE-based implementation for private Transformer model, and our implementation of Powerformer on the BERT-tiny model using RNS-CKKS takes 503 seconds on a single-threaded CPU, and to the best of our knowledge, this is the first end-to-end non-interactive Transformer implementation using HE.

Mario: Multi-round Multiple-Aggregator Secure Aggregation with Robustness against Malicious Actors

Federated Learning (FL) enables multiple clients to collaboratively train a machine learning model while keeping their data private, eliminating the need for data sharing. Two common approaches to secure aggregation (SA) in FL are the single-aggregator and multiple-aggregator models.
Existing multiple-aggregator protocols such as Prio (NSDI 2017), Prio+ (SCN 2022), Elsa (S\&P 2023) either offer robustness only in the presence of semi-honest servers or provide security without robustness and are limited to two aggregators.
We introduce Mario, the first multi-aggregator SA protocol that is both secure in a malicious setting and provides robustness. Similar to prior work of Prio and Prio+, Mario provides secure aggregation in a setup of $n$ servers and $m$ clients. Unlike previous work, Mario removes the assumption of semi-honest servers, and provides a complete protocol with robustness against less than $n/2$ malicious servers, defense with input validation of upto $m-2$ corrupted clients, and dropout of any number of clients. Our implementation shows that Mario is $3.40\times$ and $283.4\times$ faster than Elsa and Prio+, respecitively.

Code-Based Zero-Knowledge from VOLE-in-the-Head and Their Applications: Simpler, Faster, and Smaller

Zero-Knowledge (ZK) protocols allow a prover to demonstrate the truth of a statement without disclosing additional information about the underlying witness. Code-based cryptography has a long history but did suffer from periods of slow development. Recently, a prominent line of research have been contributing to designing efficient code-based ZK from MPC-in-the-head (Ishai et al., STOC 2007) and VOLE-in-the head (VOLEitH) (Baum et al., Crypto 2023) paradigms, resulting in quite efficient standard signatures. However, none of them could be directly used to construct privacy-preserving cryptographic primitives. Therefore, Stern's protocols remain to be the major technical stepping stones for developing advanced code-based privacy-preserving systems.
This work proposes new code-based ZK protocols from VOLEitH paradigm for various relations and designs several code-based privacy-preserving systems that considerably advance the state-of-the-art in code-based cryptography. Our first contribution is a new ZK protocol for proving the correctness of a regular (non-linear) encoding process, which is utilized in many advanced privacy-preserving systems. Our second contribution are new ZK protocols for concrete code-based relations. In particular, we provide a ZK of accumulated values with optimal witness size for the accumulator (Nguyen et al., Asiacrypt 2019). Our protocols thus open the door for constructing more efficient privacy-preserving systems. Moreover, our ZK protocols have the advantage of being simpler, faster, and smaller compared to Stern-like protocols. To illustrate the effectiveness of our new ZK protocols, we develop ring signature (RS) scheme, group signature (GS) scheme, fully dynamic attribute-based signature scheme from our new ZK. The signature sizes of the resulting schemes are two to three orders of magnitude smaller than those based on Stern-like protocols in various parameter settings. Finally, our first ZK protocol yields a standard signature scheme, achieving ``signature size + public key size'' as small as $3.05$ KB, which is slightly smaller than the state-of-the-art signature scheme (Cui et al., PKC 2024) based on the regular syndrome decoding problems.

LogRobin++: Optimizing Proofs of Disjunctive Statements in VOLE-Based ZK

In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, $\mathcal{P}$ and $\mathcal{V}$ agree on $B$ fan-in $2$ circuits $\mathcal{C}_0, \ldots, \mathcal{C}_{B-1}$ over a field $\mathbb{F}$; each circuit has $n_{\mathit{in}}$ inputs, $n_\times$ multiplications, and one output. $\mathcal{P}$'s goal is to demonstrate the knowledge of a witness $(\mathit{id} \in [B]$, $\boldsymbol{w} \in \mathbb{F}^{n_{\mathit{in}}})$, s.t. $\mathcal{C}_{\mathit{id}}(\boldsymbol{w}) = 0$ where neither $\boldsymbol{w}$ nor $\mathit{id}$ is revealed. Disjunctive statements are effective, for example, in implementing ZKP based on sequential execution of CPU steps.
This paper studies ZKP (of knowledge) protocols over disjunctive statements based on Vector OLE. Denoting by $\lambda$ the statistical security parameter and let $\rho \overset{\Delta}{=} \max\{\log |\mathbb{F}|, \lambda\}$, the previous state-of-the-art protocol $\mathsf{Robin}$ (Yang et al. CCS'23) required $(n_{\mathit{in}}+3n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho B)$ bits of communication with $ \mathcal{O}(1)$ rounds, and $\mathsf{Mac'n'Cheese}$ (Baum et al. CRYPTO'21) required $(n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + 2n_\times\rho + \mathcal{O}(\rho \log B)$ bits of communication with $\mathcal{O}(\log B)$ rounds, both in the VOLE-hybrid model.
Our novel protocol $\mathsf{LogRobin}\texttt{++}$ achieves the same functionality at the cost of $(n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho \log B)$ bits of communication with $\mathcal{O}(1)$ rounds in the VOLE-hybrid model. Crucially, $\mathsf{LogRobin}\texttt{++}$ takes advantage of two new techniques -- (1) an $\mathcal{O}(\log B)$-overhead approach to prove in ZK that an IT-MAC commitment vector contains a zero; and (2) the realization of VOLE-based ZK over a disjunctive statement, where $\mathcal{P}$ commits only to $\boldsymbol{w}$ and multiplication outputs of $\mathcal{C}_{\mathit{id}}(\boldsymbol{w})$ (as opposed to prior work where $\mathcal{P}$ commits to $\boldsymbol{w}$ and all three wires that are associated with each multiplication gate).
We implemented $\mathsf{LogRobin}\texttt{++}$ over Boolean (i.e., $\mathbb{F}_2$) and arithmetic (i.e., $\mathbb{F}_{2^{61}-1}$) fields. In our experiments, including the cost of generating VOLE correlations, $\mathsf{LogRobin}\texttt{++}$ achieved up to $170 \times$ optimization over $\mathsf{Robin}$ in communication, resulting in up to $7\times$ (resp. $3\times$) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.

Agile Asymmetric Cryptography and the Case for Finite Fields

Cryptographic agility, the ability to easily and quickly modify cryptography in a sys- tem, is one of the most important features of any cryptographic system. Any algorithm may be attacked and, at some point in time, be broken. The most obvious solution is to change the cryptographic algorithm, however this has high risk and cost. Another solution is to use agile algorithms. Agile algorithms have security parameters easily changed to increase protection against attacks.
In this paper we will show that finite field based algorithms are the most agile of currently used classical cryptography. A critical portion of this will be to show that the bottleneck for the primary costing attack, the number field sieve, is the linear algebra portion of the attack, and not the sieving portion.
This paper examines the agility of all three algorithm categories and dispels a few myths about their strengths.

New constructions of pseudorandom codes

Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new
cryptographic primitive with applications in watermarking generative AI models.
These are codes where a collection of polynomially many codewords is
computationally indistinguishable from random, except to individuals with the
decoding key. In this work, we examine the assumptions under which PRCs with
robustness to a constant error rate exist.
1. We show that if both the planted hyperloop assumption introduced in
[BKR23] and security of a version of Goldreich's PRG hold, then there exist
public-key PRCs for which no efficient adversary can distinguish a polynomial
number of codewords from random with better than $o(1)$ advantage.
2. We revisit the construction of [CG24] and show that it can be based on a
wider range of assumptions than presented in [CG24]. To do this, we introduce a
weakened version of the planted XOR assumption which we call the weak planted
XOR assumption and which may be of independent interest.
3. We initiate the study of PRCs which are secure against space-bounded
adversaries. We show how to construct secret-key PRCs of length $O(n)$ which
are $\textit{unconditionally}$ indistinguishable from random by
$\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.

Blind Multisignatures for Anonymous Tokens with Decentralized Issuance

We propose the first constructions of anonymous tokens with decentralized issuance. Namely, we consider a dynamic set of signers/issuers; a user can obtain a token from any subset of the signers, which is publicly verifiable and unlinkable to the issuance process. To realize this new primitive we formalize the notion of Blind Multi-Signatures (BMS), which allow a user to interact with multiple signers to obtain a (compact) signature; even if all the signers collude they are unable to link a signature to an interaction with any of them.
We then present two BMS constructions, one based on BLS signatures and a second based on discrete logarithms without pairings. We prove security of both our constructions in the Algebraic Group Model.
We also provide a proof-of-concept implementation and show that it has low-cost verification, which is the most critical operation in blockchain applications.

Security Bounds for Proof-Carrying Data from Straightline Extractors

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry.
Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses would lead to setting parameters that are prohibitively expensive.
In this work we study the concrete security of recursive composition, with the goal of better understanding how to reasonably set parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK (i.e., recursive composition incurs essentially no security loss).
We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, which results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle (there is no need to instantiated the oracle to carry out the security reduction).
As a notable application, our work offers an idealized model that provides new, albeit heuristic, insights for the concrete security of \emph{recursive STARKs} used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.

A Waterlog for Detecting and Tracing Synthetic Text from Large Language Models

We propose waterlogs, a new direction to detect and trace synthetic text outputs from large language models based on transparency logs. Waterlogs offer major categorical advantages over watermarking: it (1) allows for the inclusion of arbitrary metadata to facilitate tracing, (2) is publicly verifiable by third parties, and (3) operates in a distributed manner while remaining robust and efficient.
Waterlogs rely on a verifiable Hamming distance index, a novel data structure that we describe, to efficiently search multi-dimensional semantic hashes of natural language embeddings in a verifiable manner. This data structure may be of independent interest.
We implement a waterlog, which we call DREDGE, and benchmark it using synthetic text generated by GPT-2 1.5B and OPT-13B; embeddings are generated via OpenAI's text-embedding-ada-002 model. We provide empirical benchmarks on the efficiency of appending text to the log and querying it for matches. We compare our results to watermarking and outline areas for further research.

A Time-Space Tradeoff for the Sumcheck Prover

The sumcheck protocol is an interactive protocol for verifying the sum of a low-degree polynomial over a hypercube. This protocol is widely used in practice, where an efficient implementation of the (honest) prover algorithm is paramount. Prior work contributes highly-efficient prover algorithms for the notable special case of multilinear polynomials (and related settings). [CTY11] presents two algorithms, the first of which uses logarithmic space but runs in superlinear time; the latter runs in linear time but uses linear space.
In this short note, we present a family of prover algorithms for the multilinear sumcheck protocol that offer new time-space tradeoffs. In particular, we recover the aforementioned algorithms as special cases.
Moreover, we provide an efficient implementation of the new algorithms, and our experiments show that the asymptotics translate into new concrete efficiency tradeoffs

Cryptanalysis of the Peregrine Lattice-Based Signature Scheme

The Peregrine signature scheme is one of the candidates in the ongoing Korean post-quantum cryptography competition. It is proposed as a high-speed variant of Falcon, which is a hash-and-sign signature scheme over NTRU lattices and one of the schemes selected by NIST for standardization. To this end, Peregrine replaces the lattice Gaussian sampler in the Falcon signing procedure with a new sampler based on the centered binomial distribution. While this modification offers significant advantages in terms of efficiency and implementation, it does not come with a provable guarantee that signatures do not leak information about the signing key. Unfortunately, lattice based signature schemes in the hash-and-sign paradigm that lack such a guarantee (such as GGH, NTRUSign or DRS) have generally proved insecure.
In this paper, we show that Peregrine is no exception, by demonstrating a practical key recovery attack against it. We observe that the distribution of Peregrine signatures is a hidden transformation of some public distribution and still leaks information about the signing key. By adapting the parallelepiped-learning technique of Nguyen and Regev (Eurocrypt 2006), we show that the signing key can be recovered from a relatively small number of signatures. The learning technique alone yields an approximate version of the key, from which we can recover the exact key using a decoding technique due to Thomas Prest (PKC 2023).
For the reference implementation (resp. the official specification version) of Peregrine-512, we fully recover the secret key with good probability in a few hours given around 25,000 (resp. 11 million) signature samples.

Blockchain-based decentralized identity system: Design and security analysis

This paper presents a novel blockchain-based decentralized identity system (DID), tailored for enhanced digital identity management in Internet of Things (IoT) and device-to-device (D2D) networks. The proposed system features a hierarchical structure that effectively merges a distributed ledger with a mobile D2D network, ensuring robust security while streamlining communication. Central to this design are the gateway nodes, which serve as intermediaries, facilitating DID registration and device authentication through smart contracts and distributed storage systems. A thorough security analysis underscores the system’s resilience to common cyber threats and adherence to critical principles like finality and liveness.

Towards package opening detection at power-up by monitoring thermal dissipation

Among the various threats to secure ICs, many are semi-invasive in the sense that their application requires the removal of the package to gain access to either the front or back of the target IC. Despite this stringent application requirements, little attention is paid to embedded techniques aiming at checking the package's integrity. This paper explores the feasibility of verifying the package integrity of microcontrollers by examining their thermal dissipation capability.

ZKFault: Fault attack analysis on zero-knowledge based post-quantum digital signature schemes

Computationally hard problems based on coding theory, such as the syndrome decoding problem, have been used for constructing secure cryptographic schemes for a long time. Schemes based on these problems are also assumed to be secure against quantum computers. However, these schemes are often considered impractical for real-world deployment due to large key sizes and inefficient computation time. In the recent call for standardization of additional post-quantum digital signatures by the National Institute of Standards and Technology, several code-based candidates have been proposed, including LESS, CROSS, and MEDS. These schemes are designed on the relatively new zero-knowledge framework. Although several works analyze the hardness of these schemes, there is hardly any work that examines the security of these schemes in the presence of physical attacks.
In this work, we analyze these signature schemes from the perspective of fault attacks. All these schemes use a similar tree-based construction to compress the signature size. We attack this component of these schemes. Therefore, our attack is applicable to all of these schemes. In this work, we first analyze the LESS signature scheme and devise our attack. Furthermore, we showed how this attack can be extended to the CROSS signature scheme. Our attacks are built on very simple fault assumptions. Our results show that we can recover the entire secret key of LESS and CROSS using as little as a single fault. Finally, we propose various countermeasures to prevent these kinds of attacks and discuss their efficiency and shortcomings.

Privacy-Preserving Breadth-First-Search and Maximal-Flow

We present novel Secure Multi-Party Computation (SMPC) protocols to perform Breadth-First-Searches (BFSs) and determine maximal flows on dense secret-shared graphs. In particular, we introduce a novel BFS protocol that requires only $\mathcal{O}(\log n)$ communication rounds on graphs with $n$ nodes, which is a big step from prior work that requires $\mathcal{O}(n \log n)$ rounds. This BFS protocol is then used in a maximal flow protocol based on the Edmonds-Karp algorithm, which requires $\mathcal{O}(n^3 \log n)$ rounds. We further optimize the protocol for cases where an upper bound $U$ on the capacities is publicly known by using a capacity scaling approach. This yields a new protocol which requires $\mathcal{O}(n^2 \log n \log U)$ rounds. Finally, we introduce a novel max flow protocol based on algorithms by Dinic and Tarjan with round complexity $\mathcal{O}(n^3)$.
All protocols presented in this paper use SMPC primitives as a black-box, allowing our protocols to be used as building blocks in a wide range of settings and applications. We evaluate our protocols with semi-honest and malicious security in different network settings. Our logarithmic BFS protocol is up to 69 times faster than prior protocols on small graphs with less than 100 nodes, but is outperformed by protocols with lower computational complexity on graphs with thousands of nodes. Further, we find our Dinic-Tarjan protocol to be faster than the Edmonds-Karp and capacity scaling protocols in our evaluation, albeit trends indicating capacity scaling protocols to be faster on graph sizes not reached in our evaluation.

On the Relationship between Public Key Primitives via Indifferentiability

Recently, Masny and Rindal [MR19] formalized a notion called Endemic Oblivious Transfer (EOT), and they proposed a generic transformation from Non-Interactive Key Exchange (NIKE) to EOT with standalone security in the random oracle (RO) model. However, from the model level, the relationship between idealized NIKE and idealized EOT and the relationship between idealized elementary public key primitives have been rarely researched.
In this work, we investigate the relationship between ideal NIKE and ideal one-round EOT, as well as the relationship between ideal public key encryption (PKE) and ideal two-round Oblivious Transfer (OT), in the indifferentiability framework proposed by Maurer et al.(MRH04). Our results are threefold: Firstly, we model ideal PKE without public key validity test, ideal one-round EOT and ideal two-round OT in the indifferentiability framework. Secondly, we show that ideal NIKE and ideal one-round EOT are equivalent, and ideal PKE without public key validity test are equivalent to ideal two-round OT. Thirdly, we show a separation between ideal two-round OT and ideal one-round EOT, which implies a separation between ideal PKE and ideal NIKE.

Public-key encryption from a trapdoor one-way embedding of $SL_2(\mathbb{N})$

We obfuscate words of a given length in a free monoid on two generators with a simple factorization algorithm (namely $SL_2(\mathbb{N})$) to create a public-key encryption scheme. We provide a reference implementation in Python and suggested parameters. The security analysis is between weak and non-existent, left to future work.

Distributed Broadcast Encryption from Lattices

A broadcast encryption scheme allows a user to encrypt a message to $N$ recipients with a ciphertext whose size scales sublinearly with $N$. While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup process that generates a set of public parameters. Thereafter, users can independently generate their own public keys and post them to a public-key directory. Moreover, anyone can broadcast an encrypted message to any subset of user public keys with a ciphertext whose size scales sublinearly with the size of the broadcast set. Unlike traditional broadcast encryption, there are no long-term secrets in distributed broadcast encryption and users can join the system at any time (by posting their public key to the public-key directory).
Previously, distributed broadcast encryption schemes were known from standard pairing-based assumptions or from powerful tools like indistinguishability obfuscation or witness encryption. In this work, we provide the first distributed broadcast encryption scheme from a falsifiable lattice assumption. Specifically, we rely on the $\ell$-succinct learning with errors (LWE) assumption introduced by Wee (CRYPTO 2024). Previously, the only lattice-based candidate for distributed broadcast encryption goes through general-purpose witness encryption, which in turn is only known from the /private-coin/ evasive LWE assumption, a strong and non-falsifiable lattice assumption. Along the way, we also describe a more direct construction of broadcast encryption from lattices.

Unforgeability of Blind Schnorr in the Limited Concurrency Setting

Blind signature schemes enable a user to obtain a digital signature on a message from a signer without revealing the message itself. Among the most fundamental examples of such a scheme is blind Schnorr, but recent results show that it does not satisfy the standard notion of security against malicious users, One-More Unforgeability (OMUF), as it is vulnerable to the ROS attack. However, blind Schnorr does satisfy the weaker notion of sequential OMUF, in which only one signing session is open at a time, in the Algebraic Group Model (AGM) + Random Oracle Model (ROM), assuming the hardness of the Discrete Logarithm (DL) problem.
This paper serves as a first step towards characterizing the security of blind Schnorr in the limited concurrency setting. Specifically, we show that blind Schnorr satisfies OMUF when at most two signing sessions can be concurrently open (in the AGM+ROM, assuming DL). Our argument suggests that it is plausible that blind Schnorr satisfies OMUF for up to polylogarithmically many concurrent signing sessions. Our security proof involves interesting techniques from linear algebra and combinatorics.

Circuit ABE with poly(depth, λ)-sized Ciphertexts and Keys from Lattices

We present new lattice-based attribute-based encryption (ABE) and
laconic function evaluation (LFE) schemes for circuits with *sublinear*
ciphertext overhead. For depth $d$ circuits over $\ell$-bit inputs, we obtain
* an ABE with ciphertext and secret key size $O(1)$;
* a LFE with ciphertext size $\ell + O(1)$ and digest size $O(1)$;
* an ABE with public key and ciphertext size $O(\ell^{2/3})$ and
secret key size $O(1)$,
where $O(\cdot)$ hides $\mbox{poly}(d,\lambda)$ factors. The first two results achieve almost optimal ciphertext and secret key / digest sizes, up to the $\mbox{poly}(d)$ dependencies. The security of our schemes relies on $\ell$-succinct LWE, a falsifiable assumption which is implied by evasive LWE. At the core of our results is a new technique for compressing LWE samples $\mathbf{s}(\mathbf{A}-\mathbf{x} \otimes \mathbf{G})$ as well as the matrix $\mathbf{A}$.

PIGEON: A Framework for Private Inference of Neural Networks

Privacy-Preserving Machine Learning is one of the most relevant use cases for Secure Multiparty Computation (MPC). While private training of large neural networks such as VGG-16 or ResNet-50 on state-of-the-art datasets such as Imagenet is still out of reach, given the performance overhead of MPC, private inference is starting to achieve practical runtimes. However, we show that in contrast to plaintext machine learning, the usage of GPU acceleration for both linear and nonlinear neural network layers is actually counterproductive in PPML and leads to performance and scaling penalties. This can be observed by slow ReLU performance, high GPU memory requirements, and inefficient batch processing in state-of-the-art PPML frameworks, which hinders them from scaling to multiple images per second inference throughput and more than eight images per batch on ImageNet.
To overcome these limitations, we propose PIGEON, an open-source framework for Private Inference of Neural Networks. PIGEON utilizes a novel ABG programming model that switches between \underline{A}rithmetic vectorization, \underline{B}itslicing, and \underline{G}PU offloading depending on the MPC-specific computation required by each layer.
Compared to the state-of-the-art PPML framework Piranha, PIGEON achieves two orders of magnitude improvements in ReLU throughput, reduces peak GPU memory utilization by one order of magnitude, and scales better with large batch size. This translates to one to two orders of magnitude improvements in throughput for large ImageNet batch sizes (e.g. 192) and more than 70\% saturation of a 25 Gbit/s network.

Privacy Comparison for Bitcoin Light Client Implementations

Light clients implement a simple solution for Bitcoin's scalability problem, as they do not store the entire blockchain but only the state of particular addresses of interest. To be able to keep track of the updated state of their addresses, light clients rely on full nodes to provide them with the required information. To do so, they must reveal information about the addresses they are interested in. This paper studies the two most common light client implementations, SPV and Neutrino with regards to their privacy. We define privacy metrics for comparing the privacy of the different implementations. We evaluate and compare the privacy of the implementations over time on real Bitcoin data and discuss the inherent privacy-communication tradeoff. In addition, we propose general techniques to enhance light client privacy in the existing implementations. Finally, we propose a new SPV-based light client model, the aggregation model, evaluate it, and show it can achieve enhanced privacy than in the existing light client implementations.

Private Eyes: Zero-Leakage Iris Searchable Encryption

This work introduces Private Eyes, the first zero-leakage biometric database. The only leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from symmetric searchable encryption. Approximate proximity queries are used: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric.
Private Eyes combines locality sensitive-hashing or LSHs (Indyk and Motwani, STOC 1998) and oblivious maps. One computes many LSHs of each record in the database, and uses these hashes as keys in an encrypted map with the matching biometric readings concatenated as the value. At search time with a noisy reading, one computes the LSHs, and retrieves the disjunction of the resulting values from the map. The underlying encrypted map needs to efficiently answer disjunction queries.
We focus on the iris biometric which requires a large number of LSHs, approximately $1000$. Boldyreva and Tang's (PoPETS 2021) design yields a suitable map for a small number of LSHs (their application was in zero-leakage $k$-nearest-neighbor search).
Our solution is a zero-leakage disjunctive map designed for the setting when most clauses do not match any records. For the iris, on average at most $6\%$ of LSHs match any stored value. Our scheme is implemented and open-sourced.
We evaluate using the ND-0405 dataset; this dataset has $356$ irises suitable for testing. To scale our evaluation, we use a generative adversarial network to produce synthetic irises. Accurate statistics on sizes beyond available datasets is crucial to optimizing the cryptographic primitives. This tool may be of independent interest. For the largest tested parameters of a $5000$ iris database, search requires $26$ rounds of communication and $26$ minutes of single-threaded computation.

Reducing the Number of Qubits in Quantum Information Set Decoding

This paper presents an optimization of the memory cost of the quantum Information Set Decoding (ISD) algorithm proposed by Bernstein (PQCrypto 2010), obtained by combining Prange's ISD with Grover's quantum search.
When the code has constant rate and length $n$, this algorithm essentially performs a quantum search which, at each iteration, solves a linear system of dimension $\mathcal{O}(n)$. The typical code lengths used in post-quantum public-key cryptosystems range from $10^3$ to $10^5$. Gaussian elimination, which was used in previous works, needs $\mathcal{O}(n^2)$ space to represent the matrix, resulting in millions or billions of (logical) qubits for these schemes.
In this paper, we propose instead to use the algorithm for sparse matrix inversion of Wiedemann (IEEE Trans. inf. theory 1986). The interest of Wiedemann's method is that one relies only on the implementation of a matrix-vector product, where the matrix can be represented in an implicit way. This is the case here.
We give two main trade-offs, which we have fully implemented, tested on small instances, and benchmarked for larger instances. The first one is a quantum circuit using $\mathcal{O}(n)$ qubits, $\mathcal{O}(n^3)$ Toffoli gates like Gaussian elimination, and depth $\mathcal{O}(n^2 \log n)$. The second one is a quantum circuit using $\mathcal{O}(n \log^2 n)$ qubits, $\mathcal{O}(n^3)$ gates in total but only $\mathcal{O}( n^2 \log^2 n)$ Toffoli gates, which relies on a different representation of the search space.
As an example, for the smallest Classic McEliece parameters we estimate that the Quantum Prange's algorithm can run with 18098 qubits, while previous works would have required at least half a million qubits.

Collision Resistance from Multi-Collision Resistance for all Constant Parameters

A $t$-multi-collision-resistant hash function ($t$-MCRH) is a family of shrinking functions for which it is computationally hard to find $t$ distinct inputs mapping to the same output for a function sampled from this family. Several works have shown that $t$-MCRHs are sufficient for many of the applications of collision-resistant hash functions (CRHs), which correspond to the special case of $t = 2$.
An important question is hence whether $t$-MCRHs for $t > 2$ are fundamentally weaker objects than CRHs. As a first step towards resolving this question, Rothblum and Vasudevan (CRYPTO '22) recently gave non-black-box constructions of infinitely-often secure CRHs from $t$-MCRHs for $t \in \{3,4\}$ assuming the MCRH is sufficiently shrinking. Earlier on, Komargodski and Yogev (CRYPTO '18) also showed that $t$-MCRHs for any constant $t$ imply the weaker notion of a distributional CRH.
In this paper, we remove the limitations of prior works, and completely resolve the question of the power of $t$-MCRHs for constant $t$ in the infinitely-often regime, showing that the existence of such a function family always implies the existence of an infinitely-often secure CRH. As in the works mentioned above, our construction is non-blackbox and non-constructive. We further give a new domain extension result for MCRHs that enables us to show that the underlying MCRH need only have arbitrarily small linear shrinkage (mapping $(1 + \epsilon)n$ bits to $n$ bits for any fixed $\epsilon > 0$) to imply the existence of CRHs.

Expanding the Toolbox: Coercion and Vote-Selling at Vote-Casting Revisited

Coercion is a challenging and multi-faceted threat that prevents people from expressing their will freely. Similarly, vote-buying does to undermine the foundation of free democratic elections. These threats are especially dire for remote electronic voting, which relies on voters to express their political will freely but happens in an uncontrolled environment outside the polling station and the protection of the ballot booth. However, electronic voting in general, both in-booth and remote, faces a major challenge, namely to ensure that voters can verify that their intent is captured correctly without providing a receipt of the cast vote to the coercer or vote buyer.
Even though there are known techniques to resist or partially mitigate coercion and vote-buying, we explicitly demonstrate that they generally underestimate the power of malicious actors by not accounting for current technological tools that could support coercion and vote-selling.
In this paper, we give several examples of how a coercer can force voters to comply with his demands or how voters can prove how they voted. To do so, we use tools like blockchains, delay encryption, privacy-preserving smart contracts, or trusted hardware. Since some of the successful coercion attacks occur on voting schemes that were supposed/claimed/proven to be coercion-resistant or receipt-free, the main conclusion of this work is that the coercion models should be re-evaluated, and new definitions of coercion and receipt-freeness are necessary. We propose such new definitions as part of this paper and investigate their implications.

Ultrametric integral cryptanalysis

A systematic method to analyze divisibility properties is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis.
The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.

Haze and Daze: Compliant Privacy Mixers

Blockchains enable mutually distrustful parties to perform financial operations in a trustless, decentralized, publicly-verifiable environment. Blockchains typically offer little privacy, and thus motivated the construction of privacy mixers, a solution to make funds untraceable. Privacy mixers concern regulators due to their increasing use by bad actors to illegally conceal the origin of funds. Consequently, Tornado Cash, the largest privacy mixer to date, is sanctioned by large portions of the Ethereum network.
In this work, we propose Haze and Daze, two privacy mixers that mitigate the undesired abuse of privacy mixers for illicit activities. Haze guarantees users’ privacy together with compliance, i.e., funds can be withdrawn as long as they were deposited from a non-banned address, without revealing any information on the matching deposit. This means that once a user is flagged as non-compliant, their funds can no longer exit the mixer. However, this leads to a race condition for bad actors to withdraw funds before becoming flagged as unlawful in the banned-addresses list. Thus, we introduce Daze, a second mixer protocol that, in addition to compliance, enables retroactive de-anonymization of transactions of non-compliant users, making the mixer fruitless for them. To maintain privacy of compliant users, the de-anonymization procedure is performed by a committee, with privacy guaranteed as long as at least one of the committee members is honest. Moreover, Haze and Daze have an optional feature for non-compliant funds to be released from the mixer to some predetermined entity.
We empirically evaluate our solution in a proof-of-concept system, demonstrating gas consumption for each deposit and withdrawal that is comparable to Tornado Cash for compliant users, both for Haze and Daze. To the best of our knowledge, our solution is the first to guarantee compliance and privacy on the blockchain (on-chain) that is implemented via a smart contract.

The Black-Box Simulation Barrier Persists in a Fully Quantum World

Zero-Knowledge (ZK) protocols have been a subject of intensive study due to their fundamental importance and versatility in modern cryptography. However, the inherently different nature of quantum information significantly alters the landscape, necessitating a re-examination of ZK designs.
A crucial aspect of ZK protocols is their round complexity, intricately linked to $\textit{simulation}$, which forms the foundation of their formal definition and security proofs. In the $\textit{post-quantum}$ setting, where honest parties and their communication channels are all classical but the adversaries could be quantum, Chia, Chung, Liu, and Yamakawa [FOCS'21] demonstrated the non-existence of constant-round $\textit{black-box-simulatable}$ ZK arguments (BBZK) for $\mathbf{NP}$ unless $\mathbf{NP} \subseteq \mathbf{BQP}$. However, this problem remains widely open in the full-fledged quantum future that will eventually arrive, where all parties (including the honest ones) and their communication are naturally quantum.
Indeed, this problem is of interest to the broader theory of quantum computing. It has been an important theme to investigate how quantum power fundamentally alters traditional computational tasks, such as the $\textit{unconditional}$ security of Quantum Key Distribution and the incorporation of Oblivious Transfers in MiniQCrypt. Moreover, quantum communication has led to round compression for commitments and interactive arguments. Along this line, the above problem is of great significance in understanding whether quantum computing could also change the nature of ZK protocols in some fundamentally manner.
We resolved this problem by proving that only languages in $\mathbf{BQP}$ admit constant-round $\textit{fully-quantum}$ BBZK. This result holds significant implications. Firstly, it illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm. Secondly, it relates ZK round complexity with the intriguing problem of $\mathbf{BQP}$ vs $\mathbf{QMA}$, which is out of the reach of previous analogue impossibility results in the classical or post-quantum setting. Lastly, it justifies the need for the $\textit{non-black-box}$ simulation techniques or the relaxed security notions employed in existing constant-round fully-quantum BBZK protocols.

The Zeros of Zeta Function Revisited

Let $\zeta(z)=\sum_{n=1}^{\infty} \frac{1}{n^z}$, $\psi(z)=\sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n^z}, z\in \mathbb{C}$. We show that $\psi(z)\not=(1-2^{1-z})\zeta(z)$, if $0<z<1$. Besides, we clarify that the known zeros are not for the original series, but very probably for the alternating series.

Design issues of ``an anonymous authentication and key agreement protocol in smart living''

The Li et al.'s scheme [Computer Communications, 186 (2022), 110-120)] uses XOR operation to realize the private transmission of sensitive information, under the assumption that if only one parameter in the expression $ a= b\oplus c $ is known, an adversary cannot retrieve the other two. The assumption neglects that the operands $b$ and $c$ must be of the same bit-length, which leads to the exposure of a substring in the longer operand. The scheme wrongly treats timestamps as random strings to encrypt a confidential parameter. These misuses result in the loss of sensor node's anonymity, the loss of user anonymity and untraceability, insecurity against off-line password guessing attack, and insecurity against impersonation attack. The analysis techniques developed in this note is helpful for the future works on designing such schemes.

Cryptobazaar: Private Sealed-bid Auctions at Scale

This work introduces Cryptobazaar, a novel scalable, private, and decentralized sealed-bid auction protocol. In particular, our protocol protects the privacy of losing bidders by preserving the confidentiality of their bids while ensuring public verifiability of the outcome and relying only on a single untrusted auctioneer for coordination. At its core, Cryptobazaar combines an efficient distributed protocol to compute the logical-OR for a list of unary-encoded bids with various novel zero-knowledge succinct arguments of knowledge that may be of independent interest. We further present variants of our protocol that can be used for efficient first-, second-, and more generally $(p+1)$st-price as well as sequential first-price auctions. Finally, the performance evaluation of our Cryptobazaar implementation shows that it is highly practical. For example, a single run of an auction with $128$ bidders and a price range of $1024$ values terminates in less than $0.5$ sec and requires each bidder to send and receive only about $32$ KB of data.

Oraqle: A Depth-Aware Secure Computation Compiler

In the past decade, tens of homomorphic encryption compilers have been released, and there are good reasons for these compilers to exist. Firstly, homomorphic encryption is a powerful secure computation technique in that it is relatively easy for parties to switch from plaintext computation to secure computations when compared to techniques like secret sharing. However, the technique is mathematically involved and requires expert knowledge to express computations as homomorphic encryption operations. So, these compilers support users who might otherwise not have the time or expertise to optimize the computation manually. Another reason is that homomorphic encryption is still computationally expensive, so compilers allow users to optimize their secure computation tasks.
One major shortcoming of these compilers is that they often do not allow users to use high-level primitives, such as equality checks, comparisons, and AND and OR operations between many operands. The compilers that do are either based on TFHE, requiring large bootstrapping keys that must be sent to the evaluator, or they only work in the Boolean domain, excluding many potentially more performant circuits.
Moreover, compilers must reduce the multiplicative depth of the circuits they generate to minimize the noise growth inherent to these homomorphic encryption schemes. However, many compilers only consider reducing the depth as an afterthought.
We propose the Oraqle compiler, which solves both problems at once by implementing depth-aware arithmetization, a technique for expressing high-level primitives as arithmetic operations that are executable by homomorphic encryption libraries. Instead of generating one possible circuit, the compiler generates multiple circuits that trade off the number of multiplications with the multiplicative depth. If the depth of the resulting circuits is low enough, they may be evaluated using a BFV or BGV library that does not require bootstrapping keys. We demonstrate that our compiler allows for significant performance gains.

SQIsign2D-East: A New Signature Scheme Using 2-dimensional Isogenies

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition. SQIsign has attracted much attention because of its very short signature and key size among the candidates for the NIST PQC standardization. Recently, a lot of new schemes have been proposed that use high-dimensional isogenies. Among them, the signature scheme called SQIsignHD has an even shorter signature size than SQIsign. However, it requires 4-dimensional isogeny computations for the signature verification.
In this paper, we propose a new signature scheme, SQIsign2D-East, which requires only two-dimensional isogeny computations for verification, thus reducing the computational cost of verification. First, we generalized an algorithm called RandIsogImg, which computes a random isogeny of non-smooth degree. Then, by using this generalized RandIsogImg, we construct a new signature scheme SQIsign2D-East.

BackMon: IC Backside Tamper Detection using On-Chip Impedance Monitoring

The expansion of flip-chip technologies and a lack of backside protection make the integrated circuit (IC) vulnerable to certain classes of physical attacks mounted from the IC's backside. Laser-assisted probing, electromagnetic, and body-biasing injection attacks are examples of such attacks. Unfortunately, there are few countermeasures proposed in the literature, and none are available commercially. Those that do exist are not only expensive but also incompatible with current IC manufacturing processes. They also cannot be integrated into legacy systems, such as field programmable gate arrays (FPGAs), which are integral parts of many industrial and defense systems. In this paper, we demonstrate how the impedance monitoring of the printed circuit board (PCB) and IC package's power distribution network (PDN) using on-chip circuit-based network analyzers can detect IC backside tampering. Our method is based on the fact that any attempt to expose the backside silicon substrate, such as the removal of the fan and heatsinks, leads to changes in the equivalent impedance of the package's PDN, and hence, scanning the package impedance will reveal if the package integrity has been violated. To validate our claims, we deploy an on-FPGA network analyzer on an AMD Zynq UltraScale+ MPSoC manufactured with 16 nm technology, which is part of a multi-PCB system. We conduct a series of experiments at different temperatures, leveraging the difference of means as the statistical metric, to demonstrate the effectiveness of our method in detecting tamper events required to expose the IC backside silicon.

Multiple-Tweak Differential Attack Against SCARF

In this paper, we present the first third-party cryptanalysis of SCARF, a tweakable low-latency block cipher designed to thwart contention-based cache attacks through cache randomization. We focus on multiple-tweak differential attacks, exploiting biases across multiple tweaks. We establish a theoretical framework explaining biases for any number of rounds and verify this framework experimentally. Then, we use these properties to develop a key recovery attack on 7-round SCARF with a time complexity of \(2^{76}\), achieving a 98.9% success rate in recovering the 240-bit secret key. Additionally, we introduce a distinguishing attack on the full 8-round SCARF in a multi-key setting, with a complexity of \(c \times 2^{67.55}\), demonstrating that SCARF does not provide 80-bit security under these conditions. We also explore whether our approach could be extended to the single-key model and discuss the implications of different S-box choices on the attack success.

Practical Two-party Computational Differential Privacy with Active Security

In this work we revisit the problem of using general-purpose MPC schemes to emulate the trusted dataholder in differential privacy (DP), to achieve the same accuracy but without the need to trust one single dataholder. In particular, we consider the two-party model where two computational parties (or dataholders), each with their own dataset, wish to compute a canonical DP mechanism on their combined data and to do so with active security. We start by remarking that available definitions of computational DP (CDP) for protocols are somewhat ill-suited for such a use-case, due to them either poorly capturing some strong security guarantees commonly given by general-purpose MPC protocols, or having too strict requirements in the sense that they need significant adjustment in order to be satisfiable by using common DP and MPC techniques. With this in mind, we propose a new version of simulation-based CDP, called SIM$^*$-CDP, and prove it to be stronger than the IND-CDP and SIM-CDP and incomparable to SIM$^+$-CDP. We demonstrate the usability of the SIM$^*$-CDP definition by showing how to satisfy it by the use of an available distributed protocol for sampling truncated geometric noise. Further, we use the protocol to compute two-party inner-products with CDP and active security, and with accuracy equal to that of the central model, being the first to do so. Finally, we provide an open-sourced implementation and benchmark its practical performance. Our implementation generates a truncated geometric sample in between about 0.035 and 3.5 seconds (amortized), depending on network and parameter settings, comparing favourably to existing implementations.

Toward Full $n$-bit Security and Nonce Misuse Resistance of Block Cipher-based MACs

In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool, namely extended Mirror theory based on two independent permutations to a wide range of $\xi_{\max}$ including inequalities. We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.

Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHE

We propose time-memory trade-off algorithms for evaluating look-up table (LUT) in both the leveled homomorphic encryption (LHE) and fully homomorphic encryption (FHE) modes in TFHE. For an arbitrary $n$-bit Boolean function, we reduce evaluation time by a factor of $O(n)$ at the expense of an additional memory of "only" $O(2^n)$ as a trade-off: The total asymptotic memory is also $O(2^n)$, which is the same as that of prior works. Our empirical results demonstrate that a $7.8 \times$ speedup in runtime is obtained with a $3.8 \times$ increase in memory usage for 16-bit Boolean functions in the LHE mode. Additionally, in the FHE mode, we achieve reductions in both runtime and memory usage by factors of $17.9 \times$ and $2.5 \times $, respectively, for 8-bit Boolean functions. The core idea is to decompose the function $f$ into sufficiently small subfunctions and leverage the precomputed results for these subfunctions, thereby achieving significant performance improvements at the cost of additional memory.

Encrypted MultiChannel Communication (EMC2): Johnny Should Use Secret Sharing

Nowadays, the problem of point-to-point encryption is solved by the wide adaptation of protocols like TLS. However, challenges persist for End-to-End Encryption (E2EE). Current E2EE solutions, such as PGP and secure messengers like Signal, suffer from issues like 1) low usability, 2) small user base, 3) dependence on central service providers, and 4) susceptibility to backdoors. Concerns over legally mandated backdoors are rising as the US and EU are proposing new surveillance regulations requiring chat monitoring. We present a new E2EE solution called Encrypted MultiChannel Communication, based on n-out-of-n secret sharing. EMC2 splits messages into multiple secret shares and sends them through independent channels. We show that multiple independent channels exist between users and EMC2 provides E2EE with no single point of trust, no setup, and is understandable by the general public. Our solution complements existing tools and aims to strengthen the argument against legally enforced backdoors by demonstrating their ineffectiveness.

Lego-DLC: batching module for commit-carrying SNARK under Pedersen Engines

The synergy of commitments and zk-SNARKs is
widely used in various applications, particularly in fields like
blockchain, to ensure data privacy and integrity without revealing
secret information. However, proving multiple commitments in
a batch imposes a large overhead on a zk-SNARK system. One
solution to alleviate the burden is the use of commit-and-prove
SNARK (CP-SNARK) approach. LegoSNARK defines a new
notion called commit-carrying SNARK (cc-SNARK), a special-
ized form of CP-SNARK, and introduces a compiler to build
commit-carrying SNARKs into commit-and-prove SNARKs. Us-
ing this compiler, the paper shows a commit-and-prove version
of Groth16 that improves the proving time (about 5,000×).
However, proving $l$-multiple commitments simultaneously with
this compiler faces a performance issue, as the linking system in
LegoSNARK requires $O(l)$ pairings on the verifier side.
To enhance efficiency, we propose a new batching module
called Lego-DLC, designed for handling multiple commitments. This
module is built by combining a $\Sigma$-protocol with commitment-
carrying SNARKs under Pedersen engines in which our mod-
ule can support all commit-carrying SNARKs under Pedersen
engines. In this paper, we provide the concrete instantiations
for Groth16 and Plonk. In the performance comparison, for
$2^{16}$ commitments, with a verification time of just 0.064s—over
30x faster than LegoSNARK’s 1.972s—our approach shows
remarkable efficiency. The slightly longer prover time of 1.413s
(compared to LegoSNARK’s 0.177s), around 8x is a small trade-
off for this performance gain.

$\Pi$-signHD: A New Structure for the SQIsign Family with Flexible Applicability

Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes.
In this paper, we propose a new structure for the SQIsign family: Pentagon Isogeny-based Signature in High Dimension (referred to as $\Pi$-signHD).
The new structure separates the hash of the commitment and that of the message by employing two cryptographic hash functions. This feature is desirable in reality, particularly for applications based on mobile low-power devices or for those deployed interactively over the Internet or in the cloud computing setting. This structure can be generally applicable to all the variants of SQIsign. In this work, we focus on the instance based on SQIsignHD, proposed by Dartois, Leroux, Robert and Wesolowski (Eurocrypt 2024). Compared with SQIsignHD, $\Pi$-signHD has the same signature size (even smaller for some application scenarios). For the NIST-I security level, the signature size of $\Pi$-signHD can be reduced to 519 bits, while the SQIsignHD signature takes 870 bits. Additionally, $\Pi$-signHD has an efficient online signing process, and enjoys much desirable application flexibility. In our experiments, the online signing process of $\Pi$-signHD runs in 4 ms.

Hard-Label Cryptanalytic Extraction of Neural Network Models

The machine learning problem of extracting neural network parameters has been proposed for nearly three decades. Functionally equivalent extraction is a crucial goal for research on this problem. When the adversary has access to the raw output of neural networks, various attacks, including those presented at CRYPTO 2020 and EUROCRYPT 2024, have successfully achieved this goal. However, this goal is not achieved when neural networks operate under a hard-label setting where the raw output is inaccessible.
In this paper, we propose the first attack that theoretically achieves functionally equivalent extraction under the hard-label setting, which applies to ReLU neural networks. The effectiveness of our attack is validated through practical experiments on a wide range of ReLU neural networks, including neural networks trained on two real benchmarking datasets (MNIST, CIFAR10) widely used in computer vision. For a neural network consisting of $10^5$ parameters, our attack only requires several hours on a single core.

Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions

Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of multi-party private set union (MPSU) protocols: The first category builds on public-key techniques, where existing works require a super-linear number of public-key operations, resulting in their poor practical efficiency. The second category builds on oblivious transfer and symmetric-key techniques. The only work in this category, proposed by Liu and Gao (ASIACRYPT 2023), features the best concrete performance among all existing protocols, but still has super-linear computation and communication. Moreover, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice.
There remain two significant open problems so far: no MPSU protocol achieves semi-honest security based on oblivious transfer and symmetric-key techniques, and no MPSU protocol achieves both linear computation and linear communication complexity. In this work, we resolve both of them.
- We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $3.9-10.0 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $2^{20}$ items each.
- We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao.
We implement our protocols and conduct an extensive experiment to compare the performance of our protocols and the state-of-the-art. To the best of our knowledge, our code is the first correct and secure implementation of MPSU that reports on large-size experiments.

Authentica: A Secure Authentication Mechanism using a Software-defined Unclonable Function

Password-based authentication is an extensively used method to authenticate users. It uses cryptography to communicate the authentication process. On the contrary, the physically unclonable function (PUF)-based authentication mechanism is also gaining popularity rapidly due to its usability in IoT devices. It is a lightweight authentication mechanism that does not use cryptography protocol. PUF-based authentication mechanisms cannot authenticate users. To overcome the drawback of PUF, we introduce a software-defined unclonable function (SUF, for short). Contrary to the PUF, the SUF is used to authenticate users, not devices. We use SUF to implement a lightweight password-based authentication mechanism termed Authentica. Authentica bridges the gap between the password-based and the PUF-based authentication mechanism. Authentica does not use cryptography for authentication. However, we establish challenge-response using cryptography during the registration phase, which is a one-time cost. Authentica addresses a) impersonation attacks, b) collision attacks, c) dictionary and rainbow table attacks, d) replay attacks, e) DDoS attacks, f) the domino effect issues, and g) the challenge-response database leakage issues.

ASOZ: a decentralized payment system with privacy preserving and auditing on public blockchain

Decentralized payment systems have gradually received more attention in recent years. By removing the trusted intermediary used for accounting ledgers, those payment systems fundamentally empower users to control their assets. As privacy concerns grow, some cryptocurrencies are proposed to preserve the privacy of users. However, those cryptocurrencies also inadvertently facilitate illicit activities such as money laundering, fraudulent trading, etc. So it is necessary to design an auditing scheme. To solve this problem, many privacy-preserving and auditing schemes have been proposed. However, there exists no scheme that effectively solves the issue of privacy-preserving and auditing on both user identity and transaction value.
In this paper, we propose a design for a decentralized payment system named ASOZ. We use cryptographic accumulators based on Merkle trees for accounting and use a combination of Twisted ElGamal, Non-Interactive Zero-Knowledge(NIZK), Bulletproofs, and zk-SNARKs for privacy-preserving and auditing. Our scheme achieves full transaction audit in global mixing, while the additional cost introduced remains within an acceptable range, specifically an 8% increment in proof generation time and a 23% rise in verification time. Our scheme is capable of handling large-scale transaction scenarios such as designated contract markets, and offers the strongest privacy protection capabilities in coin mixer schemes.

Improved Circuit Synthesis with Multi-Value Bootstrapping for FHEW-like Schemes

In recent years, the research community has made great progress in improving techniques for privacy-preserving computation, such as fully homomorphic encryption (FHE). Despite the progress, there remain open challenges, mainly in performance and usability, to further advance the adoption of these technologies. This work provides multiple contributions that improve the current state-of-the-art in both areas. More specifically, we significantly simplify the multi-value bootstrapping by Carpov, Izabachène, and Mollimard [CIM19] for Boolean-based FHE schemes such as FHEW or TFHE, making the concept usable in practice. Based on our simplifications, we implement an easy-to-use interface for multi-value bootstrapping in the open-source library FHE-Deck [fhe23], derive new parameter sets for multi-bit encryptions with state-of-the-art security, and build a toolset that translates high-level code to multi-bit operations on encrypted data using circuit synthesis. We propose and integrate the first non-trivial FHE-specific optimizations for privacy-preserving circuit synthesis: look-up table (LUT) grouping and adder substitution. Using LUT grouping, we reduce the number of bootstrapping operations by almost 40% on average, while for adder substitution, we reduce the number of required bootstrappings by up to 85% for certain use cases. Overall, the execution time is up to 4.2x faster with all optimizations enabled compared to previous state-of-the-art circuit synthesis.

Single Instance Self-Masking via Permutations

Self-masking allows the masking of success criteria, part of a problem instance (such as the sum in a subset-sum instance) that restricts the number of solutions. Self-masking is used to prevent the leakage of helpful information to attackers; while keeping the original solution valid and, at the same time, not increasing the number of unplanned solutions.
Self-masking can be achieved by xoring the sums of two (or more) independent subset sum instances \cite{DD20, CDM22}, and by doing so, eliminate all known attacks that use the value of the sum of the subset to find the subset fast, namely, in a polynomial time; much faster than the naive exponential exhaustive search.
We demonstrate that the concept of self-masking can be applied to a single instance of the subset sum and a single instance of the permuted secret-sharing polynomials.
We further introduce the benefit of permuting the bits of the success criteria, avoiding leakage of information on the value of the $i$'th bit of the success criteria, in the case of a single instance, or the parity of the $i$'th bit of the success criteria in the case of several instances.
In the case of several instances, we permute the success criteria bits of each instance prior to xoring them with each other. One basic permutation and its nesting versions (e.g., $\pi^i$) are used, keeping the solution space small and at the same time, attempting to create an ``all or nothing'' effect, where the result of a wrong $\pi$ trials does not imply much.

Self Masking for Hardering Inversions

The question whether one way functions (i.e., functions that are easy to compute but hard to invert) exist is arguably one of the central problems in complexity theory, both from theoretical and practical aspects. While proving that such functions exist could be hard, there were quite a few attempts to provide functions which are one way "in practice", namely, they are easy to compute, but there are no known polynomial time algorithms that compute their (generalized) inverse (or that computing their inverse is as hard as notoriously difficult tasks, like factoring very large integers).
In this paper we study a different approach. We provide a simple heuristic, called self masking, which converts a given polynomial time computable function $f$ into a self masked version $[{f}]$, which satisfies the following: for a random input $x$, $[{f}]^{-1}([{f}](x))=f^{-1}(f(x))$ w.h.p., but a part of $f(x)$, which is essential for computing $f^{-1}(f(x))$ is masked in $[{f}](x)$. Intuitively, this masking makes it hard to convert an efficient algorithm which computes $f^{-1}$ to an efficient algorithm which computes $[{f}]^{-1}$, since the masked parts are available to $f$ but not to $[{f}]$.
We apply this technique on variants of the subset sum problem which were studied in the context of one way functions, and obtain functions which, to the best of our knowledge, cannot be inverted in polynomial time by published techniques.

A Recursive zk-based State Update System

This paper introduces a ZKP (zero-knowledge proof) based state update system, where each block contains a SNARK proof aggregated from the user generated zkVM (zero knowledge virtual machine) proofs. It enables users to generate state update proofs in their local machines, contributing to a secure, decentralized verification process. Our main contribution in this paper, the recursive proofs system, addresses scalability by recursively verifying user proofs and aggregating them in a hierarchical tree structure up to a root proof, serving as a block proof. The proposed solution advances current blockchain paradigms by offering efficient recursive verification through ZKP, enhancing security and reducing computational load.

New Techniques for Preimage Sampling: Improved NIZKs and More from LWE

Recent constructions of vector commitments and non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve the following /shifted multi-preimage sampling problem/: given matrices $\mathbf{A}_1, \ldots, \mathbf{A}_\ell \in \mathbb{Z}_q^{n \times m}$ and targets $\mathbf{t}_1, \ldots, \mathbf{t}_\ell \in \mathbb{Z}_q^n$, sample a shift $\mathbf{c} \in \mathbb{Z}_q^n$ and short preimages $\boldsymbol{\pi}_1, \ldots, \boldsymbol{\pi}_\ell \in \mathbb{Z}_q^m$ such that $\mathbf{A}_i \boldsymbol{\pi}_i = \mathbf{t}_i + \mathbf{c}$ for all $i \in [\ell]$. In this work, we introduce a new technique for sampling $\mathbf{A}_1, \ldots, \mathbf{A}_\ell$ together with a succinct public trapdoor for solving the multi-preimage sampling problem with respect to $\mathbf{A}_1, \ldots, \mathbf{A}_\ell$. This enables the following applications:
* We provide a dual-mode instantiation of the hidden-bits model (and by correspondence, a dual-mode NIZK proof for NP) with (1) a linear-size common reference string (CRS); (2) a transparent setup in hiding mode (which yields statistical NIZK arguments); and (3) hardness from LWE with a polynomial modulus-to-noise ratio. This improves upon the work of Waters (STOC 2024) which required a quadratic-size structured reference string (in both modes) and LWE with a super-polynomial modulus-to-noise ratio.
* We give a statistically-hiding vector commitment with transparent setup and polylogarithmic-size CRS, commitments, and openings from SIS. This simultaneously improves upon the vector commitment schemes of de Castro and Peikert (EUROCRYPT 2023) as well as Wee and Wu (EUROCRYPT 2023).
At a conceptual level, our work provides a unified view of recent lattice-based vector commitments and hidden-bits model NIZKs through the lens of the shifted multi-preimage sampling problem.

DL-SITM: Deep Learning-Based See-in-the-Middle Attack on AES

The see-in-the-middle (SITM) attack combines differential cryptanalysis and the ability to observe differential patterns in the side-channel leakage traces to reveal the secret key of SPN-based ciphers. While SITM presents a fresh perspective to side-channel analysis and allows attacks on deeper cipher rounds, there are practical difficulties that come with this method. First, one must realize a visual inspection of millions of power traces. Second, there is a strong requirement to reduce noise to a minimum, achieved by averaging over 1000 traces in the original work, to see the patterns. Third, the presence of a jitter-based countermeasure greatly affects pattern identification, making the visual inspection infeasible. In this paper we aim to tackle these difficulties by using a machine learning approach denoted as DL-SITM (deep learning SITM). The fundamental idea of our approach is that, while a collision obscured by noise is imperceptible in a manual inspection, a powerful deep learning model can identify it, even when a jitter-based countermeasure is in place. As we show with a practical experiment, the proposed DL-SITM approach can distinguish the two valid differentials from over 4M differential traces with only six false positives. Extrapolating from the parameters of this experiment, we get a rough estimate of $2^{43}$ key candidates for the post-processing step of our attack, which places it easily in the practical range. At the same time, we show that even with a jitter countermeasure shifting the execution by $\pm15$ samples, the testing f1-score stays at a relatively high (0.974).

Efficient Asymmetric PAKE Compiler from KEM and AE

Password Authenticated Key Exchange (PAKE) allows two parties to establish a secure session key with a shared low-entropy password pw. Asymmetric PAKE (aPAKE) extends PAKE in the client-server setting, and the server only stores a password file instead of the plain password so as to provide additional security guarantee when the server is compromised.
In this paper, we propose a novel generic compiler from PAKE to aPAKE in the Universal Composable (UC) framework by making use of Key Encapsulation Mechanism (KEM) and Authenticated Encryption (AE).
-- Our compiler admits efficient instantiations from lattice to yield lattice-based post-quantum secure aPAKE protocols. When instantiated with Kyber (the standardized KEM algorithm by the NIST), the performances of our compiler outperform other lattice-based compilers (Gentry et al. CRYPTO 2006) in all aspects, hence yielding the most efficient aPAKE compiler from lattice. In particular, when applying our compiler to the UC-secure PAKE schemes (Santos et al. EUROCRYPT 2023, Beguinet et al. ACNS 2023), we obtain the most efficient UC-secure aPAKE schemes from lattice.
-- Moreover, the instantiation of our compiler from the tightly-secure matrix DDH (MDDH)-based KEM (Pan et al. CRYPTO 2023) can compile the tightly-secure % CDH-based PAKE scheme (Liu et al. PKC 2023) to a tightly-secure MDDH-based aPAKE, which serves as the first tightly UC-secure aPAKE scheme.

A Note on Ligero and Logarithmic Randomness

We revisit the Ligero proximity test, and its logarithmic randomness variant, in the framework of [EA23] and show a simple proof that improves the soundness error of the original logarithmic randomness construction of [DP23] by a factor of two. This note was originally given as a presentation in ZK Summit 11.

Coercion-resistant i-voting with short PIN and OAuth 2.0

This paper presents an architecture for an OAuth 2.0-based i-voting
solution using a mobile native client in a variant of the Ara´ujo-Traor´e
protocol. We follow a systematic approach by identifying relevant OAuth
2.0 specifications and best practices. Having defined our framework, we
identify threats applicable to our proposed methodology and detail how
our design mitigates them to provide a safer i-voting process.

MIFARE Classic: exposing the static encrypted nonce variant

MIFARE Classic smart cards, developed and licensed by NXP, are widely used but have been subjected to numerous attacks over the years. Despite the introduction of new versions, these cards have remained vulnerable, even in card-only scenarios. In 2020, the FM11RF08S, a new variant of MIFARE Classic, was released by the leading Chinese manufacturer of unlicensed "MIFARE compatible" chips. This variant features specific countermeasures designed to thwart all known card-only attacks and is gradually gaining market share worldwide.
In this paper, we present several attacks and unexpected findings regarding the FM11RF08S. Through empirical research, we discovered a hardware backdoor and successfully cracked its key. This backdoor enables any entity with knowledge of it to compromise all user-defined keys on these cards without prior knowledge, simply by accessing the card for a few minutes.
Additionally, our investigation into older cards uncovered another hardware backdoor key that was common to several manufacturers.

Practical Post-Quantum Signatures for Privacy

The transition to post-quantum cryptography has been an enormous challenge and effort for cryptographers over the last decade, with impressive results such as the future NIST standards. However, the latter has so far only considered central cryptographic mechanisms (signatures or KEM) and not more advanced ones, e.g., targeting privacy-preserving applications. Of particular interest is the family of solutions called blind signatures, group signatures and anonymous credentials, for which standards already exist, and which are deployed in billions of devices. Such a family does not have, at this stage, an efficient post-quantum counterpart although very recent works improved this state of affairs by offering two different alternatives: either one gets a system with rather large elements but a security proved under standard assumptions or one gets a more efficient system at the cost of ad-hoc interactive assumptions or weaker security models. Moreover, all these works have only considered size complexity without implementing the quite complex building blocks their systems are composed of. In other words, the practicality of such systems is still very hard to assess, which is a problem if one envisions a post-quantum transition for the corresponding systems/standards.
In this work, we propose a construction of so-called signature with efficient protocols (SEP), which is the core of such privacy-preserving solutions. By revisiting the approach by Jeudy et al. (Crypto 2023) we manage to get the best of the two alternatives mentioned above, namely short sizes with no compromise on security. To demonstrate this, we plug our SEP in an anonymous credential system, achieving credentials of less than 80 KB. In parallel, we fully implemented our system, and in particular the complex zero-knowledge framework of Lyubashevsky et al. (Crypto'22), which has, to our knowledge, not be done so far. Our work thus not only improves the state-of-the-art on privacy-preserving solutions, but also significantly improves the understanding of efficiency and implications for deployment in real-world systems.

A Note on Zero-Knowledge for NP and One-Way Functions

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be useful for didactic purposes. We also remark that the same result hold for (imperfect) iO for 3CNF, or Witness Encryption for NP.

Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction

We explore Zero-Knowledge proofs (ZKP) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness of ZK CPUs with a large number of instructions of varying sizes.
We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state-of-the-art, where cost scales with the size of the largest CPU instruction (largest CFG node).
Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK.
We implemented an interactive tight arithmetic (over $\mathbb{F}_{2^{61}-1}$) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a $5$-$18×$ improvement when instructions are of varied size. Our VOLE-based tight ZK CPU (over $\mathbb{F}_{2^{61}-1}$) can execute $100$K (resp. $450$K) multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ $102$ Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory, may be of independent interest.

Problems and New Approaches for Crypto-Agility in Operational Technology

In recent years, cybersecurity has also become relevant for Operational Technology (OT). Critical systems like industrial automation systems or transportation systems are faced with new threats, and therefore require the implementation of thorough security measures. Regulations further mandate the deployment and regular verification of these security measures. However, OT systems differ from well-known systems of classic Information Technology (IT), such as mission times spanning decades, infrequent updates only during on-site maintenance, or diverse devices with varying support for security measures. The growing field of crypto-agility examines approaches to integrate security measures in an agile and flexible way, making updates easier and, therefore, encouraging a more frequent deployment of them. This paper contributes to this research field in the context of secure communication in two ways. We first examine the current state of crypto-agility by providing an overview of existing measures for OT systems. Then, we propose a new architecture concept with different deployment approaches to integrate security measures in a crypto-agile way. Based on a security library with a generic interface and a flexible proxy application, our architecture is capable of securing both new OT systems and existing ones via retrofit.

Don't Trust Setup! New Directions in Pre-Constrained Cryptography

The recent works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority. In this work we significantly expand this area by defining several new primitives and providing constructions from simple, standard assumptions as follows.
- Pre-Constrained Encryption. We define a weaker notion of pre-constrained encryption (PCE), as compared to the work of Ananth et al. which nevertheless suffices for all known applications. We then provide constructions for general constraints, satisfying malicious security from a variety of assumptions including DDH, LWE, QR and DCR. Our LWE based construction satisfies unconditional security against malicious authorities. In contrast, the construction by Ananth et al. supporting general constraints must rely (inherently) on strong assumptions like indistinguishability obfuscation.
- Pre-Constrained Static Functional Encryption and Input Obfuscation. We provide a new definition for pre-constrained functional encryption in the so-called static setting (PCSFE) where the functions to be embedded in secret keys are specified during the setup phase. We provide constructions for PCSFE supporting general constraints, with security against malicious authorities. As in the case of PCE, our first construction can be instantiated from a variety of assumptions including DDH, LWE, QR and DCR. Our second, LWE based construction satisfies unconditional security against malicious authorities.
We also study succinctness in PCSFE, where the public key is sublinear in the number of function keys. We provide the first construction from LWE in the random oracle model. We additionally provide a heuristic construction in the standard model using lattices together with groups.
- Pre-Constrained Input Obfuscation. We define and provide the first construction of pre-constrained input obfuscation from the same assumptions as those used to instantiate PCSFE.
- Pre-Constrained Group Signatures. For pre-constrained group signatures (PCGS), we provide the first construction supporting general constraints, achieving unconditional security against malicious authorities from the LWE assumption. The only other construction by Bartusek et al. supports the restricted set/database membership constraint, and achieves computational security from the DDH assumption (and is therefore quantum insecure).

OAE-RUP: A Strong Online AEAD Security Notion and its Application to SAEF

Release of unverified plaintexts (RUP) security is an important target for robustness in AE schemes. It is also highly crucial for lightweight (LW) implementations of online AE schemes on memory-constrained devices. Surprisingly, very few online AEAD schemes come with provable guarantees against RUP integrity and not one with any well-defined RUP confidentiality.
In this work, we first propose a new strong security notion for online AE schemes called OAE-RUP that captures security under blockwise processing of both encryption (which includes nonce-misuse) and decryption (which includes RUP). Formally, OAE-RUP combines the standard RUP integrity notion INT-RUP with a new RUP confidentiality notion sOPRPF (strong Online PseudoRandom Permutation followed by a pseudorandom Function). sOPRPF is based on the concept of "strong online permutations" and can be seen as an extension of the well-known CCA3 notion (Abed et al., FSE 2014) that captures arbitrary-length inputs.
An OAE-RUP-secure scheme is resistant against nonce-misuse as well as leakage of unverified plaintexts where the integrity remains unaffected, and the confidentiality of any encrypted plaintext is preserved up to the leakage of the longest prefix with the leaked plaintexts and the leakage of the length of the longest prefix with the nonce-repeating ciphertexts.
We then prove the OAE-RUP security of the SAEF mode. SAEF is a ForkAE mode (Asiacrypt 2019) that is optimized for authenticated encryption of short messages and processes the message blocks sequentially and in an online manner. At SAC 2020, it was shown that SAEF is also an online nonce misuse-resistant AE (OAE), offering enhanced security against adversaries that make blockwise adaptive encryption queries. It has remained an open question if SAEF also resists attacks against blockwise adaptive decryption adversaries or, more generally, when the decrypted plaintext is released before verification (RUP).
Our proofs are conducted using the coefficients H technique, and they show that, without any modifications, SAEF is OAE-RUP secure up to the birthday bound, i.e., up to $2^{n/2}$ processed data blocks, where $n$ is the block size of the forkcipher.

Universal Vector Commitments

We propose a new notion of vector commitment schemes with proofs of (non-)membership that we call universal vector commitments. We show how to build them directly from (i) Merkle commitments, and (ii) a universal accumulator and a plain vector commitment scheme. We also present a generic construction for universal accumulators over large domains from any vector commitment scheme, using cuckoo hashing. Leveraging the aforementioned generic constructions, we show that universal vector commitment schemes are implied by plain vector commitments and cuckoo hashing.

Oryx: Private detection of cycles in federated graphs

This paper proposes Oryx, a system for efficiently detecting cycles in federated graphs where parts of the graph are held by different parties and are private. Cycle detection is an important building block in designing fraud detection algorithms that operate on confidential transaction data held by different financial institutions. Oryx allows detecting cycles of various length while keeping the topology of the graphs secret, and it does so efficiently; Oryx achieves quasilinear computational complexity and scales well with more machines thanks to a parallel design. Our implementation of Oryx running on a single 32-core AWS machine (for each party) can detect cycles of up to length 6 in under 5 hours in a financial transaction graph that consists of tens of millions of nodes and edges. While the costs are high, Oryx’s protocol parallelizes well and can use additional hardware resources. Furthermore, Oryx is, to our knowledge, the first and only system that can handle this task

Compass: Encrypted Semantic Search with High Accuracy

We introduce Compass, a semantic search system over encrypted data that offers high accuracy, comparable to state-of-the-art plaintext search algorithms while protecting data, queries and search results from a fully compromised server. Additionally, Compass enables privacy-preserving RAG where both the RAG database and the query are protected. Compass contributes a novel way to traverse the Hierarchical Navigable Small Worlds (HNSW) graph, a top-performing nearest neighbor search index, over Oblivious RAM, a cryptographic primitive with strong security guarantees. Our techniques, Directional Neighbor Filtering, Speculative Greedy Search, and HNSW-tailored Path ORAM ensure that Compass achieves user-perceived latencies of a few seconds and is orders of magnitude faster than baselines for encrypted embeddings search.

Efficient Batch Algorithms for the Post-Quantum Crystals Dilithium Signature Scheme and Crystals Kyber Encryption Scheme

Digital signatures ensure authenticity and secure communication. They are used to verify the integrity and authenticity of signed documents and are widely utilized in various fields such as information technologies, finance, education, and law. They are crucial in securing servers against cyber attacks and authenticating connections between clients and servers. Additionally, encryption is used in many areas, such as secure communication, cloud, server and database security to ensure data confidentiality. Performing batch encryption, signature generation, and signature verification simultaneously and efficiently is highlighted as a beneficial approach for many systems. This work focuses on efficient batch signature generation with Dilithium, batch verifications of signatures from the same user using Crystals Dilithium (NIST's post-quantum digital signature standard) and batch encryption to a single user with Crystals Kyber (NIST's post-quantum encryption/KEM standard). One of the main operations of Dilithium and Kyber is the matrix-vector product with polynomial entries. So, the naive approach to generate/verify m signatures with Dilithium (or encrypt $m$ messages with Kyber) where m>1 is to perform $m$ such multiplications. In this paper, we propose to use efficient matrix multiplications of sizes greater than four to generate/verify m signatures with Dilithium and greater than two to encrypt $m$ messages with Kyber. To this end, batch algorithms that transform the polynomial matrix-vector multiplication in Dilithium's and Kyber's structures into polynomial matrix-matrix multiplication are designed. The batch numbers and the sizes of the matrices to be multiplied based on the number of repetitions of Dilithium's signature algorithm are determined. Also, batch versions of Dilithium verification and Kyber encryption algorithms are proposed. Moreover, many efficient matrix-matrix multiplication algorithms, such as Strassen-like multiplications and commutative matrix multiplications, are analyzed to design the best algorithms that are compatible with the specified dimensions and yield improvements. Various multiplication formulas are derived for different security levels of Dilithium signature generation, verification, and Kyber encryption. Improvements up to 28.1%, 33.3%, and 31.5% in the arithmetic complexities are observed at three different security levels of Dilithium's signature, respectively. The proposed batch Dilithium signature algorithm and the efficient multiplication algorithms are also implemented, and 34.22%, 17.40%, and 10.15% improvements on CPU cycle counts for three security levels are obtained. The multiplication formulas used for batch Dilithium signature generation are also applied for batch Dilithium verification. At three different levels of security, improvements in the arithmetic complexity are observed of up to 28.13%, 33.33%, and 31.25%. Furthermore, 49.88%, 56.60%, and 61.08% improvements on CPU cycle counts for three security levels are achieved, respectively. As a result of implementing Kyber Batch Encryption with efficient multiplication algorithms, 12.50%, 22.22%, and 28.13% improvements on arithmetic complexity, as well as 22.34%, 24.07%, and 30.83\% improvements on CPU cycle counts, are observed for three security levels.

ARADI and LLAMA: Low-Latency Cryptography for Memory Encryption

In this paper, we describe a low-latency block cipher (ARADI) and authenticated encryption mode (LLAMA) intended to support memory encryption applications.

Rare structures in tensor graphs - Bermuda triangles for cryptosystems based on the Tensor Isomorphism problem

Recently, there has been a lot of interest in improving the understanding of the practical hardness of the 3-Tensor Isomorphism (3-TI) problem, which, given two 3-tensors, asks for an isometry between the two. The current state-of-the-art for solving this problem is the algebraic algorithm of Ran et al. '23 and the graph-theoretic algorithm of Narayanan et al. '24 that have both slightly reduced the security of the signature schemes MEDS and ALTEQ, based on variants of the 3-TI problem (Matrix Code Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE) respectively).
In this paper, we propose a new combined technique for solving the 3-TI problem. Our algorithm, as typically done in graph-based algorithms, looks for an invariant in the graphs of the isomorphic tensors that can be used to recover the secret isometry. However, contrary to usual combinatorial approaches, our approach is purely algebraic. We model the invariant as a system of non-linear equations and solve it. Using this modelling we are able to find very rare invariant objects in the graphs of the tensors — cycles of length 3 (triangles) — that exist with probability approximately $1/q$. For solving the system of non-linear equations we use Gröbner-basis techniques adapted to tri-graded polynomial rings. We analyze the algorithm theoretically, and we provide lower and upper bounds on its complexity. We further provide experimental support for our complexity claims. Finally, we describe two dedicated versions of our algorithm tailored to the specifics of the MCE and the ATFE problems.
The implications of our algorithm are improved cryptanalysis of both MEDS and ALTEQ for the cases when a triangle exists, i.e. in approximately $1/q$ of the cases. While for MEDS, we only marginally reduce the security compared to previous work, for ALTEQ our results are much more significant with at least 60 bits improvement compared to previous work for all security levels. For Level I parameters, our attack is practical, and we are able to recover the secret key in only 1501 seconds.
The code is available for testing and verification of our results.

A Formal Analysis of Apple’s iMessage PQ3 Protocol

We present the formal verification of Apple’s iMessage PQ3, a highly performant, device-to-device messaging protocol offering strong security guarantees even against an adversary with quantum computing capabilities. PQ3 leverages Apple’s identity services together with a custom, post-quantum secure initialization phase and afterwards it employs a double ratchet construction in the style of Signal, extended to provide post-quantum, post-compromise security.
We present a detailed formal model of PQ3, a precise specification of its fine-grained security properties, and machine-checked security proofs using the TAMARIN prover. Particularly novel is the integration of post-quantum secure key encapsulation into the relevant protocol phases and the detailed security claims along with their complete formal analysis. Our analysis covers both key ratchets, including unbounded loops, which was believed by some to be out of scope of symbolic provers like TAMARIN (it is not!).