One of the primary approaches used to construct lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Such a scheme may abort and restart during signing which corresponds to rejection sampling produced signatures to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be. In this work, we develop a new method to construct signatures influenced by the rejection condition. This allows our rejection sampling to target significantly narrower output distributions than previous approaches, allowing much more compact signatures. The combined size of a signature and a verification key for the resulting scheme is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon.

Recent work proposed by Bernstein et al. (from EPRINT 2024) identified two timing attacks, KyberSlash1 and KyberSlash2, targeting ML-KEM decryption and encryption algorithms, respectively, enabling efficient recovery of secret keys. To mitigate these vulnerabilities, correctives were promptly applied across implementations. In this paper, we demonstrate a very simple side-channel-assisted power analysis attack on the patched implementations of ML-KEM. Our result showed that original timing leakage can be shifted to power consumption leakage that can be exploited on specific data. We performed a practical validation of this attack on both the standard and a shuffled implementations of ML-KEM on a Cortex-M4 platform, confirming its effectiveness. Our approach enables the recovery of the ML-KEM secret key in just 30 seconds for the standard implementation, and approximately 3 hours for the shuffled implementation, achieving a 100% success rate in both cases.

Multi-input functional encryption is a primitive that allows for the evaluation of an $\ell$-ary function over multiple ciphertexts, without learning any information about the underlying plaintexts. This type of computation is useful in many cases where one has to compute over encrypted data, such as privacy-preserving cloud services, federated learning, or more generally delegation of computation from multiple clients. It has recently been shown by Alborch et al. in PETS '24 to be useful to construct a randomized functional encryption scheme for obtaining differentially private data analysis over an encrypted database supporting linear queries. In this work we propose the first secret-key multi-input quadratic functional encryption scheme satisfying simulation security. Current constructions supporting quadratic functionalities, proposed by Agrawal et al. in CRYPTO '21 and TCC '22, only reach indistinguishibility-based security. Our proposed construction is generic, and for a concrete instantiation, we propose a new function-hiding inner-product functional encryption scheme proven simulation secure against one challenge ciphertext in the standard model, which is of independent interest. We then use these two results to construct an efficient randomized quadratic functional encryption scheme, from which we obtain differentially private data analysis over an encrypted database supporting quadratic queries. Finally, we give and fully benchmark an implementation of the randomized scheme. This work is an extended version of the paper "Simulation Secure Multi-Input Quadratic Functional Encryption" at SAC '24, where the multi-input quadratic functional encryption scheme and function-hiding inner-product functional encryption schemes were first presented (Section 3 and Seciton 4).

At FSE'15, Mennink introduced two tweakable block ciphers, $\widetilde{F}[1]$ and $\widetilde{F}[2]$, both utilizing an $n$-bit tweak. It was demonstrated that $\widetilde{F}[1]$ is secure for up to $2^{2n/3}$ queries, while $\widetilde{F}[2]$ is secure for up to $2^n$ queries, assuming the underlying block cipher is an ideal cipher with $n$-bit key and $n$-bit data. Later, at ASIACRYPT'16, Wang et al. showed a birthday bound attack on Mennink's design (which was later corrected in the eprint version {\textbf eprint 2015/363}) and proposed 32 new candidates for tweakable block ciphers that are derived from $n$-bit ideal block ciphers. It was shown that all the $32$ constructions are provably secure up to $2^n$ queries. All the proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher, $\widetilde{G2}$, which uses $2n$-bit tweaks and is constructed from three $n$-bit block cipher calls, proving its security up to $n$ bits, assuming that the underlying block cipher is an ideal cipher. They have also shown that it is impossible to design a tweakable block cipher with $2n$-bit tweaks using only two $n$-bit block cipher calls while achieving security beyond the birthday bound. In this paper, we advance this research further. We show that any tweakable block cipher design with $3n$-bit tweaks based on only three block cipher calls, where at least one key is tweak-independent, is vulnerable to a birthday bound distinguishing attack. We then propose a tweakable block cipher, $\widetilde{\textsf{G}_3}^*$ that uses three block cipher calls and admits $3n$-bit tweaks, achieves security up to $O(2^{2n/3})$ queries when all three block cipher keys are tweak-dependent. Furthermore, we prove that using four ideal block cipher calls, with at least one key being tweak-dependent, is necessary and sufficient to achieve $n$-bit security for a tweakable block cipher that admits $3n$-bit tweaks. Finally, we propose a tweakable block cipher, $\widetilde{\textsf{G}_r}$, which uses $(r+1)$ block cipher calls and processes $rn$-bit tweaks, achieving security up to $O(2^n)$ queries when at least one block cipher key is tweak-dependent.

Garbled Circuits are essential building blocks in cryptography, and extensive research has explored their construction from both applied and theoretical perspectives. However, a challenge persists: While theoretically designed garbled circuits offer optimal succinctness--remaining constant in size regardless of the underlying circuit’s complexit--and are reusable for multiple evaluations, their concrete computational costs are prohibitively high. On the other hand, practically efficient garbled circuits, inspired by Yao’s garbled circuits, encounter limitations due to substantial communication bottlenecks and a lack of reusability. To strike a balance, we propose a novel concept: online-offline garbling. This approach leverages instance-independent and (partially) reusable preprocessing during an offline phase, to enable the creation of constant-size garbled circuits in an online phase, while maintaining practical efficiency. Specifically, during the offline stage, the garbler generates and transmits a reference string, independent of the computation to be performed later. Subsequently, in the online stage, the garbler efficiently transforms a circuit into a constant-size garbled circuit. The evaluation process relies on both the reference string and the garbled circuit. We demonstrate that by leveraging existing tools such as those introduced by Applebaum et al. (Crypto’13) and Chongwon et al. (Crypto’17), online-offline garbling can be achieved under a variety of assumptions, including the hardness of Learning With Errors (LWE), Computational Diffie-Hellman (CDH), and factoring. In contrast, without the help of an offline phase, constant-size garbling is only feasible under the LWE and circular security assumptions, or the existence of indistinguishability obfuscation. However, these schemes are still very inefficient, several orders of magnitude more costly than Yao-style garbled circuits. To address this, we propose a new online-offline garbling scheme based on Ring LWE. Our scheme offers both asymptotic and concrete efficiency. It serves as a practical alternative to Yao-style garbled circuits, especially in scenarios where online communication is constrained. Furthermore, we estimate the concrete latency using our approach in realistic settings and demonstrate that it is 2-20X faster than using Yao-style garbled circuits. This improvement is estimated without taking into account parallelization of computation, which can lead to further performance improvement using our scheme.

The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios. In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering all of its modes – especially the complex interaction between its different key-exchange modes – in the framework of the Tamarin prover, making our resulting model one of the most complex Tamarin models to date. To our surprise, Tamarin finds a cross-protocol attack that allows a network attacker to completely break authentication of the pre-shared key mode. We implemented our attack on the SPDM reference implementation, and reported the issue to the SPDM developers. DMTF registered our attack as a CVE with CVSS rating 9 (critical). We propose a fix and develop the first formal symbolic proof using the Tamarin prover for the fixed SPDM 1.2 protocol as a whole. The resulting model of the main modes and their interactions is highly complex, and we develop supporting lemmas to enable proving properties in the Tamarin prover, including the absence of all cross-protocol attacks. Our fix has been incorporated into both the reference implementation and the newest version of the standard. Our results highlight the need for a holistic analysis of other internet standards and the importance of providing generalized security guarantees across entire protocols.

The CRYSTALS-Dilithium digital signature scheme, selected by NIST as a post-quantum cryptography (PQC) standard under the name ML-DSA, employs a public key compression technique intended for performance optimization. Specifically, the module learning with error instance $({\bf A}, {\bf t})$ is compressed by omitting the low-order bits ${\bf t_0}$ of the vector ${\bf t}$. It was recently shown that knowledge of ${\bf t_0}$ enables more effective side-channel attacks on Dilithium implementations. Another recent work demonstrated a method for reconstructing ${\bf t_0}$ from multiple signatures. In this paper, we build on this method by applying profiled deep learning-assisted side-channel analysis to partially recover the least significant bit of ${\bf t_0}$ from power traces. As a result, the number of signatures required for the reconstruction of ${\bf t_0}$ can be reduced by roughly half. We demonstrate how the new ${\bf t_0}$ reconstruction method enhances the efficiency of recovering the secret key component ${\bf s}_1$, and thus facilitates digital signature forgery, on an ARM Cortex-M4 implementation of Dilithium.

We present the first public and in-depth cryptanalysis of TEA-3, a stream cipher used in TETRA radio networks that was kept secret until recently. While the same also holds for the six other TETRA encryption algorithms, we pick TEA-3 to start with as (i) it is not obviously weakened as TEA-{1,4,7} but (ii) in contrast to TEA-2 it is approved only for extra-European emergency service, and (iii) as already noted by [MBW23] the TEA-3 design surprisingly contains a non-bijective S-box. Most importantly, we show that the 80-bit non-linear feedback shift register operating on the key decomposes into a cascade of two 40-bit registers. Although this hints at an intentional weakness at first glance, we are not able to lift our results to a practical attack. Other than that, we show how the balanced non-linear feedback functions used in the state register of TEA-3 can be constructed.

Local Differential Privacy (LDP) mechanisms consist of (locally) adding controlled noise to data in order to protect the privacy of their owner. In this paper, we introduce a new cryptographic primitive called LDP commitment. Usually, a commitment ensures that the committed value cannot be modified before it is revealed. In the case of an LDP commitment, however, the value is revealed after being perturbed by an LDP mechanism. Opening an LDP commitment therefore requires a proof that the mechanism has been correctly applied to the value, to ensure that the value is still usable for statistical purposes. We also present a security model for this primitive, in which we define the hiding and binding properties. Finally, we present a concrete scheme for an LDP staircase mechanism (generalizing the randomized response technique), based on classical cryptographic tools and standard assumptions. We provide an implementation in Rust that demonstrates its practical efficiency (the generation of a commitment requires just a few milliseconds). On the application side, we show how our primitive can be used to ensure simultaneously privacy, usability and traceability of medical data when it is used for statistical studies in an open science context. We consider a scenario where a hospital provides sensitive patients data signed by doctors to a research center after it has been anonymized, so that the research center can verify both the provenance of the data (i.e. verify the doctors’ signatures even though the data has been noised) and that the data has been correctly anonymized (i.e. is usable even though it has been anonymized).

The Gentry-Peikert-Vaikuntanathan (GPV) framework is utilized for constructing digital signatures, which is proven to be secure in the classical/quantum random-oracle model. Falcon is such a signature scheme, recognized as a compact and efficient signature among NIST-standardized signature schemes. Although a signature scheme based on the GPV framework is theoretically highly secure, it could be vulnerable to side-channel attacks and hence further research on physical attacks is required to make a robust signature scheme. We propose a general secret key recovery attack on GPV signatures using partial information about signatures obtained from side-channel attack. The three main contributions are summarized as follows. First, we introduce, for the first time, a concept of vulnerable partial information of GPV signatures and propose a secret key recovery attack, called OLS attack, which effectively utilizes partial information. In contrast to the approaches of Guerreau et al. (CHES 2022) and Zhang et al. (Eurocrypt 2023), which utilize filtered (or processed) signatures with hidden parallelepiped or learning slice schemes, the OLS attack leverages all the available signatures without filtering. We prove that the secret key recovered by the OLS attack converges to the real secret key in probability as the number of samples increases. Second, we utilize Gaussian leakage as partial information for the OLS attack on Falcon. As a result, the OLS attack shows a significantly higher success rate with fewer samples than the existing attack schemes. Furthermore, by incorporating the DDGR attack, the OLS attack can recover the secret key using much less samples with a success rate close to 100%. Moreover, we propose more efficient OLS attack on Falcon, which reduces the number of required side-channel attacks. Third, we propose an error-tolerant power analysis attack using MAP decoding, which effectively corrects the errors in samples to utilize Gaussian leakage correctly. In conclusion, the OLS attack is expected to strengthen the security of the GPV signatures including Falcon.

In PKC'24, de Saint Guilhem and Pedersen give a pseudorandom function basing on a relaxed group action assumption in the semi-honest setting. Basing on the assumption, they build an oblivious pseudorandom function (OPRF). Later, a recent paper by Levin and Pedersen uses the same function to build a verifiable random function (VRF), using the same assumption. We give a structural attack on this problem by reducing it to a few group action inverse problems (GAIP/DLog) over small subgroups. This reduction allows us to apply a CRT-based attack to recover the secret key, ultimately lowering the problem’s effective security strength to under 70 classical bits when using CSIDH-512. Hence the strength of their pseudorandom functions is bounded above by the GAIP over the largest prime order subgroup. Clearly, Kuperberg’s subexponential attack can be used to further reduce its quantum security.

Information-theoretic or unconditional security provides the highest level of security --- independent of the computational capability of an adversary. Secret-sharing techniques achieve information-theoretic security by splitting a secret into multiple parts (called shares) and storing the shares across non-colluding servers. However, secret-sharing-based solutions suffer from high overheads due to multiple communication rounds among servers and/or information leakage due to access-patterns (i.e.., the identity of rows satisfying a query) and volume (i.e., the number of rows satisfying a query). We propose SeaSearch, an information-theoretically secure approach that uses both additive and multiplicative secret-sharing, to efficiently support a large class of selection queries involving conjunctive, disjunctive, and range conditions. Two major contributions of SeaSearch are: (i) a new search algorithm using additive shares based on fingerprints, which were developed for string-matching over cleartext; and (ii) two row retrieval algorithms: one is based on multiplicative shares and another is based on additive shares. SeaSearch does not require communication among servers storing shares and does not reveal any information to an adversary based on access-patterns and volume.

Differential privacy (DP) has become the gold standard for privacy-preserving data analysis, but implementing it correctly has proven challenging. Prior work has focused on verifying DP at a high level, assuming the foundations are correct and a perfect source of randomness is available. However, the underlying theory of differential privacy can be very complex and subtle. Flaws in basic mechanisms and random number generation have been a critical source of vulnerabilities in real-world DP systems. In this paper, we present SampCert, the first comprehensive, mechanized foundation for differential privacy. SampCert is written in Lean with over 12,000 lines of proof. It offers a generic and extensible notion of DP, a framework for constructing and composing DP mechanisms, and formally verified implementations of Laplace and Gaussian sampling algorithms. SampCert provides (1) a mechanized foundation for developing the next generation of differentially private algorithms, and (2) mechanically verified primitives that can be deployed in production systems. Indeed, SampCert’s verified algorithms power the DP offerings of Amazon Web Services (AWS), demonstrating its real-world impact. SampCert’s key innovations include: (1) A generic DP foundation that can be instantiated for various DP definitions (e.g., pure, concentrated, Rényi DP); (2) formally verified discrete Laplace and Gaussian sampling algorithms that avoid the pitfalls of floating-point implementations; and (3) a simple probability monad and novel proof techniques that streamline the formalization. To enable proving complex correctness properties of DP and random number generation, SampCert makes heavy use of Lean’s extensive Mathlib library, leveraging theorems in Fourier analysis, measure and probability theory, number theory, and topology.

In this paper, we investigate the security of lightweight block ciphers, focusing on those that utilize the ADD-Rotate-XOR (ARX) and AND-Rotate-XOR (AND-RX) design paradigms. More specifically, we examine their resilience against boomerang-style attacks. First, we propose an automated search strategy that leverages the boomerang connectivity table (BCT) for AND operations ($\wedge BCT$) to conduct a complete search for boomerang and rectangle distinguishers for AND-RX ciphers. The proposed search strategy automatically considers all possible $\wedge BCT$ switches in the middle of the boomerang to optimise distinguishing probability. The correctness of the search strategy was verified experimentally. We were able to find the best boomerang and rectangle distinguishers to date in the single-key model for lightweight block ciphers KATAN32/48/64} and SIMON32/48. Next, we investigated BCT properties of ARX ciphers and discovered that a truncated boomerang switch could be formulated for the lightweight ARX cipher, CHAM. We were able to find the best single-key and related-key rectangle distinguishers to date for Cham. Our findings provide more accurate security margins of these lightweight ciphers against boomerang-style attacks.

Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the evelopment of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer to specify (2) which is often simple(r). Recently, works by Bünz–Fisch (TCC’23) and Aardal et al. (CRYPTO’24) provide new frameworks, called almost special soundness and predicate special soundness, respectively. To handle insufficiencies of special soundness, they deviate from its spirit and augment it in different ways. The necessity for their changes is that special soundness does not allow the challenges for useful sets of transcripts to depend on the transcripts themselves, but only on the challenges in the transcripts. As a consequence, (generalised) special soundness cannot express extraction strategies which reduce a computational problem to finding “inconsistent” accepting transcripts, for example in PCP/IOP-based or lattice-based proof systems, and thus provide (very) sub-optimal extractors. In this work, we introduce adaptive special soundness which captures extraction strategies exploiting inconsistencies between transcripts, e.g. transcripts containing different openings of the same commitment. Unlike (generalised) special soundness (Attema, Fehr, and Resch (TCC’23)), which specifies a target transcript structure, our framework allows specifying an extraction strategy which guides the extractor to sample challenges adaptively based on the history of prior transcripts. We extend the recent (almost optional) extractor of Attema, Fehr, Klooß and Resch (EPRINT 2023/1945) to our notion, and argue that it encompasses almost special soundness and predicate special soundness in many cases of interest. As a challenging application, we modularise and generalise the lattice Bulletproofs analysis by Bünz–Fisch (TCC’23) using the adaptive special soundness framework. Moreover, we extend their analysis to the ring setting for a slightly wider selection of rings than rational integers.

Multilateral Trade Credit Set-off (MTCS) is a process run by a service provider that collects trade credit data (i.e. obligations from a firm to pay another firm) from a network of firms and detects cycles of debts that can be removed from the system. The process yields liquidity savings for the participants, who can discharge their debts without relying on expensive loans. We propose an MTCS protocol that protects firms' sensitive data, such as the obligation amount or the identity of the firms they trade with. Mathematically, this is analogous to solving the Minimum Cost Flow (MCF) problem over a graph of $n$ firms, where the $m$ edges are the obligations. State-of-the-art techniques for Secure MCF have an overall complexity of $O(n^{10} \log n)$ communication rounds, making it barely applicable even to small-scale instances. Our solution leverages novel secure techniques such as Graph Anonymization and Network Simplex to reduce the complexity of the MCF problem to $O(max(n, \log\log{n+m}))$ rounds of interaction per pivot operations in which $O(max(n^2, nm))$ comparisons and multiplications are performed. Experimental results show the tradeoff between privacy and optimality.

The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size $L$ bits, its communication complexity is $O(nL+n^2 \log n)$, which is optimal up to a $\log n$ factor. Unfortunately, Chen’s analysis is rather intricate and complex. Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments. Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible. In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%. In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. In this paper, we introduce a new language, the Add/XNOR problem, which has the simplest structure and perfect randomness, by extending the subset sum problem. We prove that P $\neq$ NP as it shows that the square-root complexity is necessary to solve the Add/XNOR problem. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time.

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number $N$, whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if not all exponents are the same. In particular, to factor an $n$-bit integer $N=P^2 Q$ (with $P$ and $Q$ prime, and $Q<2^m$ for some $m$), our circuit uses $\widetilde{O}(m)$ qubits and has depth at most $\widetilde{O}(m + n/m)$, with $\widetilde{O}(n)$ quantum gates. When $m=\Theta(n^a)$ with $2/3 < a < 1$, the space and depth are sublinear in $n$, yet no known classical algorithms exploit the relatively small size of $Q$ to run faster than general-purpose factoring algorithms. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Crucially, our circuit reads the bits of the classical value $B$ in a streaming fashion, never storing more than $\widetilde{O}(\log A)$ qubits of quantum information at one time. In the context of the larger Jacobi algorithm for factoring $N = P^2Q$, this reduces the overall qubit count to be roughly proportional to the length of $Q$, rather than the length of $N$. Our circuit for computing the Jacobi symbol is also highly gate-efficient and parallelizable, achieving gate count $\widetilde{O}(\log B)$ and depth at most $\widetilde{O}(\log A + \log B/\log A)$. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems, such as computing the greatest common divisor, and thus could be of independent interest.

We introduce a new approach between classical security proofs of modes of operation and dedicated security analysis for known cryptanalysis families: General Practical Cryptanalysis. This allows us to analyze generically the security of the sum of two keyed permutations against known attacks. In many cases (of course, not all), we show that the security of the sum is strongly linked to that of the composition of the two permutations. This enables the construction of beyond-birthday bound secure low-latency PRFs by cutting a known-to-be-secure block cipher into two equal parts. As a side result, our general analysis shows an inevitable difficulty for the key recovery based on differential-type attacks against the sum, which leads to a correction of previously published attacks on the dedicated design Orthros.

Fully Homomorphic Encryption (FHE) enables secure computation of functions on ciphertexts without requiring decryption. Specifically, AP-like HE schemes exploit an intrinsic bootstrapping method called blind rotation. In blind rotation, a look-up table is homomorphically evaluated on the input ciphertext through the iterative multiplication of monomials. However, the algebraic structure of the multiplicative group of monomials imposes certain limitations on the input and output plaintext space: 1. only a fraction of the input plaintext space can be bootstrapped, 2. the output plaintext space is restricted to subsets of real numbers. In this paper, we design a novel bootstrapping method called slot blind rotation. The key idea of our approach is to utilize the automorphism group instead of monomials. More specifically, the look-up table is encoded into a single polynomial using SIMD (Single Instruction Multiple Data) packing and is rotated via a series of homomorphic multiplications and automorphisms. This method achieves two significant advantages: 1. the entire input plaintext space can be bootstrapped, 2. a more broad output plaintext space, such as complex numbers or finite field/rings can be supported. Finally, we present a new HE scheme leveraging the slot blind rotation technique and provide a proof-of-concept implementation. We also demonstrate the the benchmark results and provide recommended parameter sets.

This article presents a cryptanalysis of a 19th-century encrypted manuscript discovered in the archives of Conde de Siete Fuentes in Tenerife, Canary Islands, Spain. The manuscript, preserved by the heirs of the 6th Count of Valle de Salazar, utilizes a polyalphabetic substitution cipher. The cryptanalysis was performed by applying statistical frequency analysis and developing a Python script for decryption, resulting in the authors successfully deciphering the message. The decrypted letter reveals political communications discussing the strategic positioning of Tenerife as the capital, the dissolution of local councils, and the influence of key political figures. The analysis compares the cipher with historical encryption techniques, and identifies the unique characteristics of the manuscript’s encryption method. The study highlights the political dynamics and alliances within Tenerife’s nobility and their interactions with the central Spanish government, providing significant insights into, both, the cryptographic practices and political maneuvers of the time.

This work investigates persistent fault analysis on ASCON cipher that has been recently standardized by NIST USA for lightweight cryptography applications. In persistent fault, the fault once injected through RowHammer injection techniques, exists in the system during the entire encryption phase. In this work, we propose a model to mount persistent fault analysis (PFA) on ASCON cipher. In the finalization round of the ASCON cipher, we identify that the fault-injected S-Box operation in the permutation round, $p^{12}$, is vulnerable to leaking infor- mation about the secret key. The model can exist in two variants, a single instance of fault-injected S-Box out of 64 parallel S-Box invocations, and the same faulty S-Box iterated 64 times. The attack model demonstrates that any Spongent construction operating with authenticated encryption with associated data (AEAD) mode is vulnerable to persistent faults. In this work, we demonstrate the scenario of a single fault wherein the fault, once injected is persistent until the device is powered off. Using the pro- posed method, we successfully retrieve the 128-bit key in ASCON. Our experiments show that the minimum number and the maximum num- ber of queries required are 63 plaintexts and 451 plaintexts, respectively. Moreover, we observe that the number of queries required to mount the attack depends on fault location in the S-box LUT as observed from the plots reporting the minimum number of queries and average number of queries for 100 key values.

This paper studies an extension of the Linear Approximation Table (LAT) of vectorial Boolean mappings (also known as Substitution boxes) used in Linear Cryptanalysis (LC). This extended table is called NonLinear Approximation Table (NLAT).

The advent of quantum computing has profound implications for current technologies, offering advancements in optimization while posing significant threats to cryptographic algorithms. Public-key cryptosystems relying on prime factorization or discrete logarithms are particularly vulnerable, whereas block ciphers (BCs) remain secure through increased key lengths. In this study, we introduce a novel quantum implementation of SLIM, a lightweight block cipher optimized for 32-bit plaintext and an 80-bit key, based on a Feistel structure. This implementation distinguishes itself from other BC quantum implementations in its class (64–128-bit) by utilizing a minimal number of qubits while maintaining robust cryptographic strength and efficiency. By employing an innovative design that minimizes qubit usage, this work highlights SLIM’s potential as a resource-efficient and secure candidate for quantum-resistant encryption protocols.

Encrypted messaging systems obstruct content moderation, although they provide end-to-end security. As a result, misinformation proliferates in these systems, thereby exacerbating online hate and harassment. The paradigm of ``Reporting-then-Tracing" shows great potential in mitigating the spread of misinformation. For instance, message traceback (CCS'19) traces all the dissemination paths of a message, while source tracing (CCS'21) traces its originator. However, message traceback lacks privacy preservation for non-influential users (e.g., users who only receive the message once), while source tracing maintains privacy but only provides limited traceability. In this paper, we initiate the study of impact tracing. Intuitively, impact tracing traces influential spreaders central to disseminating misinformation while providing privacy protection for non-influential users. We introduce noises to hide non-influential users and demonstrate that these noises do not hinder the identification of influential spreaders. Then, we formally prove our scheme's security and show it achieves differential privacy protection for non-influential users. Additionally, we define three metrics to evaluate its traceability, correctness, and privacy using real-world datasets. The experimental results show that our scheme identifies the most influential spreaders with accuracy from 82% to 99% as the amount of noise varies. Meanwhile, our scheme requires only a 6-byte platform storage overhead for each message while maintaining a low messaging latency (< 0.25ms).

We present Orbweaver, a plausibly post-quantum functional commitment for linear relations that achieves quasilinear prover time together with $O(\log n)$ proof size and polylogarithmic verifier time. Orbweaver enables evaluation of linear functions on committed vectors over cyclotomic rings and the integers. It is extractable, preprocessing, non-interactive, structure-preserving, and supports compact public proof aggregation. The security of our scheme is based on the $k$-$R$-ISIS assumption (and its knowledge counterpart), whereby we require a trusted setup to generate a universal structured reference string. We use Orbweaver to construct succinct univariate and multilinear polynomial commitments. Concretely, our scheme has smaller proofs than most other succinct post-quantum arguments for large statements. For binary vectors of length $2^{30}$ we achieve $302$KiB linear map evaluation proofs with evaluation binding, and $1$MiB proofs when extractability is required; for $32$-bit integers these sizes are $494$KiB and $1.6$MiB, respectively.

Pairing-based arguments offer remarkably small proofs and space-efficient provers, but aggregating such proofs remains costly. Groth16 SNARKs and KZG polynomial commitments are prominent examples of this class of arguments. These arguments are widely deployed in decentralized systems, with millions of proofs generated per day. Recent folding schemes have greatly reduced the cost of proving incremental computations, such as batch proof verification. However, existing constructions require encoding pairing operations in generic constraint systems, leading to high prover overhead. In this work, we introduce Mira, a folding scheme that directly supports pairing-based arguments. We construct this folding scheme by generalizing the framework in Protostar to support a broader class of special-sound protocols. We demonstrate the versatility and efficiency of this framework through two key applications: Groth16 proof aggregation and verifiable ML inference. Mira achieves 5.8x faster prover time and 9.7x lower memory usage than the state-of-the-art proof aggregation system while maintaining a constant-size proof. To improve the efficiency of verifiable ML inference, we provide a new lincheck protocol with a verifier degree that is independent of the matrix order. We show that Mira scales effectively to larger models, overcoming the memory bottlenecks of current schemes.

Differentially private (DP) heavy-hitter detection is an important primitive for data analysis. Given a threshold $t$ and a dataset of $n$ items from a domain of size $d$, such detection algorithms ignore items occurring fewer than $t$ times while identifying items occurring more than $t+\Delta$ times; we call $\Delta$ the error margin. In the central model where a curator holds the entire dataset, $(\varepsilon,\delta)$-DP algorithms can achieve error margin $\Theta(\frac 1 \varepsilon \log \frac 1 \delta)$, which is optimal when $d \gg 1/\delta$. Several works, e.g., Poplar (S&P 2021), have proposed protocols in which two or more non-colluding servers jointly compute the heavy hitters from inputs held by $n$ clients. Unfortunately, existing protocols suffer from an undesirable dependence on $\log d$ in terms of both server efficiency (computation, communication, and round complexity) and accuracy (i.e., error margin), making them unsuitable for large domains (e.g., when items are kB-long strings, $\log d \approx 10^4$). We present hash-prune-invert (HPI), a technique for compiling any heavy-hitter protocol with the $\log d$ dependencies mentioned above into a new protocol with improvements across the board: computation, communication, and round complexity depend (roughly) on $\log n$ rather than $\log d$, and the error margin is independent of $d$. Our transformation preserves privacy against an active adversary corrupting at most one of the servers and any number of clients. We apply HPI to an improved version of Poplar, also introduced in this work, that improves Poplar's error margin by roughly a factor of $\sqrt{n}$ (regardless of $d$). Our experiments confirm that the resulting protocol improves efficiency and accuracy for large $d$.

In this work we state and prove an abstract version of the multi-forking lemma of Pointcheval and Stern from EUROCRYPT'96. Earlier, Bellare and Neven had given an abstract version of forking lemma for two-collisions (CCS'06). While the original purpose of the forking lemma was to prove security of signature schemes in the random oracle methodology, the abstract forking lemma can be used to obtain security proofs for multi-signatures, group signatures, and compilation of interactive protocols under the Fiat-Shamir random-oracle methodology.

The Hidden Weight Bit Function (HWBF) has drawn considerable attention for its simplicity and cryptographic potential. Despite its ease of implementation and favorable algebraic properties, its low nonlinearity limits its direct application in modern cryptographic designs. In this work, we revisit the HWBF and propose a new weightwise quadratic variant obtained by combining the HWBF with a bent function. This construction offers improved cryptographic properties while remaining computationally efficient. We analyze the balancedness, nonlinearity, and other criteria of this function, presenting theoretical bounds and experimental results to highlight its advantages over existing functions in similar use cases. The different techniques we introduce to study the nonlinearity of this function also enable us to bound the nonlinearity of a broad family of weightwise quadratic functions, both theoretically and practically. We believe these methods are of independent interest.

Private deep neural network (DNN) inference based on secure two-party computation (2PC) enables secure privacy protection for both the server and the client. However, existing secure 2PC frameworks suffer from a high inference latency due to enormous communication. As the communication of both linear and non-linear DNN layers reduces with the bit widths of weight and activation, in this paper, we propose PrivQuant, a framework that jointly optimizes the 2PC-based quantized inference protocols and the network quantization algorithm, enabling communication-efficient private inference. PrivQuant proposes DNN architecture-aware optimizations for the 2PC protocols for communication-intensive quantized operators and conducts graph-level operator fusion for communication reduction. Moreover, PrivQuant also develops a communication-aware mixed precision quantization algorithm to improve the inference efficiency while maintaining high accuracy. The network/protocol co-optimization enables PrivQuant to outperform prior-art 2PC frameworks. With extensive experiments, we demonstrate PrivQuant reduces communication by $11\times, 2.5\times \mathrm{and}~ 2.8\times$, which results in $8.7\times, 1.8\times ~ \mathrm{and}~ 2.4\times$ latency reduction compared with SiRNN, COINN, and CoPriv, respectively.

Private set intersection (PSI) allows any two parties (say client and server) to jointly compute the intersection of their sets without revealing anything else. Fully homomorphic encryption (FHE)-based PSI is a cryptographic solution to implement PSI-based protocols. Most FHE-based PSI protocols implement hash function approach and oblivious transfer approach. The main limitations of their protocols are 1) high communication complexity, that is, $O(xlogy)$ (where $x$ is total number of elements on client side, and $y$ is total number of elements on server side), and 2) high memory usage due to SIMD packing for encrypting large digit numbers. In this work, we design a novel tree-based approach to store the large digit numbers that achieves less communication complexity, that is, $O(|d|^{2})$ (where $d$ is digits of a mobile number). Later we implement our protocol using Tenseal library. Our designed protocol opens the door to find the common elements with less communication complexity and less memory usage.

Liu et al. (EuroS&P 2019) introduced Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS) to enhance the security of stealth address and deterministic wallet. In this paper, we point out that the current security notions are insufficient in practice, and introduce a new security notion which we call consistency. Moreover, we explore the unforgeability to provide strong unforgeability for outsider which captures the situation that nobody, except the payer and the payee, can produce a valid signature. From the viewpoint of cryptocurrency functionality, it allows us to implement a refund functionality. Finally, we propose a generic construction of PDPKS that provides consistency and outsider strong unforgeability. The design is conceptually much simpler than known PDPKS constructions. It is particularly note that the underlying strongly unforgeable signature scheme is required to provide the strong conservative exclusive ownership (S-CEO) security (Cremers et al., IEEE S&P 2021). Since we explicitly require the underlying signature scheme to be S-CEO secure, our security proof introduces a new insight of exclusive ownership security which may be of independent interest. As instantiations, we can obtain a pairing-based PDPKS scheme in the standard model, a discrete-logarithm based pairing-free PDPKS scheme in the random oracle model, and a lattice-based PDPKS scheme in the random oracle model, and so on.

In the usual syntax of digital signatures, the verification algorithm takes a verification key in addition to a signature and a message, whereas in ECDSA with key recovery, which is used in Ethereum, no verification key is input to the verification algorithm. Instead, a verification key is recovered from a signature and a message. In this paper, we explore BUFF security of ECDSA with key recovery (KR-ECDSA), where BUFF stands for Beyond UnForgeability Features (Cremers et al., IEEE S&P 2021). As a result, we show that KR-ECDSA provides BUFF security, except weak non-resignability (wNR). We pay attention to that the verification algorithm of KR-ECDSA takes an Ethereum address addr as input, which is defined as the rightmost 160-bits of the Keccak-256 hash of the corresponding ECDSA verification key, and checks the hash value of the recovered verification key is equal to addr. Our security analysis shows that this procedure is mandatory to provide BUFF security. We also discuss whether wNR is mandatory in Ethereum or not. To clarify the above equality check is mandatory to provide BUFF security in KR-ECDSA, we show that the original ECDSA does not provide any BUFF security. As a by-product of the analysis, we show that one of our BUFF attacks also works against the Aumayr et al.'s ECDSA-based adaptor signature scheme (ASIACRYPT 2021). We emphasize that the attack is positioned outside of their security model.

A Byzantine consensus protocol is essential in decentralized systems as the protocol ensures system consistency despite node failures. Research on consensus in wireless networks receives relatively less attention, while significant advancements in wired networks. However, consensus in wireless networks has equal significance as in wired networks. In this paper, we propose a new reliable broadcast protocol that can achieve reliability with high fault tolerance over than the SOTA (PODC '05). With the new protocol, we further develop the first wireless network Byzantine consensus protocol under the assumption of partial synchrony. Notably, this consensus protocol removes the requirement of leaders and fail-over mechanism in prior works. We formally prove the correctness of both our new broadcast protocol and consensus protocol.

One-way functions are essential tools for cryptography. However, the existence of one-way functions is still an open conjecture. By constructing a function with classical bits as input and quantum states as output, we prove for the first time the existence of quantum one-way functions. It provides theoretical guarantees for the security of many quantum cryptographic protocols.

We give new constructions of succinct non-interactive arguments ($\mathsf{SNARG}$s) for $\mathsf{NP}$ in the settings of both non-adaptive and adaptive soundness. Our construction of non-adaptive $\mathsf{SNARG}$ is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption ($\mathsf{FHE}$) scheme as well as a batch argument ($\mathsf{BARG}$) scheme. Specifically, for any choice of parameters $\ell$ and $L$, we construct a candidate $\mathsf{SNARG}$ scheme for any $\mathsf{NP}$ language $\mathcal{L}$ with the following properties: - the proof length is $\ell\cdot \mathsf{poly}(\lambda)$, - the common reference string $\mathsf{crs}$ has length $L\cdot \mathsf{poly}(\lambda)$, and - the setup is transparent (no private randomness). We prove that this $\mathsf{SNARG}$ has non-adaptive soundness assuming the existence of any $\mathsf{SNARG}$ where the proof size is $\ell$, the $\mathsf{crs}$ size is $L$, and there is a size $L$ Extended Frege ($\mathcal{EF}$) proof of completeness for the $\mathsf{SNARG}$. Moreover, we can relax the underlying $\mathsf{SNARG}$ to be any 2-message privately verifiable argument where the first message is of length $L$ and the second message is of length $\ell$. This yields new $\mathsf{SNARG}$ constructions based on any ``$\mathcal{EF}$-friendly'' designated-verifier $\mathsf{SNARG}$ or witness encryption scheme. We emphasize that our $\mathsf{SNARG}$ is universal in the sense that it does not depend on the argument system. We show several new implications of this construction that do not reference proof complexity: - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ from evasive $\mathsf{LWE}$ and $\mathsf{LWE}$. This gives a candidate lattice-based $\mathsf{SNARG}$ for $\mathsf{NP}$. - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ assuming the (non-explicit) existence of any $\mathsf{iO}$ and $\mathsf{LWE}$. - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with a short and transparent (i.e., uniform) $\mathsf{crs}$ assuming $\mathsf{LWE}$, $\mathsf{FHE}$ and the (non-explicit) existence of any hash function that makes Micali's $\mathsf{SNARG}$ construction sound. - a non-adaptive $\mathsf{SNARG}$ for languages such as $\mathsf{QR}$ and $\overline{\mathsf{DCR}}$ assuming only $\mathsf{LWE}$. In the setting of adaptive soundness, we show how to convert any designated verifier $\mathsf{SNARG}$ into publicly verifiable $\mathsf{SNARG}$, assuming the underlying designated verifier $\mathsf{SNARG}$ has an $\mathcal{EF}$ proof of completeness. As a corollary, we construct an adaptive $\mathsf{SNARG}$ for $\mathsf{UP}$ with a transparent $\mathsf{crs}$ assuming subexponential $\mathsf{LWE}$ and evasive $\mathsf{LWE}$. We prove our results by extending the encrypt-hash-and-$\mathsf{BARG}$ paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24].

Group signature (GS) is a well-known cryptographic primitive providing anonymity and traceability. Several implication results have been given by mainly focusing on the several security levels of anonymity, e.g., fully anonymous GS implies public key encryption (PKE) and selfless anonymous GS can be constructed from one-way functions and non-interactive zero knowledge poofs, and so on. In this paper, we explore an winning condition of full traceability: an adversary is required to produce a valid group signature whose opening result is an uncorrupted user. We demonstrate a generic construction of GS secure in the Bellare-Micciancio-Warinschi (BMW) model except the above condition from PKE only. We emphasize that the proposed construction is quite artificial and meaningless in practice because the verification algorithm always outputs 1 regardless of the input. This result suggests us the winning condition is essential in full traceability, i.e., an uncorrupted user must exist. We also explore a public verifiability of GS-based PKE scheme and introduce a new formal security definition of public verifiability by following BUFF (Beyond UnForgeability Features) security. Our definition guarantees that the decryption result of a valid cyphertext is in the message space specified by the public key. We show that the GS-based PKE scheme is publicly verifiable if the underlying GS scheme is fully traceable.

We describe Crescent, a construction and implementation of privacy-preserving credentials. The system works by upgrading the privacy features of existing credentials, such as JSON Web Tokens (JWTs) and Mobile Driver’s License (mDL) and as such does not require a new party to issue credentials. By using zero-knowledge proofs of possession of these credentials, we can add privacy features such as selective disclosure and unlinkability, without help from credential issuers. The system has practical performance, offering fast proof generation and verification times (tens of milliseconds) after a once-per-credential setup phase. We give demos for two practical scenarios, proof of employment for benefits eligibility (based on an employer-issued JWT), and online age verification (based on an mDL). We provide an open-source implementation to enable further research and experimentation. This paper is an early draft describing our work, aiming to include enough material to describe the functionality, and some details of the internals of our new library, available at https://github.com/microsoft/crescent-credentials.

Similarity search, i.e., retrieving vectors in a database that are similar to a query, is the backbone of many applications. Especially, graph-based methods show state-of-the-art performance. For sensitive applications, it is critical to ensure the privacy of the query and the dataset. In this work, we introduce GraSS, a secure protocol between client (query owner) and server (dataset owner) for graph-based similarity search based on fully homomorphic encryption (FHE). Both the client-input privacy against the server and the server-input privacy against the client are achievable based on underlying security assumptions on FHE. We first propose an FHE-friendly graph structure with a novel index encoding method that makes our protocol highly scalable in terms of data size, reducing the computational complexity of neighborhood retrieval process from $O(n^2)$ to $\tilde{O}(n)$ for the total number of nodes $n$. We also propose several core FHE algorithms to perform graph operations under the new graph structure. Finally, we introduce GraSS, an end-to-end solution of secure graph-based similarity search based on FHE. To the best of our knowledge, it is the first FHE-based solution for secure graph-based database search. We implemented GraSS with an open-source FHE library and estimated the performance on a million-scale dataset. GraSS identifies (approximate) top-16 in about $83$ hours achieving search accuracy of $0.918$, making it over $28\times$ faster than the previous best-known FHE-based solution.

Several protocols have been proposed recently for threshold ECDSA signatures, mostly in the dishonest-majority setting. Yet in so-called key-management networks, where a fixed set of servers share a large number of keys on behalf of multiple users, it may be reasonable to assume that a majority of the servers remain uncompromised, and in that case there may be several advantages to using an honest-majority protocol. With this in mind, we describe an efficient protocol for honest-majority threshold ECDSA supporting batch generation of key-independent presignatures that allow for "non-interactive'" online signing; these properties are not available in existing dishonest-majority protocols. Our protocol offers low latency and high throughput, and runs at an amortized rate of roughly 1.3 ms/presignature.

Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves. For example, a user who has received a digital passport credential can prove their “age is $>18$” without revealing any other attributes such as their name or date of birth. Despite inherent value for privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic assumptions that require system-wide changes to existing issuer infrastructure. In addition, issuers often require digital identity credentials to be *device-bound* by incorporating the device’s secure element into the presentation flow. As a result, schemes like BBS+ require updates to the hardware secure elements and OS on every user's device. In this paper, we propose a new anonymous credential scheme for the popular and legacy-deployed Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme. By adding efficient zk arguments for statements about SHA256 and document parsing for ISO-standardized identity formats, our anonymous credential scheme is that first one that can be deployed *without* changing any issuer processes, *without* requiring changes to mobile devices, and *without* requiring non-standard cryptographic assumptions. Producing ZK proofs about ECDSA signatures has been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms. We overcome this bottleneck by designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA. Our proofs for ECDSA can be generated in 60ms. When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, we can generate a zero-knowledge proof for the MDOC presentation flow in 1.2 seconds on mobile devices depending on the credential size. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.

Securing information communication dates back thousands of years ago. The meaning of information security, however, has evolved over time and today covers a very wide variety of goals, including identifying the source of information, the reliability of information, and ultimately whether the information is trustworthy. In this paper, we will look at the evolution of the information security problem and the approaches that have been developed for providing information protection. We argue that the more recent problem of misinformation and disinformation has shifted the content integrity problem from the protection of message syntax to the protection of message semantics. This shift, in the age of advanced AI systems, a technology that can be used to mimic human-generated content as well as to create bots that mimic human behaviour on the Internet, poses fundamental technological challenges that evade existing technologies. It leaves social elements, including public education and a suitable legal framework, as increasingly the main pillars of effective protection, at least in the short run. It also poses an intriguing challenge to the scientific community: to design effective solutions that employ cryptography and AI, together with incentivization to engage the global community, to ensure the safety of the information ecosystem.

Homomorphic encryption (HE)-based deep neural network (DNN) inference protects data and model privacy but suffers from significant computation overhead. We observe transforming the DNN weights into circulant matrices converts general matrix-vector multiplications into HE-friendly 1-dimensional convolutions, drastically reducing the HE computation cost. Hence, in this paper, we propose PrivCirNet, a protocol/network co-optimization framework based on block circulant transformation. At the protocol level, PrivCirNet customizes the HE encoding algorithm that is fully compatible with the block circulant transformation and reduces the computation latency in proportion to the block size. At the network level, we propose a latency-aware formulation to search for the layer-wise block size assignment based on second-order information. PrivCirNet also leverages layer fusion to further reduce the inference cost. We compare PrivCirNet with the state-of-the-art HE-based framework Bolt (IEEE S&P 2024) and HE-friendly pruning method SpENCNN (ICML 2023). For ResNet-18 and Vision Transformer (ViT) on Tiny ImageNet, PrivCirNet reduces latency by $5.0\times$ and $1.3\times$ with iso-accuracy over Bolt, respectively, and improves accuracy by $4.1\%$ and $12\%$ over SpENCNN, respectively. For MobileNetV2 on ImageNet, PrivCirNet achieves $1.7\times$ lower latency and $4.2\%$ better accuracy over Bolt and SpENCNN, respectively. Our code and checkpoints are available at https://github.com/Tianshi-Xu/PrivCirNet.

Sparse Learning With Errors (sLWE) is a novel problem introduced at Crypto 2024 by Jain et al., designed to enhance security in lattice-based cryptography against quantum attacks while maintaining computational efficiency. This paper presents the first third-party analysis of the ternary variant of sLWE, where both the secret and error vectors are constrained to ternary values. We introduce a combinatorial attack that employs a subsystem extraction technique followed by a Meet-in-the-Middle approach, effectively recovering the ternary secret vector. Our comprehensive analysis explores the attack's performance across various sparsity and modulus settings, revealing critical security limitations inherent in ternary sLWE. Our analysis does not claim to present any attack on the proposal of Jain et al.; rather, it supports their assertion that sparse LWE is vulnerable for small secrets, particularly for ternary secrets and ternary errors. Notably, our findings indicate that the recommended parameters, which the developers claim provide security equivalent to LWE with a dimension of 1024, may not hold true for the ternary variant of sLWE. Our research highlights that, particularly with a modulus of $2^{64}$, the secret key can be recovered in a practical timeframe, supporting the developers' claim of vulnerability in this case. Additionally, for configurations with moduli of $2^{32}$ and $2^{16}$, we observe a significant reduction in the security margin. This suggests that the actual security level may be significantly weaker than intended. Overall, our work contributes crucial insights into the cryptographic robustness of ternary sLWE, emphasizing the need for further strengthening to protect against potential attacks and setting the stage for future research in this area.

As smartphone usage continues to grow, the demand for note-taking applications, including memo and diary apps, is rapidly increasing. These applications often contain sensitive information such as user schedules, thoughts, and activities, making them key targets for analysis in digital forensics. Each year, new note-taking applications are released, most of which include lock features to protect user data. However, these security features can create challenges for authorized investigators attempting to access and analyze application data. This paper aims to support investigators by conducting a static analysis of Android-based note-taking applications. It identifies how and where data is stored and explains methods for extracting and decrypting encrypted data. Based on the analysis, the paper concludes by proposing future research directions in the field of digital forensics.

The transition to Post-Quantum (PQ) cryptography is increasingly mandated by national agencies and organizations, often involving a phase where classical and PQ primitives are combined into hybrid solutions. In this context, existing protocols must be adapted to ensure quantum resistance while maintaining their security goals. These adaptations can significantly impact performance, particularly on embedded devices. In this article, we focus on standardized protocols which support application management on eSIMs across different modes. This is a complex use-case, involving constrained devices with stringent security requirements. We present PQ adaptations, including both hybrid and fully PQ versions, for all modes. Using ProVerif, we provide automated proofs that verify the security of these PQ variants. Additionally, we analyze the performance impact of implementing PQ protocols on devices, measuring runtime and bandwidth consumption. Our findings highlight the resource overhead associated with achieving post-quantum security for eSIM management.

Hyperelliptic curve cryptography (HECC) is a candidate to standardization which is a competitive alternative to elliptic curve cryptography (ECC). We extend Regev's algorithm to this setting. For genus-two curves relevant to cryptography, this yields a quantum attack up to nine times faster than the state-of-the-art. This implies that HECC is slightly weaker than ECC. In a more theoretical direction, we show that Regev's algorithm obtains its full speedup with respect to Shor's when the genus is high, a setting which is already known to be inadequate for cryptography.

This study aims to determine the complete and precise differential properties of SM4, which have remained unknown for over twenty years after the cipher was initially released. A Boolean Satisfiability Problem (SAT) based automatic search approach is employed to achieve the objective. To improve the limited efficiency of the search focused on differential probabilities, we want to investigate the feasibility of integrating human expertise into an automatic approach to enhance the search speed. This study presents the construction of four new SAT models that describe the human-identified specific properties of short differential characteristics. All of these models are integrated into the fundamental model, and the SAT solver is implemented to assess the acceleration capabilities of the new models. The experimental results indicate that including three new models effectively decreases the overall execution time of the SAT solver. Using the novel models, we obtain the first precise minimal values for the number of active S-boxes of SM4 under single-key (complete rounds) and related-key (1-round to 19-round) settings. The first precise upper bound for differential probabilities of SM4 (1-round to 20-round) is also determined. In addition, we present the first publicly revealed optimal 19-round differential characteristic of SM4.

In CRYPTO 2019, Gohr introduced the method of differential neural cryptanalysis, utilizing neural networks as the underlying distinguishers to achieve distinguishers for (5-8)-round of the Speck32/64 cipher and subsequently recovering keys for 11 and 12 rounds. Inspired by this work, we propose an enhanced neural cryptanalysis framework that combines the Efficient Channel Attention (ECA) module with residual networks. By introducing the channel attention mechanism to emphasize key features and leveraging residual networks to facilitate efficient feature extraction and gradient flow, we achieve improved performance. Additionally, we employ a new data format that combines the ciphertext and the penultimate round ciphertext as input samples, providing the distinguisher with more useful features. Compared with the known results, our work enhance the accuracy of the neural distinguishers for Simeck32/64 (10-12)-round and achieve a new 13-round distinguisher. We also improve the accuracy of the Simeck48/96 (10-11)-round distinguishers and develop new (12-16)-round neural distinguishers. Moreover, we enhance the accuracy of the Simeck64/128 (14-18)-round distinguishers and obtain a new 19-round neural distinguisher. As a result, we achieve the highest accuracy and the longest rounds distinguishers for Simeck32/64, Simeck48/96, and Simeck64/128.

A proof of solvency (or proof of reserves) is a zero-knowledge proof conducted by centralized cryptocurrency exchange to offer evidence that the exchange owns enough cryptocurrency to settle each of its users' balances. The proof seeks to reveal nothing about the finances of the exchange or its users, only the fact that it is solvent. The literature has already started to explore how to make proof size and verifier time independent of the number of (i) users on the exchange, and (ii) addresses used by the exchange. We argue there are a few areas of improvement. First, we propose and implement a full end-to-end argument that is fast for the exchange to prove (minutes), small in size (KBs), and fast to verify (seconds). Second, we deal with the natural conflict between Bitcoin and Ethereum's cryptographic setting (secp256k1) and more ideal settings for succinctness (e.g., pairing-based cryptography) with a novel mapping approach. Finally, we discuss how to adapt the protocol to the concrete parameters of bls12-381 (which is relevant because the bit-decomposition of all user balances will exceed the largest root of unity of the curve for even moderately-sized exchanges).

The evasive LWE assumption, proposed by Wee [Eurocrypt'22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions: (i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto'22 Tsabary, Asiacrypt'22 VWW, Crypto'23 ARYY] respectively, showing that these assumptions are unlikely to hold. (ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples. (iii) We show that under our assumption formulations, the security proofs of [Asiacrypt'22 VWW] and [Crypto'23 ARYY] can be recovered, and we reason why the security proof of [Crypto'22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption.

We will present here new multivariate encryption algorithms. This is interesting since few multivariate encryption scheme currently exist, while their exist many more multivariate signature schemes. Our algorithms will combine several ideas, in particular the idea of the LL’ perturbation originally introduced, but only for signature, in [GP06]. In this paper, the LL’ perturbation will be used for encryption and will greatly differ from [GP06]. As we will see, our algorithms resists to all known attacks (in particular Gröbner attacks and MinRank attacks) and have reasonable computation time.

In this paper, we aim to enhance and automate advanced techniques for impossible differential attacks. To demonstrate these advancements, we present improved attacks on the LBlock and HIGHT block ciphers. More precisely, we (a) introduce a methodology to automatically invert symmetric ciphers when represented as directed acyclic graphs, a fundamental step in the search for impossible differential trails and in key recovery techniques; (b) automate the search for impossible differential distinguishers, reproducing recent techniques and results; (c) present a new hybrid model combining cell-wise properties and bit-wise granularity; (d) integrate these techniques in the automated tool CLAASP; (e) demonstrate the effectiveness of the tool by reproducing a state-of-the-art 16-round impossible differential for LBlock previously obtained using a different technique and exhibiting a new 18-round improbable trail; (f) improve the state-of-the-art single-key recovery of HIGHT for 27 rounds, by automating the use of hash tables to current state-of-the-art results.

In this short paper we consider a format preserving encryption when a nonce is available. The encryption itself mimics a stream cipher where the keystream is of a (non-binary) radix $R$. We give a few practical and efficient ways to generate such a keystream from a binary keystream generator.

In many lightweight cryptography applications, low area and latency are required for efficient implementation. The gate count in the cipher and the circuit depth must be low to minimize these two metrics. Many optimization strategies have been developed for the linear layer, led by the Boyer-Peralta (BP) algorithm. The Advanced Encryption Standard (AES) has been a focus of extensive research in this area. However, while the linear layer uses only XOR gates, the S-box, which is an essential nonlinear component in symmetric cryptography, uses various gate types, making optimization challenging, particularly as the bit size increases. In this paper, we propose a new framework for a heuristic search to optimize the circuit depth or XOR gate count of S-box circuits. Existing S-box circuit optimization studies have divided the nonlinear and linear layers of the S-box, optimizing each separately, but limitations still exist in optimizing large S-box circuits. To extend the optimization target from individual internal components to the entire S-box circuit, we extract the XOR information of each node in the target circuit and reconstruct the nodes based on nonlinear gates. Next, we extend the BP algorithm-based heuristics to address nonlinear gates and incorporate this into the framework. It is noteworthy that the effects of our framework occur while maintaining the AND gate count and AND depth without any increase. To demonstrate the effectiveness of the proposed framework, we apply it to the AES, SNOW3G, and Saturnin S-box circuits. Our results include depth improvements by about 40% and 11% compared to the existing AES S-box [BP10] and Saturnin super S-box [CDL+20] circuits, respectively. We implement a new circuit for the SNOW3G S-box, which has not previously been developed, and apply our framework to reduce its depth. We expect the proposed framework to contribute to the design and implementation of various symmetric-key cryptography solutions.

A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments. In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script, without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with secure majority. In particular, we present $\mathsf{BitVM}$, a two-party protocol realizing a generic virtual machine by a combination of cryptographic and incentive mechanisms. We conduct a formal analysis of $\mathsf{BitVM}$, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach: in the optimistic case (i.e., in the absence of disputes between parties), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin.

In this paper we define the novel concept token-based key exchange (TBKE), which can be considered a cross between non-interactive key exchange (NIKE) and attribute-based encryption (ABE). TBKE is a scheme that allows users within an organization to generate shared keys for a subgroup of users through the use of personal tokens and secret key. The shared key generation is performed locally and no interaction between users or with a server is needed. The personal tokens are derived from a set of universal tokens and a master secret key which are generated and stored on a trusted central server. Users are only required to interact with the server during setup or if new tokens are provided. To reduce key escrow issues the server can be erased after all users have received their secret keys. Alternatively, if the server is kept available TBKE can additionally provide token revocation, addition and update. We propose a very simple TBKE protocol using bilinear pairings. The protocol is secure against user coalitions based upon a novel hidden matrix problem. The problems requires an adversary to compute where the adversary must compute a matrix product in the exponent, where some components are given in the clear and others are hidden as unknown exponents. We argue that the hidden matrix problem is as hard as dLog in the bilinear group model.

In this paper, we present a batching technique for oracles corresponding to codewords of a Reed–Solomon code. This protocol is inspired by the round function of the STIR protocol (CRYPTO 2024). Using this oracle batching protocol, we propose a construction of a practically efficient accumulation scheme, which we call BOIL. Our accumulation scheme can be initiated with an arbitrary correlated holographic IOP, leading to a new class of PCD constructions. The results of this paper were originally given as a presentation at zkSummit12.

This paper studies quantum linear key-recovery attacks on block ciphers. The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC 2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum \emph{correlation state}, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily. In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon's algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon attacks.

This work proposes a multi-level compiler framework to transform programs with loop structures to efficient algorithms over fully homomorphic encryption (FHE). We observe that, when loops operate over ciphertexts, it becomes extremely challenging to effectively interpret the control structures within the loop and construct operator cost models for the main body of the loop. Consequently, most existing compiler frameworks have inadequate support for programs involving non-trivial loops, undermining the expressiveness of programming over FHE. To achieve both efficient and general program execution over FHE, we propose CHLOE, a new compiler framework with multi-level control-flow analysis for the effective optimization of compound repetition control structures. We observe that loops over FHE can be classified into two categories depending on whether the loop condition is encrypted, namely, the transparent loops and the oblivious loops. For transparent loops, we can directly inspect the control structures and build operator cost models to apply FHE-specific loop segmentation and vectorization in a fine-grained manner. Meanwhile, for oblivious loops, we derive closed-form expressions and static analysis techniques to reduce the number of potential loop paths and conditional branches. In the experiment, we show that \NAME can compile programs with complex loop structures into efficient executable codes over FHE, where the performance improvement ranges from $1.5\times$ to $54\times$ (up to $10^{5}\times$ for programs containing oblivious loops) when compared to programs produced by the-state-of-the-art FHE compilers.

We propose a solution for optimized scaling of multi-party computation using the MP-SPDZ framework (CCS’20). It does not use manual optimization but extends the compiler and the virtual machine of the framework, thus providing an improvement for any user. We found that our solution improves timings four-fold for a simple example in MP-SPDZ, and it improves an order of magnitude on every framework using secret sharing considered by Hastings et al. (S&P’19) either in terms of time or RAM usage. The core of our approach is finding a balance between communication round optimization and memory usage.

Oblivious pseudorandom function (OPRF) is a two-party cryptographic protocol that allows the receiver to input $x$ and learn $F(x)$ for some PRF $F$, only known to the sender. For private set intersection (PSI) applications, OPRF protocols have evolved to enhance efficiency, primarily using symmetric key cryptography. Current state-of-the-art protocols, such as those by Rindal and Schoppmann (Eurocrypt '21), leverage vector oblivious linear evaluation (VOLE) and oblivious key-value store (OKVS) constructions. In this work, we identify a flaw in an existing security proof, and present practical attacks in the malicious model, which results in additional PRF evaluations than the previous works' claim. In particular, the attack for malicious model is related to the concept of OKVS overfitting, whose hardness is conjectured in previous works. Our attack is the first one to discuss the concrete hardness of OKVS overfitting problem. As another flavour of contribution, we generalize OKVS-based OPRF constructions, suggesting new instantiations using a VOLE protocol with only Minicrypt assumptions. Our generalized construction shows improved performance in high-speed network environments, narrowing the efficiency gap between the OPRF constructions over Cryptomania and Minicrypt.

We present a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of 1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and 2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.

In this study, we present the first side-channel attack on the ARADI block cipher, exposing its vulnerabilities to physical attacks in non-profiled scenarios. We propose a novel bitwise divide-and-conquer methodology tailored for ARADI, enabling key recovery. Furthermore, based on our attack approach, we present a stepwise method for recovering the full 256-bit master key. Through experiments on power consumption traces from an ARM processor, we demonstrate successful recovery of target key bits, validating the effectiveness of our proposed method. Our findings highlight critical weaknesses in physical security of ARADI and underscore the necessity of implementing effective countermeasures to address side-channel vulnerabilities.

As advancements in quantum computing present potential threats to current cryptographic systems, it is necessary to reconsider and adapt existing cryptographic frameworks. Among these, Grover's algorithm reduces the attack complexity of symmetric-key encryption, making it crucial to evaluate the security strength of traditional symmetric-key systems. In this paper, we implement an efficient quantum circuit for the ARIA symmetric-key encryption and estimate the required quantum resources. Our approach achieves a reduction of over 61\% in full depth and over 65.5\% in qubit usage compared to the most optimized previous research. Additionally, we estimate the cost of a Grover attack on ARIA and evaluate its post-quantum security strength.

This article generalizes the widely-used GLV decomposition for scalar multiplication to a broader range of elliptic curves with moderate CM discriminant \( D < 0 \) (up to a few thousand in absolute value). Previously, it was commonly believed that this technique could only be applied efficiently for small \( D \) values (e.g., up to \( 100 \)). In practice, curves with \( j \)-invariant \( 0 \) are most frequently employed, as they have the smallest possible \( D = -3 \). This article participates in the decade-long development of numerous real-world curves with moderate \( D \) in the context of ZK-SNARKs. Such curves are typically derived from others, which limits the ability to generate them while controlling the magnitude of \( D \). The most notable example is so-called "lollipop" curves demanded, among others, in the Mina protocol. Additionally, the new results are relevant to one of the "classical" curves (with \( D = -619 \)) from the Russian ECC standard. This curve was likely found using the CM method (with overwhelming probability), though this is not explicitly stated in the standard. Its developers seemingly sought to avoid curves with small \( D \) values, aiming to mitigate potential DLP attacks on such curves, and hoped these attacks would not extend effectively to \( D = -619 \). One goal of the present article is to address the perceived disparity between the \( D = -3 \) curves and the Russian curve. Specifically, the Russian curve should either be excluded from the standard for potential security reasons or local software should begin leveraging the advantages of the GLV decomposition.

This work investigates constructions of threshold fully homomorphic encryption with low communication, i.e., with small ciphertexts and small decryption shares. In this context, we discuss in detail the technicalities for achieving full-fledged threshold FHE, and put forward limitations regarding prior works, including an attack against the recent construction of Boudgoust and Scholl [ASIACRYPT 2023]. In light of our observations, we generalize the definition of threshold fully homomorphic encryption by adding an algorithm which allows to introduce additional randomness in ciphertexts before they are decrypted by parties. In this setting, we are able to propose a construction which offers small ciphertexts and small decryption shares.

As dataset sizes continue to grow, users face increasing difficulties in performing processing tasks on their local machines. From this, privacy concerns about data leakage have led data owners to upload encrypted data and utilize secure range queries to cloud servers. To address these challenges, order-revealing encryption (ORE) has emerged as a promising solution for large numerical datasets. Building on this, delegatable order-revealing encryption (DORE) was introduced, allowing operations between encrypted datasets with different secret keys in multi-client ORE environments. DORE operates through authorization tokens issued by the data owner. However, security concerns had arisen about unauthorized users exploiting data without permission, leading to the development of a secure order-revealing encryption scheme (SEDORE). These attacks can result in unauthorized data access and significant financial losses in modern cloud service providers (CSPs) utilizing pay-per-query systems. In addition, efficient delegatable order-revealing encryption (EDORE), which improves speed and storage compared to SEDORE with identical security levels, was also introduced. Although both SEDORE and EDORE were designed to be robust against these attacks, we have identified that they still retain the same vulnerabilities within the same threat model. To address these issues, we propose Verifiable Delegatable Order-Revealing Encryption (VDORE), which protects against attacks by using the Schnorr Signature Scheme to verify the validity of the token that users send. We propose a precise definition and robust proof to improve the unclear definition and insufficient proof regarding token unforgeability in the SEDORE. Furthermore, the token generation algorithm in VDORE provides about a $1.5\times$ speed-up compared to SEDORE.

Quantum computing has attracted substantial attention from researchers across various fields. In case of the symmetric key cryptography, the main problem is posed by the application of Grover's search. In this work, we focus on quantum analysis of the lightweight block cipher LED. This paper proposes an optimized quantum circuit for LED, minimizing the required number of qubits, quantum gates, and circuit depth. Furthermore, we conduct Grover's attack and Search with Two Oracles (STO) attack on the proposed LED cipher, estimating the quantum resources required for the corresponding attack oracles. The STO attack outperforms the usual Grover's search when the state size is less than the key size. Beyond analyzing the cipher itself (i.e., the ECB mode), this work also evaluates the effectiveness of quantum attacks on LED across different modes of operation.

With the emergence of DeFi, attacks based on re-ordering transactions have become an essential problem for public blockchains. Such attacks include front-running or sandwiching transactions, where the adversary places transactions at a particular place within a block to influence a financial asset’s market price. In the Ethereum space, the value extracted by such attacks is often referred to as miner/maximal extractable value (MEV), which to date is estimated to have reached a value of more than USD 1.3B. A promising approach to protect against MEV is to hide the transaction data so block proposers cannot choose the order in which transactions are executed based on the transactions’ content. This paper describes the cryptographic protocol underlying the Shutter network. Shutter has been available as an open-source project since the end of 2021 and has been running in production since Oct. 2022.

A message authentication code (MAC) is a symmetric-key cryptographic function used to authenticate a message by assigning it a tag. This tag is a short string that is difficult to reproduce without knowing the key. The tag ensures both the authenticity and integrity of the message, enabling the detection of any modifications. A significant number of existing message authentication codes (MACs) are based on block ciphers (BCs) and tweakable block ciphers (TBCs). These MACs offer various trade-offs in properties, such as data processing rate per primitive call, use of single or multiple keys, security levels, pre- or post-processing, parallelizability, state size, and optimization for short/long queries. In this work, we propose the $\mathsf{Sonikku}$ family of expanding primitive based MACs, consisting of three instances: $\mathsf{BabySonic}$, $\mathsf{DarkSonic}$, and $\mathsf{SuperSonic}$. The $\mathsf{Sonikku}$ MACs are -- 1) faster than the state-of-the-art TBC-based MACs; 2) secure beyond the birthday bound in the input block size; 3) smaller in state size compared to state-of-the-art MACs; and 4) optimized with diverse trade-offs such as pre/post-processing-free execution, parallelization, small footprint, and suitability for both short and long queries. These attributes make them favorable for common applications as well as ``IoT'' and embedded devices where processing power is limited. On a Cortex-M4 32-bit microcontroller, $\mathsf{BabySonic}$ with $\mathsf{ForkSkinny}$ achieves a speed-up of at least 2.11x (up to 4.36x) compared to state-of-the-art ZMAC with $\mathsf{SKINNY}$ for 128-bit block sizes and queries of 95B or smaller. $\mathsf{DarkSonic}$ and $\mathsf{SuperSonic}$ with $\mathsf{ForkSkinny}$ achieve a speed-up of at least 1.93x for small queries of 95B or smaller and 1.48x for large queries up to 64KB, respectively, against ZMAC with $\mathsf{SKINNY}$ for both 64- and 128-bit block sizes. Similar to ZMAC and PMAC2x, we then demonstrate the potential of our MAC family by using $\mathsf{SuperSonic}$ to construct a highly efficient, beyond-birthday secure, stateless, and deterministic authenticated encryption scheme, which we call SonicAE.

Evaluating the security of LWE-based KEMs involves two crucial metrics: the hardness of the underlying LWE problem and resistance to decryption failure attacks, both significantly influenced by the secret key and error distributions. To mitigate the complexity and timing vulnerabilities of Gaussian sampling, modern LWE-based schemes often adopt either the uniform or centered binomial distribution (CBD). This work focuses on Kyber to evaluate its security under both distributions. Compared with the CBD, the uniform distribution over the same range enhances the LWE hardness but also increases the decryption failure probability, amplifying the risk of decryption failure attacks. We introduce a majority-voting-based key recovery method, and carry out a practical decryption failure attack on Kyber512 in this scenario with a complexity of $2^{37}$. Building on this analysis, we propose uKyber, a variant of Kyber that employs the uniform distribution and parameter adjustments under the asymmetric module-LWE assumption. Compared with Kyber, uKyber maintains comparable hardness and decryption failure probability while reducing ciphertext sizes. Furthermore, we propose a multi-value sampling technique to enhance the efficiency of rejection sampling under the uniform distribution. These properties make uKyber a practical and efficient alternative to Kyber for a wide range of cryptographic applications.

The rise of microarchitectural attacks has necessitated robust detection and mitigation strategies to secure computing systems. Traditional tools, such as static and dynamic code analyzers and attack detectors, often fall short due to their reliance on predefined patterns and heuristics that lack the flexibility to adapt to new or evolving attack vectors. In this paper, we introduce for the first time a microarchitecture security assistant, built on OpenAI's GPT-3.5, which we refer to as µLAM. This assistant surpasses conventional tools by not only identifying vulnerable code segments but also providing context-aware mitigations, tailored to specific system specifications and existing security measures. Additionally, µLAM leverages real-time data from dynamic Hardware Performance Counters (HPCs) and system specifications to detect ongoing attacks, offering a level of adaptability and responsiveness that static and dynamic analyzers cannot match. For fine-tuning µLAM, we utilize a comprehensive dataset that includes system configurations, mitigations already in place for different generations of systems, dynamic HPC values, and both vulnerable and non-vulnerable source codes. This rich dataset enables µLAM to harness its advanced LLM natural language processing capabilities to understand and interpret complex code patterns and system behaviors, learning continuously from new data to improve its predictive accuracy and respond effectively in real time to both known and novel threats, making it an indispensable tool against microarchitectural threats. In this paper, we demonstrate the capabilities of µLAM by fine-tuning and testing it on code utilizing well-known cryptographic libraries such as OpenSSL, Libgcrypt, and NaCl, thereby illustrating its effectiveness in securing critical and complex software environments.

Proxy re-encryption (PRE) allows semi-honest party (called proxy) to convert a ciphertext under a public key into a ciphertext under another public key. Due to this functionality, there are various applications such as encrypted email forwarding, key escrow, and securing distributed file systems. Meanwhile, post-quantum cryptography (PQC) is one of the most important research areas because development of quantum computers has been advanced recently. In particular, there are many researches on public key encryption (PKE) algorithms selected/submitted in the NIST (National Institute of Standards and Technology) PQC standardization. However, there is no post-quantum PRE scheme secure against adaptive chosen ciphertext attacks (denoted by CCA security) while many (post-quantum) PRE schemes have been proposed so far. In this paper, we propose a bounded CCA secure PRE scheme based on CRYSTALS-Kyber which is a selected algorithm in the NIST PQC competition. To this end, we present generic constructions of bounded CCA secure PRE. Our generic constructions start from PRE secure against chosen plaintext attacks (denoted by CPA security). In order to instantiate our generic constructions, we present a CPA secure PRE scheme based on CRYSTALS-Kyber.

The proliferation of data outsourcing and cloud services has heightened privacy vulnerabilities. CKKS, among the most prominent homomorphic encryption schemes, allows computations on encrypted data, serving as a critical privacy safeguard. However, performance remains a central bottleneck, hindering widespread adoption. Existing optimization efforts often prioritize latency reduction over throughput performance. This paper presents HI-CKKS, a throughput-oriented High-performance Implementation of CKKS homomorphic encryption, addressing these challenges. Our HI-CKKS introduces a batch-supporting asynchronous execution scheme, effectively mitigating frequent data interactions and high waiting delays between hosts and servers in service-oriented scenarios. We analyze the fundamental (I)NTT primitive, which is critical in CKKS, and develop a hierarchical, hybrid high-throughput implementation. This includes efficient arithmetic module instruction set implementations, unified kernel fusion, and hybrid memory optimization strategies that significantly improve memory access efficiency and the performance of (I)NTT operations. Additionally, we propose a multi-dimensional parallel homomorphic multiplication scheme aimed at maximizing throughput and enhancing the performance of (I)NTT and homomorphic multiplication. In conclusion, our implementation is deployed on the RTX 4090, where we conduct a thorough throughput performance evaluation of HI-CKKS, enabling us to pinpoint the most effective parallel parameter settings. Compared to the CPU implementation, our system achieves throughput increases of $175.08\times$, $191.27\times$, and $679.57\times$ for NTT, INTT, and HMult, respectively. And our throughput performance still demonstrates a significant improvement, ranging from $1.54\times$ to $693.17\times$ compared to the latest GPU-based works.

This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over $\mathbb{F}_2$, we improve on a previous work and study the degree of regularity of the modeling of the exact weight SDP. Additionally, we introduce a novel technique that transforms SDP instances over $\mathbb{F}_q$ into systems of polynomial equations and thoroughly investigate the dimension of their varieties. Experimental results are provided to evaluate the complexity of solving SDP instances using our models through Gröbner bases techniques.

We present an efficient and simple multi-party private set intersection cardinality (PSI-CA) protocol that allows several parties to learn the intersection size of their private sets without revealing any other information. Our protocol is highly efficient because it only utilizes the Oblivious Key-Value Store and zero-sharing techniques, without incorporating components such as OPPRF (Oblivious Programmable Pseudorandom Function) which is the main building block of multi-party PSI-CA protocol by Gao et al. (PoPETs 2024). Our protocol exhibits better communication and computational overhead than the state-of-the-art. To compute the intersection between 16 parties with a set size of $2^{20}$ each, our PSI-CA protocol only takes 5.84 seconds and 326.6 MiB of total communication, which yields a reduction in communication by a factor of up to 2.4× compared to the state-of-the-art multi-party PSI-CA protocol of Gao et al. (PoPETs 2024). We prove that our protocol is secure in the presence of a semi-honest adversary who may passively corrupt any $(t-2)$-out-of-$t$ parties once two specific participants are non-colluding.

Private Set Intersection (PSI) is a cryptographic primitive that allows two parties to obtain the intersection of their private input sets while revealing nothing more than the intersection. PSI and its numerous variants, which compute on the intersection of items and their associated weights, have been widely studied. In this paper, we revisit the problem of finding the best item in the intersection according to weight sum introduced by Beauregard et al. (SCN '22), which is a special variant of PSI. We present two new protocols that achieve the functionality. The first protocol is based on Oblivious Pseudorandom Function (OPRF), additively homomorphic encryption and symmetric-key encryption, while the second one is based on Decisional Diffie-Hellman (DDH) assumption, additively homomorphic encryption and symmetric-key encryption. Both protocols are proven to be secure against semi-honest adversaries. Compared with the original protocol proposed by Beauregard et al. (abbreviated as the FOCI protocol), which requires all weights in the input sets to be polynomial in magnitude, our protocols remove this restriction. We compare the performance of our protocols with the FOCI protocol both theoretically and empirically. We find out that the performance of FOCI protocol is primarily affected by the size of the intersection and the values of elements’ weights in intersection when fixing set size, while the performance of ours is independent of these two factors. In particular, in the LAN setting, when the set sizes are $n=10000$, intersection size of $\frac{n}{2}$, the weights of the elements are uniformly distributed as integers from $\left[0, n-1\right]$, our DDH-based protocol has a similar run-time to the FOCI protocol. However, when the weights of the elements belonging to $\left[0, 10n-1\right]$ and $\left[0, 100n-1\right]$, our DDH-based protocol is between a factor $2\times$ and $5\times$ faster than the FOCI protocol.

Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as $f(\vec{s}) = \vec{t} \bmod q$ and $\|\vec{s}\|\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments: (i) We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds. (ii) We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits polynomial-size subtractive sets. (iii) We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathbb{Z}$-inner-products as $\mathcal{R}$-inner-products for some structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a square-free odd part. (iv) We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that $\vec{s}$ satisfying $f(\vec{s}) = \vec{t} \bmod q$ has binary coefficients, without soundness gap and with polynomial-size modulus $q$.

We further explore the explicit connections between supersingular curve isogenies and Bruhat-Tits trees. By identifying a supersingular elliptic curve $E$ over $\mathbb{F}_p$ as the root of the tree, and a basis for the Tate module $T_\ell(E)$; our main result is that given a vertex $M$ of the Bruhat-Tits tree one can write down a generator of the ideal $I \subseteq \text{End}(E)$ directly, using simple linear algebra, that defines an isogeny corresponding to the path in the Bruhat-Tits tree from the root to the vertex $M$. In contrast to previous methods to go from a vertex in the Bruhat-Tits tree to an ideal, once a basis for the Tate module is set up and an explicit map $\Phi : \text{End}(E) \otimes_{\mathbb{Z}_\ell} \to M_2( \mathbb{Z}_\ell )$ is constructed, our method does not require any computations involving elliptic curves, isogenies, or discrete logs. This idea leads to simplifications and potential speedups to algorithms for converting between isogenies and ideals.

Succinct non-interactive arguments of knowledge (SNARKs) enable a prover to produce a short and efficiently verifiable proof of the validity of an arbitrary NP statement. Recent constructions of efficient SNARKs have led to interest in using them for a wide range of applications, but unfortunately, deployment of SNARKs in these applications faces a key bottleneck: SNARK provers require a prohibitive amount of time and memory to generate proofs for even moderately large statements. While there has been progress in reducing prover time, prover memory remains an issue. In this work, we describe Scribe, a new low-memory SNARK that can efficiently prove large statements even on cheap consumer devices such as smartphones by leveraging a plentiful, but heretofore unutilized, resource: disk storage. In more detail, instead of storing its (large) intermediate state in RAM, Scribe's prover instead stores it on disk. To ensure that accesses to state are efficient, we design Scribe's prover in a *read-write streaming* model of computation that allows the prover to read and modify its state only in a streaming manner. We implement and evaluate Scribe's prover, and show that, on commodity hardware, it can easily scale to circuits of size $2^{28}$ gates while using only 2GB of memory and incurring only minimal proving latency overhead (10-35%) compared to a state-of-the-art memory-intensive baseline (HyperPlonk [EUROCRYPT 2023]) that requires much more memory. Our implementation minimizes overhead by leveraging the streaming access pattern to enable several systems optimizations that together mask I/O costs.

The Ascon authenticated encryption scheme and hash function of Dobraunig et al (Journal of Cryptology 2021) were recently selected as winner of the NIST lightweight cryptography competition. The mode underlying Ascon authenticated encryption (Ascon-AE) resembles ideas of SpongeWrap, but not quite, and various works have investigated the generic security of Ascon-AE, all covering different attack scenarios and with different bounds. This work systemizes knowledge on the mode security of Ascon-AE, and fills gaps where needed. We consider six mainstream security models, all in the multi-user setting: (i) nonce-respecting security, reflecting on the existing bounds of Chakraborty et al (ASIACRYPT 2023, ACISP 2024) and Lefevre and Mennink (SAC 2024), (ii) nonce-misuse resistance, observing a non-fixable flaw in the proof of Chakraborty et al (ACISP 2024), (iii) nonce-misuse resilience, delivering missing security analysis, (iv) leakage resilience, delivering a new security analysis that supersedes the informal proof sketch (though in a different model) of Guo et al (ToSC 2020), (v) state-recovery security, expanding on the analysis of Lefevre and Mennink, and (vi) release of unverified plaintext, also delivering missing security analysis. We also match all bounds with tight attacks. As a bonus, we systemize the knowledge on Ascon-Hash and Ascon-PRF (but there are no technical novelties here).

This paper investigates pseudorandom generation in the context of masked cryptographic implementation. Although masking and pseudorandom generators (PRGs) have been distinctly studied for a long time, little literature studies how the randomness in the masked implementation should be generated. The lack of analysis on mask-bits generators makes the practical security of masked cryptographic implementation unclear, and practitioners (e.g., designer, implementer, and evaluator) may be confused about how to realize it. This paper provides a novel viewpoint and comprehensive analyses by developing new three models, which correspond to respective practical scenarios of leakage assessment, quantitative evaluation of side-channel security (e.g., success rate), and practical deployment. We reveal what properties are required for each scenario. In particular, we support a long-held belief/folklore with a proof: for the output of PRG for masking, cryptographic security (i.e., randomness and unpredictability) is sufficient but not necessary, but only a statistical uniformity is necessary. In addition, we thoroughly investigate the SCA security of PRGs in the wild in the masking context. We conclude this paper with some recommendations for practitioners, with a proposal of leakage-resilient method of comparative performance.

This paper introduces the Pad Thai message recovery attack on REDOG, a rank-metric code-based encryption scheme selected for the second round of evaluation in the Korean Post-Quantum Cryptography (KPQC) competition. The attack exploits the low rank weight of a portion of the ciphertext to construct multiple systems of linear equations, one of which is noise-free and can be solved to recover the secret message. The Pad Thai attack significantly undermines the security of REDOG, revealing that its provided security is much lower than originally claimed.

The CL cryptosystem, introduced by Castagnos and Laguillaumie in 2015, is a linearly homomorphic encryption scheme that has seen numerous developments and applications in recent years, particularly in the field of secure multiparty computation. Designing efficient zero-knowledge proofs for the CL framework is critical, especially for achieving adaptive security for such multiparty protocols. This is a challenging task due to the particularities of class groups of quadratic fields used to instantiate the groups of unknown order required in the CL framework. In this work, we provide efficient proofs and arguments for statements involving a large number of ciphertexts. We propose a new batched proof for correctness of CL ciphertexts and new succinct arguments for correctness of a shuffle of these ciphertexts. Previous efficient proofs of shuffle for linearly homomorphic encryption were designed for Elgamal “in the exponent” which has only a limited homomorphic property. In the line of a recent work by Braun, Damgard and Orlandi (CRYPTO 2023), all the new proofs and arguments provide partial extractability, a property that we formally introduce here. Thanks to this notion, we show that bulletproof techniques, which are in general implemented with groups of known prime order, can be applied in the CL framework despite the use of unknown order groups, giving non interactive arguments of logarithmic sizes. To prove the practicability of our approach we have implemented these protocols with the BICYCL library, showing that computation and communication costs are competitive. We also illustrate that the partial extractability of our proofs provide enough guarantees for complex applications by presenting a bipartite private set intersection sum protocol which achieves security against malicious adversaries using CL encryption, removing limitations of a solution proposed by Miao et al. (CRYPTO 2020).

The fast-paced development and deployment of private messaging applications demands mechanisms to protect against the concomitant potential for abuse. While widely used end-to-end encrypted (E2EE) messaging systems have deployed mechanisms for users to verifiably report abusive messages without compromising the privacy of unreported messages, abuse reporting schemes for systems that additionally protect message metadata are still in their infancy. Existing solutions either focus on a relatively small portion of the design space or incur much higher communication and computation costs than their E2EE brethren. This paper introduces new abuse reporting mechanisms that work for any private messaging system based on onion encryption. This includes low-latency systems that employ heuristic or opportunistic mixing of user traffic, as well as schemes based on mixnets. Along the way, we show that design decisions and abstractions that are well-suited to the E2EE setting may actually impede security and performance improvements in the metadata-hiding setting. We also explore stronger threat models for abuse reporting and moderation not explored in prior work, showing where prior work falls short and how to strengthen both our scheme and others' -- including deployed E2EE messaging platforms -- to achieve higher levels of security. We implement a prototype of our scheme and find that it outperforms the best known solutions in this setting by well over an order of magnitude for each step of the message delivery and reporting process, with overheads almost matching those of message franking techniques used by E2EE encrypted messaging apps today.

Folding schemes (Kothapalli et al., CRYPTO 2022) are a conceptually simple, yet powerful cryptographic primitive that can be used as a building block to realise incrementally verifiable computation (IVC) with low recursive overhead without general-purpose non-interactive succinct arguments of knowledge (SNARK). Most folding schemes known rely on the hardness of the discrete logarithm problem, and thus are both not quantum-resistant and operate over large prime fields. Existing post-quantum folding schemes (Boneh, Chen, ePrint 2024/257) based on lattice assumptions instead are secure under structured lattice assumptions, such as the Module Short Integer Solution Assumption (MSIS), which also binds them to relatively complex arithmetic. In contrast, we construct Lova, the first folding scheme whose security relies on the (unstructured) SIS assumption. We provide a Rust implementation of Lova, which makes only use of arithmetic in hardware-friendly power-of-two moduli. Crucially, this avoids the need of implementing and performing any finite field arithmetic. At the core of our results lies a new exact Euclidean norm proof which might be of independent interest.

This paper introduces a cryptographic method that enables users to prove that an event occurred in the past and that a specified amount of time has since elapsed, without disclosing the exact timestamp of the event. The method leverages zero-knowledge proofs and an on-chain Incremental Merkle Tree to store hash commitments. By utilizing the Poseidon hash function and implementing zero-knowledge circuits in Noir, this approach ensures both the integrity and confidentiality of temporal information.

Automated cryptanalysis has seen a lot of attraction and success in the past decade, leading to new distinguishers or key-recovery attacks against various ciphers. We argue that the improved efficiency and usability of these new tools have been undervalued, especially for design processes. In this article, we break for the first time the classical iterative design paradigm for symmetric-key primitives, where constructions are built around the repetition of a round function. We propose instead a new design framework, so-called uKNIT, that allows a round-by-round optimization-led automated construction of the primitives and where each round can be entirely different from the others (the security/performance trade-off actually benefiting from this non-alignment). This new design framework being non-trivial to instantiate, we further propose a method for SPN ciphers using a genetic algorithm and leveraging advances in automated cryptanalysis: given a pool of good cipher candidates on $x$ rounds, our algorithm automatically generates and selects $(x+1)$-round candidates by evaluating their security and performance. We emphasize that our design pipeline is also the first to propose a fully automated design process, with completely integrated implementation and security analysis. We finally exemplify our new design strategy on the important use-case of low-latency cryptography, by proposing the uKNIT-BC block cipher, together with a complete security analysis and benchmarks. Compared to the state-of-the-art in low-latency ciphers (PRINCEv2), uKNIT-BC improves on all crucial security and performance directions at the same time, reducing latency by 10%, while increasing resistance against classical differential/linear cryptanalysis by more than 10%. It also reduces area by 17% and energy consumption by 44% when fixing the latency of both ciphers. As a contribution of independent interest, we discovered a generalization of the Superposition-Tweakey (STK) construction for key schedules, unlocking its application to bit-oriented ciphers.

We consider the problem of electing a leader among $n$ parties with the guarantee that each (honest) party has a reasonable probability of being elected, even in the presence of a coalition that controls a subset of parties, trying to bias the output. This notion is called ``game-theoretic fairness'' because such protocols ensure that following the honest behavior is an equilibrium and also the best response for every party and coalition. In the two-party case, Blum's commit-and-reveal protocol (where if one party aborts, then the other is declared the leader) satisfies this notion and it is also known that one-way functions are necessary. Recent works study this problem in the multi-party setting. They show that composing Blum's 2-party protocol for $\log n$ rounds in a tournament-tree-style manner results with {perfect game-theoretic fairness}: each honest party has probability $\ge 1/n$ of being elected as leader, no matter how large the coalition is. Logarithmic round complexity is also shown to be necessary if we require perfect fairness against a coalition of size $n-1$. Relaxing the above two requirements, i.e., settling for approximate game-theoretic fairness and guaranteeing fairness against only constant fraction size coalitions, it is known that there are $O(\log ^* n)$ round protocols. This leaves many open problems, in particular, whether one can go below logarithmic round complexity by relaxing only one of the strong requirements from above. We manage to resolve this problem for commit-and-reveal style protocols, showing that - $\Omega(\log n/\log\log n)$ rounds are necessary if we settle for approximate fairness against very large (more than constant fraction) coalitions; - $\Omega(\log n)$ rounds are necessary if we settle for perfect fairness against $n^\epsilon$ size coalitions (for any constant $\epsilon>0$). These show that both relaxations made in prior works are necessary to go below logarithmic round complexity. Lastly, we provide several additional upper and lower bounds for the case of single-round commit-and-reveal style protocols.

We present the first comprehensive study on thresholdizing practical OV-based signature schemes, specifically focusing on MAYO and UOV. Our approach begins by addressing the challenges associated with thresholdizing algorithms that sample solutions to linear equation systems of the form $Ax = y$, which are fundamental to OV-based signature schemes. Previous attempts have introduced levels of leakage that we deem insecure. We propose a novel minimum-leakage solution and assess its practicality. Furthermore, we explore the thresholdization of the entire functionality of these signature schemes, demonstrating their unique applications in networks and cryptographic protocols.

Ensuring transaction privacy in blockchain systems is essential to safeguard user data and financial activity from exposure on public ledgers. This paper conducts a systematization of knowledge (SoK) on privacy-preserving techniques in cryptocurrencies with native privacy features. We define and compare privacy notions such as confidentiality, k-anonymity, full anonymity, and sender-receiver unlinkability, and categorize the cryptographic techniques employed to achieve these guarantees. Our analysis highlights the trade-offs between privacy guarantees, scalability, and regulatory compliance. Finally, we evaluate the usability of the most popular private cryptocurrencies providing insights into their practical deployment and user interaction. Through this analysis, we identify key gaps and challenges in current privacy solutions, highlighting areas where further research and development are needed to enhance privacy while maintaining scalability and security.

In this paper, we put forward a new practical application of Inner-Product Functional Encryption (IPFE) that we call Message Selection functional encryption (M-Sel) which allows users to decrypt selected portions of a ciphertext. In a message selection functional encryption scheme, the plaintext is partitioned into a set of messages M = {m1, . . . , mt}. The encryption of M consists in encrypting each of its elements using distinct encryption keys. A user with a functional decryption key skx derived from a selection vector x can access a subset of M from the encryption thereof and nothing more. Our construction is generic and combines a symmetric encryption scheme and an inner product functional encryption scheme, therefore, its security is tied to theirs. By instantiating our generic construction from a DDH-based IPFE we obtain a message selection FE with constant-size decryption keys suitable for key storage in lightweight devices in the context of Internet of Things (IoT).

The interest in realizing generic PQC KEM-based PAKEs has increased significantly in the last few years. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on the well-studied PAKE protocol EKE by Bellovin and Merritt (IEEE S&P ’92), both CAKE and its variant OCAKE do not fully protect against quantum adversaries, as they rely on the Ideal Cipher (IC) model. Related and follow-up works, including Pan and Zeng (ASIACRYPT ’23), Dos Santos et al. (EUROCRYPT ’23), Alnahawi et al. (CANS ’24), and Arragia et al. (IACR ’24/308) although touching on that issue, still rely on an IC. Considering the lack of a quantum IC model and the difficulty of using the classical IC to achieve secure instantiations on public keys in general and PQC in particular, we set out to eliminate it from PAKE design. In this paper, we present the No IC Encryption (NICE)-PAKE, a (semi)-generic PAKE framework providing a quantum-safe alternative for the IC, utilizing simpler cryptographic components for the authentication step. To give a formal proof for our construction, we introduce the notions of A-Part-Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak Hint LWE assumptions, as well as its application to ring and module LWE. Notably, this side quest led to some surprising discoveries, as we concluded that the new notion is not directly interchangeable between the LWE variants, or at least not in a straightforward manner. Further, we show that our approach requires some tedious tweaking for the parameter choices in both FrodoKEM and CRYSTALS-Kyber to obtain a secure PAKE construction. We also address some fundamental issues with the common IC usage and identify differences between lattice KEMs regarding their suitability for generic PQC PAKEs, especially regarding the structure of their public keys. We believe that this work marks a further step towards achieving complete security against quantum adversaries in PQC PAKEs.

Recently, Francati et al. (Asiacrypt 2023) provided the first registered functional encryption (Reg-FE) beyond predicates. Reg-FE addresses the key escrow problem in functional encryption by allowing users to generate their own key pairs, effectively replacing the traditional private-key generator with a key curator. The key curator holds no secret information and runs deterministic algorithms to generate master public key for encryption and helper keys for decryption. However, existing Reg-FE schemes under standard assumptions require fixed data sizes, which limits their practicality in real-world applications. In this work, we introduce Multi-Function Registered Functional Encryption for Inner-Product (MultiReg-FE for IP), a novel extension of Reg-FE. It enables users to register multiple functions under a single public key. With MultiReg-FE, we achieve both Reg-FE for Unbounded Inner-Product (Unbounded IP), which removes the need to predetermine vector lengths, and Reg-FE for Attribute-Weighted Sums with Inner-Product (AWSw/IP), allowing computations over arbitrary numbers of attribute-value pairs. All our schemes achieve adaptive-IND-security. Specifically, we present: -MultiReg-FE for Inner-Product, which supports unbounded number of function vectors from each user. - Reg-FE for Unbounded Inner-Product, removing the need for preset vector lengths. - The first Reg-FE for AWSw/IP in public-key settings.

We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power Residue PRF (Damgård CRYPTO’88), a generalization of the Legendre PRF. For security parameter $\lambda$, we consider the PRF $\mathsf{Gold}_k(x)$ that maps an integer $x$ modulo a public prime $p = 2^\lambda\cdot g + 1$ to the element $(k + x)^g \bmod p$, where $g$ is public and $\log g \approx 2\lambda$. At the core of our constructions are efficient novel methods for evaluating $\mathsf{Gold}$ within two-party computation ($\mathsf{2PC}\text{-}\mathsf{Gold}$), achieving different security requirements. Here, the server $\mathcal{P}_s$ holds the PRF key $k$ whereas the client $\mathcal{P}_c$ holds the PRF input $x$, and they jointly evaluate $\mathsf{Gold}$ in 2PC. $\mathsf{2PC}\text{-}\mathsf{Gold}$ uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: • For a semi-honest $\mathcal{P}_s$ and a malicious $\mathcal{P}_c$: a $\mathsf{2PC}\text{-}\mathsf{Gold}$ that just uses a single (V)OLE correlation, and has a communication complexity of $3$ field elements ($2$ field elements if we only require a uniformly sampled key) and a computational complexity of $\mathcal{O}(\lambda)$ field operations. We refer to this as half-malicious security. • For malicious $\mathcal{P}_s$ and $\mathcal{P}_c$: a $\mathsf{2PC}\text{-}\mathsf{Gold}$ that just uses $\frac{\lambda}{4} + \mathcal{O}(1)$ VOLE correlations, and has a communication complexity of $\frac{\lambda}{4} + \mathcal{O}(1)$ field elements and a computational complexity of $\mathcal{O}(\lambda)$ field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where $\mathcal{P}_c$ repeatedly evaluates the PRF under the same key. Furthermore, we extend $\mathsf{2PC}\text{-}\mathsf{Gold}$ to Verifiable OPRFs and use the methodology from Beullens et al. (ePrint’24) to obtain strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented $\mathsf{2PC}\text{-}\mathsf{Gold}$—with (PQ) VOLEs—and benchmarked them. For example, our half-malicious (resp. malicious) $n$-batched PQ OPRFs incur about $100$B (resp. $1.9$KB) of amortized communication for $\lambda = 128$ and large enough $n$.

One-more problems like One-More Discrete Logarithm (OMDL) and One-More Diffie--Hellman (OMDH) have found wide use in cryptography, due to their ability to naturally model security definitions for interactive primitives like blind signatures and oblivious PRF. Furthermore, a generalization of OMDH called Threshold OMDH (TOMDH) has proven useful for building threshold versions of interactive protocols. However, due to their complexity it is often unclear how hard such problems actually are, leading cryptographers to analyze them in idealized models like the Generic Group Model (GGM) and Algebraic Group Model (AGM). In this work we give a complete characterization of known group-based one-more problems in the AGM, using the $Q$-DL hierarchy of assumptions defined in the work of Bauer, Fuchsbauer and Loss (CRYPTO '20). 1. Regarding (T)OMDH, we show (T)OMDH is part of the $Q$-DL hierarchy in the AGM; in particular, $Q$-OMDH is equivalent to $Q$-DL. Along the way we find and repair a flaw in the original GGM hardness proof of TOMDH, thereby giving the first correct proof that TOMDH is hard in the GGM. 2. Regarding OMDL, we show the $Q$-OMDL problems constitute an infinite hierarchy of problems in the AGM incomparable to the $Q$-DL hierarchy; that is, $Q$-OMDL is separate from $Q'$-OMDL if $Q' \neq Q$, and also separate from $Q'$-DL unless $Q = Q' = 0$.

Fixed point arithmetic (FPA) is essential to enable practical Privacy-Preserving Machine Learning. When multiplying two fixed-point numbers, truncation is required to ensure that the product maintains correct precision. While multiple truncation schemes based on Secure Multiparty Computation (MPC) have been proposed, which of the different schemes offers the best trade-off between accuracy and efficiency on common PPML datasets and models has remained underexplored. In this work, we study several different stochastic and exact truncation approaches found in the MPC literature that require different slack sizes, i.e., additional bits required by each secret share to ensure correctness. We provide novel, improved construction for each truncation approach in the semi-honest 3-PC and malicious 4-PC settings, which reduce communication and round complexity up to three times. Moreover, we propose a truncation scheme that does not introduce any communication overhead in the online phase and exactly matches the accuracy of plaintext floating-point PyTorch inference of VGG-16 on the ImageNet dataset with over 80% accuracy using shares with a bitlength of only 32. This is the first time that high PPML accuracy is demonstrated on ImageNet.