A prominent countermeasure against side channel attacks, the hiding countermeasure, typically involves shuffling operations using a permutation algorithm. Especially in the era of Post-Quantum Cryptography, the importance of the hiding coun- termeasure is emphasized due to computational characteristics like those of lattice and code-based cryptography. In this context, swiftly and securely generating permutations has a critical impact on an algorithm’s security and efficiency. The widely adopted Fisher-Yates shuffle, because of its high security and ease of implementation, is prevalent. However, it has a limitation of complexity O(𝑁) due to its sequential nature. In response, we propose a time-area trade-off swap algorithm, FSS, based on the Butterfly Network with only log(𝑁) depth, log(𝑁) works and O(1) operation time in parallel. We will calculate the maximum gain that an attacker can achieve through butterfly operations with only log(𝑁) depth from side channel analysis perspective. In particular, we will show that it is possible to derive a generalized formula of the attack complexity with higher-order side channel attacks for arbitrary input sizes through a fractal structure of the butterfly network. Furthermore, our research highlights the possibility of generating efficient and secure permutations utilizing a minimal amount of randomness.

Delegatable anonymous credentials (DACs) enable a root issuer to delegate credential-issuing power, allowing a delegatee to take a delegator role. To preserve privacy, credential recipients and verifiers should not learn anything about intermediate issuers in the delegation chain. One particularly efficient approach to constructing DACs is due to Crites and Lysyanskaya (CT-RSA '19). In contrast to previous approaches, it is based on mercurial signatures (a type of equivalence-class signature), offering a conceptually simple design that does not require extensive use of zero-knowledge proofs. Unfortunately, current constructions of ``CL-type'' DACs only offer a weak form of privacy-preserving delegation: if an adversarial issuer (even an honest-but-curious one) is part of a user's delegation chain, they can detect when the user shows its credential. This is because the underlying mercurial signature schemes allows a signer to identify his public key in a delegation chain. We propose CL-type DACs that overcome the above limitation based on a new mercurial signature scheme that provides adversarial public key class hiding which ensures that adversarial signers who participate in a user's delegation chain cannot exploit that fact to trace users. We achieve this introducing structured public parameters for each delegation level. Since the related setup produces critical trapdoors, we discuss techniques from updatable structured reference strings in zero-knowledge proof systems (Groth et al. CRYPTO '18) to guarantee the required privacy needs. In addition, we propose a simple way to realize revocation for CL-type DACs via the concept of revocation tokens. While we showcase this approach to revocation using our DAC scheme, it is generic and can be applied to any CL-type DAC system. Revocation is a vital feature that is largely unexplored and notoriously hard to achieve for DACs, thus providing revocation can help to make DAC schemes more attractive in practical applications.

A security proof for a key exchange protocol requires writing down a security definition. Authors typically have a clear idea of the level of security they aim to achieve, e.g., forward secrecy. Defining the model formally additionally requires making choices on games vs. simulation-based models, partnering, on having one or more Test queries and on adopting a style of avoiding trivial attacks: exclusion, penalizing or filtering. We elucidate the consequences, advantages and disadvantages of the different possible model choices. Concretely, we show that a model with multiple Test queries composes tightly with symmetric-key protocols while models with a single Test query require a hybrid argument that loses a factor in the number of sessions. To illustrate the usefulness of models with multiple Test queries, we prove the Naxos protocol security in said model and obtain a tighter bound than adding a hybrid argument on top of a proof in a single Test query model. Our composition model exposes partnering information to the adversary, circumventing a previous result by Brzuska, Fischlin, Warinschi, and Williams (CCS 2011) showing that the protocol needs to provide public partnering. Moreover, our baseline theorem of key exchange partnering shows that partnering by key equality provides a joint baseline for most known partnering mechanisms, countering previous criticism by Li and Schäge (CCS 2017) that security in models with existential quantification over session identifiers is non-falsifiable.

By introducing collision information, the existing side-channel Correlation-Enhanced Collision Attacks (CECAs) performed collision-chain detection, and reduced a given candidate space to a significantly smaller collision-chain space, leading to more efficient key recovery. However, they are still limited by low collision detection speed and low success rate of key recovery. To address these issues, we first give a Collision Detection framework with Genetic Algorithm (CDGA), which exploits Genetic Algorithm to detect the collision chains and has a strong capability of global searching. Secondly, we theoretically analyze the performance of CECA, and bound the searching depth of its output candidate vectors with a confidence level using a rigorous hypothesis test, which is suitable both for Gaussian and non-Gaussian leakages. This facilitates the initialization of the population. Thirdly, we design an innovative goal-directed mutation method to randomly select new gene values for replacement, thus improving efficiency and adaptability of the CDGA. Finally, to optimize the evolutionary of CDGA, we introduce roulette selection strategy to employ a probability assignment based on individual fitness values to guarantee the preferential selection of superior genes. A single-point crossover strategy is also used to introduce novel gene segments into the chromosomes, thus enhancing the genetic diversity of the population. Experiments verify the superiority of our CDGA.

Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data. As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf{P/Poly}$ require strong cryptographic assumptions which are powerful enough to build indistinguishability obfuscation. In contrast, bounded-collusion FE, in which the adversary is restricted to making at most $Q$ function queries for some polynomial $Q$ determined at setup, can be built from the minimal assumptions of public-key encryption (for public-key FE) [Sahai and Seyalioglu, CCS 2010; Gorbunov, Vaikuntanathan, and Wee, CRYPTO 2012] and secret-key encryption (for secret-key FE)[Ananth, Vaikuntanathan, TCC 2019]. In this paper, we introduce and build bounded-collusion streaming FE for any polynomial bound $Q$ from the same minimal assumptions of public-key encryption (for public-key sFE) and secret-key encryption (for secret-key sFE). Similarly to the original sFE paper of Guan, Korb, and Sahai, our scheme satisfies semi-adaptive-function-selective security which is similar to standard adaptive indistinguishability-based security except that we require all functions to be queried before any of the challenge messages. Along the way, our work also replaces a key ingredient (called $\mathsf{One}\text{-}\mathsf{sFE}$) from the original work of Guan, Korb, and Sahai with a much simpler construction based on garbled circuits.

We present an efficient layered circuit design for SHA3-256 Merkle tree verification, suitable for a GKR proof system, that achieves logarithmic verification and proof size. We demonstrate how to compute the predicate functions for our circuit in $O(\log n)$ time to ensure logarithmic verification and provide GKR benchmarks for our circuit.

Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice. In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks. We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as special cases of our solvers. Thereby, we provide a systematization of previously obtained information and used algorithms in real-world side-channel attacks. In contrast to lattice-based approaches, our framework is not limited to value leakage. For example, it can deal with noisy Hamming weight leakage or partially incorrect information. Moreover, it improves upon the recovery of the secret key from approximate hints in the form they arise in real-world attacks. Our framework has several practical applications: We exemplarily show that a recent attack can be improved; we reduce the number of traces and corresponding ciphertexts and increase the noise resistance. Further, we explain how distribution hints could be applied in the context of previous attacks and outline a potential new attack.

Many fast SNARKs apply the sum-check protocol to an $n$-variate polynomial of the form $g(x) = \text{eq}(w,x) \cdot p(x)$, where $p$ is a product of multilinear polynomials, $w \in \mathbb{F}^n$ is a random vector, and $\text{eq}$ is the multilinear extension of the equality function. In this setting, we describe an optimization to the sum-check prover that substantially reduces the cost coming from the $\text{eq}(w, x)$ factor. Our work further improves on a prior optimization by Gruen (ePrint 2023), and in the small-field case, can be combined with additional optimizations by Bagad, Domb, and Thaler (ePrint 2024), and Dao and Thaler (ePrint 2024). Over large prime-order fields, our optimization eliminates roughly $2^{n + 1}$ field multiplications compared to a standard linear-time implementation of the prover, and roughly $2^{n-1}$ field multiplications when considered on top of Gruen's optimization. These savings are about a 25% (respectively 10%) end-to-end prover speedup in common use cases, and potentially even larger when working over binary tower fields.

Non-interactive zero-knowledge (NIZK) proofs of knowledge have proven to be highly relevant for securely realizing a wide array of applications that rely on both privacy and correctness. They enable a prover to convince any party of the correctness of a public statement for a secret witness. However, most NIZKs do not natively support proving knowledge of a secret witness that is distributed over multiple provers. Previously, collaborative proofs [51] have been proposed to overcome this limitation. We investigate the notion of composability in this setting, following the Commit-and-Prove design of LegoSNARK [17]. Composability allows users to combine different, specialized NIZKs (e.g., one arithmetic circuit, one boolean circuit, and one for range proofs) with the aim of reducing the prove generation time. Moreover, it opens the door to efficient realizations of many applications in the collaborative setting such as mutually exclusive prover groups, combining collaborative and single-party proofs and efficiently implementing publicly auditable MPC (PA-MPC). We present the first, general definition for collaborative commit-and-prove NIZK (CP-NIZK) proofs of knowledge and construct distributed protocols to enable their realization. We implement our protocols for two commonly used NIZKs, Groth16 and Bulletproofs, and evaluate their practicality in a variety of computational settings. Our findings indicate that composability adds only minor overhead, especially for large circuits. We experimented with our construction in an application setting, and when compared to prior works, our protocols reduce latency by 18–55× while requiring only a fraction (0.2%) of the communication.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) allow a prover to convince a verifier of the correct execution of a large computation in private and easily-verifiable manner. These properties make zkSNARKs a powerful tool for adding accountability, scalability, and privacy to numerous systems such as blockchains and verifiable key directories. Unfortunately, existing zkSNARKs are unable to scale to large computations due to time and space complexity requirements for the prover algorithm. As a result, they cannot handle real-world instances of the aforementioned applications. In this work, we introduce Hekaton, a zkSNARK that overcomes these barriers and can efficiently handle arbitrarily large computations. We construct Hekaton via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof. Underlying this framework is a new technique for efficiently handling data that is shared between chunks that we believe could be of independent interest. We implement a distributed prover for Hekaton, and evaluate its performance on a compute cluster. Our experiments show that Hekaton achieves strong horizontal scalability (proving time decreases linearly as we increase the number of nodes in the cluster), and is able to prove large computations quickly: it can prove computations of size $2^{35}$ gates in under an hour, which is much faster than prior work. Finally, we also apply Hekaton to two applications of real-world interest: proofs of batched insertion for a verifiable key directory and proving correctness of RAM computations. In both cases, Hekaton is able to scale to handle realistic workloads with better efficiency than prior work.

In recent years, there have been several constructions combining FHE with SNARGs to add integrity guarantees to FHE schemes. Most of these works focused on improving efficiency, while the precise security model with regards to client side input privacy has remained understudied. Only recently it was shown by Manulis and Nguyen (Eurocrypt'24) that this combination does not yield IND-CCA1 security. So an interesting open question is: does the SNARG actually add any meaningful security to input privacy? We address this question in this note and give a security definition that meaningfully captures the security of the FHE plus SNARG construction.

This article presents an innovative project for a Central Bank Digital Currency (CBDC) infrastructure. Focusing on security and reliability, the proposed architecture: (1) employs post-quantum cryptography (PQC) algorithms for long-term security, even against attackers with access to cryptographically-relevant quantum computers; (2) can be integrated with a Trusted Execution Environment (TEE) to safeguard the confidentiality of transaction contents as they are processed by third-parties; and (3) uses Distributed Ledger Technology (DLT) to promote a high level of transparency and tamper resistance for all transactions registered in the system. Besides providing a theoretical discussion on the benefits of this architecture, we experimentally evaluate its components. Namely, as PQC algorithms, we consider three signature schemes being standardized by the National Institute of Standards and Technology (NIST), CRYSTALS-Dilithium, Falcon, and SPHINCS+. Those algorithms are integrated into the Hyperledger Besu (DLT) and executed both inside and outside an Intel SGX TEE environment. According to our results, CRYSTALS-Dilithium-2 combined with classical secp256k1 signatures leads to the shortest execution times when signing blocks in the DLT, reaching 1.68ms without the TEE, and 2.09ms with TEE. The same combination also displays the best results for signature verifications, achieving 0.5ms without a TEE and 1.98ms with a TEE. We also describe the main aspects of the evaluation methodology and the next steps in validating the proposed infrastructure. The conclusions drawn from our experiments is that the combination of PQC and TEE promises highly secure and effective DLT-based CBDC scenarios, ready to face the challenges of the digital financial future and potential quantum threats.

We show that the Chunka-Banerjee-Goswami authentication and key agreement scheme [Wirel. Pers. Commun., 117, 1361-1385, 2021] fails to keep user anonymity, not as claimed. It only keeps pseudonymity. Anonymous actions are designed to be unlinkable to any entity, but pseudonymous actions can be traced back to a certain entity. We also find the scheme is insecure against offline dictionary attack.

Functional bootstrapping in FHE schemes such as FHEW and TFHE allows the evaluation of a function on an encrypted message, in addition to noise reduction. Implementing programs that directly use functional bootstrapping is challenging and error-prone. In this paper, we propose a heuristic that automatically maps Boolean circuits to functional bootstrapping instructions. Unlike other approaches, our method does not limit the encrypted data plaintext space to a power-of-two size, allowing the instantiation of functional bootstrapping with smaller parameters. Furthermore, the negacyclic property of functional bootstrapping is exploited to extend the plaintext space. Despite the inherently greedy nature of the heuristic, experimental results show that the mapped circuits exhibit a significant reduction in evaluation time. Our heuristic demonstrates a $45\%$ reduction in evaluation time when compared to hand-optimized Trivium and Kreyvium implementations.

Compilers often weaken or even discard software-based countermeasures commonly used to protect programs against side-channel attacks; worse, they may also introduce vulnerabilities that attackers can exploit. The solution to this problem is to develop compilers that preserve such countermeasures. Prior work establishes that (a mildly modified version of) the CompCert and Jasmin formally verified compilers preserve constant-time, an information flow policy that ensures that programs are protected against timing side-channel attacks. However, nothing is known about preservation of speculative constant-time, a strengthening of the constant-time policy that ensures that programs are protected against Spectre-v1 attacks. We first show that preservation of speculative constant-time fails in practice by providing examples of secure programs whose compilation is not speculative constant-time using GCC (GCC -O0 and GCC -O1) and Jasmin. Then, we define a proof-of-concept compiler that distills some of the critical passes of the Jasmin compiler and use the Coq proof assistant to prove that it preserves speculative constant-time. Finally, we patch the Jasmin speculative constant-time type checker and demonstrate that all cryptographic implementations written in Jasmin can be fixed with minimal impact.

In recent years, formal verification has emerged as a crucial method for assessing security against Side-Channel attacks of masked implementations, owing to its remarkable versatility and high degree of automation. However, formal verification still faces technical bottlenecks in balancing accuracy and efficiency, thereby limiting its scalability. Former tools like maskVerif and CocoAlma are very efficient but they face accuracy issues when verifying schemes that utilize properties of Boolean functions. Later, SILVER addressed the accuracy issue, albeit at the cost of significantly reduced speed and scalability compared to maskVerif. Consequently, there is a pressing need to develop formal verification tools that are both efficient and accurate for designing secure schemes and evaluating implementations. This paper’s primary contribution lies in proposing several approaches to develop a more efficient and scalable formal verification tool called Prover, which is built upon SILVER. Firstly, inspired by the auxiliary data structures proposed by Eldib et al. and optimistic sampling rule of maskVerif, we introduce two reduction rules aimed at diminishing the size of observable sets and secret sets in statistical independence checks. These rules substantially decrease, or even eliminate, the need for repeated computation of probability distributions using Reduced Ordered Binary Decision Diagrams (ROBDDs), a time-intensive procedure in verification. Subsequently, we integrate one of these reduction rules into the uniformity check to mitigate its complexity. Secondly, we identify that variable ordering significantly impacts efficiency and optimize it for constructing ROBDDs, resulting in much smaller representations of investigated functions. Lastly, we present the algorithm of Prover, which efficiently verifies the security and uniformity of masked implementations in probing model with or without the presence of glitches. Experimental results demonstrate that our proposed tool Prover offers a better balance between efficiency and accuracy compared to other state-of-the-art tools (IronMask, CocoAlma, maskVerif, and SILVER). In our experiments, we also found an S-box that can only be verified by Prover, as IronMask cannot verify S-boxes, and both CocoAlma and maskVerif suffer from false positive issues. Additionally, SILVER runs out of time during verification.

Making the most of TFHE programmable bootstrapping to evaluate functions or operators otherwise challenging to perform with only the native addition and multiplication of the scheme is a very active line of research. In this paper, we systematize this approach and apply it to build an 8-bit FHE processor abstraction, i.e., a software entity that works over FHE-encrypted 8-bit data and presents itself to the programmer by means of a conventional-looking assembly instruction set. In doing so, we provide several homomorphic LookUp Table (LUT) dereferencing operators based on variants of the tree-based method and show that they are the most efficient option for manipulating encryptions of 8-bit data (optimally represented as two basis 16 digits). We then systematically apply this approach over a set of around 50 instructions, including, notably, conditional assignments, divisions, or fixed-point arithmetic operations. We further test the approach on several simple algorithms, including the execution of a neuron with a sigmoid activation function with 16-bit precision. We conclude the paper by comparing our work to the FHE compilers available in the state of the art. Finally, this work reveals that a very limited set of functional bootstrapping patterns is versatile and efficient enough to achieve general-purpose FHE computations beyond the boolean circuit approach. As such, these patterns may be an appropriate target for further works on advanced software optimizations or hardware implementations.

A common misconception is that the computational abilities of circuits composed of additions and multiplications are restricted to simple formulas only. Such arithmetic circuits over finite fields are actually capable of computing any function, including equality checks, comparisons, and other highly non-linear operations. While all those functions are computable, the challenge lies in computing them efficiently. We refer to this search problem as arithmetization. Arithmetization is a key problem in secure computation, as techniques like homomorphic encryption and secret sharing compute arithmetic circuits rather than the high-level programs that programmers are used to. The objective in arithmetization has typically been to minimize the number of multiplications (multiplicative size), as multiplications in most secure computation techniques are significantly more expensive to compute than additions. However, the multiplicative depth of a circuit arguably plays an even more important role in deciding the computational cost: For homomorphic encryption, it strongly affects the choice of cryptographic parameters and the number of bootstrapping operations required, which are orders of magnitude more expensive to compute than multiplications. In fact, if we can limit the multiplicative depth of a circuit such that we do not need to perform any bootstrapping, we can omit the large bootstrapping keys required to perform them all together. We argue that arithmetization should be treated as a multi-objective minimization problem, in which a trade-off can be made between a circuit's multiplicative size and depth. We present efficient depth-aware arithmetization methods for many primitive operations such as exponentiation, univariate functions, equality checks, comparisons, and ANDs and ORs, which take into account that squaring can be cheaper than arbitrary multiplications, and we study how to compose them.

Exploiting the notion of carries, we obtain improved upper bounds for the length of the shortest addition chains $\iota(2^n-1)$ producing $2^n-1$. Most notably, we show that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2}(\iota(n)-\lfloor \frac{\log n}{\log 2}\rfloor+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\{\frac{n}{2^j}\})$$ then the inequality $$\iota(2^n-1)\leq n+1+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\bigg(\{\frac{n}{2^j}\}-\xi(n,j)\bigg)+\iota(n)$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$, $\{\cdot\}$ denotes the fractional part of $\cdot$ and where $\xi(n,1):=\{\frac{n}{2}\}$ with $\xi(n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor\}$ and so on.

The field of post-quantum cryptography (PQC) is continuously evolving. Many researchers are exploring efficient PQC implementation on various platforms, including x86, ARM, FPGA, GPU, etc. In this paper, we present an Efficient CryptOgraphy CRYSTALS (ECO-CRYSTALS) implementation on standard 64-bit RISC-V Instruction Set Architecture (ISA). The target schemes are two winners of the National Institute of Standards and Technology (NIST) PQC competition: CRYSTALS-Kyber and CRYSTALS-Dilithium, where the two most time-consuming operations are Keccak and polynomial multiplication. Notably, this paper is the first to deploy Kyber and Dilithium on the 64-bit RISC-V ISA. Firstly, we propose a better scheduling strategy for Keccak, which is specifically tailored for the 64-bit dual-issue RISC-V architecture. Our 24-round Keccak permutation (Keccak-$p$[1600,24]) achieves a 59.18% speed-up compared to the reference implementation. Secondly, we apply two modular arithmetic (Montgomery arithmetic and Plantard arithmetic) in the polynomial multiplication of Kyber and Dilithium to get a better lazy reduction. Then, we propose a flexible dual-instruction-issue scheme of Number Theoretic Transform (NTT). As for the matrix-vector multiplication, we introduce a row-to-column processing methodology to minimize the expensive memory access operations. Compared to the reference implementation, we obtain a speedup of 53.85%$\thicksim$85.57% for NTT, matrix-vector multiplication, and INTT in our ECO-CRYSTALS. Finally, our ECO-CRYSTALS implementation for key generation, encapsulation, and decapsulation in Kyber achieves 399k, 448k, and 479k cycles respectively, achieving speedups of 60.82%, 63.93%, and 65.56% compared to the NIST reference implementation. Similarly, our ECO-CRYSTALS implementation for key generation, sign, and verify in Dilithium reaches 1,364k, 3,191k, and 1,369k cycles, showcasing speedups of 54.84%, 64.98%, and 57.20%, respectively.

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance varies from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we delve into the rectangle key recovery and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Not only does it encompass the four existing rectangle key recovery algorithms, but it also reveals five new types of attacks that were previously overlooked. Further, we put forward a counterpart for boomerang key recovery attacks, which supports any possible attacking parameters as well. Along with these new key recovery algorithms, we propose a framework to automatically determine the best parameters for the attack. To demonstrate the efficiency of the new key recovery algorithms, we apply them to \serpent, \aes-192, \craft, \skinny, and \deoxysbc-256 based on existing distinguishers, yielding a series of improved attacks.

Privacy-preserving machine learning (PPML) enables multiple distrusting parties to jointly train ML models on their private data without revealing any information beyond the final trained models. In this work, we study the client-aided two-server setting where two non-colluding servers jointly train an ML model on the data held by a large number of clients. By involving the clients in the training process, we develop efficient protocols for training algorithms including linear regression, logistic regression, and neural networks. In particular, we introduce novel approaches to securely computing inner product, sign check, activation functions (e.g., ReLU, logistic function), and division on secret shared values, leveraging lightweight computation on the client side. We present constructions that are secure against semi-honest clients and further enhance them to achieve security against malicious clients. We believe these new client-aided techniques may be of independent interest. We implement our protocols and compare them with the two-server PPML protocols presented in SecureML (Mohassel and Zhang, S&P'17) across various settings and ABY2.0 (Patra et al., Usenix Security'21) theoretically. We demonstrate that with the assistance of untrusted clients in the training process, we can significantly improve both the communication and computational efficiency by orders of magnitude. Our protocols compare favorably in all the training algorithms on both LAN and WAN networks.

For many pairing-based cryptographic protocols such as Direct Anonymous Attestation (DAA) schemes, the arithmetic on the first pairing subgroup $\mathbb{G}_1$ is more fundamental. Such operations heavily depend on the sizes of prime fields. At the 192-bit security level, Gasnier and Guillevic presented a curve named GG22D7-457 with CM-discriminant $D = 7$ and embedding degree $k = 22$. Compared to other well-known pairing-friendly curves at the same security level, the curve GG22D7-457 has smaller prime field size and $\rho$-value, which benefits from the fast operations on $\mathbb{G}_1$. However, the pairing computation on GG22D7-457 is not efficient. In this paper, we investigate to derive a higher performance for the pairing computation on GG22D7-457. We first propose novel formulas of the super-optimal pairing on this curve by utilizing a $2$-isogeny as GLV-endomorphism. Besides, this tool can be generalized to more generic families of pairing-friendly curves with $n$-isogenies as endomorphisms. In our paper, we provide the explicit formulas for the super-optimal pairings exploiting $2, 3$-isogenies. Finally, we make a concrete computational cost analysis and implement the pairing computations on curve GG22D7-457 using our approaches. In terms of Miller function evaluation, employing the techniques in this paper obtain a saving of $24.44\% $ in $\mathbb{F}_p$-multiplications compared to the optimal ate pairing. As for the running time, the experimental results illustrate that the Miller loop on GG22D7-457 by utilizing our methods is $26.0\%$ faster than the state-of-the-art. Additionally, the performance of the super-optimal pairing on GG22D7-457 is competitive compared to the well-known pairing-friendly curves at the 192-bit security level. These results show that GG22D7-457 becomes an attractive candidate for the pairing-based protocols. Furthermore, our techniques have the potential to enhance the applications of super-optimal pairings on more pairing-friendly curves.

The rapid evolution of post-quantum cryptography, spurred by standardization efforts such as those led by NIST, has highlighted the prominence of lattice-based cryptography, notably exemplified by CRYSTALS-Kyber. However, concerns persist regarding the security of cryptographic implementations, particularly in the face of Side-Channel Attacks (SCA). The usage of operations like the Number Theoretic Transform (NTT) in CRYSTALS-Kyber introduces vulnerabilities to SCA, especially single-trace ones, such as soft-analytical side-channel attacks. To address this threat, Ravi et al. proposed local masking as a countermeasure by randomizing the NTT’s twiddle factors, but its implementation and security implications require further investigation. This paper presents a hardware implementation of the NTT with local masking, evaluating its performance, area utilization, and security impacts. Additionally, it analyzes the vulnerabilities inherent in local masking and assesses its practical security effectiveness through non-specific t-tests, showing that there are configurations of local masking that are more prone to leakage than others.

We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code. Since its introduction in 1978, this is the first time an analysis of the McEliece cryptosystem breaks the exponential barrier.

This paper presents extensions to the OpenTitan hardware root of trust that aim at enabling high-performance lattice-based cryptography. We start by carefully optimizing ML-KEM and ML-DSA - the two primary algorithms selected by NIST for standardization - in software targeting the OTBN accelerator. Based on profiling results of these implementations, we propose tightly integrated extensions to OTBN, specifically an interface from OTBN to OpenTitan's Keccak accelerator (KMAC core) and extensions to the OTBN ISA to support operations on 256-bit vectors. We implement these extensions in hardware and show that we achieve a speedup by a factor between 6 and 9 for different operations and parameter sets of ML-KEM and ML-DSA compared to our baseline implementation on unmodified OTBN. This speedup is achieved with an increase in cell count of less than 12% in OTBN, which corresponds to an increase of less than 2% for the full Earlgrey OpenTitan core.

We show that the authentication protocol [IEEE Internet Things J., 2023, 10(1), 867-876] is not correctly specified, because the server cannot complete its computations. To revise, the embedded device needs to compute an extra point multiplication over the underlying elliptic curve. We also find the protocol cannot provide anonymity, not as claimed. It can only provide pseudonymity.

Computing the maximum from a list of secret inputs is a widely-used functionality that is employed ei- ther indirectly as a building block in secure computation frameworks, such as ABY (NDSS’15) or directly used in multiple applications that solve optimisation problems, such as secure machine learning or secure aggregation statistics. Incremental distributed point function (I-DPF) is a powerful primitive (IEEE S&P’21) that significantly reduces the client- to-server communication and are employed to efficiently and securely compute aggregation statistics. In this paper, we investigate whether I-DPF can be used to improve the efficiency of secure two-party computation (2PC) with an emphasis on computing the maximum value and the k-th (with k unknown to the computing parties) ranked value from a list of secret inputs. Our answer is affir- mative, and we propose novel secure 2PC protocols that use I-DPF as a building block, resulting in significant efficiency gains compared to the state-of-the-art. More precisely, our contributions are: (i) We present two new secure computa- tion frameworks that efficiently compute secure aggregation statistics bit-wisely or batch-wisely; (ii) we propose novel protocols to compute the maximum value, the k-th ranked value from a list of secret inputs; (iii) we provide variations of the proposed protocols that can perform batch computations and thus provide further efficiency improvements; and (iv) we provide an extensive performance evaluation for all proposed protocols. Our protocols have a communication complexity that is independent of the number of secret inputs and linear to the length of the secret input domain. Our experimental re- sults show enhanced efficiency over state-of-the-art solutions, particularly notable when handling large-scale inputs. For instance, in scenarios involving an input set of five million elements with an input domain size of 31 bits, our protocol ΠMax achieves an 18% reduction in online execution time and a 67% decrease in communication volume compared to the most efficient existing solution.

Building a Consensus platform for shared sequencing can power an ecosystem of layer-2 solutions such as rollups which are crucial for scaling blockchains (e.g.,Ethereum). However, it drastically differs from conventional Consensus for blockchains in two key considerations: • (No) Execution: A shared sequencing platform is not responsible for pre-validating blocks nor for processing state updates. Therefore, agreement is formed on a sequence of certificates of block data-availability (DA) without persisting them or obtaining blocks in full. At the same time, the platform must stream block data with very high efficiency to layer-2 entities for execution, or (in the case of rollups) for proof generation. • Builder-Exchange: A shared sequencing platform delegates to external entities to build blocks and separates it from the role of a consensus proposer. This allows an ecosystem of specialized builders to pre-validate transactions for diversified rollups, languages, and MEV exploits. However, separating the task of block-building from proposing brings a new challenge. Builders want assurances that their blocks would commit in exchange for revealing their contents, whereas validators/proposers want assurance that the data in committed blocks will be available and fees paid. Neither one trusts the other, hence the shared sequencing platform should facilitate a “fair-exchange” between builders and the sequencing network. The Espresso Sequencing Network is purpose-built to address these unique considerations. Among the main novelties of the design are (i) a three-layered DA system called Tiramisu, coupled with (ii) a costless integration of the DA with the platform’s consensus core, and (iii) a Builder-Exchange mechanism between builders and the consensus core. Note that this paper relies substantially on and can be seen as an extension of The Espresso Sequencer: HotShot Consensus and Tiramisu Data Availability [84].

‎In this paper‎, ‎using the concept of equivalence of mappings we characterize all of the one-XOR matrices which are used in hardware applications and propose a family of lightweight linear mappings for software-oriented applications in symmetric cryptography‎. ‎Then‎, ‎we investigate interleaved linear mappings and based upon this study‎, ‎we present generalized dynamic primitive LFSRs along with dynamic linear components for construction of diffusion layers. ‎From the mathematical viewpoint‎, ‎this paper presents involutive sparse binary matrices as well as sparse binary matrices with sparse inverses‎. ‎Another interesting result of our investigation is that‎, ‎by our characterization of one-XOR matrices‎, ‎the search space for finding a $k$ such that $x^n+x^k+1$ is a primitive trinomial could be reduced‎.

Side-channel-analysis (SCA) resistance with cost optimization in AES hardware implementations remains a significant challenge. While traditional masking-based schemes offer provable security, they often incur substantial resource overheads (latency, area, randomness, performance, power consumption). Alternatively, the RAMBAM scheme introduced a redundancy-based approach to control the signal-to-noise ratio, and achieves exponential leakage reduction as redundancy increases. This method results in only a slight increase in area and in power consumption, and a significant decrease in the amount of randomness needed, without any increase in latency. However, it lacks a formal security proof. In this study, we introduce a scheme, denoted STORM, that synergizes RAMBAM's methodology with the utilization of look-up-tables (LUTs) in memory (ROM/RAM) in a redundant domain. STORM, like RAMBAM, is as fast as a typical unprotected implementation and has the same latency, but has a significantly higher maximal clock frequency than RAMBAM, and consumes less than half the power. RAMBAM and STORM are code-based schemes in the sense that their set of representations is a code in the vector space $GF(2)^{8+d}$. RAMBAM requires a richer structure of a ring on $GF(2)^{8+d}$ and a ring homomorphism whereas STORM utilizes a simple vector space. In code-based-masking (CBM), as in all masking schemes, non-interference based notions (t-S/NI) are fundamental for establishing provable security. RAMBAM and STORM diverge from this approach. While CBM employs codes in vector spaces over $GF(2^8)$ for AES protection, RAMBAM and STORM use codes over $GF(2)$ without the need for t-S/NI-gadgets, leaving them both smaller and more efficient. Independence in security proofs typically means that in each individual computation (in a clock-cycle), at least one share does not participate. This approach does not work for RAMBAM where several field multiplications are executed sequentially in a cycle. However, in STORM no multiplications are performed due to its memory based tables, leaving only (independent) bitwise-XORs. Therefore, the reasoning necessary for proving security is different and STORM, unlike RAMBAM, enjoys provable security. We consider two distinct scenarios, \emph{both with provable security}: (1) STORM1 --- ``leakage-free’’ memory reads, demonstrating (1,1,0)-robustness for LUTs with redundancy 2 in the 1-probe model and for LUTs with redundancy 6 in the 2-probe model, and (2) STORM2 --- leaky memory reads, where additional protection mechanisms and a notion of memory-read robustness are introduced. STORM can be implemented not only in HW, but in SW as well. However, this paper and the proofs in it relate to STORM's HW implementations.

In this note, we introduce the MATTER Tweakable Block Cipher, designed principally for low latency in low-area hardware implementations, but that can also be implemented in an efficient and compact way in software. MATTER is a 512-bit wide balanced Feistel network with three to six rounds, using the ASCON permutation as the round function. The Feistel network defines a keyed, non-tweakable core, which is made tweakable by using the encryption of the tweak as its key. Key and tweak are 320-bit inputs. MATTER is particularly suitable for use in an OCB-like mode of operation, with an encrypted checksum for authentication.

We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing limitations of existing isogeny-based ring signatures. First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas. Second, we propose a variant of SQIsign that is resistant to the distinguisher attack with only a $\times 1.33$ increase in size and we render it to a ring signature, that we refer as $\mathsf{Erebor}$. This variant introduces a new zero-knowledge assumption that ensures full anonymity. The efficiency of $\mathsf{Erebor}$ remains comparable to that of SQIsign, with only a proportional increase due to the ring size. This results in a signature size of $0.68 \mathsf{KB}$ for 4 users and $1.35 \mathsf{KB}$ for 8 users, making it the most compact post-quantum ring signature for up to 31 users. Third, we revisit the GPS signature scheme (Asiacrypt'17), developing efficient subroutines to make the scheme more efficient and significantly reduce the resulting signature size. By integrating our scheme with the paradigm by Beullens, Katsumata, and Pintore (Asiacrypt'20), we achieve an efficient logarithmic ring signature, that we call $\mathsf{Durian}$, resulting in a signature size of $9.87 \mathsf{KB}$ for a ring of size 1024.

Hyperledger Fabric, an open-source, enterprise-grade consortium platform, employs an endorsement policy wherein a set of endorsers signs transaction proposals from clients to confirm their authenticity. The signatures from endorsers constitute the core component of endorsement. However, when dealing with dynamic transactions with high timeliness and frequent updates (e.g., stock trading, real-time ad delivery, news reporting, etc.), the current endorsement process somewhat slows down the transaction execution. Meanwhile, handling these continuously updated transactions consumes significant resources from endorsers, thereby constraining overall application efficiency. To address these issues, this paper devises a novel sanitizable and accountable endorsement scheme by proposing a sanitizable multi-signature (SMS) as the theoretical tool. Specifically, we introduce the novel concept of sanitizable multi-signature and detail its instantiation. SMS combines the advantages of multi-signature and sanitizable signature, maintaining the compactness of the signature while allowing the sanitizer to adjust the initial endorsement result to fit the updated transaction content without interacting with the endorsers, so that both the authenticity and timeliness of transactions can be ensured. Additionally, SMS incorporates an innovative accountability mechanism to trace instances of improper data updates, thereby enhancing the security and reliability of the endorsement process. We demonstrate the security of the proposed scheme through rigorous security analysis. Performance evaluations show that SMS can significantly reduce verification overhead and transaction size compared to the default ECDSA scheme in Fabric. Specifically, when verifying multiple endorsers' endorsements, our scheme exhibits a storage space reduction by approximately 30%-40% and a verification time reduction ranging from 9.2% to nearly 26.3%.

Many efficient custom protocols have been developed for two-party private set intersection (PSI), that allow the parties to learn the intersection of their private sets. However, these approaches do not yield efficient solutions in the dynamic setting when the parties’ sets evolve and the intersection has to be computed repeatedly. In this work we propose a new framework for this problem of updatable PSI — with elements being inserted and deleted — in the semihonest model based on structured encryption. The framework reduces the problem of updatable PSI to a new variant of structured encryption (StE) for an updatable set datatype, which may be of independent interest. Our final construction is a constant round protocol with worst-case communication and computation complexity that grows linearly in the size of the updates and only poly-logarithmically with the size of the accumulated sets. Our protocol is the first to support arbitrary inserts and deletes for updatable PSI.

We present Hyperion, an end-to-end verifiable e-voting scheme that allows the voters to identify their votes in cleartext in the final tally. In contrast to schemes like Selene or sElect, identification is not via (private) tracker numbers but via cryptographic commitment terms. After publishing the tally, the Election Authority provides each voter with an individual dual key. Voters identify their votes by raising their dual key to their secret trapdoor key and finding the matching commitment term in the tally. The dual keys are self-certifying in that, without the voter's trapdoor key, it is intractable to forge a dual key that, when raised to the trapdoor key, will match an alternative commitment. On the other hand, a voter can use their own trapdoor key to forge a dual key to fool any would-be coercer. Additionally, we propose a variant of Hyperion that counters the tracker collision threat present in Selene. We introduce individual verifiable views: each voter gets their own independently shuffled view of the master Bulletin Board. We provide new improved definitions of privacy and verifiability for e-voting schemes and prove the scheme secure against these, as well as proving security with respect to earlier definitions in the literature. Finally, we provide a prototype implementation and provide measurements which demonstrate that our scheme is practical for large scale elections.

We present AQQUA, a permissionless, private, and auditable payment system built on top of Quisquis. Unlike other auditable payment systems, AQQUA supports auditing, while maintaining privacy. It allows users to hold multiple accounts, perform concurrent transactions, and features a non-increasing state. AQQUA achieves auditability by introducing two authorities: one for registration and one for auditing. These authorities cannot censor transactions, thus preserving the decentralized nature of the system. Users create an initial account with the registration authority and then privately transact by using provably unlinkable updates of it. Audits can be voluntarily initiated by the users or requested by the audit authority at any time. Compliance is proved in zero-knowledge against a set of policies which include a maximum limit in the amount sent/received during a time period or in a single transfer, non-participation in a specific transaction or selective disclosure of the value exchanged. To analyze the security of AQQUA we formally define a security model for private and auditable decentralized payment systems. Using this model, we prove that AQQUA satisfies anonymity towards both the public and the auditor, theft prevention, and audit soundness.

Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien Robert have focused on the computation of $\ell$-isogenies in theta-models of level $n$ coprime to $\ell$ (which requires to use $n^g$ coordinates in dimension $g$). For cryptographic applications, we need to compute chains of $2$-isogenies, requiring to use $\geq 3^g$ coordinates in dimension $g$ with state of the art algorithms. In this paper, we present algorithms to compute chains of $2$-isogenies between abelian varieties of dimension $g\geq 1$ with theta-coordinates of level $n=2$, generalizing a previous work by Pierrick Dartois, Luciano Maino, Giacomo Pope and Damien Robert in dimension $g=2$. We propose an implementation of these algorithms in dimension $g=4$ to compute endomorphisms of elliptic curve products derived from Kani's lemma with applications to SQIsignHD and SIDH cryptanalysis. We are now able to run a complete key recovery attack on SIDH when the endomorphism ring of the starting curve is unknown within a few seconds on a laptop for all NIST SIKE parameters.

Lattice cryptography is currently a major research focus in public-key encryption, renowned for its ability to resist quantum attacks. The introduction of ideal lattices (ring lattices) has elevated the theoretical framework of lattice cryptography. Ideal lattice cryptography, compared to classical lattice cryptography, achieves more acceptable operational efficiency through fast Fourier transforms. However, to date, issues of impracticality or insecurity persist in ideal lattice problems. In order to provide a reasonable and secure trapdoor algorithm, this paper introduces the concept of "Inner Product Ring LWE" and establishes its quantum resistance and indistinguishability using knowledge of time complexity, fixed-point theory, and statistical distances. Inner product Ring LWE is easier to construct trapdoor algorithms compared to Ring LWE. Additionally, leveraging the properties of NTRU, we propose a more secure Ring SIS trapdoor algorithm.

Blockchain technology ensures accountability, transparency, and redundancy in critical applications, includ- ing IoT with embedded systems. However, the reliance on public-key cryptography (PKC) makes blockchain vulnerable to quantum computing threats. This paper addresses the urgent need for quantum-safe blockchain solutions by integrating Post- Quantum Cryptography (PQC) into blockchain frameworks. Utilizing algorithms from the NIST PQC standardization pro- cess, we aim to fortify blockchain security and resilience, partic- ularly for IoT and embedded systems. Despite the importance of PQC, its implementation in blockchain systems tailored for embedded environments remains underexplored. We propose a quantum-secure blockchain architecture, evaluating various PQC primitives and optimizing transaction sizes through tech- niques such as public-key recovery for Falcon, achieving up to 17% reduction in transaction size. Our analysis identifies Falcon-512 as the most suitable algorithm for quantum-secure blockchains in embedded environments, with XMSS as a viable stateful alternative. However, for embedded devices, Dilithium demonstrates a higher transactions-per-second (TPS) rate compared to Falcon, primarily due to Falcon’s slower sign- ing performance on ARM CPUs. This highlights the signing time as a critical limiting factor in the integration of PQC within embedded blockchains. Additionally, we integrate smart contract functionality into the quantum-secure blockchain, assessing the impact of PQC on smart contract authentication. Our findings demonstrate the feasibility and practicality of deploying quantum-secure blockchain solutions in embedded systems, paving the way for robust and future-proof IoT applications.

As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new protocols that are resistant to quantum attacks has become essential. Extensive research in this area had led to the design of several post-quantum AKA schemes. In this paper, we analyze two post-quantum AKA schemes proposed by Dharminder et al. [2022] and Pursharthi and Mishra. [2024] and demonstrate that these schemes are not secure against active adversaries. An adversary can impersonate an authorized user to the server. We then propose reliable solutions to prevent these attacks.

This report presents the security protocols and general trust architecture of the SMARTEDGE swarm computing platform. Part 1 describes the coordination protocols for use in a swarm production environment, e.g. a smart factory, and Part 2 deals with crowd-sensing scenarios characteristic of traffic-control swarms.

In crowdsourcing systems, requesters publish tasks, and interested workers provide answers to get rewards. Worker anonymity motivates participation since it protects their privacy. Anonymity with unlinkability is an enhanced version of anonymity because it makes it impossible to ``link'' workers across the tasks they participate in. Another core feature of crowdsourcing systems is worker quality which expresses a worker's trustworthiness and quantifies their historical performance. In this work, we present AVeCQ, the first crowdsourcing system that reconciles these properties, achieving enhanced anonymity and verifiable worker quality updates. AVeCQ relies on a suite of cryptographic tools, such as zero-knowledge proofs, to (i) guarantee workers' privacy, (ii) prove the correctness of worker quality scores and task answers, and (iii) commensurate payments. AVeCQ is developed modularly, where requesters and workers communicate over a platform that supports pseudonymity, information logging, and payments. To compare AVeCQ with the state-of-the-art, we prototype it over Ethereum. AVeCQ outperforms the state-of-the-art in three popular crowdsourcing tasks (image annotation, average review, and Gallup polls). E.g., for an Average Review task with 5 choices and 128 workers AVeCQ is 40% faster (including computing and verifying necessary proofs, and blockchain transaction processing overheads) with the task's requester consuming 87% fewer gas.

As a prominent category of side-channel attacks (SCAs), plaintext-checking (PC) oracle-based SCAs offer the advantages of generality and operational simplicity on a targeted device. At TCHES 2023, Rajendran et al. and Tanaka et al. independently proposed the multiple-valued (MV) PC oracle, significantly reducing the required number of queries (a.k.a., traces) in the PC oracle. However, in practice, when dealing with environmental noise or inaccuracies in the waveform classifier, they still rely on majority voting or the other technique that usually results in three times the number of queries compared to the ideal case. In this paper, we propose an improved method to further reduce the number of queries of the MV-PC oracle, particularly in scenarios where the oracle is imperfect. Compared to the state-of-the-art at TCHES 2023, our proposed method reduces the number of queries for a full key recovery by more than $42.5\%$. The method involves three rounds. Our key observation is that coefficients recovered in the first round can be regarded as prior information to significantly aid in retrieving coefficients in the second round. This improvement is achieved through a newly designed grafted tree. Notably, the proposed method is generic and can be applied to both the NIST key encapsulation mechanism (KEM) standard Kyber and other significant candidates, such as Saber and Frodo. We have conducted extensive software simulations against Kyber-512, Kyber-768, Kyber-1024, FireSaber, and Frodo-1344 to validate the efficiency of the proposed method. An electromagnetic attack conducted on real-world implementations, using an STM32F407G board equipped with an ARM Cortex-M4 microcontroller and Kyber implementation from the public library \textit{pqm4}, aligns well with our simulations.

At Eurocrypt'24, Mureau et al. formally defined the Lattice Isomorphism Problem for module lattices (module-LIP) in a number field $\mathbb{K}$, and proposed a heuristic randomized algorithm solving module-LIP for modules of rank 2 in $\mathbb{K}^2$ with a totally real number field $\mathbb{K}$, which runs in classical polynomial time for a large class of modules and a large class of totally real number field under some reasonable number theoretic assumptions. In this paper, by introducing a (pseudo) symplectic automorphism of the module, we successfully reduce the problem of solving module-LIP over CM number field to the problem of finding certain symplectic automorphism. Furthermore, we show that a weak (pseudo) symplectic automorphism can be computed efficiently, which immediately turns out to be the desired automorphism when the module is in a totally real number field. This directly results in a provable deterministic polynomial-time algorithm solving module-LIP for rank-2 modules in $\mathbb{K}^2$ where $\mathbb{K}$ is a totally real number field, without any assumptions or restrictions on the modules and the totally real number fields. Moreover, the weak symplectic automorphism can also be utilized to invalidate the omSVP assumption employed in HAWK's forgery security analysis, although it does not yield any actual attacks against HAWK itself.

We study a large family of generalized class groups of imaginary quadratic orders $O$ and prove that they act freely and (essentially) transitively on the set of primitively $O$-oriented elliptic curves over a field $k$ (assuming this set is non-empty) equipped with appropriate level structure. This extends, in several ways, a recent observation due to Galbraith, Perrin and Voloch for the ray class group. We show that this leads to a reinterpretation of the action of the class group of a suborder $O' \subseteq O$ on the set of $O'$-oriented elliptic curves, discuss several other examples, and briefly comment on the hardness of the corresponding vectorization problems.

In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group $G$ with a generator $g$ and a prime order $N$, and we want to prepare some advice of size $S$, such that we can efficiently distinguish $(g^{x},g^{y},g^{xy})$ from $(g^{x},g^{y},g^{z})$ in time $T$ for uniformly and independently chosen $x,y,z$ from $\mathbb{Z}_N$. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes, such as the Diffie–Hellman key exchange protocol. We prove that any generic preprocessing DDH algorithm (operating in any cyclic group) achieves advantage at most $O(ST^2 / N)$. This bound matches the best known attack up to poly-log factors, and confirms that DDH is as secure as the (seemingly harder) discrete logarithm problem against preprocessing attacks. Our result resolves an open question by Corrigan-Gibbs and Kogan (EUROCRYPT 2018), who proved optimal bounds for many variants of discrete logarithm problems except DDH (with an $\tilde{O}(\sqrt{ST^2/N})$ bound). We obtain our results by adopting and refining the approach by Gravin, Guo, Kwok, Lu (SODA 2021) and by Yun (EUROCRYPT 2015). Along the way, we significantly simplified and extended the above techniques which may be of independent interest. The highlights of our techniques are as follows: (1) We obtain a simpler reduction from decisional problems against $S$-bit advice to their $S$-wise XOR lemmas against zero-advice, recovering the reduction by Gravin, Guo, Kwok and Lu (SODA 2021). (2) We show how to reduce generic hardness of decisional problems to their variants in the simpler hyperplane query model proposed by Yun (EUROCRYPT 2015). This is the first work analyzing a decisional problem in Yun's model, answering an open problem proposed by Auerbach, Hoffman, and Pascual-Perez (TCC 2023). (3) We prove an $S$-wise XOR lemma of DDH in Yun's model. As a corollary, we obtain the generic hardness of the $S$-XOR DDH problem.

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data. However, due to the impending threat of quantum computers on our existing public-key cryptographic schemes and the limited resources available on IoT devices, it is important to design lightweight post-quantum cryptographic (PQC) schemes suitable for these devices. In this work, we explored the design space of learning with error-based PQC schemes to design a lightweight key-encapsulation mechanism (KEM) suitable for resource-constrained devices. We have done a scrupulous and extensive analysis and evaluation of different design elements, such as polynomial size, field modulus structure, reduction algorithm, {and} secret and error distribution of an LWE-based KEM. Our explorations led to the proposal of a lightweight PQC-KEM, Rudraksh, without compromising security. Our scheme provides security against chosen ciphertext attacks (CCA) with more than 100 bits of Core-SVP post-quantum security and belongs to the NIST-level-I security category (provide security at least as much as AES-128). We have also shown how ASCON can be used for lightweight pseudo-random number generation and hash function in the lattice-based KEMs instead of the widely used Keccak for lightweight design. Our FPGA results show that Rudraksh currently requires the least area among the PQC KEMs of similar security. Our implementation of Rudraksh provides a $\sim3\times$ improvement in terms of the area requirement compared to the state-of-the-art area-optimized implementation of Kyber, can operate at $63\%$-$76\%$ higher frequency with respect to high-throughput Kyber, and improves time-area-product $\sim2\times$ compared to the state-of-the-art compact implementation of Kyber published in HPEC 2022.

Known attacks on the tropical implementation of Stickel protocol involve solving a minimal covering problem, and this leads to an exponential growth in the time required to recover the secret key as the used polynomial degree increases. Consequently, it can be argued that Alice and Bob can still securely execute the protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some other semirings with idempotent addition (such as the max-min or fuzzy semiring). In this paper, we propose alternative methods to attacking Stickel protocol that avoid this minimal covering problem and the associated exponential time complexity. These methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain global optimization techniques.

In side-channel testing, the standard timing analysis works when the vendor can provide a measurement to indicate the execution time of cryptographic algorithms. In this paper, we find that there exists timing leakage in power/electromagnetic channels, which is often ignored in traditional timing analysis. Hence a new method of timing analysis is proposed to deal with the case where execution time is not available. Different execution time leads to different execution intervals, affecting the locations of plaintext and ciphertext transmission. Our method detects timing leakage by studying changes in plaintext-ciphertext correlation when traces are aligned forward and backward. Experiments are then carried out on different cryptographic devices. Furthermore, we propose an improved timing analysis framework which gives appropriate methods for different scenarios.

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

Akavia, Gentry, Halevi, and Vald introduced the security notion of function-chosen-plaintext-attack (FuncCPA security) for public-key encryption schemes. FuncCPA is defined by adding a functional re-encryption oracle to the IND-CPA game. This notion is crucial for secure computation applications where the server is allowed to delegate a part of the computation to the client. Dodis, Halevi, and Wichs introduced a stronger variant called FuncCPA$^+$. They showed FuncCPA$^+$ implies FuncCPA and conjectured that FuncCPA$^+$ is strictly stronger than FuncCPA. They left an open problem to clarify the relationship between these variants. Contrary to their conjecture, we show that FuncCPA is equivalent to FuncCPA$^+$. We show it by two proofs with a trade-off between the number of queries and the number of function inputs. Furthermore, we show these parameters determine the security levels of FuncCPA and FuncCPA$^+$.

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, and recent works have made significant progress on reducing the concrete computational costs of single-server PIR. However, existing constructions have high communication overhead, especially for databases with small records. In this work, we introduce Respire, a lattice-based PIR scheme tailored for databases of small records. To retrieve a single record from a database with over a million 256-byte records, the Respire protocol requires just 6.1 KB of online communication; this is a 5.9x reduction compared to the best previous lattice-based scheme. Moreover, Respire naturally extends to support batch queries. Compared to previous communication-efficient batch PIR schemes, Respire achieves a 3.4-7.1x reduction in total communication while maintaining comparable throughput (200-400 MB/s). The design of Respire relies on new query compression and response packing techniques based on ring switching in homomorphic encryption.

Orion (Xie et al. CRYPTO'22) is a recent plausibly post-quantum zero-knowledge argument system with a linear time prover. It improves over Brakedown (Golovnev et al. ePrint'21 and CRYPTO'23) by reducing the proof size and verifier complexity to be polylogarithmic and additionally adds the zero-knowledge property. The argument system is demonstrated to be concretely efficient with a prover time being the fastest among all existing succinct proof systems and a proof size that is an order of magnitude smaller than Brakedown. Since its publication in CRYPTO 2022, two revisions have been made to the zk-SNARK. First, there was an issue with how zero-knowledge was handled. Second, Orion was discovered to be unsound, which was then repaired through the use of a commit-and-prove SNARK as an "outer" SNARK. As we will show in this paper, unfortunately, Orion in its current revision is still unsound (with and without the zero-knowledge property) and we will demonstrate practical attacks on it. We then show how to repair Orion without additional assumptions, with the resuling polynomial commitment denoted as Scorpius, which requires non-trivial fixes when aiming to preserve the linear time prover complexity. The proposed fixes lead to an even improved efficiency, i.e., smaller proof size and verifier time, over the claimed efficiency of the initial version of Orion. We also apply the recent ideas of Diamond and Posen (CiC'24) to make the challenge in Orion logarithmically sized. Moreover, we provide the first rigorous security proofs and explicitly consider multi-point openings and non-interactivity. While revisiting Orion we make some additional contributions which might be of independent interest, most notable an improved code randomization technique that retains the minimum relative distance.

In this paper, we formulate a special class of systems of linear equations over finite fields that appears naturally in the provable security analysis of several MAC and PRF modes of operation. We derive lower bounds on the number of solutions for such systems adhering to some predefined restrictions, and apply these lower bounds to derive tight PRF security for several constructions. We show security up to $2^{3n/4}$ queries for the single-keyed variant of the Double-block Hash-then-Sum (DBHtS) construction, called 1k-DBHtS, under appropriate assumptions on the underlying hash function. We show that the single-key variants of PMAC+ and LightMAC+, called 1k-PMAC+ and 1k-LightMAC+ achieve the required hash function properties, and thus, achieve $3n/4$-bit security. Additionally, we show that the sum of $r$ independent copies of the Even-Mansour cipher is a secure PRF up to $2^{\frac{r}{r+1}n}$ queries.

Traceable Receipt-free Encryption (TREnc) is a verifiable public-key encryption primitive introduced at Asiacrypt 2022. A TREnc allows randomizing ciphertexts in transit in order to remove any subliminal information up to a public trace that ensures the non-malleability of the underlying plaintext. A remarkable property of TREnc is the indistinguishability of the randomization of chosen ciphertexts against traceable chosen-ciphertext attacks (TCCA). This property can support applications like voting, and it was shown that receipt-free non-interactive voting, where voters are unable to convince any third party of the content of their vote, can be generically built from a TREnc. While being a very promising primitive, the few existing TREnc mechanisms either require a secret coin CRS or are fairly demanding in time and space requirements. Their security proofs also come with a linear security degradation in the number of challenge ciphertexts. We address these limitations and offer two efficient public coin TREnc mechanisms tailored for the two common tallying approaches in elections: homomorphic and mixnet-based. The TCCA security of our mechanisms also enjoys an almost-tight reduction to SXDH, based on a new randomizable technique of independent interest in the random oracle model. A Rust implementation of our TREnc mechanisms demonstrates that we can verifiably encrypt 64 bits in less than a second, and full group elements in around 30 ms., which is sufficient for most real-world applications. While comparing with other solutions, we show that our approaches lead to the most efficient non-interactive receipt-free voting system to date.

FRI is a cryptographic protocol widely deployed today as a building block of many efficient SNARKs that help secure transactions of hundreds of millions of dollars per day. The Fiat-Shamir security of FRI—vital for understanding the security of FRI-based SNARKs—has only recently been formalized and established by Block et al. (ASIACRYPT ’23). In this work, we complement the result of Block et al. by providing a thorough concrete security analysis of non-interactive FRI under various parameter settings from protocols deploying (or soon to be deploying) FRI today. We find that these parameters nearly achieve their desired security targets (being at most 1-bit less secure than their targets) for non-interactive FRI with respect to a certain security conjecture about the FRI Protocol. However, in all but one set of parameters, we find that the provable security of non-interactive FRI under these parameters is severely lacking, being anywhere between 21- and 63-bits less secure than the conjectured security. The conjectured security of FRI assumes that known attacks are optimal, the security of these systems would be severely compromised should a better attack be discovered. In light of this, we present parameter guidelines for achieving 100-bits of provable security for non-interactive FRI along with a methodology for tuning these parameters to suit the needs of protocol designers.

Servan-Schreiber et al. (S&P 2023) presented a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function. Their construction relies on costly non-interactive secret-shared proofs and is not secure in post-quantum setting. We give a construction of PACL from publicly verifiable secret sharing (PVSS) under short integer solution (SIS). Our construction adapts the Gentry et al’s scheme (Eurocrypt 2022) for post-quantum setting based on learning with error assumption (LWE). The implementation of our PACL with different files showed that it is feasible even at different sizes, and should remain so even with large secret vectors. This construction has many applications for access control by applying FSS. We show how to apply the proposed PACL construction to secure data retrieval. We also present a scheme for secure data retrieval with access control, which might be of independent interest.

Private Stream Aggregation (PSA) allows clients to send encryptions of their private values to an aggregator that is then able to learn the sum of these values but nothing else. It has since found many applications in practice, e.g. for smart metering or federated learning. In 2018, Becker et al. proposed the first lattice-based PSA scheme LaPS (NDSS 2018), with putative post-quantum security, which has subsequently been patented. In this paper, we describe two attacks on LaPS that break the claimed aggregator obliviousness security notion, where the second attack even allows to recover the secret keys of the clients, given enough encryptions. Moreover, we review the PSA literature for other occurrences of the responsible flawed proof steps. By explicitly tracking down and discussing these flaws, we clarify and hope to contribute to the literature on PSA schemes, in order to prevent further insecure schemes in practice. Finally, we point out that a Real-or-Random variant of the security notion that is often used as a substitute to make proofs easier, is not well-defined and potentially weaker than the standard PSA security notion. We propose a well defined variant and show that it is equivalent to the standard security notion of PSA under mild assumptions.

We show that the authentication key agreement scheme [IEEE Trans. Smart Grid, 2023, 14(5), 3816-3827] is flawed due to its inconsistent computations. We also show that the scheme fails to keep anonymity, not as claimed.

We investigate shift-invariant vectorial Boolean functions on $n$ bits that are lifted from Boolean functions on $k$ bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its lifted functions is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.

Let K be a commutative ring. We refer to a connected bipartite graph G = G_n(K) with partition sets P = K^n (points) and L = K^n (lines) as an affine graph over K of dimension dim(G) = n if the neighbourhood of each vertex is isomorphic to K. We refer to G as an algebraic affine graph over K if the incidence between a point (x_1, x_2, . . . , x_n) and line [y_1, y_2, . . . , y_n] is defined via a system of polynomial equations of the kind f_i = 0 where f_i ∈ K[x_1, x_2, . . . , x_n, y_1, y_2, . . . , y_n]. We say that an affine algebraic graph is a Jordan-Gauss graph over K if the incidences between points and lines are given by a quadratic system of polynomial equations, and the neighbourhood of each vertex is given as a solution set of the system of linear equations in row-echelon form. For each integral domain K we consider the known explicit construction of the family of Jordan-Gauss graphs A(n, K), n = 2, 3, . . . with cycle indicator ≥ 2n + 2. Additionally several constructions of families of edge intransitive Jordan-Gauss graphs over K of increasing girth with well defined projective limit will be presented. This projective limit is a forest defined by the system of algebraic equations. In the case K = F_q, q ≥ 3 we present results of computer experiments for the evaluation of girth, cycle indicator, diameter and the second largest eigenvalue of the constructed graphs, and we formulate several conjectures on their properties. One of the conjectures is that the girth of A(n, F_q) is 2[(n+ 5)/2]. We discuss briefly some applications of Jordan-Gauss graphs of large girth to Graph Theory, Algebraic Geometry and the theory of LDPC codes; and we consider ideas to use groups related to these graphs in Noncommutative Cryptography and Stream Ciphers Design.

Auditing throughout a fiscal year is integral to organizations with transactional activity. Organizations transact with each other and record the details for all their economical activities so that a regulatory committee can verify the lawfulness and legitimacy of their activity. However, it is computationally infeasible for the committee to perform all necessary checks for each organization. To overcome this, auditors assist in this process: organizations give access to all their internal data to their auditors, who then produce reports regarding the consistency of the organization's data, alerting the committee to any inconsistencies. Despite this, numerous issues that result in fines annually revolve around such inconsistencies in bookkeeping across organizations. Notably, committees wishing to verify the correctness of auditor-provided reports need to redo all their calculations; a process which is computationally proportional to the number of organizations. In fact, it becomes prohibitive when considering real-world settings with thousands of organizations. In this work, we propose two protocols, CLOSC and CLOLC, whose goals are to enable auditors and a committee to verify the consistency of transactions across different ledgers. Both protocols ensure that for every transaction recorded in an organization's ledger, there exists a dual one in the ledger of another organization while safeguarding against other potential attacks. Importantly, we minimize the information leakage to auditors and other organizations and guarantee three crucial security and privacy properties that we propose: (i) transaction amount privacy, (ii) organization-auditor unlinkability, and (iii) transacting organizations unlinkability. At the core of our protocols lies a two-tier ledger architecture alongside a suite of cryptographic tools. To demonstrate the practicality and scalability of our designs, we provide extensive performance evaluation for both CLOSC and CLOLC. Our numbers are promising, i.e., all computation and verification times lie in the range of seconds, even for millions of transactions, while the on-chain storage costs for an auditing epoch are encouraging i.e. in the range of GB for millions of transactions and thousands of organizations.

Handling congestion in blockchain systems is a fundamental problem given that the security and decentralization objectives of such systems lead to designs that compromise on (horizontal) scalability (what sometimes is referred to as the ``blockchain trilemma''). Motivated by this, we focus on the question whether it is possible to design a transaction inclusion policy for block producers that facilitates fee and delay predictability while being incentive compatible at the same time. Reconciling these three properties is seemingly paradoxical given that the dominant approach to transaction processing is based on first-price auctions (e.g., as in Bitcoin) or dynamic adjustment of the minimum admissible fee (e.g. as in Ethereum EIP-1559) something that breaks fee predictability. At the same time, in fixed fee mechanisms (e.g., as in Cardano), fees are trivially predictable but are subject to relatively inexpensive bribing or denial of service attacks where transactions may be delayed indefinitely by a well funded attacker, hence breaking delay predictability. In this work, we set out to address this problem by putting forward blockchain space tokenization (BST), namely a new capability of a blockchain system to tokenize its capacity for transactions and allocate it to interested users who are willing to pay ahead of time for the ability to post transactions regularly for a period of time. We analyze our system in the face of worst-case transaction-processing attacks by introducing a security game played between the mempool mechanism and an adversary. Leveraging this framework, we prove that BST offers predictable and asymptotically optimal delays, predictable fees, and is incentive compatible, thus answering the question posed in the affirmative.

Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a kind of proof system that enables a prover to convince a verifier that an NP statement is true efficiently. In the last decade, various studies made a lot of progress in constructing more efficient and secure zk-SNARKs. Our research focuses on designated-verifier zk-SNARKs, where only the verifier knowing some secret verification state can be convinced by the proof. A natural idea of getting a designated-verifier zk-SNARK is encrypting a publicly-verifiable zk-SNARK's proof via public-key encryption. This is also the core idea behind the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain designated-verifier zk-SNARKs. However, the transformation only applies to zk-SNARKs which requires the complicated trusted setup phase and sticks on storage-expensive common reference strings. The loss of the secret verification state also makes the proof immediately lose the designated-verifier property. To address these issues, we first define "strong designated-verifier" considering the case where the adversary has access to the secret verification state, then propose a construction of strong designated-verifier zk-SNARKs. The construction inspired by designated verifier signatures based on two-party ring signatures does not use encryption and can be applied on any public-verifiable zk-SNARKs to yield a designated-verifiable variant. We introduce our construction under the circuit satisfiability problem and implement it in Circom, then test it on different zk-SNARKs, showing the validity of our construction.

Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) protocols introduced to achieve load-balancing in large-scale networks, which is defined as the maximum communication complexity required by any one player within the protocol execution. Towards the goal of achieving low bottleneck complexity, prior works proposed MPC protocols for computing symmetric functions in the correlated randomness model, where players are given input-independent correlated randomness in advance. However, the previous protocols with polylogarithmic bottleneck complexity in the number of players $n$ require a large amount of correlated randomness that is linear in $n$, which limits the per-party efficiency as receiving and storing correlated randomness are the bottleneck for efficiency. In this work, we present for the first time MPC protocols for symmetric functions such that bottleneck complexity and the amount of correlated randomness are both polylogarithmic in $n$, assuming collusion of size at most $n-o(n)$ players. Furthermore, one of our protocols is even computationally efficient in that each player performs only $\mathrm{polylog}(n)$ arithmetic operations while the computational complexity of the previous protocols is $O(n)$. Technically, our efficiency improvements come from novel protocols based on ramp secret sharing to realize basic functionalities with low bottleneck complexity, which we believe may be of interest beyond their applications to secure computation of symmetric functions.

Deduplication is a vital preprocessing step that enhances machine learning model performance and saves training time and energy. However, enhancing federated learning through deduplication poses challenges, especially regarding scalability and potential privacy violations if deduplication involves sharing all clients’ data. In this paper, we address the problem of deduplication in a federated setup by introducing a pioneering protocol, Efficient Privacy-Preserving Multi-Party Deduplication (EP-MPD). It efficiently removes duplicates from multiple clients’ datasets without compromising data privacy. EP-MPD is constructed in a modular fashion, utilizing two novel variants of the Private Set Intersection protocol. Our extensive experiments demonstrate the significant benefits of deduplication in federated learning of large language models. For instance, we observe up to 19.61% improvement in perplexity and up to 27.95% reduction in running time. EP-MPD effectively balances privacy and performance in federated learning, making it a valuable solution for large-scale applications.

Isogeny-based schemes often come with special requirements on the field of definition of the involved elliptic curves. For instance, the efficiency of SQIsign, a promising candidate in the NIST signature standardisation process, requires a large power of two and a large smooth integer $T$ to divide $p^2-1$ for its prime parameter $p$. We present two new methods that combine previous techniques for finding suitable primes: sieve-and-boost and XGCD-and-boost. We use these methods to find primes for the NIST submission of SQIsign. Furthermore, we show that our methods are flexible and can be adapted to find suitable parameters for other isogeny-based schemes such as AprèsSQI or POKE. For all three schemes, the parameters we present offer the best performance among all parameters proposed in the literature.

In this work, we introduce enhanced high-order masking techniques tailored for Dilithium, the post-quantum signature scheme recently standardized by NIST. We improve the masked generation of the masking vector $\vec{y}$, based on a fast Boolean-to-arithmetic conversion modulo $q$. We also describe an optimized gadget for the high-order masked rejection sampling, with a complexity independent from the size of the modulus $q$. We prove the security of our gadgets in the classical ISW $t$-probing model. Finally, we detail our open-source C implementation of these gadgets integrated into a fully masked Dilithium implementation, and provide an efficiency comparison with previous works.

In this short note, we introduce a specific class of rank two lattices over CM fields endowed with additional symmetries, which are involved in the decomposition of algebraic integers in Hermitian squares. As an application, we show an elementary reduction from the module-LIP problem in rank 2 over a CM or totally real number field to the finding of a square basis in such lattices.

In this article we present a non-uniform reduction from rank-2 module-LIP over Complex Multiplication fields, to a variant of the Principal Ideal Problem, in some fitting quaternion algebra. This reduction is classical deterministic polynomial-time in the size of the inputs. The quaternion algebra in which we need to solve the variant of the principal ideal problem depends on the parameters of the module-LIP problem, but not on the problem's instance. Our reduction requires the knowledge of some special elements of this quaternion algebras, which is why it is non-uniform. In some particular cases, these elements can be computed in polynomial time, making the reduction uniform. This is the case for the Hawk signature scheme: we show that breaking Hawk is no harder than solving a variant of the principal ideal problem in a fixed quaternion algebra (and this reduction is uniform).

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

The one-time pad cipher is renowned for its theoretical perfect security, yet its practical deployment is primarily hindered by the key-size and distribution challenge. This paper introduces a novel approach to key distribution called q-stream, designed to make symmetric-key cryptography, and the one-time pad cipher in particular, a viable option for contemporary secure communications, and specifically, post-quantum cryptography, leveraging quantum noise and combinatorics to ensure secure and efficient key-distribution between communicating parties. We demonstrate that our key-distribution mechanism has a variable, yet quantifiable hardness of at least 504 bits, established from immutable mathematical laws, rather than conjectured-intractability, and how we overcome the one-time pad key-size issue with a localised quantum-noise seeded key-generation function, having a system hardness of at least 2304 bits, while introducing sender authentication and message integrity. Whilst the proposed solution has potential applications in fields requiring very high levels of security, such as military communications and large financial transactions, we show from our research with a prototype of q-stream, that it is sufficiently practical and scaleable for use in common browser-based web-applications, without any modification to the browser (i.e. plug-ins), running above SSL/TLS at the application level, where in tests, it achieved a key-distribution rate of around 7 million keys over a 5 minute surge-window, in a single (multi-threaded) instance of q-stream.

We show that the data storage scheme [IEEE/ACM Trans. Netw., 2023, 31(4), 1550-1565] is flawed due to the false secret sharing protocol, which requires that some random $4\times 4$ matrixes over the finite field $F_p$ (a prime $p$) are invertible. But we find its mathematical proof for invertibility is incorrect. To fix this flaw, one needs to check the invertibility of all 35 matrixes so as to generate the proper 7 secret shares.

Oblivious Transfer (OT) is a fundamental cryptographic primitive, becoming a crucial component of a practical secure protocol. OT is typically implemented in software, and one way to accelerate its running time is by using hardware implementations. However, such implementations are vulnerable to side-channel attacks (SCAs). On the other hand, protecting interactive protocols against SCA is highly challenging because of their longer secrets (which include inputs and randomness), more complicated design, and running multiple instances. Consequently, there are no truly practical leakage-resistant OT protocols yet. In this paper, we introduce two tailored indistinguishability-based security definitions for leakage-resilient OT, focusing on protecting the sender's state. Second, we propose a practical semi-honest secure OT protocol that achieves these security levels while minimizing the assumptions on the protocol's building blocks and the use of a secret state. Finally, we extend our protocol to support sequential composition and explore efficiency-security tradeoffs.

Matrix congruential generators is an important class of pseudorandom number generators. In this paper we show how to predict a class of Matrix congruential generators matrix congruential generators with unknown parameters. Given a few truncated digits of high-order bits output by a matrix congruential generator, we give a method based on lattice reduction to recover the parameters and the initial state of the generator.

Clustering is a crucial unsupervised learning method extensively used in the field of data analysis. For analyzing big data, outsourced computation is an effective solution but privacy concerns arise when involving sensitive information. Fully homomorphic encryption (FHE) enables computations on encrypted data, making it ideal for such scenarios. However, existing privacy-preserving clustering based on FHE are often constrained by the high computational overhead incurred from FHE, typically requiring decryption and interactions after only one iteration of the clustering algorithm. In this work, we propose a more efficient approach to evaluate the one-hot vector for the index of the minimum in an array with FHE, which fully exploits the parallelism of single-instruction-multiple-data of FHE schemes. By combining this with FHE bootstrapping, we present a practical FHE-based k-means clustering protocol whose required round of interactions between the data owner and the server is optimal, i.e., accomplishing the entire clustering process on encrypted data in a single round. We implement this protocol using the CKKS FHE scheme. Experiments show that our protocol significantly outperforms the state-of-the-art FHE-based k-means clustering protocols on various public datasets and achieves comparable accuracy to plaintext result. Additionally, We adapt our protocol to support mini-batch k-means for large-scale datasets and report its performance.

We propose a generalization of Zhandry’s compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry’s technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle’s database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.

Strike-lists are a common technique for rollback and replay prevention in protocols that require that clients remain anonymous or that their current position in a state machine remain confidential. Strike-lists are heavily used in anonymous credentials, e-cash schemes, and trusted execution environments, and are widely deployed on the web in the form of Privacy Pass (PoPETS '18) and Google Private State Tokens. In such protocols, clients submit pseudorandom tokens associated with each action (e.g., a page view in Privacy Pass) or state transition, and the token is added to a server-side list to prevent reuse. Unfortunately, the size of a strike-list, and hence the storage required by the server, is proportional to the total number of issued tokens, $N \cdot t$, where $N$ is the number of clients and $t$ is the maximum number of tickets per client. In this work, we ask whether it is possible to realize a strike-list-like functionality, which we call the anonymous tickets functionality, with storage requirements proportional to $N \log(t)$. For the anonymous tickets functionality we construct a secure protocol from standard assumptions that achieves server storage of $O(N)$ ciphertexts, where each ciphertext encrypts a message of length $O(\log(t))$. We also consider an extension of the strike-list functionality where the server stores an arbitrary state for each client and clients advance their state with some function $s_i\gets f(s_{i-1},\mathsf{auxinput})$, which we call the anonymous outsourced state-keeping functionality. In this setting, malicious clients are prevented from rolling back their state, while honest clients are guaranteed anonymity and confidentiality against a malicious server. We achieve analogous results in this setting for two different classes of functions. Our results rely on a new technique to preserve client anonymity in the face of selective failure attacks by a malicious server. Specifically, our protocol guarantees that misbehavior of the server either (1) does not prevent the honest client from redeeming a ticket or (2) provides the honest client with an escape hatch that can be used to simulate a redeem in a way that is indistinguishable to the server.

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $\mathbf{x}$ and the proof $\boldsymbol{\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle \mathbf{q},(\mathbf{x} \| \boldsymbol{\pi}) \rangle$ jointly to $\mathbf{x}$ and $\boldsymbol{\pi}$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of DPPs, obtaining the following results: - Small-field DPP. For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a DPP for proving that there exists $\mathbf{w}$ such that $C(\mathbf{x}, \mathbf{w})=1$ with a proof $\boldsymbol{\pi}$ of length $S\cdot\mathsf{poly}(|\mathbb{F}|)$ and soundness error $\varepsilon=O(1 / \sqrt{|\mathbb{F}|})$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. - Large-field DPP. If $|\mathbb{F}|\ge\mathsf{poly}(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ and proof length $O(S)$ (in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. - Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field $\mathbb{F}$ up to some constant factor $c>1$, independent of $\mathbb{F}$. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). - Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.

EagleSign is one of the 40 “Round 1 Additional Signatures” that is accepted for consideration in the supplementary round of the Post-Quantum Cryptography standardization process, organized by NIST. Its design is based on structured lattices, and it boasts greater simplicity and performance compared to the two lattice signatures already selected for standardization: Falcon and Dilithium. In this paper, we show that those claimed advantages come at the cost of security. More precisely, we show that the distribution of EagleSign signatures leaks information about the private key, to the point that only a few hundred signatures on arbitrary known messages suffice for a full key recovery, for all proposed parameters. A related vulnerability also affects EagleSign-V2, a subsequent version of the scheme specifically designed to thwart the initial attack. Although a larger number of signatures is required for key recovery, the idea of the attack remains largely similar. Both schemes come with proofs of security that we show are flawed.

The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing the internal differential characteristic. Further more, we figure out the expected size of collision subsets in internal differentials, by analyzing the collision probability of the digests rather than the intermediate states input to the last nonlinear layer. These techniques enhance the analysis of internal differentials, leading to the best collision attacks on four round-reduced variants of the SHA-3 instances. In particular, the number of attacked rounds is extended to 5 from 4 for SHA3-384, and to 6 from 5 for SHAKE256.

Payment channels are one of the most prominent off-chain scaling solutions for blockchain systems. However, regulatory institutions have difficulty embracing them, as the channels lack insights needed for Anti-Money Laundering (AML) auditing purposes. Our work tackles the problem of a formal reliable and controllable inspection of off-ledger payment channels, by offering a novel approach for maintaining and reliably auditing statistics of payment channels. We extend a typical trustless Layer 2 protocol and provide a lightweight and scalable protocol such that: - every state channel is provably auditable w.r.t. a configurable set of policy queries, such that a regulator can retrieve reliable insights about the channel; - no information beyond the answers to auditing queries is leaked; - the cryptographic operations are inexpensive, the setup is simple, and storage complexity is independent of the transaction graph's size. We present a concrete protocol, based on Hydra Isomorphic State Channels (FC'21), and tie the creation of a state channel to real-world identifiers, both in a plain and privacy-preserving manner. For this, we employ verifiable credentials for decentralized identifiers, specifically verifiable Legal Entity Identifiers (vLEI) that increasingly gain traction for financial service providers and regulated institutions.

Enhanced pqsigRM is a code-based hash-and-sign scheme proposed to the second National Institute of Standards and Technology call for post-quantum signatures. The scheme is based on the $(U,U+V)$-construction and it enjoys remarkably small signature lengths, about $1$KBytes for a security level of $128$ bits. Unfortunately we show that signatures leak information about the underlying $(U,U+V)$-structure. It allows to retrieve the private-key with~$100, 000$ signatures.

The aim of an algebraic attack is to find the secret key by solving a collection of relations that describe the internal structure of a cipher for observations of plaintext/cipher-text pairs. Although algebraic attacks are addressed for cryptanalysis of block and stream ciphers, there is a limited understanding of the impact of algebraic representation of the cipher on the efficiency of solving the resulting collection of equations. In this paper, we investigate on how different S-box representations affect the complexity of algebraic attacks, in an empirical manner. In the literature some algebraic properties are intuitively proposed to evaluate optimality of an algebraic description of S-boxes for algebraic cryptanalysis. In this paper, we compare different S-box representation for algebraic cryptanalysis with doing experiments with SR family of block ciphers. We also show that the so-called \textit{Forward-Backward} representation which is in contrast with all mentioned criteria for optimal representations criteria, practically gives better results than the compliant representations. We also compare the representations for both $GF(2)$ and $GF(2^n)$ fields.

Model quantization has become a common practice in machine learning (ML) to improve efficiency and reduce computational/communicational overhead. However, adopting quantization in privacy-preserving machine learning (PPML) remains challenging due to the complex internal structure of quantized operators, which leads to inefficient protocols under the existing PPML frameworks. In this work, we propose a new PPML paradigm that is tailor-made for and can benefit from quantized models. Our main observation is that lookup tables can ignore the complex internal constructs of any functions which can be used to simplify the quantized operator evaluation. We view the model inference process as a sequence of quantized operators, and each operator is implemented by a lookup table. We then develop an efficient private lookup table evaluation protocol, and its online communication cost is only $\log n$, where $n$ is the size of the lookup table. On a single CPU core, our protocol can evaluate $2^{26}$ tables with 8-bit input and 8-bit output per second. The resulting PPML framework for quantized models offers extremely fast online performance. The experimental results demonstrate that our quantization strategy achieves substantial speedups over SOTA PPML solutions, improving the online performance by $40\sim 60 \times$ w.r.t. convolutional neural network (CNN) models, such as AlexNet, VGG16, and ResNet18, and by $10\sim 25 \times$ w.r.t. large language models (LLMs), such as GPT-2, GPT-Neo, and Llama2.

The authors of Jolt [AST24] pioneered a unique method for creating zero-knowledge virtual machines, known as the lookup singularity. This technique extensively uses lookup tables to create virtual machine circuits. Despite Jolt’s performance being twice as efficient as the previous state-of-the-art1 , there is potential for further enhancement. The initial release of Jolt uses Spartan [Set20] and Hyrax [WTs+ 18] as their backend, leading to two constraints. First, Hyrax employs Pedersen commitment to build inner product arguments, which requires elliptic curve operations. Second, the verification of a Hyrax commitment takes square root time $O(\sqrt{N})$ relative to the circuit size $N$ . This makes the recursive verification of a Jolt proof impractical, as the verification circuit would need to execute all the Hyrax verification logic in-circuit. A later version of Jolt includes Zeromorph [KT23] and HyperKZG as their commitment backend, making the system recursion-friendly, as now the recursive verifier only needs to perform $O(\log N)$ operations, but at the expense of a need for a trusted setup. Our scheme, Jolt-b, addresses these issues by transitioning to the extension field of the Goldilocks and using the Basefold commitment scheme [ZCF23], which has an $O(\log^2 N)$ verifier time. This scheme mirrors the modifications of Plonky2 over the original Plonk [GWC19]: it transitions from EC fields to the Goldilocks field; it replaces the EC-based commitment scheme with an encoding-based commitment scheme. We implemented Jolt-b, along with an optimized version of the Basefold scheme. Our benchmarks show that at a cost of 2.47x slowdown for the prover, we achieve recursion friendliness for the original Jolt. In comparison with other recursion-friendly Jolt variants, our scheme is 1.24x and 1.52x faster in prover time than the Zeromorph and HyperKZG variants of Jolt, respectively.

Verifiable Random Functions (VRFs) are cryptographic primitives that generate unpredictable randomness along with proofs that are verifiable, a critical requirement for blockchain applications in decentralized finance, online gaming, and more. Existing VRF constructions often rely on centralized entities, creating security vulnerabilities. Distributed VRFs (DVRFs) offer a decentralized alternative but face challenges like large proof sizes or dependence on computationally expensive bilinear pairings. In this research, a unique distributed VRF (DVRF) system called DVRFwCP with considerable improvements is proposed. DVRFwCP has constant-size proofs, which means that the size of the proof does not change based on the number of participants. This overcomes a significant drawback of earlier DVRF systems, which saw proof size increase with participant count. Furthermore, DVRFwCP produces more efficient verification than previous systems by eliminating the requirement for bilinear pairings throughout the verification process. These innovations contribute to a more secure and scalable solution for generating verifiable randomness in decentralized environments. We compare our construction to well-established DVRF instantiations such as DDH-DVRF and GLOW-DVRF while also pointing out the major improvement in the estimated gas cost of these algorithms.

Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size, with optimal parameter size—meaning the lengths of public parameters, keys, and signatures are all constant. Our construction can be instantiated from various standard assumptions, including LWE and DLIN. This substantially improves the state-of-the-art ABS scheme by Boyle, Goldwasser, and Ivan (PKC 2014), which, while achieving optimal parameter size, relies on succinct non-interactive arguments of knowledge that can only be constructed from non-standard assumptions. Our generic construction is based on RAM delegations. At a high level, we leverage the fact that the circuit associated with the signature can be made public and compress it using the power of RAM delegation. This allows us to achieve an overall optimal parameter size while simultaneously hiding the user’s policy.

Every computing paradigm involving communication requires new security protocols employing cryptography. For example, the Internet gave rise to TLS/SSL, and Mobile Computing gave rise to End to End Encryption protocols. In this paper, we address an emerging IoT paradigm involving beacons attached to things and security protocols associated with this new configuration. Specifically, we address the ``beacon notification problem,'' a critical IoT paradigm aims at providing secure and efficient real-time notifications from beacons to their owners. Since the beacon notification problem has not yet been formally defined, we begin by inspecting natural requirements based on the operational setting and establishing correctness, security, and privacy definitions through the use of cryptographic games. To resolve this problem, we propose a novel cryptographic tool we call XDHIES, which is a considerable extension of available Diffie-Hellman encryption schemes. We then show a new notification protocol built upon XDHIES and we prove that this cryptographic protocol is secure and private and successfully meets all the above problem's requirements.

Recent advancements in transformers have revolutionized machine learning, forming the core of Large language models (LLMs). However, integrating these systems into everyday applications raises privacy concerns as client queries are exposed to model owners. Secure multiparty computation (MPC) allows parties to evaluate machine learning applications while keeping sensitive user inputs and proprietary models private. Due to inherent MPC costs, recent works introduce model-specific optimizations that hinder widespread adoption by machine learning researchers. CrypTen (NeurIPS'21) aimed to solve this problem by exposing MPC primitives via common machine learning abstractions such as tensors and modular neural networks. Unfortunately, CrypTen and many other MPC frameworks rely on polynomial approximations of the non-linear functions, resulting in high errors and communication complexity. This paper introduces Curl, an easy-to-use MPC framework that evaluates non-linear functions as lookup tables, resulting in better approximations and significant round and communication reduction. Curl exposes a similar programming model as CrypTen and is highly parallelizable through tensors. At its core, Curl relies on discrete wavelet transformations to reduce the lookup table size without sacrificing accuracy, which results in up to $19\times$ round and communication reduction compared to CrypTen for non-linear functions such as logarithms and reciprocals. We evaluate Curl on a diverse set of LLMs, including BERT, GPT-2, and GPT Neo, and compare against state-of-the-art related works such as Iron (NeurIPS'22) and Bolt (S&P'24) achieving at least $1.9\times$ less communication and latency. Finally, we resolve a long-standing debate regarding the security of widely used probabilistic truncation protocols by proving their security in the stand-alone model. This is of independent interest as many related works rely on this truncation style.

Given the recent progress in machine learning (ML), the cryptography community has started exploring the applicability of ML methods to the design of new cryptanalytic approaches. While current empirical results show promise, the extent to which such methods may outperform classical cryptanalytic approaches is still somewhat unclear. In this work, we initiate exploration of the theory of ML-based cryptanalytic techniques, in particular providing new results towards understanding whether they are fundamentally limited compared to traditional approaches. Whereas most classic cryptanalysis crucially relies on directly processing individual samples (e.g., plaintext-ciphertext pairs), modern ML methods thus far only interact with samples via gradient-based computations that average a loss function over all samples. It is, therefore, conceivable that such gradient-based methods are inherently weaker than classical approaches. We introduce a unifying framework for capturing both ``sample-based'' adversaries that are provided with direct access to individual samples and ``gradient-based'' ones that are restricted to issuing gradient-based queries that are averaged over all given samples via a loss function. Within our framework, we establish a general feasibility result showing that any sample-based adversary can be simulated by a seemingly-weaker gradient-based one. Moreover, the simulation exhibits a nearly optimal overhead in terms of the gradient-based simulator's running time. Finally, we extend and refine our simulation technique to construct a gradient-based simulator that is fully parallelizable (crucial for avoiding an undesirable overhead for parallelizable cryptanalytic tasks), which is then used to construct a gradient-based simulator that executes the particular and highly useful gradient-descent method. Taken together, although the extent to which ML methods may outperform classical cryptanalytic approaches is still somewhat unclear, our results indicate that such gradient-based methods are not inherently limited by their seemingly restricted access to the provided samples.

In this work, we use some recent developments in lattice-based cryptanalytic tools to revisit a fault attack on RSA-CRT signatures based on the Partial Approximate Common Divisor (PACD) problem. By reducing the PACD to a Hidden Number Problem (HNP) instance, we decrease the number of required faulted bits from 32 to 7 in the case of a 1024-bit RSA. We successfully apply the attack to RSA instances up to 8192-bit and present an enhanced analysis of the error-tolerance in the Bounded Distance Decoding (BDD) with predicate approach. Finally, evaluating the impact of standard side-channel and fault countermeasures, we show that merely verifying the signature before output is not an adequate protection against this attack. The reduction from PACD to HNP might be of independent interest.

Single Sign-On (SSO) allows users to conveniently authenticate to many Relying Parties (RPs) through a central Identity Provider (IdP). SSO supports unlinkable authentication towards the RPs via pairwise pseudonyms, where the IdP assigns the user an RP-specific pseudonym. This feature has been rolled out prominently within Apple's SSO service. While establishing unlinkable identities provides privacy towards RPs, it actually emphasizes the main privacy problem of SSO: with every authentication request, the IdP learns the RP that the user wants to access. Solutions to overcome this limitation exist, but either assume users to behave honestly or require them to manage long-term cryptographic keys. In this work, we propose the first SSO system that can provide such pseudonymous authentication in an unobservable yet strongly secure and convenient manner. That is, the IdP blindly derives the user's pairwise pseudonym for the targeted RP without learning the RP's identity and without requiring key material handled by the user. We formally define the desired security and privacy properties for such unlinkable, unobservable, and strongly secure SSO. In particular, our model includes the often neglected RP authentication: the IdP typically wants to limit its services to registered RPs only and thus must be able to (blindly) verify that it issues the token and pseudonym to such a registered RP. We propose a simple construction that combines signatures with efficient proofs-of-knowledge with a blind, yet verifiable, evaluation of the Hashed-Diffie-Hellman PRF. We prove the security of our construction and demonstrate its efficiency through a prototypical implementation, which requires a running time of 2-12ms per involved party.

Physical attacks, and among them fault injection attacks, are a significant threat to the security of embedded systems. Among the means of fault injection, laser has the significant advantage of being extremely spatially accurate. Numerous state-of-the-art studies have investigated the use of lasers to inject faults into a target at run-time. However, the high precision of laser fault injection comes with requirements on the knowledge of the implementation and exact execution time of the victim code. The main contribution of this work is the demonstration on experimental basis that it is also possible to perform laser fault injection on an unpowered device. Specifically, we targeted the Flash non-volatile memory of a 32-bit microcontroller. The advantage of this new attack path is that it does not require any synchronisation between the victim and the attacker. We provide an experimental characterization of this phenomenon with a description of the fault model from the physical level up to the software level. Finally, we applied these results to carry out a persistent fault analysis on a 128-bit AES with a particularly realistic attacker model which reinforces the interest of the PFA.

In 2018, Mouha et al. (IEEE Trans. Reliability, 2018) performed a post-mortem investigation of the correctness of reference implementations submitted to the SHA3 competition run by NIST, finding previously unidentified bugs in a significant portion of them, including two of the five finalists. Their innovative approach allowed them to identify the presence of such bugs in a black-box manner, by searching for counterexamples to expected cryptographic properties of the implementations under test. In this work, we extend their approach to key encapsulation mechanisms (KEMs) and digital signature schemes (DSSs). We perform our tests on multiple versions of the LibOQS collection of post-quantum schemes, to capture implementations at different points of the recent Post-Quantum Cryptography Standardization Process run by NIST. We identify multiple bugs, ranging from software bugs (segmentation faults, memory overflows) to cryptographic bugs, such as ciphertext malleability in KEMs claiming IND-CCA security. We also observe various features of KEMs and DSS that do not contradict any security guarantees, but could appear counter-intuitive.

The use of Internet of Things (IoT) devices in embedded systems has become increasingly popular with advancing technologies. These devices become vulnerable to cyber attacks as they gain popularity. The cryptographic operations performed for the purpose of protection against cyber attacks are crucial to yield fast results in open networks and not slow down network traffic. Therefore, to enhance communication security, studies have been conducted in the literature on using asymmetric encryption and symmetric encryption together in IoT devices for activities such as key sharing, encryption, decryption, data signing, and verifying signed data. In this study, we first propose a cryptographic system engaging of IoT devices operated from a server. Then we do performance analysis of our proposal. In particular, we evaluate the elliptic curve Diffie-Hellman key exchange and elliptic curve digital signature algorithms on the Secp256r1 elliptic curve and AES symmetric encryption via the Micro uECC library conducted with the 32-bit STM32F410RB Nucleo development board microprocessor running at 48 MHz.

This paper proposes a fast and efficient FPGA-based hardware-software co-design for the supersingular isogeny key encapsulation (SIKE) protocol controlled by a custom RISC-V processor. Firstly, we highly optimize the core unit, the polynomial-based field arithmetic logic unit (FALU), with the proposed fast convolution-like multiplier (FCM) to significantly reduce the resource consumption while still maintaining low latency and constant time for all the four SIKE parameters. Secondly, we pack the small isogeny and point operations in hardware, devise a coarse-grained reconfigurable hardware architecture (CGRHA) based on FALU as the co-processor, and apply it to the RISC-V core with customized instructions, effectively avoiding extra time consumption for the data exchange with the software side and meanwhile increasing flexibility. Finally, we code the hardware in SystemVerilog language and the software in C language and run experiments on FPGAs. In the co-processor implementation, the experiment results show that our design for the four SIKE parameters achieves 2.6-4.4x speedup and obtains comparable or better area-time product to or than the state-of-the-art. In the hardware-software co-design experiments, we still have the superiority in speed and only <10\% of extra time is introduced by mutual communication.

The notion of Anamorphic Encryption (Persiano et al. Eurocrypt 2022) aims at establishing private communication against an adversary who can access secret decryption keys and influence the chosen messages. Persiano et al. gave a simple, black-box, rejection sampling-based technique to send anamorphic bits using any IND-CPA secure scheme as underlying PKE. In this paper however we provide evidence that their solution is not as general as claimed: indeed there exists a (contrived yet secure) PKE which lead to insecure anamorphic instantiations. Actually, our result implies that such stateless black-box realizations of AE are impossible to achieve, unless weaker notions are targeted or extra assumptions are made on the PKE. Even worse, this holds true even if one resorts to powerful non-black-box techniques, such as NIZKs, $ i\mathcal{O} $ or garbling. From a constructive perspective, we shed light those required assumptions. Specifically, we show that one could bypass (to some extent) our impossibility by either considering a weaker (but meaningful) notion of AE or by assuming the underlying PKE to (always) produce high min-entropy ciphertexts. Finally, we prove that, for the case of Fully-Asymmetric AE, $ i\mathcal{O}$ can actually be used to overcome existing impossibility barriers. We show how to use $ i\mathcal{O} $ to build Fully-Asymmetric AE (with small anamorphic message space) generically from any IND-CPA secure PKE with sufficiently high min-entropy ciphertexts. Put together our results provide a clearer picture of what black-box constructions can and cannot achieve.

Cryptographic wallets are an essential tool in Blockchain networks to ensure the secure storage and maintenance of an user's cryptographic keys. Broadly, wallets can be divided into three categories, namely custodial, non-custodial, and shared-custodial wallets. The first two are centralized solutions, i.e., the wallet is operated by a single entity, which inherently introduces a single point of failure. Shared-custodial wallets, on the other hand, are maintained by two independent parties, e.g., the wallet user and a service provider, and hence avoid the single point of failure centralized solutions. Unfortunately, current shared-custodial wallets suffer from significant privacy issues. In our work, we introduce password-authenticated deterministic wallets (PADW), a novel and efficient shared-custodial wallet solution, which exhibits strong security and privacy guarantees. In a nutshell, in a PADW scheme, the secret key of the user is shared between the user and the server. In order to generate a signature, the user first authenticates itself to the server by providing a password and afterwards engages in an interactive signing protocol with the server. Security is guaranteed as long as at most one of the two parties is corrupted. Privacy, on the other hand, guarantees that a corrupted server cannot link a transaction to a particular user. We formally model the notion of PADW schemes and we give an instantiation from blind Schnorr signatures. Our construction allows for deterministic key derivation, a feature that is widely used in practice by existing wallet schemes, and it does not rely on any heavy cryptographic primitives. We prove our scheme secure against adaptive adversaries in the random oracle model and under standard assumptions. That is, our security proof only relies on the assumption that the Schnorr signature scheme is unforgeable and that a public key encryption scheme is CCA-secure.