Motivated by applications to the internet of things (IoT), Cremers, Naor, Paz, and Ronen (CRYPTO '22) recently considered a setting in which multiple parties share a common password and want to be able to pairwise authenticate. They observed that using standard password-authenticated key exchange (PAKE) protocols in this setting allows for catastrophic impersonation attacks whereby compromise of a single party allows an attacker to impersonate any party to any other. To address this, they proposed the notion of identity-binding PAKE (iPAKE) and showed constructions of iPAKE protocol CHIP. We present LATKE, a framework for iPAKE that allows us to construct protocols with features beyond what CHIP achieves. In particular, we can instantiate the components of our framework to yield an iPAKE protocol with post-quantum security and identity concealment, where one party hides its identity until it has authenticated the other. This is the first iPAKE protocol with either property. To demonstrate the concrete efficiency of our framework, we implement various instantiations and compare the resulting protocols to CHIP when run on commodity hardware. The performance of our schemes is very close to that of CHIP, while offering stronger security properties.

Zero-knowledge proof systems for computational integrity have seen a rise in popularity in the last couple of years. One of the results of this development is the ongoing effort in designing so-called arithmetization-friendly hash functions in order to make these proofs more efficient. One of these new hash functions, Poseidon, is extensively used in this context, also thanks to being one of the first constructions tailored towards this use case. Many of the design principles of Poseidon have proven to be efficient and were later used in other primitives, yet parts of the construction have shown to be expensive in real-word scenarios. In this paper, we propose an optimized version of Poseidon, called Poseidon2. The two versions differ in two crucial points. First, Poseidon is a sponge hash function, while Poseidon2 can be either a sponge or a compression function depending on the use case. Secondly, Poseidon2 is instantiated by new and more efficient linear layers with respect to Poseidon. These changes allow to decrease the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%. This makes Poseidon2 the currently fastest arithmetization-oriented hash function without lookups. Besides that, we address a recently proposed algebraic attack and propose a simple modification that makes both Poseidon and Poseidon2 secure against this approach.

In this paper we propose Differential Fault Attack (DFA) on two Fully Homomorphic Encryption (FHE) friendly stream ciphers Rasta and $\text {FiLIP} _ {\text {DSM}} $. Design criteria of Rasta rely on affine layers and nonlinear layers, whereas $\text {FiLIP} _ {\text {DSM}} $ relies on permutations and a nonlinear fil- ter function. Here we show that the secret key of these two ciphers can be recovered by injecting only 1 bit fault in the initial state. Our DFA on full round (# rounds = 6) Rasta with 219 block size requires only one block (i.e., 219 bits) of normal and faulty keystream bits. In the case of our DFA on FiLIP-430 (one instance of $\text {FiLIP} _ {\text {DSM}} $), we need 30000 normal and faulty keystream bits.

Monero is a popular cryptocurrency with strong privacy guarantees for users’ transactions. At the heart of Monero’s privacy claims lies a complex transaction system called RingCT, which combines several building blocks such as linkable ring signatures, homomorphic commitments, and range proofs, in a unique fashion. In this work, we provide the first rigorous security analysis for RingCT (as given in Zero to Monero, v2.0.0, 2020) in its entirety. This is in contrast to prior works that only provided security arguments for parts of RingCT. To analyze Monero’s transaction system, we introduce the first holistic security model for RingCT. We then prove the security of RingCT in our model. Our framework is modular: it allows to view RingCT as a combination of various different sub-protocols. Our modular approach has the benefit that these components can be easily updated in future versions of RingCT, with only minor modifications to our analysis. At a technical level, we split our analysis in two parts. First, we identify which security notions for building blocks are needed to imply security for the whole system. Interestingly, we observe that existing and well-established notions (e.g., for the linkable ring signature) are insufficient. Second, we analyze all building blocks as implemented in Monero and prove that they satisfy our new notions. Here, we leverage the algebraic group model to overcome subtle problems in the analysis of the linkable ring signature component. As another technical highlight, we show that our security goals can be mapped to a suitable graph problem, which allows us to take advantage of the theory of network flows in our analysis. This new approach is also useful for proving security of other cryptocurrencies.

We introduce a new primitive called anonymous counting tokens (ACTs) which allows clients to obtain blind signatures or MACs (aka tokens) on messages of their choice, while at the same time enabling issuers to enforce rate limits on the number of tokens that a client can obtain for each message. Our constructions enforce that each client will be able to obtain only one token per message and we show a generic transformation to support other rate limiting as well. We achieve this new property while maintaining the unforgeability and unlinkability properties required for anonymous tokens schemes. We present four ACT constructions with various trade-offs for their efficiency and underlying security assumptions. One construction uses factorization-based primitives and a cyclic group. It is secure in the random oracle model under the q-DDHI assumption (in a cyclic group) and the DCR assumption. Our three other constructions use bilinear maps: one is secure in the standard model under q-DDHI and SXDH, one is secure in the random oracle model under SXDH, and the most efficient of the three is secure in the random oracle model and generic bilinear group model.

Data outsourcing is a solution aimed at addressing the security and reliability issues of data storage by ensuring professional handling of the data. The growing use of outsourcing is causing concern among users due to the lack of assurance regarding the security and reliability of data stored on servers. To address these issues, some attempts have been made to implement Secret Sharing-based Data Outsourcing (SSDO) schemes. The low efficiency of these schemes led researchers to use an index server (IS). However, IS are susceptible to frequency analysis. Bucket-Chain $B^+Tree$ ($BCB^+Tree$) was proposed to tackle the frequency analysis in the current Index Server Secret Sharing-based Data Outsourcing (ISSDO) schemes. Nevertheless, this scheme works very well when the data is discrete with a limited range. Otherwise, the scheme's efficiency declines significantly as it has to store one index in each bucket and the number of buckets rises significantly, rendering the use of an IS useless. In this paper, a new data structure is proposed to store the indexes in IS to mitigate this efficiency concern. Briefly, the domain of values is divided into several segments, and indexes of values in each segment are stored inside a $Shard$. Additionally, a data outsourcing scheme has been presented based on the proposed data structure. It can withstand collaboration from up to $k-1$ dishonest servers even if they have access to the IS.

This is the second update of this report. In this update, we partially solve Open problem 2 and completely solve Open problem 3 from the previous version. By doing this we address one modification of the Panny's attack done by Nils Langius. In the first update we introduced conditions for choosing the parameters that render the attacks (both classical and quantum algorithms attacks) proposed by Lorenz Panny in March 2023 on the first variant, inapplicable. For the classical attack, we prove that the discrete logarithms that he was basing his attack upon do not exist for the new parameters. For the quantum algorithm attacks where he proposed computing a basis of a three-dimensional lattice, as proposed in Kitaev's generalization of Shor's quantum algorithm, we prove that for our transformation, the rank of that lattice (the Abelian Stabiliser in Kitaev's terminology) has a rank one, which makes the Kitaev's quantum algorithm inapplicable. In this paper we construct algebraic structures where rising to the non-associative power indices is no longer tied with the Discrete Logarithm Problem but with a variant of a problem that has been analysed in the last two decades and does not have a quantum polynomial algorithm that solves it. The problem is called Exponential Congruences Problem (ECP). By this, \emph{we disprove} the claims presented in the ePrint report 2021/583 titled "Entropoids: Groups in Disguise" by Lorenz Panny that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} Additionally, we construct an Arithmetic for power indices and propose generic recipe guidelines that we call "Entropic-Lift" for transforming some of the existing classical cryptographic schemes that depend on the hardness of Discrete Logarithm Problem to post-quantum cryptographic schemes that will base their security on the hardness of the Entropoid variant of the Exponential Congruences Problem (EECP). As concrete examples, we show how to transform the classical Diffie-Hellman key exchange, DSA and Schnorr signature schemes. We also post several open problems (two of them now are solved) in relation to EECP and the "Entropic-Lift" transformation.

Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is $\tilde{O}(m^5)$. In this work we propose a modification of the algorithm for which the number of qubits is $\tilde{O}(m^2)$ in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of $\mathbb{Q}(\zeta_m+\zeta_m^{-1})$, the quantum algorithms is much simpler because it is a hidden subgroup problem (HSP) algorithm rather than its error estimation counterpart: continuous hidden subgroup problem (CHSP). We also discuss the (minor) speed-up obtained when exploiting Galois automorphisms thnaks to the Buchmann-Pohst algorithm over $\mathcal{O}_K$-lattices.

How to evaluate the security of Substitution-Permutation Network (SPN) block ciphers against impossible differential (ID) cryptanalysis is a valuable problem. In this paper, a series of methods for bounding the length of IDs of SPN block ciphers are proposed. Firstly, we propose the definitions of minimal representative set and partition table. Therefore, an improved partition-first implementation strategy for bounding the length of IDs is given. Secondly, we introduce a new definition of ladder and propose the ladder-first implementation strategy for bounding the length of IDs. In order to be able to apply ladder-first implementation strategy in practice, the methods for determining ladders and integrating a ladder into searching models are given. Thirdly, a heuristic algorithm called dynamic-ladder-partition implementation strategy is proposed. According to our experimental results, dynamic-ladder-partition implementation strategy is more suitable for SPN ciphers whose number of elements in partition tables is little. Fourthly, rotation-equivalence ID sets of ciphers are explored to reduce the number of models that need to be considered. As applications, we show that 9-round PRESENT, 5-round AES, 6-round Rijndael-160, 7-round Rijndael-192, 7-round Rijndael-224 and 7-round Rijndael-256 do not have any ID under the sole assumption that the round keys are uniformly random. What's more, we obtain that 8-round GIFT-64, 12-round GIFT-128 and 14-round SKINNY-128 do not have any ID under the assumptions that GIFT and SKINNY are Markov ciphers and the round keys are uniformly random. Our methods fill crucial gaps on bounding the length of IDs with the differential properties of S-boxes considered. They enhance our confidence in the security and are valuable, especially for designers.

Blockchain has been broadly recognized as a breakthrough technology of the world. Web3, recently, is emerging as a buzzword, indicating the next generation of Internet based on Blockchain, envisioning the Internet of Money to store and transfer value. However, when people want a comprehensive view throughout advancements in the Blockchain space, there is a missing in the academic domain and scientific publications regarding distributed ledger technology (DLT) classification and taxonomy for the evolution of public Blockchain generations. In this research, the author attempts to classify DLTs in terms of data structure (ledger type), governance and accessibility. Furthermore, based on the well-known problems and the most technical challenges in Blockchain space, the author studies breaking and significant inventions of various blockchain protocols to give a taxonomy for the evolution of four public Blockchain generations, blockchain layers (0, 1, 2, 3). The first and second generations are dominated by Bitcoin and Ethereum, respectively. The latest state-of-the-art blockchain protocols are developing and shaping the third and fourth generations, where several ``Ethereum-killer" candidates are trying to solve major problems, to offer fantastic functions and capacity, by their own outstanding innovations and distinguished architectural designs. This work helps readers quickly capture historical evolution and innovations of Blockchain, envisioning the next advancements of Web3 as well as the Internet of Value (Internet 2.0).

We give the first examples of public-key encryption schemes which can be proven to achieve multi-challenge, multi-user CCA security via reductions that are tight in time, advantage, and memory. Our constructions are obtained by applying the KEM-DEM paradigm to variants of Hashed ElGamal and the Fujisaki-Okamoto transformation that are augmented by adding uniformly random strings to their ciphertexts and/or keys. The reductions carefully combine recent proof techniques introduced by Bhattacharyya’20 and Ghoshal- Ghosal-Jaeger-Tessaro’22. Our proofs for the augmented ECIES version of Hashed-ElGamal make use of a new computational Diffie-Hellman assumption wherein the adversary is given access to a pairing to a random group, which we believe may be of independent interest.

Protecting metadata of communications has been an area of active research since the dining cryptographers problem was introduced by David Chaum in 1988. The Snowden revelations from 2013 resparked research in this direction. Consequently over the last decade we have witnessed a flurry of novel systems designed to protect metadata of users' communications online. However, such systems leverage different assumptions and design choices to achieve their goal; resulting in a scattered view of the desirable properties, potential vulnerabilities, and limitations of existing metadata-protecting communication systems (MPCS). In this work we survey 31 systems targeting metadata-protected communications, and present a unified view of the current state of affairs. We provide two different taxonomies for existing MPCS, first into four different categories by the precise type of metadata protections they offer, and next into six families based on the core techniques that underlie them. By contrasting these systems we identify potential vulnerabilities, as well as subtle privacy implications of design choices of existing MPCS. Furthermore, we identify promising avenues for future research for MPCS, and desirable properties that merit more attention.

Cryptographic wallets are an essential tool to securely store and maintain users’ secret keys and consequently their funds in Blockchain networks. A compelling approach to construct such wallets is to share the user’s secret key among several devices, such that an adversary must corrupt multiple machines to extract the entire secret key. Indeed, many leading cryptocurrency companies such as Coinbase, Binance, or ZenGo have started offering such distributed wallets to their customers. An important feature of a cryptographic wallet is its compatibility with the so-called BIP32 specification, the most widely adopted standard for cryptographic wallets. Essentially, BIP32 specifies the notion of a hierarchical deterministic wallet, which allows to create a key hierarchy in a deterministic fashion. Unfortunately, despite significant interest, no practically efficiently solution for a fully distributed wallet scheme, that also follows the BIP32 standard, exists. In this work, we show the first concretely efficient construction of a fully distributed wallet that is compliant with the BIP32 standard. To this end, we first provide a game-based notion of threshold signatures with rerandomizable keys and show an instantiation via the Gennaro and Goldfeder threshold ECDSA scheme (CCS’18). We then observe that one of BIP32’s key derivation mechanisms, the so-called hardened derivation, cannot efficiently be translated to the threshold setting. Instead, we devise a novel and efficient hardened derivation mechanism for the threshold setting that satisfies the same properties as the original mechanism as specified by BIP32. As a final contribution, we evaluate our solution with respect to its running time and communication cost.

We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt. In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information on it, even in a non-interactive way, without public-key primitives, and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstatesQIP and ZKstatesQMA.

Secure RAM computation allows a number of parties to evaluate a function represented as a random-access machine (RAM) program in a way that reveals nothing about the private inputs of the parties except from what is already revealed by the function output itself. In this work we present \emph{Ramen}, which is a new protocol for computing RAM programs securely among three parties, tolerating up to one passive corruption. Ramen provides reasonable asymptotic guarantees and is concretely efficient at the same time. We have implemented our protocol and provide extensive benchmarks for various settings. Asymptotically, our protocol requires a constant number of rounds and an amortized sublinear amount of communication and computation per memory access. In terms of concrete efficiency, our protocol outperforms previous solutions. For a memory of size $2^{26}$ our memory accesses are \(25\times\) faster in the LAN and \(8\times\) faster in the WAN setting, when compared to the previously fastest, and concurrent, solution by Vadapalli, Henry, and Goldberg (USENIX Security 2023). Due to our superior asymptotic guarantees, the efficiency gap is only widening as the memory gets larger and for this reason Ramen provides the currently most scalable concretely efficient solution for securely computing RAM programs.

Trick-taking games are traditional card games played all over the world. There are many such games, and most of them can be played online through dedicated applications, either for fun or for betting money. However, these games have an intrinsic drawback: each player plays its cards according to several secret constraints (unknown to the other players), and if a player does not respect these constraints, the other players will not realize it until much later in the game. In 2019, X. Bultel and P. Lafourcade proposed a cryptographic protocol for Spades in the random oracle model allowing peer-to-peer trick-taking games to be played securely without the possibility of cheating, even by playing a card that does not respect the secret constraints. However, to simulate card shuffling, this protocol requires a custom proof of shuffle with quadratic complexity in the number of cards, which makes the protocol inefficient in practice. In this paper, we improve their work in several ways. First, we extend their model to cover a broader range of games, such as those implying a set of cards set aside during the deal (for instance Triomphe or French Tarot). Then, we propose a new efficient construction for Spades in the standard model (without random oracles), where cards are represented by partially homomorphic ciphertexts. It can be instantiated by any standard generic proof of shuffle, which significantly improves the efficiency. We demonstrate the feasibility of our approach by giving an implementation of our protocol, and we compare the performances of the new shuffle protocol with the previous one. Finally, we give a similar protocol for French Tarot, with comparable efficiency.

Among the fourth round finalists of the NIST post-quantum cryptography standardization process for public-key encryption algorithms and key encapsulation mechanisms, three rely on hard problems from coding theory. Key encapsulation mechanisms are frequently used in hybrid cryptographic systems: a public-key algorithm for key exchange and a secret key algorithm for communication. A major point is thus the initial key exchange that is performed thanks to a key encapsulation mechanism. In this paper, we analyze side-channel vulnerabilities of the key encapsulation mechanism implemented by the Classic McEliece cryptosystem, whose security is based on the syndrome decoding problem. We use side-channel leakages to reduce the complexity of the syndrome decoding problem by reducing the length of the code considered. The columns punctured from the original code reduce the complexity of a hard problem from coding theory. This approach leads to efficient profiled side-channel attacks that recover the session key with high success rates, even in noisy scenarios.

In this work we present a novel actively secure dishonest majority MPC protocol, \textsc{SuperPack}, whose efficiency improves as the number of \emph{honest} parties increases. Concretely, let $0<\epsilon<1/2$ and consider an adversary that corrupts $t<n(1-\epsilon)$ out of $n$ parties. \textsc{SuperPack} requires $6/\epsilon$ field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and $10/\epsilon$ assuming circuit-independent preprocessing. In contrast, most of the previous works such as SPDZ (Damg\aa rd \emph{et al}, ESORICS 2013) and its derivatives perform the same regardless of whether there is only one honest party or a constant (non-majority) fraction of honest parties. A notable exception is due to Goyal \emph{et al} (CRYPTO 2022), which achieves $58/\epsilon + 96/\epsilon^2$ field elements assuming circuit-independent preprocessing. Our work improves this result substantially by a factor of at least $25$ in the circuit-independent preprocessing model. Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim \emph{et al}, ACNS 2019), which achieves $2(1-\epsilon)n$ field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as $n$ grows, and as $\epsilon$ approaches $1/2$. For example, if there are $90\%$ corruptions ($\epsilon=0.1$), with $n=50$ our online protocol is $1.5\times$ better than Turbospeedz and with $n=100$ this factor is $3\times$, but for $70\%$ corruptions ($\epsilon=0.3$) with $n=50$ our online protocol is $3.5\times$ better, and for $n=100$ this factor is $7\times$. Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of $\approx \epsilon n/2$ smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz. Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority \textsc{TurboPack} (Escudero \emph{et al}, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD. We implement both \textsc{SuperPack} and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.

Quantum public-key encryption [Gottesman; Kawachi et al., Eurocrypt’05] generalizes public-key encryption (PKE) by allowing the public keys to be quantum states. Prior work indicated that quantum PKE can be constructed from assumptions that are potentially weaker than those needed to realize its classical counterpart. In this work, we show that quantum PKE can be constructed from any quantum-secure one-way function. In contrast, classical PKE is believed to require more structured assumptions. Our construction is simple, uses only classical ciphertexts, and satisfies the strong notion of CCA security.

We describe a new related nonce attack able to extract the original signing key from a small collection of ECDSA signatures generated with weak PRNGs. Under suitable conditions on the modulo order of the PRNG, we are able to attack linear, quadratic, cubic as well as arbitrary degree recurrence relations (with unknown coefficients) with few signatures and in negligible time. We also show that for any collection of randomly generated ECDSA nonces, there is one more nonce that can be added following the implicit recurrence relation, and that would allow retrieval of the private key; we exploit this fact to present a novel rogue nonce attack against ECDSA. Up to our knowledge, this is the first known attack exploiting generic and unknown high-degree algebraic relations between nonces that do not require assumptions on the value of single bits or bit sequences (e.g. prefixes and suffixes).

In [15], Leonardi and Ruiz-Lopez propose an additively homomorphic public key encryption scheme whose security is expected to depend on the hardness of the $\textit{learning homomorphism with noise problem}$ (LHN). Choosing parameters for their primitive requires choosing three groups $G$, $H$, and $K$. In their paper, Leonardi and Ruiz-Lopez claim that, when $G$, $H$, and $K$ are abelian, then their public-key cryptosystem is not quantum secure. In this paper, we study security for finite abelian groups $G$, $H$, and $K$ in the classical case. Moreover, we study quantum attacks on instantiations with solvable groups.

We present Fusion, a post-quantum one-time digital signature scheme with non-interactive aggregation with security resting on the short integer solution problem over ideal lattices. Fusion is structurally similar to CRYSTALS-Dilithium, but Fusion is based upon the aggregatable one-time lattice-based scheme by Boneh and Kim. Fusion parameters conservatively target at least $128$ bits of security against forgery, taking tightness gaps into account, and with tighter bounds than the BK scheme. Aggregate Fusion signatures are logarithmically sized in the number of keys, so aggregating enough signatures can be more efficient than stacking Dilithium or Falcon signatures.

Guo and Johansson (ASIACRYPT 2021), and MATZOV (tech.~report 2022) have independently claimed improved attacks against various NIST lattice candidate by adding a Fast Fourier Transform (FFT) trick on top of the so-called Dual-Sieve attack. Recently, there was more follow up work in this line adding new practical improvements. However, from a theoretical perspective, all of these works are painfully specific to Learning with Errors, while the principle of the Dual-Sieve attack is more general (Laarhoven & Walter, CT-RSA 2021). More critically, all of these works are based on heuristics that have received very little theoretical and experimental attention. This work attempts to rectify the above deficiencies of the literature. We first propose a generalization of the FFT trick by Guo and Johansson to arbitrary Bounded Distance Decoding instances. This generalization offers a new improvement to the attack. We then theoretically explore the underlying heuristics and show that these are in contradiction with formal, unconditional theorems in some regimes, and with well-tested heuristics in other regimes. The specific instantiations of the recent literature fall into this second regime. We confirm these contradictions with experiments, documenting several phenomena that are not predicted by the analysis, including a ``waterfall-floor'' phenomenon, reminiscent of Low-Density Parity-Check decoding failures. We conclude that the success probability of the recent Dual-Sieve-FFT attacks are presumably significantly overestimated. We further discuss the adequate way forward towards fixing the attack and its analysis.

Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output. A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open. In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system. We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a ``masked'' version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. As part of our study, we scrutinize recent proposals for the definition and constructions of threshold homomorphic encryption schemes and show new random oracle uninstantiability results that may be of independent interest.

In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as possible, which is called a full CNF characterization (FCC, in short) problem. In this work, we establish a complete theory to solve a best solution of a FCC problem. Specifically, we start from plain sets, which can be characterized by exactly one clause. By exploring mergeable sets, we find a sufficient and necessary condition for characterizing a plain set. Based on the properties of plain sets, we further provide an algorithm for solving a FCC problem with $S$, which can generate all the minimal plain closures of $S$ and produce a best FCC theoretically. We also apply our algorithm to S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables. All of our FCCs are the best-known results at present.

The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible. We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits. To overcome the negative effect of a lower accuracy arising from ignoring bit conditions on inactive bits, we propose an additional tool for deducing all bit conditions automatically. Such a tool is based on a directed-graph capturing the whole computation process of ARX primitives by drawing links among intermediate words and operations. The digraph is also applicable in the MILP model construction process: it enables us to identify the parameters upper bounding the number of bit conditions so as to define the objective function; it is further used to connect the boomerang top and bottom signed differential paths by introducing proper constraints to avoid incompatible intersections. Benefiting from the approximate model and the directed-graph based tool, the solving time of the new MILP model is significantly reduced, enabling us to deduce signed differential paths efficiently and accurately. To show the utility of our method, we propose boomerang attacks on the keyed permutations of three ARX hash functions of BLAKE. For the first time we mount an attack on the full 7 rounds of BLAKE3, with the complexity as low as $2^{180}$. Our best attack on BLAKE2s can improve the previously best result by 0.5 rounds but with lower complexity. The attacks on BLAKE-256 cover the same 8 rounds with the previous best result but with complexity $2^{16}$ times lower. All our results are verified practically with round-reduced boomerang quartets.

We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of Shrink-MD, a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used EdDSA signature scheme, improving prior work in two ways: (1) we give proofs for the case that the hash function is an MD-style one, reflecting the use of SHA512 in the NIST standard, and (2) we improve the tightness of the reduction so that one has guarantees for group sizes in actual use.

This paper introduces protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client reads, and (b) the client either obtains the "authentic" record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. Standard private-information-retrieval schemes either do not ensure this form of output authenticity, or they require multiple database replicas with an honest majority. In contrast, we offer multi-server schemes that protect security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Performing an authenticated private PGP-public-key lookup on an OpenPGP key server's database of 3.5 million keys (3 GiB), using two non-colluding servers, takes under 1.2 core-seconds of computation, essentially matching the time taken by unauthenticated private information retrieval. Our authenticated single-server schemes are 30-100$\times$ more costly than state-of-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties.

OpenPubkey makes a client-side modification to OpenID Connect so that an ID Token issued by an OpenID Provider commits to a user held public key. This transforms an ID Token into a certificate that cryptographically binds an OpenID Connect identity to a public key. We call such an ID Token, a PK Token. The user can then sign messages with their signing key and these signatures can be authenticated and attributed to the user’s OpenID Connect identity. This allows OpenPubkey to upgrade OpenID Connect from Bearer Authentication to Proof-of-Possession, eliminating trust assumptions in OpenID Connect and defeating entire categories of attacks present in OpenID Connect. OpenPubkey was designed to satisfy a decade-long need for this functionality. Prior to OpenPubkey, OpenID Connect did not have a secure way for users to sign statements under their OpenID identities. OpenPubkey is transparent to users and OpenID Providers. An OpenID Provider can not even determine that OpenPubkey is being used. This makes OpenPubkey fully compatible with existing OpenID Providers. In fact a variant of OpenPubkey is currently deployed and used to authenticate signed messages and identities for users with accounts on Google, Microsoft, Okta, and Onelogin. OpenPubkey does not add new trusted parties to OpenID Connect and reduces preexisting trust assumptions. If used in tandem with our MFA-cosigner, OpenPubkey can maintain security even against a malicious OpenID Provider (the most trusted party in OpenID Connect).

An Ideal Cipher (IC) is a cipher where each key defines a random permutation on the domain. Ideal Cipher on a group has many attractive applications, e.g., the Encrypted Key Exchange (EKE) protocol for Password Authenticated Key Exchange (PAKE) [10], or asymmetric PAKE (aPAKE) [40, 36]. However, known constructions for IC on a group domain all have drawbacks, including key leakage from timing information [15], requiring 4 hash-onto-group operations if IC is an 8-round Feistel [27], and limiting the domain to half the group [12] or using variable-time encoding [56, 48] if IC is implemented via (quasi-) bijections from groups to bitstrings [40]. We propose an IC relaxation called a (Randomized) Half-Ideal Cipher (HIC), and we show that HIC on a group can be realized by a modified 2-round Feistel (m2F), at a cost of 1 hash-onto-group operation, which beats existing IC constructions in versatility and computational cost. HIC weakens IC properties by letting part of the ciphertext be non-random, but we exemplify that it can be used as a drop-in replacement for IC by showing that EKE [10] and aPAKE of [40] realize respectively UC PAKE and UC aPAKE even if they use HIC instead of IC. The m2F construction can also serve as IC domain extension, because m2F constructs HIC on domain D from an RO-indiferrentiable hash onto D and an IC on 2κ-bit strings, for κ a security parameter. One application of such extender is a modular lattice-based UC PAKE using EKE instantiated with HIC and anonymous lattice-based KEM.

Whereas theoretical attacks on standardized crypto primitives rarely lead to actual practical attacks, the situation is different for side-channel attacks. Improvements in the performance of side-channel attacks are of utmost importance. In this paper, we propose a framework to be used in key-recovery side-channel attacks on CCA-secure post-quantum encryption schemes. The basic idea is to construct chosen ciphertext queries to a plaintext checking oracle that collects information on a set of secret variables in a single query. Then a large number of such queries is considered, each related to a different set of secret variables, and they are modeled as a low-density parity-check code (LDPC code). Secret variables are finally determined through efficient iterative decoding methods, such as belief propagation, using soft information. The utilization of LDPC codes offers efficient decoding, source compression, and error correction benefits. It has been demonstrated that this approach provides significant improvements compared to previous work by reducing the required number of queries, such as the number of traces in a power attack. The framework is demonstrated and implemented in two different cases. On one hand, we attack implementations of HQC in a timing attack, lowering the number of required traces considerably compared to attacks in previous work. On the other hand, we describe and implement a full attack on a masked implementation of Kyber using power analysis. Using the ChipWhisperer evaluation platform, our real-world attacks recover the long-term secret key of a first-order masked implementation of Kyber-768 with an average of only 12 power traces.

The historical domain of information hiding is alternatively used nowadays for communication security. Maybe the oldest and certainly one of the most studied field that falls in this category is steganography. Within the current paper, we focus on image steganography techniques in the case of the JPEG format. We propose a corrected and optimized version of the J3 stegosystem which, to the best of our knowledge and as shown throughout the paper, may be considered a very good choice in terms of security and efficiency as compared to current solutions. We reconstruct the entire J3 algorithm (pre-processing, message insertion and extraction) and detail all the modifications. We also present implementation optimizations and cover all practical cases while still using the maximum image insertion capacity.

In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is flexibility; i.e., any aggregatable VSS and NIKE scheme can be employed, and the construction will remain secure. To prove the security of our generic construction, we introduce formalized game based notions of security for DKGs, building upon existing notions in the literature. However, these prior security notions either were presented informally, omitted important requirements, or assumed certain algebraic structure of the underlying scheme. Our security notions make no such assumption of underlying algebraic structure, and explicitly consider details such as participant consistency, communication patterns, and key validity. Further, our security notions imply simulatability with respect to a target key generation scheme without rewinding. Hence, any construction that is proven secure using our security notions additionally imply UC security. We then present STORM, a concrete instantiation of our generic construction that is secure in the discrete logarithm setting in the random oracle model. STORM is more efficient than related DKG schemes in the literature. Because of its simple design and composability, it is a practical choice for real world settings and standardization efforts.

The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in improving storage utilization by removing redundant data among cross-users, limit its effectiveness. Thus, we propose a practical Oblivious Store, PEO-Store, which integrates the obliviousness property into the cloud while removing redundancy without compromising security. Unlike conventional schemes, PEO-Store randomly selects a delegate for each client to communicate with the cloud, breaking the mapping link between a valid access pattern sequence and a specific client. Each client encrypts their data and shares it with selected delegates, who act as intermediaries with the cloud provider. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof to protect access pattern privacy and accurately identify and remove redundancy in the cloud. The theoretical proof demonstrates that the probability of identifying the valid access pattern with a specific user is negligible in our design. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

In this short note, we describe a few implementation techniques that allow performing key pair generation for the Falcon and Hawk lattice-based signature schemes, and for the BAT key encapsulation scheme, in a fully constant-time way and without any use of floating-point operations. Our new code is faster than previously published implementations, especially when running on small embedded systems, and uses less RAM.

A secret-sharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only pre-defined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper bounds on the share size of a secret-sharing scheme realizing an arbitrary access structure and the best known lower bounds on the size of these shares. For an arbitrary $n$-party access structure, the best known upper bound on the share size is $2^{O(n)}$. On the other hand, the best known lower bound on the total share size is much smaller, i.e., $\Omega(n^2/\log (n))$ [Csirmaz, \emph{Studia Sci. Math. Hungar.}]. This lower bound was proved more than 25 years ago and no major progress has been made since. In this paper, we study secret-sharing schemes for $k$-hypergraphs, i.e., for access structures where all minimal authorized sets are of size exactly $k$ (however, unauthorized sets can be larger). We consider the case where $k$ is small, i.e., constant or at most $\log (n)$. The trivial upper bound for these access structures is $O(n\cdot \binom{n-1}{k-1})$ and this can be slightly improved. If there were efficient secret-sharing schemes for such $k$-hypergraphs (e.g., $2$-hypergraphs or $3$-hypergraphs), then we would be able to construct secret-sharing schemes for arbitrary access structures that are better than the best known schemes. Thus, understanding the share size required for $k$-hypergraphs is important. Prior to our work, the best known lower bound for these access structures was $\Omega(n \log (n))$, which holds already for graphs (i.e., $2$-hypergraphs). We improve this lower bound, proving a lower bound of $\Omega(n^{2-1/(k-1)}/k)$ on the total share size for some explicit $k$-hypergraphs, where $3 \leq k \leq \log (n)$. For example, for $3$-hypergraphs we prove a lower bound of $\Omega(n^{3/2})$. For $\log (n)$-hypergraphs, we prove a lower bound of $\Omega(n^{2}/\log (n))$, i.e., we show that the lower bound of Csirmaz holds already when all minimal authorized sets are of size $\log (n)$. Our proof is simple and shows that the lower bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz. Using our results, we prove a near quadratic separation between the required share size for realizing an explicit access structure and the monotone circuit size describing the access structure,i.e., the share size in $\Omega(n^2/\log(n))$ and the monotone circuit size is $O(n\log(n))$ (where the circuit has depth $3$).

A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors. In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using {\it surrogate differentiation}. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x) \oplus f(x \oplus \alpha)$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$'s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p \geq 2^{-32}$ and all their linear approximations with bias $|p| \geq 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangs. In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.

Recent advancements in low-cost cryptography have converged upon the use of nanoscale level structural variances as sources of entropy that is unique to each device. Consequently, such delay-based Physically Unclonable Functions or (PUFs) have gained traction for several cryptographic applications. In light of recent machine learning (ML) attacks on delay-based PUFs, the common trend among PUF designers is to either introduce non-linearity using XORs or input transformations applied on the challenges in order to harden the security of delay-based PUFs. Such approaches make machine learning modelling attacks hard by destroying the linear relationship between challenge-response pairs of a PUF. However, we propose to perceive PUFs, which are fundamentally viewed as Boolean functional mapping, as a set of delay parameters drawn from normal distribution. Using this newfound perception, we propose an alternative attack strategy in this paper. We show that instead of trying to learn the exact functional relationship between challenge-response pairs from a PUF, one can search through the search space of all PUFs to find alternative PUF delay parameter set that exhibits similar behaviour as the target PUF. The core intuition behind this strategy is that one can consider a PUF as a set of stages wherein, depending on the corresponding input challenge bit, one of the several signals within a PUF's stage win a race condition. To utilize this idea, we develop a novel Particle Swarm Optimization based framework inspired by the biomimicry of amoebic reproduction. The proposed algorithm avoids the pitfalls of textbook Genetic Algorithms and demonstrates complete break of existing delay-based PUFs which are based on arbiter chains. More specifically, we are able to model higher-rder $k$-XOR PUF variants which are resistant to all-known ML modelling techniques, including $k=13, 15$ and $20$, without the knowledge of reliability values. In addition to that, we also model PUFs that incorporate input transformation, like variants of IPUF and LP-PUF. Furthermore, we take forward this idea across different search spaces in order to learn a higher order PUF using a lower order (and simpler) PUF architecture. This allows us to explore a novel class of attacks, including modelling a $k$-XOR PUF using a $(k-1)$-XOR PUF as well as bypassing input transformations based PUF designs.

In this paper, we present the ``DORCIS'' tool, which finds depth-optimized quantum circuit implementations for arbitrary 3- and 4-bit S-boxes. It follows up from the previous LIGHTER-R tool (which only works for 4-bit S-boxes) by extending it in multiple ways. LIGHTER-R only deals at the top level (i.e., Toffoli gates), whereas DORCIS takes quantum decomposition (i.e., Clifford + T gates) into account. Further, DORCIS optimizes for quantum depth and T depth. We match, if not surpass, other optimized quantum circuit implementations put forth in the other papers. Similar to LIGHTER-R, our tool is also easy to use, and we provide an extended interface to IBM's Qiskit.

RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.

Fuzzy extractors (FE) are cryptographic primitives that establish a shared secret between two parties who have similar samples of a random source, and can communicate over a public channel. An example for this is that Alice has a stored biometric at a server and wants to have authenticated communication using a new reading of her biometric on her device. Reusability and robustness of FE, respectively, guarantee that security holds when FE is used with multiple samples, and the communication channel is tamperable. Fuzzy extractors have been studied in information theoretic and computational setting. Contributions of this paper are two-fold. First, we define a strongly robust and reusable FE that combines the strongest security requirements of FEs, and give three constructions. Construction 1 has computational security, and Constructions 2 and 3 provide information theoretic (IT) security, in our proposed model. Construction 1 provides a solution to the open question of Canetti et al. (Eurocrypt 2014), by achieving robustness and reusability (post-quantum) security in standard model for their construction. Constructions 2 and 3 offer a new approach to the construction of IT-secure FE. Construction 3 is the first robust and reusable FE with IT-security without assuming random oracle. Our robust FEs use a new IT-secure MAC with security against key-shift attack which is of independent interest. Our constructions are for structured sources which for Construction 1, matches Canetti et al.’s source. We then use our Construction 1 for biometric authentication using iris data. We use a widely used iris data set to find the system parameters of the construction for the data set, and implement it. We compare our implementation with an implementation of Canetti et al.’s reusable FE on the same data set, showing the cost of post-quantum security without using random oracle, and robustness in standard model.

Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings: in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor. In this paper, we show that if we make a mildly stronger reasonable-world assumption than prior works, we can circumvent the known limitations on miner revenue, and design auctions that generate optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world and demonstrate how such assumptions can alter the feasibility and infeasibility landscape.

We introduce the notion of a quantum trapdoor function. This is an efficiently computable unitary that takes as input a "public" quantum state and a classical string $x$, and outputs a quantum state. This map is such that (i) it is hard to invert, in the sense that it is hard to recover $x$ given the output state (and many copies of the public state), and (ii) there is a classical trapdoor that allows efficient inversion. We show that a quantum trapdoor function can be constructed from any quantum-secure one-way function. A direct consequence of this result is that, assuming just the existence of quantum-secure one-way functions, there exist: (i) a public-key encryption scheme with a quantum public key, and (ii) a two-message key-exchange protocol, assuming an appropriate notion of a quantum authenticated channel.

This paper presents a correct-by-construction method of designing an FHE model based on the automated program verifier Dafny. We model FHE operations from the ground up, including fundamentals like GCD, coprimality, Montgomery multiplications, and polynomial operations, etc., and higher level optimizations such as Residue Number System (RNS) and Number Theoretic Transform (NTT). The fully formally verified FHE model serves as a reference design for both software stack development and hardware design, and verification efforts. Open-sourcing our FHE Dafny model with modular arithmetic libraries to GitHub is in progress.

Currently, Gasper, the implemented consensus protocol of Ethereum, takes between 64 and 95 slots to finalize blocks. Because of that, a significant portion of the chain is susceptible to reorgs. The possibility to capture MEV (Maximum Extractable Value) through such reorgs can then disincentivize honestly following the protocol, breaking the desired correspondence of honest and rational behavior. Moreover, the relatively long time to finality forces users to choose between economic security and faster transaction confirmation. This motivates the study of the so-called single slot finality protocols: consensus protocols that finalize a block in each slot and, more importantly, that finalize the block proposed at a given slot within such slot. In this work we propose a simple, non-blackbox protocol that combines a synchronous dynamically available protocol with a partially synchronous finality gadget, resulting in a consensus protocol that can finalize one block per slot, paving the way to single slot finality within Ethereum. Importantly, the protocol we present can finalize the block proposed in a slot, within such slot.

Dynamic participation has recently become a crucial requirement for devising permissionless consensus protocols. This notion, originally formalized by Pass and Shi (ASIACRYPT 2017) through their "sleepy model", captures the essence of a system's ability to handle participants joining or leaving during a protocol execution. A dynamically available consensus protocol preserves safety and liveness while allowing dynamic participation. Blockchain protocols, such as Bitcoin's consensus protocol, have implicitly adopted this concept. In the context of Ethereum's consensus protocol, Gasper, Neu, Tas, and Tse (S&P 2021) presented an attack against LMD-GHOST -- the component of Gasper designed to ensure dynamic availability. Consequently, LMD-GHOST results unable to fulfill its intended function of providing dynamic availability for the protocol. Despite attempts to mitigate this issue, the modified protocol still does not achieve dynamic availability, highlighting the need for more secure dynamically available protocols. In this work, we present RLMD-GHOST, a synchronous consensus protocol that not only ensures dynamic availability but also maintains safety during bounded periods of asynchrony. This protocol is particularly appealing for practical systems where strict synchrony assumptions may not always hold, contrary to general assumptions in standard synchronous protocols. Additionally, we present the "generalized sleepy model", within which our results are proven. Building upon the original sleepy model proposed by Pass and Shi, our model extends it with more generalized and stronger constraints on the corruption and sleepiness power of the adversary. This approach allows us to explore a wide range of dynamic participation regimes, spanning from complete dynamic participation to no dynamic participation, i.e., with every participant online. Consequently, this model provides a foundation for analyzing dynamically available protocols.

Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $2\kappa+5$ bits per AND gate (for $\kappa$-bit computational security and any statistical security) and one with total communication of $2\kappa+\rho+5$ bits per AND gate (for $\rho$-bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: 1. The recent compression technique by Dittmer et al. (Crypto 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $5\rho+1$ bits to $2$ bits per AND gate for $\rho$-bit statistical security. 2. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $2\kappa+3\rho$ bits per AND gate. We designed a new authenticated garbling that does not use information theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $2\kappa+1$ bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $2\kappa+5$ bits per AND gate. 3. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $2\kappa+3\rho$ bits down to $2\kappa+\rho+1$ bits per AND gate. Combined with our first contribution, this yields total amortized communication of $2\kappa+\rho+5$ bits.

The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.

This paper gives new constructions of two-round multi-signatures and threshold signatures for which security relies solely on either the hardness of the (plain) discrete logarithm problem or the hardness of RSA, in addition to assuming random oracles. Their signing protocol is partially non-interactive, i.e., the first round of the signing protocol is independent of the message being signed. We obtain our constructions by generalizing the most efficient discrete- logarithm based schemes, MuSig2 (Nick, Ruffing, and Seurin, CRYPTO ’21) and FROST (Komlo and Goldberg, SAC ’20), to work with suitably defined linear hash functions. While the original schemes rely on the stronger and more controversial one-more discrete logarithm assumption, we show that suitable instantiations of the hash functions enable security to be based on either the plain discrete logarithm assumption or on RSA. The signatures produced by our schemes are equivalent to those obtained from Okamoto’s identification schemes (CRYPTO ’92). More abstractly, our results suggest a general framework to transform schemes secure under OMDL into ones secure under the plain DL assumption and, with some restrictions, under RSA.

BBS signatures were implicitly proposed by Boneh, Boyen, and Shacham (CRYPTO ’04) as part of their group signature scheme, and explicitly cast as stand-alone signatures by Camenisch and Lysyanskaya (CRYPTO ’04). A provably secure version, called BBS+, was then devised by Au, Susilo, and Mu (SCN ’06), and is currently the object of a standardization effort which has led to a recent RFC draft. BBS+ signatures are suitable for use within anonymous credential and DAA systems, as their algebraic structure enables efficient proofs of knowledge of message-signature pairs that support partial disclosure. BBS+ signatures consist of one group element and two scalars. As our first contribution, we prove that a variant of BBS+ producing shorter signatures, consisting only of one group element and one scalar, is also secure. The resulting scheme is essentially the original BBS proposal, which was lacking a proof of security. Here we show it satisfies, under the q-SDH assumption, the same provable security guarantees as BBS+. We also provide a complementary tight analysis in the algebraic group model, which heuristically justifies instantiations with potentially shorter signatures. Furthermore, we devise simplified and shorter zero-knowledge proofs of knowledge of a BBS message-signature pair that support partial disclosure of the message. Over the BLS12-381 curve, our proofs are 896 bits shorter than the prior proposal by Camenisch, Drijvers, and Lehmann (TRUST ’16), which is also adopted by the RFC draft. Finally, we show that BBS satisfies one-more unforgeability in the algebraic group model in a scenario, arising in the context of credentials, where the signer can be asked to sign arbitrary group elements, meant to be commitments, without seeing their openings.

Oblivious RAM (ORAM) allows a client to outsource storage to a remote server while hiding the data access pattern from the server. Many ORAM designs have been proposed to reduce the computational overhead and bandwidth blowup for the client. A recent work, Onion Ring ORAM (CCS'19), is able to achieve $O(1)$ bandwidth blowup in the online phase using fully homomorphic encryption (FHE) techniques, at the cost of a computationally expensive client-side offline phase. Furthermore, such a scheme can be categorized as a stateful construction, meaning that the client has to locally maintain a dynamic state representing the order of remote database elements. We present Panacea: a novel design of ORAM based on FHE techniques, which is non-interactive and stateless, achieves $O(1)$ bandwidth blowup, and does not require an expensive offline phase for the client to perform; in that sense, our design is the first of its kind among other ORAM designs. To provide the client with such performance benefits, our design delegates all expensive computation to the resourceful server. We additionally show how to boost the server performance significantly using probabilistic batch codes at the cost of only 1.5x in additional bandwidth blowup and 3x expansion in server storage, but less amortized bandwidth. Our experimental results show that our design, with the batching technique, is practical in terms of server computation overhead as well. Specifically, for a database size of $2^{19}$, it takes only $1.16$ seconds of amortized computation time for a server to respond to a query. As a result of the statelessness and low computational overhead on the client, and reasonable computational overhead on the server, our design is very suitable to be deployed as a cloud-based privacy-preserving storage outsourcing solution with a portable client running on a lightweight device.

A privacy pool enables clients to deposit units of a cryptocurrency into a shared pool where ownership of deposited currency is tracked via a system of cryptographically hidden records. Clients may later withdraw from the pool without linkage to previous deposits. Some privacy pools also support hidden transfer of currency ownership within the pool. In August 2022, the U.S. Department of Treasury sanctioned Tornado Cash, the largest Ethereum privacy pool, on the premise that it enables illicit actors to hide the origin of funds, citing its usage by the DPRK-sponsored Lazarus Group to launder over \$455 million dollars worth of stolen cryptocurrency. This ruling effectively made it illegal for U.S. persons/institutions to use or accept funds that went through Tornado Cash, sparking a global debate among privacy rights activists and lawmakers. Against this backdrop, we present Derecho, a system that institutions could use to request cryptographic attestations of fund origins rather than naively rejecting all funds coming from privacy pools. Derecho is a novel application of proof-carrying data, which allows users to propagate allowlist membership proofs through a privacy pool's transaction graph. Derecho is backwards-compatible with existing Ethereum privacy pool designs, adds no overhead in gas costs, and costs users only a few seconds to produce attestations.

The NIST, in its recent competition on quantum-resilient confidentiality primitives, requested the submission of exclusively KEMs. The task of KEMs is to establish secure session keys that can drive, amongst others, public key encryption and TLS-like secure channels. In this work we test the KEM abstraction in the context of constructing cryptographic schemes that are not subsumed in the PKE and secure channels categories. We find that, when used to construct a key transport scheme or when used within a secure combiner, the KEM abstraction imposes certain inconvenient limits, the settling of which requires the addition of auxiliary symmetric primitives. We hence investigate generalizations of the KEM abstraction that allow a considerably simplified construction of the above primitives. In particular, we study VKEMs and KDFEMs, which augment classic KEMs by label inputs, encapsulation handle outputs, and key derivation features, and we demonstrate that they can be transformed into KEM combiners and key transport schemes without requiring auxiliary components. We finally show that all four finalist KEMs of the NIST competition are effectively KDFEMs. Our conclusion is that only very mild adjustments are necessary to significantly increase their versatility.

The advent of quantum computers has sparked significant interest in post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all existing viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange (NIKE) is theoretically possible, it has been considered too inefficient for real-life applications. In this work, we challenge this folklore belief and provide the first evidence against it. We construct an efficient lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively-secure one. To substantiate our efficiency claim, we provide an optimised implementation of our passively-secure construction in Rust and Jasmin. Our implementation demonstrates the scheme's applicability to real-world scenarios, yielding public keys of approximately 220 KBs. Moreover, the computation of shared keys takes fewer than 12 million cycles on an Intel Skylake CPU, offering a post-quantum security level exceeding 120 bits.

We study the complexity of two-party secure arithmetic computation where the goal is to evaluate an arithmetic circuit over a finite field $F$ in the presence of an active (aka malicious) adversary. In the passive setting, Applebaum et al. (Crypto 2017) constructed a protocol that only makes a *constant* (amortized) number of field operations per gate. This protocol uses the underlying field $F$ as a black box, makes black-box use of (standard) oblivious transfer, and its security is based on arithmetic analogs of well-studied cryptographic assumptions. We present an actively-secure variant of this protocol that achieves, for the first time, all the above features. The protocol relies on the same assumptions and adds only a minor overhead in computation and communication. Along the way, we construct a highly-efficient Vector Oblivious Linear Evaluation (VOLE) protocol and present several practical and theoretical optimizations, as well as a prototype implementation. Our most efficient variant can achieve an asymptotic rate of $1/4$ (i.e., for vectors of length $w$ we send roughly $4w$ elements of $F$), which is only slightly worse than the passively-secure protocol whose rate is $1/3$. The protocol seems to be practically competitive over fast networks, even for relatively small fields $F$ and relatively short vectors. Specifically, our VOLE protocol has 3 rounds, and even for 10K-long vectors, it has an amortized cost per entry of less than 4 OT's and less than 300 arithmetic operations. Most of these operations (about 200) can be pre-processed locally in an offline non-interactive phase. (Better constants can be obtained for longer vectors.) Some of our optimizations rely on a novel intractability assumption regarding the non-malleability of noisy linear codes that may be of independent interest. Our technical approach employs two new ingredients. First, we present a new information-theoretic construction of Conditional Disclosure of Secrets (CDS) and show how to use it in order to immunize the VOLE protocol of Applebaum et al. against active adversaries. Second, by using elementary properties of low-degree polynomials, we show that, for some simple arithmetic functionalities, one can easily upgrade Yao's garbled-circuit protocol to the active setting with a minor overhead while preserving the round complexity.

In this work we apply the Type-Safe (TS) generic group model, recently introduced by Zhandry (2022), to the more general setting of group actions and extend it to the universal composability (UC) framework of Canetti (2000). We then relax this resulting model, that we call UC-TS, to define an algebraic action framework (UC-AA), where the adversaries can behave algebraically, similarly to the algebraic group model (AGM), but for group actions. Finally, we instantiate UC-AA with isogeny-based assumptions, obtaining the Explicit-Isogeny model, UC-EI, and show that, under certain assumptions, UC-EI is less restricting that UC-AGM. We demonstrate the utility of our definitions by proving UC-EI security for the passive-secure protocol described by Lai et al. (2021), hence providing the first concretely efficient two-round isogeny-based OT protocol in the random oracle model against malicious adversaries.

Joint computation on encrypted data is becoming increasingly crucial with the rise of cloud computing. In recent years, the development of multi-client functional encryption (MCFE) has made it possible to perform joint computation on private inputs, without any interaction. Well-settled solutions for linear functions have become efficient and secure, but there is still a shortcoming: if one user inputs incorrect data, the output of the function might become meaningless for all other users (while still useful for the malicious user). To address this issue, the concept of verifiable functional encryption was introduced by Badrinarayanan et al. at Asiacrypt ’16 (BGJS). However, their solution was impractical because of strong statistical requirements. More recently, Bell et al. introduced a related concept for secure aggregation, with their ACORN solution, but it requires multiple rounds of interactions between users. In this paper, – we first propose a computational definition of verifiability for MCFE. Our notion covers the computational version of BGJS and extends it to handle any valid inputs defined by predicates. The BGJS notion corresponds to the particular case of a fixed predicate, in our setting; – we then introduce a new technique called Combine-then-Descend, which relies on the class group. It allows us to construct One-time Decentralized Sum (ODSUM) on verifiable private inputs. ODSUM is the building block for our final protocol of a verifiable decentralized MCFE for inner-product, where the inputs are within a range. Our approach notably enables the efficient identification of malicious users, thereby addressing an unsolved problem in ACORN.

Number Theoretic Transform (NTT) is a fundamental building block in emerging cryptographic constructions like fully homomorphic encryption, post-quantum cryptography and zero-knowledge proof. In this work, we introduce Proteus, an open-source parametric hardware to generate pipelined architectures for the NTT. For a given parameter set including the polynomial degree and size of the coefficient modulus, Proteus can generate Radix-2 NTT architectures using Single-path Delay Feedback (SDF) and Multi-path Delay Commutator (MDC) approaches. We also present a detailed analysis of NTT implementation approaches and use several optimizations to achieve the best NTT configuration. Our evaluations demonstrate performance gain up to $1.8\times$ compared to SDF and MDC-based NTT implementations in the literature. Our SDF and MDC architectures use 1.75× and 6.5× less DSPs, and 3× and 10.5× less BRAMs, respectively, compared to state-of-the-art SDF and MDC-based NTT implementations.

Cryptographic algorithms are vital components ensuring the privacy and security of computer systems. They have constantly improved and evolved over the years following new developments, attacks, breaks, and lessons learned. A recent example is that of quantum-resistant cryptography, which has gained a lot of attention in the last decade and is leading to new algorithms being standardized today. These algorithms, however, present a real challenge: they come with strikingly different size and performance characteristics than their classical counterparts. At the same time, common foundational aspects of our transport protocols have lagged behind as the Internet remains a very diverse space in which different use-cases and parts of the world have different needs. This vision paper motivates more research and possible standards updates related to the upcoming quantum-resistant cryptography migration. It stresses the importance of amplification reflection attacks and congestion control concerns in transport protocols and presents research and standardization takeaways for assessing the impact and the efficacy of potential countermeasures. It emphasizes the need to go beyond the standardization of key encapsulation mechanisms in order to address the numerous protocols and deployments of public-key encryption while avoiding pitfalls. Finally, it motivates the critical need for research in anonymous credentials and blind signatures at the core of numerous deployments and standardization efforts aimed at providing privacy-preserving trust signals.

Is it possible to prove the deletion of a computer program after having executed it? While this task is clearly impossible using classical information alone, the laws of quantum mechanics may admit a solution to this problem. In this work, we propose a new approach to answer this question, using quantum information. In the interactive settings, we present the first fully-secure solution for blind delegation with certified deletion, assuming post-quantum hardness of the learning with errors (LWE) problem. In the non-interactive settings, we propose a construction of obfuscation with certified deletion, assuming post-quantum iO and one-way functions. Our main technical contribution is a new deletion theorem for subspace coset states [Vidick and Zhang, EUROCRYPT'21, Coladangelo et al., CRYPTO'21], which enables a generic compiler that adds the certified deletion guarantee to a variety of cryptographic primitives. In addition to our main result, this allows us to obtain a host of new primitives, such as functional encryption with certified deletion and secure software leasing for an interesting class of programs. In fact, we are able for the first time to achieve a stronger notion of secure software leasing, where even a dishonest evaluator cannot evaluate the program after returning it.

We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption functionality but comes with the guarantee that if the quantum decryption key returned by a user passes a validity test, then the user has lost the ability to decrypt. Our notion is similar in spirit to the notion of secure software leasing (SSL) introduced by Ananth and La Placa (Eurocrypt 2021) but captures significantly more general adversarial strategies. In more detail, our adversary is not restricted to use an honest evaluation algorithm to run pirated software. Our results can be summarized as follows: 1. Definitions: We introduce the definition of PKE with secure key leasing and formalize a security notion that we call indistinguishability against key leasing attacks (IND-KLA security). We also define a one-wayness notion for PKE-SKL that we call OW-KLA security and show that an OW-KLA secure PKE-SKL scheme can be lifted to an IND-KLA secure one by using the (quantum) Goldreich-Levin lemma. 2. Constructing IND-KLA PKE with Secure Key Leasing: We provide a construction of OW-KLA secure PKE-SKL (which implies IND-KLA secure PKE-SKL as discussed above) by leveraging a PKE scheme that satisfies a new security notion that we call consistent or inconsistent security against key leasing attacks (CoIC-KLA security). We then construct a CoIC-KLA secure PKE scheme using 1-key Ciphertext-Policy Functional Encryption (CPFE) that in turn can be based on any IND-CPA secure PKE scheme. 3. Identity Based Encryption, Attribute Based Encryption and Functional Encryption with Secure Key Leasing: We provide definitions of secure key leasing in the context of advanced encryption schemes such as identity based encryption (IBE), attribute-based encryption (ABE) and functional encryption (FE). Then we provide constructions by combining the above PKE-SKL with standard IBE, ABE and FE schemes. Notably, our definitions allow the adversary to request distinguishing keys in the security game, namely, keys that distinguish the challenge bit by simply decrypting the challenge ciphertext, so long as it returns them (and they pass the validity test) before it sees the challenge ciphertext. All our constructions satisfy this stronger definition, albeit with the restriction that only a bounded number of such keys be allowed to the adversary in the IBE and ABE (but not FE) security games. Prior to our work, the notion of single decryptor encryption (SDE) has been studied in the context of PKE (Georgiou and Zhandry, Eprint 2020) and FE (Kitigawa and Nishimaki, Asiacrypt 2022) but all their constructions rely on strong assumptions including indistinguishability obfuscation. In contrast, our constructions do not require any additional assumptions, showing that PKE/IBE/ABE/FE can be upgraded to support secure key leasing for free.

A multi-signature scheme allows multiple signers to jointly sign a common message. In recent years, two lattice-based two-round multi-signature schemes based on Dilithium-G were proposed: DOTT by Damgård, Orlandi, Takahashi, and Tibouchi (PKC'21) and Musig-L by Boschini, Takahashi, and Tibouchi (CRYPTO'22). In this work, we propose a new lattice-based two-round multi-signature scheme called DualMS. Compared to DOTT, DualMS is likely to significantly reduce signature size, since it replaces an opening to a homomorphic trapdoor commitment with a Dilithium-G response in the signature. Compared to Musig-L, concrete parameters show that DualMS has smaller public keys, signatures, and lower communication, while the first round cannot be preprocessed offline as in Musig-L. The main reason behind such improvements is a trapdoor-free "dual signing simulation" of our scheme. Signature simulation of DualMS is virtually the same as the normal signing procedure and does not use lattice trapdoors like DOTT and Musig-L.

Duplex-based authenticated encryption modes with a sufficiently large key length are proven to be secure up to the birthday bound 2^(c/2), where c is the capacity. However this bound is not known to be tight and the complexity of the best known generic attack, which is based on multicollisions, is much larger: it reaches (2^c)/α where α represents a small security loss factor. There is thus an uncertainty on the true extent of security beyond the bound 2^(c/2) provided by such constructions. In this paper, we describe a new generic attack against several duplex-based AEAD modes. Our attack leverages random functions statistics and produces a forgery in time complexity O(2^(3c/4)) using negligible memory and no encryption queries. Furthermore, for some duplex-based modes, our attack recovers the secret key with a negligible amount of additional computations. Most notably, our attack breaks a security claim made by the designers of the NIST lightweight competition candidate Xoodyak. This attack is a step further towards determining the exact security provided by duplex-based constructions.

LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures — basis potential (Pot) and squared sum (SS) — both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold $\delta$ for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350.

In this paper, we present the Webb Protocol, a system for building and governing cross-chain applications that can support shared anonymity set functionality across a set of identical bridged systems on compatible blockchains. The Webb Protocol is composed of two major protocols that deal with storing, updating, and validating of data and state changes that occur on a bridge and that are relevant to replicate on each connected chain. State is efficiently verifiable through the use of merkle trees and privacy is provided using zero-knowledge proofs of membership. Together, one can create applications leveraging distributed state with private property testing capabilities. Both financial and non-financial applications are described as motivating examples within the paper.

Differential-linear (DL) cryptanalysis has undergone remarkable advancements since it was first proposed by Langford and Hellman \cite{langford1994differential} in 1994. At CRYPTO 2022, Niu et al. studied the (rotational) DL cryptanalysis of $n$-bit modulo additions with 2 inputs, i.e., $\boxplus_2$, and presented a technique for evaluating the (rotational) DL correlation of ARX ciphers. However, the problem of how to automatically search for good DL trails on ARX with solvers was left open, which is the focus of this work. In this paper, we solve this open problem through some techniques to reduce complexity and a transformation technique from matrix multiplication chain to Mixed Integer Quadratically-Constrained Programs (MIQCP). First, the computational complexity of the DL correlation of $\boxplus_2$ is reduced to approximately one-eighth of the state of art, which can be computed by a $2\times2$ matrix multiplication chain of the same length as before. Some methods to further reduce complexity in special cases have been studied. Additionally, we present how to compute the extended (rotational) DL correlations of $\boxplus_k$ for $k\ge 2$, where two output linear masks of the cipher pairs can be different. Second, to ensure that the existing solver Gurobi\footnote{The solver used in this paper is Gurobi, and some ready-made functions in Gurobi are also used, such as LOG\_2 and ABS. The source code is available at \url{https://}. } can compute DL correlations of $\boxplus_2$, we propose a method to transform an arbitrary matrix multiplication chain into a MIQCP, which forms the foundation of our automatic search of DL trails in ARX ciphers. Third, in ARX ciphers, we use a single DL trail under some explicit conditions to give a good estimate of the correlation, which avoids the exhaustion of intermediate differences. We then derive an automatic method for evaluating the DL correlations of ARX, which we apply to Alzette and some versions of SPECK. Experimentally verified results confirm the validity of our method, with the predicted correlations being close to the experimental ones. To the best of our knowledge, this method finds the best DL distinguishers for these ARX primitives currently. Furthermore, we presented the lowest time-complexity attacks against 12-14 rounds of SPECK32 to date.

Privacy enhancing technologies (PETs) have been proposed as a way to protect the privacy of data while still allowing for data analysis. In this work, we focus on Fully Homomorphic Encryption (FHE), a powerful tool that allows for arbitrary computations to be performed on encrypted data. FHE has received lots of attention in the past few years and has reached realistic execution times and correctness. More precisely, we explain in this paper how we apply FHE to tree-based models and get state-of-the-art solutions over encrypted tabular data. We show that our method is applicable to a wide range of tree-based models, including decision trees, random forests, and gradient boosted trees, and has been implemented within the Concrete-ML library, which is open-source at https://github.com/zama-ai/concrete-ml. With a selected set of use-cases, we demonstrate that our FHE version is very close to the unprotected version in terms of accuracy.

Fully homomorphic encryption (FHE) is an encryption method that allows to perform computation on encrypted data, without decryption. FHE preserves the privacy of the users of online services that handle sensitive data, such as health data, biometrics, credit scores and other personal information. A common way to provide a valuable service on such data is through machine learning and, at this time, Neural Networks are the dominant machine learning model for unstructured data. In this work we show how to construct Deep Neural Networks (DNN) that are compatible with the constraints of TFHE, an FHE scheme that allows arbitrary depth computation circuits. We discuss the constraints and show the architecture of DNNs for two computer vision tasks. We benchmark the architectures using the Concrete stack, an open-source implementation of TFHE.

We present a pairing-based traitor tracing scheme for $N$ users with$$ |\mathsf{pk}| = |\mathsf{ct}| = O(N^{1/3}), \quad |\mathsf{sk}| = O(1). $$This is the first pairing-based scheme to achieve ${|\mathsf{pk}|\cdot|\mathsf{sk}|\cdot|\mathsf{ct}|=o(N)}$. Our construction relies on the (bilateral) $k$-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of $\mathsf{pk},\mathsf{ct}$ in Boneh–Sahai–Waters [Eurocrypt '06] and the size of $\mathsf{sk}$ in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.

The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

Liquidations in DeFi are both a blessing and a curse — whereas liquidations prevent lenders from capital loss, they simultaneously lead to liquidation spirals and system-wide failures. Since most lending and borrowing protocols assume liquidations are indispensable, there is an increased interest in alternative constructions that prevent immediate systemic-failure under uncertain circumstances. In this work, we introduce reversible call options, a novel financial primitive that enables the seller of a call option to terminate it before maturity. We apply reversible call options to lending in DeFi and devise Miqado, a protocol for lending platforms to replace the liquidation mechanisms. To the best of our knowledge, Miqado is the first protocol that actively mitigates liquidations to reduce the risk of liquidation spirals. Instead of selling collateral, Miqado incentivizes external entities, so-called supporters, to top-up a borrowing position and grant the borrower additional time to rescue the debt. Our simulation shows that Miqado reduces the amount of liquidated collateral by 89.82% in a worst-case scenario.

We present a new block cipher mode of operation for authenticated encryption (AE), dubbed XOCB, that has the following features: (1) beyond-birthday-bound (BBB) security based on the standard pseudorandom assumption of the internal block cipher if the maximum block length is sufficiently smaller than the birthday bound, (2) rate-1 computation, and (3) supporting any block cipher with any key length. Namely, XOCB has effectively the same efficiency as the seminal OCB while having stronger quantitative security without any change in the security model or the required primitive in OCB. Although numerous studies have been conducted in the past, our XOCB is the first mode of operation to achieve these multiple goals simultaneously.

We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Given the classical description of a quantum circuit $Q$, our obfuscator outputs a quantum state $\ket{\widetilde{Q}}$ that can be used to evaluate $Q$ repeatedly on arbitrary inputs. Instantiating the classical oracle using any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor's algorithm (SICOMP 1997). Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate \emph{null} quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum \emph{partitioning} circuits, which can be used to verify the evaluation procedure of Mahadev's quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable \emph{Pauli functional commitment}, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver's standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Hardware-based Root of Trust (HRT) is considered the gold standard for bootstrapping trust in secure computing. This paper analyzes HRT implementations across state-of-the-art TEEs and differentiates HRT implementation across two dimensions: 1) Security Properties & Threats and 2) Hardware Capabilities. Later, this work analyzes and compares 1) Intel SGX, 2) ARM TrustZone, 3) NXP Trust Architecture, 4) AMD SEV, 5) Microsoft Pluton, and 6) Apple T2 HRTs in terms of threats, security properties, and capabilities.

We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

An anamorphic encryption scheme allows two parties who share a so-called double key to embed covert messages in ciphertexts of an established PKE scheme. This protects against a dictator that can force the receiver to reveal the secret keys for the PKE scheme, but who is oblivious about the existence of the double key. We identify two limitations of the original model by Persiano, Phan, and Yung (EUROCRYPT 2022). First, in their definition a double key can only be generated once, together with a key-pair. This has the drawback that a receiver who wants to use the anamorphic mode after a dictator comes to power, needs to deploy a new key-pair, a potentially suspicious act. Second, a receiver cannot distinguish whether or not a ciphertext contains a covert message. In this work we propose a new model that overcomes these limitations. First, we allow to associate multiple double keys to a key-pair, after its deployment. This also enables deniability in case the double key only depends on the public key. Second, we propose a natural robustness notion, which guarantees that anamorphically decrypting a regularly encrypted message results in a special symbol indicating that no covert message is contained, which also eliminates certain attacks. Finally, to instantiate our new, stronger definition of anamorphic encryption, we provide generic and concrete constructions. Concretely, we show that ElGamal and Cramer-Shoup satisfy a new condition, selective randomness recoverability, which enables robust anamorphic extensions, and we also provide a robust anamorphic extension for RSA-OAEP.

Hierarchical Identity Based Encryption (HIBE) is a well studied, versatile tool used in many cryptographic protocols. Yet, since the performance of all known HIBE constructions is broadly considered prohibitive, some real-world applications avoid relying on HIBE at the expense of security. A prominent example for this is secure messaging: Strongly secure messaging protocols are provably equivalent to Key-Updatable Key Encapsulation Mechanisms (KU-KEMs; Balli et al., Asiacrypt 2020); so far, all KU-KEM constructions rely on adaptive unbounded-depth HIBE (Poettering and Rösler, Jaeger and Stepanovs, both CRYPTO 2018). By weakening security requirements for better efficiency, many messaging protocols dispense with using HIBE. In this work, we aim to gain better efficiency without sacrificing security. For this, we observe that applications like messaging only need a restricted variant of HIBE for strong security. This variant, that we call Unique-Path Identity Based Encryption (UPIBE), restricts HIBE by requiring that each secret key can delegate at most one subordinate secret key. However, in contrast to fixed secret key delegation in Forward-Secure Public Key Encryption, the delegation in UPIBE, as in HIBE, is uniquely determined by variable identity strings from an exponentially large space. We investigate this mild but surprisingly effective restriction and show that it offers substantial complexity and performance advantages. More concretely, we generically build bounded-depth UPIBE from only bounded-collusion IBE in the standard model; and we generically build adaptive unbounded-depth UPIBE from only selective bounded-depth HIBE in the random oracle model. These results significantly extend the range of underlying assumptions and efficient instantiations. We conclude with a rigorous performance evaluation of our UPIBE design. Beyond solving challenging open problems by reducing complexity and improving efficiency of KU-KEM and strongly secure messaging protocols, we offer a new definitional perspective on the bounded-collusion setting.

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel sieving-style information-set decoding (ISD) algorithm, addressing the task of solving the syndrome decoding problem. Our approach involves maintaining a list of weight-$2p$ solution vectors to a partial syndrome decoding problem and then creating new vectors by identifying pairs of vectors that collide in $p$ positions. By gradually increasing the parity-check condition by one and repeating this process iteratively, we find the final solution(s). We show that our novel algorithm performs better than other ISDs in the memory-restricted scenario when applied to McEliece. Notably, in the case of problem instances with very low relative weight, it seems to significantly outperform all previous algorithms. In particular, for code-based candidate BIKE, the algorithm has lower bit complexity than the previous best results.

We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.

Lyubashevky's signatures are based on the Fiat-Shamir with Aborts paradigm. It transforms an interactive identification protocol that has a non-negligible probability of aborting into a signature by repeating executions until a loop iteration does not trigger an abort. Interaction is removed by replacing the challenge of the verifier by the evaluation of a hash function, modeled as a random oracle in the analysis. The access to the random oracle is classical (ROM), resp. quantum (QROM), if one is interested in security against classical, resp. quantum, adversaries. Most analyses in the literature consider a setting with a bounded number of aborts (i.e., signing fails if no signature is output within a prescribed number of loop iterations), while practical instantiations (e.g., Dilithium) run until a signature is output (i.e., loop iterations are unbounded). In this work, we emphasize that combining random oracles with loop iterations induces numerous technicalities for analyzing correctness, run-time, and security of the resulting schemes, both in the bounded and unbounded case. As a first contribution, we put light on errors in all existing analyses. We then provide two detailed analyses in the QROM for the bounded case, adapted from Kiltz, Lyubashevsky, and Shaffner [EUROCRYPT'18] and from Grilo, Hövelmanns, Hülsing, and Majenz [ASIACRYPT'21]. In the process, we prove the underlying $\Sigma$-protocol to achieve a stronger zero-knowledge property than usually considered for $\Sigma$-protocols with aborts, which enables a corrected analysis. A further contribution is a detailed analysis in the case of unbounded aborts, the latter inducing several additional subtleties.

Properties of quantum mechanics have enabled the emergence of quantum cryptographic protocols achieving important goals which are proven to be impossible classically. Unfortunately, this usually comes at the cost of needing quantum power from every party in the protocol, while arguably a more realistic scenario would be a network of classical clients, classically interacting with a quantum server. In this paper, we focus on copy-protection, which is a quantum primitive that allows a program to be evaluated, but not copied, and has shown interest especially due to its links to other unclonable cryptographic primitives. Our main contribution is to show how to dequantize existing quantum copy-protection from hidden coset states, by giving a construction for classically-instructed remote state preparation for coset states. We then apply this dequantizer to obtain semi-quantum cryptographic protocols for copy-protection and tokenized signatures with strong unforgeability. In the process, we present the first secure copy-protection scheme for point functions in the plain model and a new direct product hardness property of coset states which immediately implies a strongly unforgeable tokenized signature scheme.

Combinatorial attacks on small max norm LWE keys suffer enormous memory requirements, which render them inefficient in realistic attack scenarios. Therefore, more memory-efficient substitutes for these algorithms are needed. In this work, we provide new combinatorial algorithms for recovering small max norm LWE secrets outperforming previous approaches whenever the available memory is limited. We provide analyses of our algorithms for secret key distributions of current NTRU, Kyber and Dilithium variants, showing that our new approach outperforms previous memory-efficient algorithms. For instance, considering uniformly random ternary secrets of length $n$ we improve the best known time complexity for \emph{polynomial memory} algorithms from $2^{1.063n}$ down-to $2^{0.926n}$. We obtain even larger gains for LWE secrets in $\{-m,\ldots,m\}^n$ with $m=2,3$ as found in Kyber and Dilithium. For example, for uniformly random keys in $\{-2,\ldots,2\}^n$ as is the case for Dilithium we improve the previously best time under polynomial memory restriction from $2^{1.742n}$ down-to $2^{1.282n}$. Eventually, we provide novel time-memory trade-offs continuously interpolating between our polynomial memory algorithms and the best algorithms in the unlimited memory case (May, Crypto 2021).

This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security. It reports on a formalization of simulatability in terms of linear algebra properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of erase morphisms. From a theoretical perspective, we shed light into probabilistic definitions of simulatability and matrix-based spectral approaches. This could mean, in practice, that potentially better tools can be built. Readers will find a different, and perhaps less contrived, definition of simulatability, which could enable new forms of reasoning. This work does not cover any practical implementation of the proposed tools, which is left for future work.

The widespread deployment of low-power and handheld devices opens an opportunity to design lightweight authenticated encryption schemes. The schemes so proposed must also prove their resilience under various security notions. Romulus-N1 is an authenticated encryption scheme with associated data based on a tweakable blockcipher, a primary variant of Romulus-N family which is NIST (National Institute of Standards and Technology) lightweight cryptography competition finalist; provides beyond birthday bound security for integrity security in nonce respecting scenario but fails to provide the integrity security in nonce misuse and RUP (release of unverified plaintext) scenarios. In this paper, we propose lynx, a family with $14$ members of 1-pass and rate-1 lightweight authenticated encryption schemes with associated data based on a tweakable blockcipher, that provides birthday bound security for integrity security in both nonce respecting as well as nonce misuse and RUP scenarios and birthday bound security for privacy in nonce respecting scenario. For creating such a family of schemes we propose a family of function $\mathcal{F}$ that provides a total of $72$ cases out of which we show that only $14$ of them can be used for creating authenticated encryption schemes. We provide the implementation of one of the members of lynx family on six different hardware platforms and compare it with Romulus-N1. The comparison clearly shows that the lynx member outperforms Romulus-N1 on all the six platforms.

In this paper we, for the first time, study the question under which circumstances decomposing a round function of a Substitution-Permutation Network is possible uniquely. More precisely, we provide necessary and sufficient criteria for the non-linear layer on when a decomposition is unique. Our results in particular imply that, when cryptographically strong S-boxes are used, the decomposition is indeed unique. We then apply our findings to the notion of alignment, pointing out that the previous definition allows for primitives that are both aligned and unaligned simultaneously. As a second result, we present experimental data that shows that alignment might only have limited impact. For this, we compare aligned and unaligned versions of the cipher PRESENT.

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In this work we revisit the preimage sampling algorithm proposed by Micciancio and Peikert with different contributions. We first propose a finer analysis of this procedure which results in drastic efficiency gains of up to 50% on the preimage sizes without affecting security. It can thus be used as a drop-in replacement in every construction resorting to it. We then propose a new preimage sampling method which still relies on the trapdoors of Micciancio and Peikert, but that also bridges to the Fiat-Shamir with Aborts signature paradigm by leveraging rejection sampling. It again leads to dramatic gains of up to 75% compared to the original sampling technique. This opens promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. As an application of our new procedure, we give the first lattice-based aggregate signature supporting public aggregation and that achieves relevant compression compared to the concatenation of individual signatures. Our scheme is proven secure in the aggregate chosen-key model coined by Boneh et al. in 2003, based on the well-studied assumptions Module Learning With Errors and Module Short Integer Solution.

GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime $N$ has been found, the only way for another party to independently verify the primality of $N$ used to be by repeating the expensive primality test. To avoid the need for second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime. In this paper, we propose a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can -- parallel to running the primality test for $N$ -- generate an efficiently verifiable proof at a little extra cost certifying that $N$ is not prime. The interactive protocol has statistical soundness and can be made non-interactive using the Fiat-Shamir heuristic. Our approach is based on a cryptographic primitive called Proof of Exponentiation (PoE) which, for a group $\mathbb{G}$, certifies that a tuple $(x,y,T)\in\mathbb{G}^2\times\mathbb{N}$ satisfies $x^{2^T}=y$ (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol. 2020). In particular, we show how to adapt Pietrzak's PoE at a moderate additional cost to make it a cryptographically-sound certificate of non-primality.

We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm, and show that the heuristic running time is $O(n^{\omega}(C+n)^{1+\varepsilon})$ for lattices of dimension $n$, $\omega\in (2,3]$ bounding the cost of size reduction, matrix multiplication, and QR factorization, and $C$ bounding the log of the condition number of the input basis $B$. This yields a running time of $O\left(n^\omega (p + n)^{1 + \varepsilon}\right)$ for precision $p = O(\log \|B\|_{max})$ in common applications. Our algorithm is fully practical, and we have published our implementation. We experimentally validate our heuristic, give extensive benchmarks against numerous classes of cryptographic lattices, and show that our algorithm significantly outperforms existing implementations.

We study certified everlasting secure functional encryption (FE) and many other cryptographic primitives in this work. Certified everlasting security roughly means the following. A receiver possessing a quantum cryptographic object (such as ciphertext) can issue a certificate showing that the receiver has deleted the cryptographic object and information included in the object (such as plaintext) was lost. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded after the deletion. Many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. Hence, certified everlasting security is a nice compromise (intrinsic to quantum). In this work, we define certified everlasting secure versions of FE, compute-and-compare obfuscation, predicate encryption (PE), secret-key encryption (SKE), public-key encryption (PKE), receiver non-committing encryption (RNCE), and garbled circuits. We also present the following constructions: - Adaptively certified everlasting secure collusion-resistant public-key FE for all polynomial-size circuits from indistinguishability obfuscation and one-way functions. - Adaptively certified everlasting secure bounded collusion-resistant public-key FE for $\mathsf{NC}^1$ circuits from standard PKE. - Certified everlasting secure compute-and-compare obfuscation from standard fully homomorphic encryption and standard compute-and-compare obfuscation - Adaptively (resp., selectively) certified everlasting secure PE from standard adaptively (resp., selectively) secure attribute-based encryption and certified everlasting secure compute-and-compare obfuscation. - Certified everlasting secure SKE and PKE from standard SKE and PKE, respectively. - Certified everlasting secure RNCE from standard PKE. - Certified everlasting secure garbled circuits from standard SKE.

Machine Learning (ML) is almost ubiquitously used in multiple disciplines nowadays. Recently, we have seen its usage in the realm of differential distinguishers for symmetric key ciphers. In this work, we explore the possibility of a number of ciphers with respect to various ML-based distinguishers. We show new distinguishers on the unkeyed and round reduced version of SPECK-32, SPECK-128, ASCON, SIMECK-32, SIMECK-64 and SKINNY-128. We explore multiple avenues in the process. In summary, we use neural network as well as support vector machine in various settings (such as varying the activation function), apart from experimenting with a number of input difference tuples. Among other results, we show a distinguisher of 8-round SPECK-32 that works with practical data complexity (most of the experiments take a few hours on a personal computer).

A private puncturable pseudorandom function (PRF) enables one to create a constrained version of a PRF key, which can be used to evaluate the PRF at all but some punctured points. In addition, the constrained key reveals no information about the punctured points and the PRF values on them. Existing constructions of private puncturable PRFs are only proven to be secure against a restricted adversary that must commit to the punctured points before viewing any information. It is an open problem to achieve the more natural adaptive security, where the adversary can make all its choices on-the-fly. In this work, we solve the problem by constructing an adaptively secure private puncturable PRF from standard lattice assumptions. To achieve this goal, we present a new primitive called explainable hash, which allows one to reprogram the hash function on a given input. The new primitive may find further applications in constructing more cryptographic schemes with adaptive security. Besides, our construction has collusion resistant pseudorandomness, which requires that even given multiple constrained keys, no one could learn the values of the PRF at the punctured points. Private puncturable PRFs with collusion resistant pseudorandomness were only known from multilinear maps or indistinguishability obfuscations in previous works, and we provide the first solution from standard lattice assumptions.

Unconditionally secure broadcast is feasible among parties connected by pairwise secure links only if there is a strict two-thirds majority of honest parties when no additional resources are available. This limitation may be circumvented when the parties have recourse to additional resources such as correlated randomness. Fitzi, Wolf, and Wullschleger (CRYPTO 2004) attempted to characterize the conditions on correlated randomness shared among three parties which would enable them to realize broadcast. Due to a gap in their impossibility argument, it turns out that their characterization is incorrect. Using a novel construction we show that broadcast is feasible under a considerably larger class of correlations. In fact, we realize pseudo-signatures, which are information theoretic counterparts of digital signatures using which unconditionally secure broadcast may be obtained. We also obtain a matching impossibility result thereby characterizing the class of correlations on which three-party broadcast (and pseudo-signatures) can be based. Our impossibility proof, which extends the well-know argument of Fischer, Lynch and Merritt (Distr. Comp., 1986) to the case where parties observe correlated randomness, maybe of independent interest.

Partially Oblivious Pseudorandom Functions (POPRFs) are 2-party protocols that allow a client to learn pseudorandom function (PRF) evaluations on inputs of its choice from a server. The client submits two inputs, one public and one private. The security properties ensure that the server cannot learn the private input, and the client cannot learn more than one evaluation per POPRF query. POPRFs have many applications including password-based key exchange and privacy-preserving authentication mechanisms. However, most constructions are based on classical assumptions, and those with post quantum security suffer from large efficiency drawbacks. In this work, we construct a novel POPRF from lattice assumptions and the “Crypto Dark Matter” PRF candidate (TCC’18) in the random oracle model. At a conceptual level, our scheme exploits the alignment of this family of PRF candidates, relying on mixed modulus computations, and programmable bootstrapping in the torus fully homomorphic encryption scheme (TFHE). We show that our construction achieves malicious client security based on circuit-private FHE, and client privacy from the semantic security of the FHE scheme. We further explore a heuristic approach to extend our scheme to support verifiability, based on the difficulty of computing cheating circuits in low depth. This would yield a verifiable (P)OPRF. We provide a proof-of-concept implementation and preliminary benchmarks of our construction. For the core online OPRF functionality, we require amortised 10.0KB communication per evaluation and a one-time per-client setup communication of 2.5MB.

Homomorphic Encryption~(HE) is used in many fields including information storage, data protection, privacy preservation, blockchain, and authentication. HE allows an untrusted third party to perform algebraic operations on encrypted data. Protecting the results of HE against accidental or malicious tampering attacks is still an open research challenge. In this paper, we introduce a lightweight technique that allows a data owner to verify the integrity of HE results performed in the cloud. The proposed method is quick, simple, and applicable, as it depends on adding a single digit to the encrypted message before storing it in the cloud. This digit represents verification proof and it is later used to ensure a verifiable HE. Our technique can be integrated with any HE scheme that uses encryption with non-isolated plaintext.

Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons. Originally suggested by Abdalla and Bellare, there are several proposals on how to perform this internal re-keying mechanism. For example, Liliya et al. offered the CryptoPro Key Meshing (CPKM) to be used together with GOST 28147-89 (known as the GOST block cipher). Later, ISO and the IETF adopted the Advanced CryptoPro Key Meshing (ACKPM) in ISO 10116 and RFC 8645, respectively. In this paper, we study the security of ACPKM and CPKM. We show that the internal re-keying suffers from an entropy loss in successive repetitions of the re- keying mechanism. We show some attacks based on this issue. The most prominent one has time and data complexities of $O(2^{\kappa/2} )$ and success rate of $O(2^{−\kappa/4} )$ for a $\kappa$-bit key. Furthermore, we show that a malicious block cipher designer or a faulty implementation can exploit the ACPKM (or the original CPKM) mechanism to significantly hinder the security of a protocol employing ACPKM (or CPKM). Namely, we show that in such cases, the entropy of the re-keyed key can be greatly reduced.

The no-cloning principle of quantum mechanics enables us to achieve amazing unclonable cryptographic primitives, which is impossible in classical cryptography. However, the security definitions for unclonable cryptography are tricky. Achieving desirable security notions for unclonability is a challenging task. In particular, there is no indistinguishable-secure unclonable encryption and quantum copy-protection for single-bit output point functions in the standard model. To tackle this problem, we introduce and study relaxed but meaningful security notions for unclonable cryptography in this work. We call the new security notion one-out-of-many unclonable security. We obtain the following results. - We show that one-time strong anti-piracy secure secret key single-decryptor encryption (SDE) implies one-out-of-many indistinguishable-secure unclonable encryption. - We construct a one-time strong anti-piracy secure secret key SDE scheme in the standard model from the LWE assumption. - We construct one-out-of-many copy-protection for single-bit output point functions from one-out-of-many indistinguishable-secure unclonable encryption and the LWE assumption. - We construct one-out-of-many unclonable predicate encryption (PE) from one-out-of-many indistinguishable-secure unclonable encryption and the LWE assumption. Thus, we obtain one-out-of-many indistinguishable-secure unclonable encryption, one-out-of-many copy-protection for single-bit output point functions, and one-out-of-many unclonable PE in the standard model from the LWE assumption. In addition, our one-time SDE scheme is the first SDE scheme that does not rely on any oracle heuristics and strong assumptions such as indistinguishability obfuscation and witness encryption.

Current messaging protocols are incapable of detecting active man-in-the-middle threats. Even common continuous key agreement protocols such as Signal, which offers forward secrecy and post-compromise security, are dependent on the adversary being passive immediately following state compromise, and healing guarantees are lost if the attacker is not. This work offers the first solution for detecting active man-in-the-middle attacks on such protocols by extending authentication beyond the initial public keys and binding it to the entire continuous key agreement. In this, any adversarial fork is identifiable to the protocol participants. We provide a modular construction generic for application with any continuous key agreement protocol, a specific construction for application to Signal, and security analysis. The modularity of our solution enables it to be seamlessly adopted by any continuous key agreement protocol.

The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space. In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In our model, the existence of IDs can be directly obtained by checking whether the model has a solution. In addition, our tool can also detect any contradictions between input and output differences by changing the position of the contradictions. Our method is confirmed by applying it to several block ciphers, and our results show that we can find 6-, 13-, and 12-round IDs for Midori-64, CRAFT, and SKINNY-64 within a few seconds, respectively. Moreover, by carefully analyzing the key schedule of Midori-64, we propose an equivalent key transform technique and construct a complete MILP model for an 11-round impossible differential attack (IDA) on Midori-64 to search for the minimum number of keys to be guessed. Based on our automatic technique, we present a new 11-round IDA on Midori-64, where 23 nibbles of keys need to be guessed, which reduces the time complexity compared to previous work. The time and data complexity of our attack are $2^{116.59}$ and $2^{60}$, respectively. To the best of our knowledge, this is the best IDA on Midori-64 at present.

Virtually all modern blockciphers are iterated. In this paper, we ask: to construct a secure iterated blockcipher "non-trivially", how many calls to random functions and permutations are necessary? When security means indistinguishability from a random permutation, optimality is achieved by the Even-Mansour scheme using 1 call to a public permutation. We seek for the arguably strongest security indifferentiability from an ideal cipher, a notion introduced by Maurer et al. (TCC 2004) and popularized by Coron et al. (JoC, 2014). We provide the first generic negative result/lower bounds: when the key is not too short, no iterated blockcipher making 3 calls is (statistically) indifferentiable. This proves optimality for a 4-call positive result of Guo et al. (Eprint 2016). Furthermore, using 1 or 2 calls, even indifferentiable iterated blockciphers with polynomial keyspace are impossible. To prove this, we develop an abstraction of idealized iterated blockciphers and establish various basic properties, and apply Extremal Graph Theory results to prove the existence of certain (generalized) non-random properties such as the boomerang and yoyo.

An oblivious pseudorandom function, or OPRF, is an important primitive that is used to build many advanced cryptographic protocols. Despite its relevance, very few post-quantum solutions exist. In this work, we propose a novel OPRF protocol that is post-quantum, verifiable, round-optimal, and moderately compact. Our protocol is based on a previous SIDH-based construction by Boneh, Kogan, and Woo, which was later shown to be insecure due to an attack on its one-more unpredictability. We first propose an efficient countermeasure against this attack by redefining the PRF function to use irrational isogenies. This prevents a malicious user from independently evaluating the PRF. The SIDH-based construction by Boneh, Kogan, and Woo is also vulnerable to the recent attacks on SIDH. We thus demonstrate how to efficiently incorporate the countermeasures against such attacks to obtain a secure OPRF protocol. To achieve this, we also propose the first proof of isogeny knowledge that is compatible with masked torsion points, which may be of independent interest. Lastly, we design a novel non-interactive proof of knowledge of parallel isogenies, which reduces the number of communication rounds of the OPRF to the theoretically-optimal two. Putting everything together, we obtain the most compact post-quantum verifiable OPRF protocol.