This note explains how to guarantee the membership of a point in the prime-order subgroup of an elliptic curve (over a finite field) satisfying some moderate conditions. For this purpose, we apply the Tate pairing on the curve, however it is not required to be pairing-friendly. Whenever the cofactor is small, the new subgroup test is much more efficient than other known ones, because it needs to compute at most two $n$-th power residue symbols (with small $n$) in the basic field. More precisely, the running time of the test is (sub-)quadratic in the bit length of the field size, which is comparable with the Decaf-style technique. The test is relevant, e.g., for the zk-SNARK friendly curves Bandersnatch and Jubjub proposed by the Ethereum and Zcash research teams respectively.

We present two simple zero knowledge interactive proofs that can be instantiated with many of the standard decisional or computational hardness assumptions. Compared with traditional zero knowledge proofs, in our protocols the verifiers starts first, by emitting a challenge, and then the prover answers the challenge.

This paper presents a new method for quantum identity authentication (QIA) protocols. The logic of classical zero-knowledge proofs (ZKPs) due to Schnorr is applied in quantum circuits and algorithms. This novel approach gives an exact way with which a prover $P$ can prove they know some secret by encapsulating it in a quantum state before sending to a verifier $V$ by means of a quantum channel - allowing for a ZKP wherein an eavesdropper or manipulation can be detected with a fail-safe design. This is achieved by moving away from the hardness of the Discrete Logarithm Problem towards the hardness of estimating quantum states. This paper presents a method with which this can be achieved and some bounds for the security of the protocol provided. With the anticipated advent of a `quantum internet', such protocols and ideas may soon have utility and execution in the real world.

We introduce new protocols for private set intersection (PSI), building upon recent constructions of pseudorandom correlation generators, such as vector-OLE and ring-OLE. Our new constructions improve over the state of the art on several aspects, and perform especially well in the setting where the parties have databases with small entries. We obtain three main contributions: 1. We introduce a new semi-honest PSI protocol that combines subfield vector-OLE with hash-based PSI. Our protocol is the first PSI protocol to achieve communication complexity independent of the computational security parameter κ, and has communication lower than all previous known protocols for input sizes ℓ below 70 bits. 2. We enhance the security of our protocol to the malicious setting, using two different approaches. In particular, we show that applying the dual execution technique yields a malicious PSI whose communication remains independent of κ, and improves over all known PSI protocols for small values of ℓ. 3. As most previous protocols, our above protocols are in the random oracle model. We introduce a third protocol which relies on subfield ring-OLE to achieve maliciously secure PSI in the standard model, under the ring-LPN assumption. Our protocol enjoys extremely low communication, reasonable computation, and standard model security. Furthermore, it is batchable: the message of a client can be reused to compute the intersection of their set with that of multiple servers, yielding further reduction in the overall amortized communication.

Digital signature is an essential primitive in cryptography, which can be used as the digital analogue of handwritten signatures but also as a building block for more complex systems. In the latter case, signatures with specific features are needed, so as to smoothly interact with the other components of the systems, such as zero-knowledge proofs. This has given rise to so-called signatures with efficient protocols, a versatile tool that has been used in countless applications. Designing such signatures is however quite difficult, in particular if one wishes to withstand quantum computing. We are indeed aware of only one post-quantum construction, proposed by Libert et al. at Asiacrypt'16, yielding very large signatures and proofs. In this paper, we propose a new construction that can be instantiated in both standard lattices and structured ones, resulting in each case in dramatic performance improvements. In particular, the size of a proof of message-signature possession, which is one of the main metrics for such schemes, can be brought down to less than 650 KB. As our construction retains all the features expected from signatures with efficient protocols, it can be used as a drop-in replacement in all systems using them, which mechanically improves their own performance, and has thus a direct impact on many applications. It can also be used to easily design new privacy-preserving mechanisms. As an example, we provide the first lattice-based anonymous credentials system.

Registration-based encryption (RBE) was recently introduced as an alternative to identity-based encryption (IBE), to resolve the key-escrow problem: In RBE, the trusted authority is substituted with a weaker entity, called the key curator, who has no knowledge of any secret key. Users generate keys on their own and then publicly register their identities and their corresponding public keys to the key curator. RBE is a promising alternative to IBE, retaining many of its advantages while removing the key-escrow problem, the major drawback of IBE. Unfortunately, all existing constructions of RBE use cryptographic schemes in a non black-box way, which makes them prohibitively expensive. It has been estimated that the size of an RBE ciphertext would be in the order of terabytes (though no RBE has even been implemented). In this work, we propose a new approach to construct RBE, from standard assumptions in bilinear groups. Our scheme is black-box and it is concretely highly efficient---a ciphertext is 914 bytes. To substantiate this claim, we implemented a prototype of our scheme and we show that it scales to millions of users. The public parameters of the scheme are in the order of kilobytes. The most expensive operation (registration) takes at most a handful of seconds, whereas the encryption and decryption runtimes are on the order of milliseconds. This is the first ever implementation of an RBE scheme and demonstrates that the practical deployment of RBE is already possible with today's hardware.

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic. Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method. To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size. One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice. Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists' and cryptographers' needs when working with endomorphism rings of supersingular elliptic curves. This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes. Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20]. We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign.

The understanding of directionality for updatable encryption (UE) schemes is important, but not yet completed in the literature. We show that security in the backward-leak uni-directional key updates setting is equivalent to the no-directional one. Combining with the work of Jiang (ASIACRYPT 2020) and Nishimaki (PKC 2022), it is showed that the backward-leak notion is the strongest one among all known key update notions and more relevant in practice. We propose two novel generic constructions of UE schemes that are secure in the backward-leak uni-directional key update setting from public key encryption (PKE) schemes: the first one requires a key and message homomorphic PKE scheme and the second one requires a bootstrappable PKE scheme. These PKE can be constructed based on standard assumptions (such as the Decisional Diffie-Hellman and Learning With Errors assumptions).

We give some applications of the "embedding Lemma". The first one is a polynomial time (in $\log q$) algorithm to compute the endomorphism ring $\mathrm{End}(E)$ of an ordinary elliptic curve $E/\mathbb{F}_q$, provided we are given the factorisation of $Δ_π$. In particular, this computation can be done in quantum polynomial time. The second application is an algorithm to compute the canonical lift of $E/\mathbb{F}_q$, $q=p^n$, (still assuming that $E$ is ordinary) to precision $m$ in time $\tilde{O}(n m \log^{O(1)} p)$. We deduce a point counting algorithm of complexity $\tilde{O}(n^2 \log^{O(1)} p)$. In particular the complexity is polynomial in $\log p$, by contrast of what is usually expected of a $p$-adic cohomology computation. The third application is a quasi-linear CRT algorithm to compute Siegel modular polynomials of elliptic curves, which does not rely on any heuristic or conditional result (like GRH). We also outline how to generalize these algorithms to (ordinary) abelian varieties.

Collision resistance and collision finding are now extensively exploited in Cryptography, especially in the case of quantum computing. For any function $f:[M]\to[N]$ with $f(x)$ uniformly distributed over $[N]$, Zhandry has shown that the number $\Theta(N^{1/3})$ of queries is both necessary and sufficient for finding a collision in $f$ with constant probability. However, there is still a gap between the upper and the lower bounds of query complexity in general non-uniform distributions. In this paper, we investigate the quantum query complexity of collision-finding problem with respect to general non-uniform distributions. Inspired by previous work, we pose the concept of collision domain and a new parameter $\gamma$ that heavily depends on the underlying non-uniform distribution. We then present a quantum algorithm that uses $O(\gamma^{1/6})$ quantum queries to find a collision for any non-uniform random function. By making a transformation of a problem in non-uniform setting into a problem in uniform setting, we are also able to show that $\Omega(\gamma^{1/6}\log^{-1/2}\gamma)$ quantum queries are necessary in collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicates that the proposed algorithm is nearly optimal with query complexity in general non-uniform case.

Recent private information retrieval (PIR) schemes preprocess the database with a query-independent offline phase in order to achieve sublinear computation during a query-specific online phase. These offline/online protocols expand the set of applications that can profitably use PIR, but they make a critical assumption: that the database is immutable. In the presence of changes such as additions, deletions, or updates, existing schemes must preprocess the database from scratch, wasting prior effort. To address this, we introduce incremental preprocessing for offline/online PIR schemes, allowing the original preprocessing to continue to be used after database changes, while incurring an update cost proportional to the number of changes rather than the size of the database. We adapt two offline/online PIR schemes to use incremental preprocessing and show how it significantly improves the throughput and reduces the latency of applications where the database changes over time.

The lightweight block ciphers ULC and LICID are introduced by Sliman et al. (2021) and Omrani et al. (2019) respectively. These ciphers are based on substitution permutation network structure. ULC is designed using the ULM method to increase efficiency, memory usage, and security. On the other hand, LICID is specifically designed for image data. In the ULC paper, the authors have given a full-round differential characteristic with a probability of $2^{-80}$. In the LICID paper, the authors have presented an 8-round differential characteristic with a probability of $2^{-112.66}$. In this paper, we present the 15-round ULC and the 14-round LICID differential characteristics of probabilities $2^{-45}$ and $2^{-40}$ respectively using the MILP model.

The interest shown by central banks in deploying Central Bank Digital Currency (CBDC) has spurred a blooming number of conceptually different proposals from central banks and academia. Yet, they share the common, transversal goal of providing citizens with an additional digital monetary instrument. Citizens, equipped with CBDC wallets, should have access to CBDC fund and defund operations that allow the distribution of CBDC from the central bank to citizens with the intermediation of commercial banks. Despite their key role in the CBDC deployment as acknowledged, e.g., by the European Central Bank, operations fund and defund have not been formally studied yet. In this state of affairs, this work strives to cryptographically define the problem of fund and defund of CBDC wallets as well as the security and privacy notions of interest. We consider a setting with three parties (citizen, commercial bank and central bank) and three ledgers: the CBDC ledger, the retail ledger (where citizens have their accounts with their commercial banks) and the wholesale ledger (where commercial banks have their accounts with the central bank). We follow a modular approach, initially defining the functionality of two types of ledgers: Basic Ledger (BL), which supports basic transactions, and Conditional Payment Ledger(CP), which additionally supports conditional transactions. We then use BL and CP to define the CBDC-Cash Environment (CCE) primitive, which captures the core functionality of operations fund and defund. We require that CCE satisfies balance security: either operation fund/defund is successful, or no honest party loses their funds. CCE also satisfies that fund/defund cannot be used to breach the privacy of the CBDC ledger. Finally, we provide two efficient and secure constructions for CCE to cover both CP and BL types of CBDC ledger. Our performance evaluation shows that our constructions impose small computation and communication overhead to the underlying ledgers. The modular design of CCE allows for the incorporation in our CCE constructions of any CBDC ledger proposal that can be proven a secure instance of CP or BL, enabling thereby a seamless method to provide CBDC fund and defund operations.

Functional encryption features secret keys, each associated with a key function $f$, which allow to directly recover $f(x)$ from an encryption of $x$, without learning anything more about $x$. This property is particularly useful when delegating data processing to a third party as it allows the latter to perfom its task while ensuring minimum data leakage. However, this generic term conceals a great diversity in the cryptographic constructions that strongly differ according to the functions $f$ they support. A recent series of works has focused on the ability to search a pattern within a data stream, which can be expressed as a function $f$. One of the conclusions of these works was that this function $f$ was not supported by the current state-of-the-art, which incited their authors to propose a new primitive called Stream Encryption supporting Pattern Matching (SEPM). Some concrete constructions were proposed but with some limitations such as selective security or reliance on non-standard assumptions. In this paper, we revisit the relations between this primitive and two major subclasses of functional encryption, namely Hidden Vector Encryption (HVE) and Inner Product Encryption (IPE). We indeed first exhibit a generic transformation from HVE to SEPM, which immediately yields new efficient SEPM constructions with better features than existing ones. We then revisit the relations between HVE and IPE and show that we can actually do better than the transformation proposed by Katz, Sahai and Waters in their seminal paper on predicate encryption. This allows to fully leverage the vast state-of-the-art on IPE which contains adaptively secure constructions proven under standard assumptions. This results in countless new SEPM constructions, with all the features one can wish for. Beyond that, we believe that our work sheds a new light on the relations between IPE schemes and HVE schemes and in particular shows that some of the former are more suitable to construct the latter.

Recent works of Roughgarden (EC'21) and Chung and Shi (SODA'23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a dream TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming finite block size, no non-trivial TFM can simultaenously provide incentive compatibility for any individual user, and for any miner-user coalition. In this work, we explore what new models and meaningful relaxations can allow us to circumvent the impossibility results of Chung and Shi. Besides today’s model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We prove several feasibility and infeasibility results for achieving strict and approximate incentive compatibility, respectively, in the plain model as well as the MPC-assisted model. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. Our work is also the first to characterize the mathematical landscape of transaction fee mechanism design under approximate incentive compatibility, as well as in a cryptography-assisted model.

The share size of general secret-sharing schemes is poorly understood. The gap between the best known upper bound on the total share size per party of $2^{0.59n}$ (Applebaum and Nir, CRYPTO 2021) and the best known lower bound of $\Omega(n/\log n)$ (Csirmaz, J. of Cryptology 1997) is huge (where $n$ is the number of parties in the scheme). To gain some understanding on this problem, we study the share size of secret-sharing schemes of almost all access structures, i.e., of almost all collections of authorized sets. This is motivated by the fact that in complexity, many times almost all objects are hardest (e.g., most Boolean functions require exponential size circuits). All previous constructions of secret-sharing schemes were for the worst access structures (i.e., all access structures) or for specific families of access structures. We prove upper bounds on the share size for almost all access structures. We combine results on almost all monotone Boolean functions (Korshunov, Probl. Kibern. 1981) and a construction of (Liu and Vaikuntanathan, STOC 2018) and conclude that almost all access structures have a secret-sharing scheme with share size $2^{\tilde{O}(\sqrt{n})}$. We also study graph secret-sharing schemes. In these schemes, the parties are vertices of a graph and a set can reconstruct the secret if and only if it contains an edge. Again, for this family there is a huge gap between the upper bounds - $O(n/\log n)$ (Erdös and Pyber, Discrete Mathematics 1997) - and the lower bounds - $\Omega(\log n)$ (van Dijk, Des. Codes Crypto. 1995). We show that for almost all graphs, the share size of each party is $n^{o(1)}$. This result is achieved by using robust 2-server conditional disclosure of secrets protocols, a new primitive introduced and constructed in (Applebaum et al., STOC 2020), and the fact that the size of the maximal independent set in a random graph is small. Finally, using robust conditional disclosure of secrets protocols, we improve the total share size for all very dense graphs.

In this paper, we propose a variable-sized, one-way, and randomized secure hash algorithm, VORSHA for short. We present six variants of VORSHA, which are able to generate a randomized secure hash value. VORSHA is the first secure hash algorithm to randomize the secure hash value fully. The key embodiment of our proposed algorithm is to generate a pool of pseudo-random bits using the primary hash functions and selects a few bits from the pool of bits to form the final randomized secure hash value. Each hash value of the primary hash function produces a single bit (either 0 or 1) for the pool of pseudo-random bits. Thus, VORSHA randomized the generated bit string to produce the secure hash value, and we term it as a randomized secure hash value. Moreover, the randomized secure hash value is tested using NIST-SP 800-22 statistical test suite, and the generated randomized secure hash value of VORSHA has passed all 15 statistical tests of NIST-SP 800-22. It proves that the VORSHA is able to generate a highly unpredictable yet consistent secure hash value. Moreover, VORSHA features a memory-hardness property to restrict a high degree of parallelism, which features a tiny memory footprint for legal users but massive memory requirements for adversaries. Furthermore, we demonstrate how to prevent Rainbow Table as a Service (RTaaS) attack using VORSHA. The source code is available at https://github.com/patgiri/VORSHA.

We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.

Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency, that allows users to atomically exchange coins. While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting (which also degrades fungibility and leads to high transaction fees), do not support atomic swaps across a wide range of currencies, or come with incomplete security proofs. To overcome these limitations, we introduce Sweep-UC (Read as Sweep Ur Coins), the first fair exchange protocol that simultaneously is efficient, minimizes scripting, and is compatible with a wide range of currencies (more than the state of the art). We build Sweep-UC from modular sub-protocols and give a rigorous security analysis in the UC-framework. Many of our tools and security definitions can be used in standalone fashion and may serve as useful components for future constructions of fair exchange.

We introduce CorrGapCDH, the Gap Computational Diffie-Hellman problem in the multi-user setting with Corruptions. In the random oracle model, our assumption tightly implies the security of the authenticated key exchange protocols NAXOS in the eCK model and (a simplified version of) X3DH without ephemeral key reveal. We prove hardness of CorrGapCDH in the generic group model, with optimal bounds matching the one of the discrete logarithm problem. We also introduce CorrCRGapCDH, a stronger Challenge-Response variant of our assumption. Unlike standard GapCDH, CorrCRGapCDH implies the security of the popular AKE protocol HMQV in the eCK model, tightly and without rewinding. Again, we prove hardness of CorrCRGapCDH in the generic group model, with (almost) optimal bounds. Our new results allow implementations of NAXOS, X3DH, and HMQV without having to adapt the group sizes to account for the tightness loss of previous reductions. As a side result of independent interest, we also obtain modular and simple security proofs from standard GapCDH with tightness loss, improving previously known bounds.

In practical operational networks, it is essential to validate path integrity, especially when untrusted intermediate nodes are from numerous network infrastructures operated by several network authorities. Current solutions often reveal the entire path to all parties involved, which may potentially expose the network structures to malicious intermediate attackers. Additionally, there is no prior work done to provide a systematic approach combining the complete lifecycle of packet delivery, i.e., path slicing, path validation and path rerouting, leaving these highly-intertwined modules completely separated. In this work, we present a decentralized privacy-preserving path validation system 𝑃3𝑉 that integrates our novel path validation protocol with an efficient path slicing algorithm and a malice-resilient path rerouting mechanism. Specifically, leveraging Non-Interactive Zero-Knowledge proofs, our path validation protocol XOR-Hash-NIZK protects the packet delivery tasks against information leakage about multi-hop paths and potentially the underlying network infrastructures. We implemented and evaluated our system on a state-of-the-art 5G Dispersed Computing Testbed simulating a multi-authority network. Our results show that while preserving the privacy of paths and nodes and enhancing the security of network service, our system optimizes the performance trade-off between network service quality and security/privacy.

Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, the ascending price auction with reserves is the only credible, strategyproof, revenue-optimal auction. Ferreira and Weinberg (2020) proposed the Deferred Revelation Auction (DRA) as a communication efficient auction that avoids the uniqueness results from (2020) assuming the existence of cryptographic commitments and as long as bidder valuations are MHR. They also showed DRA is not credible in settings where bidder valuations are $\alpha$-strongly regular unless $\alpha$ > 1. In this paper, we ask if blockchains allow us to design a larger class of credible auctions. We answer this question positively, by showing that DRA is credible even for $\alpha$-strongly regular distributions for all $\alpha$ > 0 if implemented over a secure and censorship-resistant blockchain. We argue ledgers provide two properties that limit deviations from a self-interested auctioneer. First, the existence of smart contracts allows one to extend the concept of credibility to settings where the auctioneer does not have a reputation — one of the main limitations for the definition of credibility from Akbarpour and Li (2020). Second, blockchains allow us to implement mechanisms over a public broadcast channel, removing the adaptive undetectable deviations driving the negative results of Ferreira and Weinberg (2020).

The 2014 European eIDAS regulation regulates strong electronic authentication and legally binding electronic signatures. Both require user "sole control". Historically smartcards are used based on direct interaction between user and relying party. Here sole control is provided by giving users both physical possession and control of the cryptographic key used for signing/authentication through a PIN. Such **classical** sole control is required in the 1999 electronic signature directive by some interpretations. The eIDAS regulation repeals the directive and explicitly relaxes its sole control requirements in a trade-off between security and usability. This allows user interaction to be outsourced to intermediary parties (authentication providers, signing services). This also allows mobile applications as user friendly alternatives for smartcards. However, current mobile platforms are only equipped with limited cryptographic hardware not supporting secure knowledge factors (PINs) controlling keys. The eIDAS relaxation raises concerns on sole control; intermediary parties should not be able to act as man-in-the-middle and impersonate users. In this paper we present a simple cryptographic design for signing and authentication on standard mobile platforms providing classical sole control. We argue that our design can meet the highest eIDAS requirements, effectively introducing a new signature category in a 2016 decision of the European Commission. We also sketch a SECDSA based implementation of the European Digital Identity Wallet recently proposed by the European Commission as part of the eIDAS regulation update.

This note describes two pairing-friendly curves that embed ed25519, of different bit security levels. Our search is not novel; it follows the standard recipe of the Cocks-Pinch method. We implemented these two curves on arkworks-rs. This note is intended to document how the parameters are being generated and how to implement these curves in arkworks-rs 0.4.0, for further reference. We name the two curves as Yafa-108 and Yafa-146: - Yafa-108 is estimated to offer 108-bit security, which we parameterized to match the 103-bit security of BN254 - Yafa-146 is estimated to offer 146-bit security, which we parameterized to match the 132-bit security of BLS12-446 or 123-bit security of BLS12-381 We use these curves as an example to demonstrate two things: - The "elastic" zero-knowledge proof, Gemini (EUROCRYPT '22), is more than being elastic, but it is more curve-agnostic and hardware-friendly. - The cost of nonnative field arithmetics can be drastic, and the needs of application-specific curves may be inherent. This result serves as evidence of the necessity of EIP-1962, and the insufficiency of EIP-2537.

In a single secret leader election protocol (SSLE), one of the system participants is chosen and, unless it decides to reveal itself, no other participant can identify it. SSLE has a great potential in protecting blockchain consensus protocols against denial of service (DoS) attacks. However, all existing solutions either make strong synchrony assumptions or have expiring registration, meaning that they require elected processes to re-register themselves before they can be re-elected again. This, in turn, prohibits the use of these SSLE protocols to elect leaders in partially-synchronous consensus protocols as there may be long periods of network instability when no new blocks are decided and, thus, no new registrations (or re-registrations) are possible. In this paper, we propose Homomorphic Sortition -- the first asynchronous SSLE protocol with non-expiring registration, making it the first solution compatible with partially-synchronous leader-based consensus protocols. Homomorphic Sortition relies on Threshold Fully Homomorphic Encryption (ThFHE) and is tailored to proof-of-stake (PoS) blockchains, with several important optimizations with respect to prior proposals. In particular, unlike most existing SSLE protocols, it works with arbitrary stake distributions and does not require a user with multiple coins to be registered multiple times. Our protocol is highly parallelizable and can be run completely off-chain after setup. Some blockchains require a sequence of rounds to have non-repeating leaders. We define a generalization of SSLE, called Secret Leader Permutation (SLP) in which the application can choose how many non-repeating leaders should be output in a sequence of rounds and we show how Homomorphic Sortition also solves this problem.

SQISign is an isogeny-based signature scheme that has short keys and signatures and is expected to be a post-quantum scheme. Its security depends on the hardness of the problem to find an isogeny between given two elliptic curves over $\mathbb{F}_{p^2}$, where $p$ is a large prime. For efficiency reasons, a public key in SQISign is taken from a set of supersingular elliptic curves with a particular property. In this paper, we investigate the security related to public keys in SQISign. First, we show some properties of the set of public keys. Next, we show that a key generation procedure used in implementing SQISign could not generate all public keys and propose a modification for the procedure. In addition, we confirm the latter result through an experiment.

Private function evaluation (PFE) is a special type of MPC protocols that, in addition to the input privacy, can preserve the function privacy. In this work, we propose a PFE scheme for RAM. In particular, we first design an efficient 4-server distributed ORAM scheme with amortized communication $O(\log n)$ per access (both reading and writing). We then simulate a RISC RAM machine over the MPC platform, hiding (i) the memory access pattern, (ii) the machine state (including registers, program counter, condition flag, etc.), and (iii) the executed instructions. Our scheme can naturally support a simplified TinyRAM instruction set; if a public RAM program $P$ with given inputs $x$ needs to execute $z$ instruction cycles, our PFE scheme is able to securely evaluate $P(x)$ on private $P$ and $x$ within $5z+1$ online rounds. We prototype and benchmark our system for set intersection, binary search, quicksort, and heapsort algorithms. For instance, to obliviously perform the binary search algorithm on a $2^{10}$ array takes $5.81s$ with function privacy.

Amortized bootstrapping offers a way to simultaneously refresh many ciphertexts of a fully homomorphic encryption scheme, at a total cost comparable to that of refreshing a single ciphertext. An amortization method for FHEW-style cryptosystems was first proposed by (Micciancio and Sorrell, ICALP 2018), who showed that the amortized cost of bootstrapping n FHEW-style ciphertexts can be reduced from $O(n)$ basic cryptographic operations to just $O(n^{\epsilon})$, for any constant $\epsilon>0$. However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the asymptotic notation. In this work, we propose an alternative amortized boostrapping method with much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost, but with a hidden constant that is only linear in $1/\epsilon$, and with reduced noise growth. This is achieved following the general strategy of (Micciancio and Sorrell), but replacing their use of the Nussbaumer transform, with a much more practical Number Theoretic Transform, with multiplication by twiddle factors implemented using ring automorphisms. A key technical ingredient to do this is a new "scheme switching" technique proposed in this paper which may be of independent interest.

A few small-state stream ciphers (SSCs) were proposed for constrained environments. All of the SSCs before the LILLE stream cipher suffered from distinguishing attacks and fast correlation attacks. The designers of LILLE claimed that it is based on the well-studied two-key Even-Mansour scheme and so is resistant to various types of attacks. This paper proposes a distinguishing attack on LILLE, the first attack since 2018. The data and time complexities to attack LILLE-40 are 2^(50.7) and 2^(41.2), respectively. We verified practically our attack on a halved version of LILLE-40. A countermeasure is suggested to strengthen LILLE against the proposed attack. We hope our attack opens the door to more cryptanalyses of LILLE.

In this paper, we present the first chosen-ciphertext (CC) cache-timing attacks on the reference implementation of HQC. We build a cache-timing based distinguisher for implementing a plaintext-checking (PC) oracle. The PC oracle uses side-channel information to check if a given ciphertext decrypts to a given message. This is done by identifying a vulnerability during the generating process of two vectors in the reference implementation of HQC. We also propose a new method of using PC oracles for chosen-ciphertext side-channel attacks against HQC, which may have independent interest. We show a general proof-of-concept attack, where we use the Flush&Reload technique and also derive, in more detail, a practical attack on an HQC execution on Intel SGX, where the Prime&Probe technique is used. We show the exact path to do key recovery by explaining the detailed steps, using the PC oracle. In both scenarios, the new attack requires $53,857$ traces on average with much fewer PC oracle calls than the timing attack of Guo et al. CHES 2022 on an HQC implementation.

In CRYPTO 2012, Zhandry developed generic semi-constant oracle technique and proved security of an identity-based encryption scheme, GPV-IBE, and full domain hash (FDH) signature scheme in the quantum random oracle model (QROM). However, the reduction provided by Zhandry incurred a quadratic reduction loss. In this work, we provide a much tighter proof, with linear reduntion loss, for the FDH, probabilistc FDH (PFDH), and GPV-IBE in the QROM. Our proof is based on the measure-and-reprogram technique developed by Don, Fehr, Majenz and Schaffner.

Micciancio and Sorrel (ICALP 2018) proposed a bootstrapping algorithm that can refresh many messages at once with sublinearly many homomorphic operations per message. However, despite the attractive asymptotic cost, it is unclear if their algorithm could ever be practical, which reduces the impact of their results. In this work, we follow their general framework, but propose an amortized bootstrapping that is conceptually simpler and asymptotically cheaper. We reduce the number of homomorphic operations per refreshed message from $O(3^\rho \cdot n^{1/\rho} \cdot \log n)$ to $O(\rho \cdot n^{1/\rho})$, and the noise overhead from $\tilde{O}(n^{2 + 3 \cdot \rho})$ to $\tilde{O}(n^{1 + \rho})$. We also make it more general, by handling non-binary messages and applying programmable bootstrapping. To obtain a concrete instantiation of our bootstrapping algorithm, we propose a double-CRT (aka RNS) version of the GSW scheme, including a new operation, called shrinking, used to speed-up homomorphic operations by reducing the dimension and ciphertext modulus of the ciphertexts. We also provide a C++ implementation of our algorithm, thus showing for the first time the practicability of the amortized bootstrapping. Moreover, it is competitive with existing bootstrapping algorithms, being even around 3.4 times faster than an equivalent non-amortized version of our bootstrapping.

Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three strategies for developing SAT models for 8-bit S-boxes that are geared toward differential probabilities and linear correlations. While these approaches cannot guarantee a minimum model size, the time needed to obtain models is drastically reduced. The newly proposed SAT model for large S-boxes enables us to establish that the upper bound on the differential probability for 14 rounds of SKINNY-128 is 2^{-131}, thereby completing the unsuccessful work of Abdelkhalek et al. We also analyse the seven AES-based constructions C1 - C7 designed by Jean and Nikolic and compute the minimum number of active S-boxes necessary to cause an internal collision using the SAT method. For two constructions C3 and C5, the current lower bound on the number of active S-boxes is increased, resulting in a more precise security analysis for these two structures.

We introduce Grotto, a framework and C++ library for space- and time-efficient $(2+1)$-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over $\mathbb{Z}_{2^{n}}$. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ``tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a single DPF what state-of-the-art approaches require many DCFs to do. Our open-source Grotto implementation supports evaluating dozens of useful functions out of the box, including trigonometric and hyperbolic functions (and their inverses); various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common (univariate) activation functions from the deep-learning literature.

This paper specifies a new arithmetization-oriented hash function called Tip5. It uses the SHARK design strategy with low-degree power maps in combination with lookup tables, and is tailored to the field with $p=2^{64}-2^{32}+1$ elements. The context motivating this design is the recursive verification of STARKs. This context imposes particular design constraints, and therefore the hash function's arithmetization is discussed at length.

Streamlined NTRU Prime is a lattice-based Key Encapsulation Mechanism (KEM) that is, together with X25519, currently the default algorithm in OpenSSH 9. Being based on lattice assumptions, it is assumed to be secure also against attackers with access to large-scale quantum computers. While Post-Quantum Cryptography (PQC) schemes have been subject to extensive research in the recent years, challenges remain with respect to protection mechanisms against attackers that have additional side-channel information such as the power consumption of a device processing secret data. As a countermeasure to such attacks, masking has been shown to be a promising and effective approach. For public-key schemes, including any recent PQC schemes, usually a mixture of Boolean and arithmetic approaches are applied on an algorithmic level. Our generic hardware implementation of Streamlined NTRU Prime decapsulation, however, follows an idea that until now was assumed to be only applicable to symmetric cryptography: gate-level masking. There, a hardware design that consists of logic gates is transformed into a secure implementation by replacing each gate with a composably secure gadget that operates on uniform random shares of secret values. In our work, we show the feasibility of applying this approach also to PQC schemes and present the first Public-Key Cryptography (PKC) – pre- and post-quantum – implementation masked at gate level considering several trade-offs and design choices. We synthesize our implementation both for Artix-7 Field-Programmable Gate Arrays (FPGAs) and 45 nm Application-Specific Integrated Circuits (ASICs), yielding practically feasible results regarding area, randomness demand and latency. Finally, we also analyze the applicability of our concept to Kyber which will be standardized by the National Institute of Standards and Technology (NIST).

In this work, we investigate the BGV scheme as implemented in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most $1.8$ bits off the experimentally observed values, they are as much as $29$ bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be $k$ times larger than the current ciphertext modulus $Q_i$. For a ratio of subsequent ciphertext moduli $\log\left( \frac{Q_i}{Qi−1}\right) = 54$ (a very common choice in HElib), we can optimise $k$ by up to $26$ bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.

In $1$-out-of-$q$ Oblivious Transfer (OT) protocols, a sender Alice is able to send one of $q\ge 2$ messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take $n$ instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the $n$ original OT instances are secure. We present new $1$-out-of-$q$ OT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an $\mathbb{F}_q$-linear secret sharing scheme on a set of $n$ participants and adversary structure $\mathcal{A}$, we can construct $n$-server, $1$-out-of-$q$ OT combiners that are secure against an adversary corrupting either Alice and a set of servers in $\mathcal{A}$, or Bob and a set of servers $B$ with $\bar{B}\notin\mathcal{A}$. If the normalized total share size of the scheme is $\ell$, then the resulting OT combiner requires $\ell$ calls to OT protocols, and the total amount of bits exchanged during the protocol is $(q^2+q+1)\ell\log q$. We also present a construction based on $1$-out-of-$2$ OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power $q\geq n$, there are $n$-server, $1$-out-of-$q$ OT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchanging $O(qn\log q)$ bits in total.

An important cryptographic operation on elliptic curves is hashing to a point on the curve. When the curve is not of prime order, the point is multiplied by the cofactor so that the result has a prime order. This is important to avoid small subgroup attacks for example. A second important operation, in the composite-order case, is testing whether a point belongs to the subgroup of prime order. A pairing is a bilinear map e : G1 × G2 → GT where G1 and G2 are distinct subgroups of prime order r of an elliptic curve, and GT is a multiplicative subgroup of the same prime order r of a finite field extension. Pairing-friendly curves are rarely of prime order. We investigate cofactor clearing and subgroup membership testing on these composite-order curves. First, we generalize a result on faster cofactor clearing for BLS curves to other pairing-friendly families of a polynomial form from the taxonomy of Freeman, Scott and Teske. Second, we investigate subgroup membership testing for G1 and G2. We fix a proof argument for the G2 case that appeared in a preprint by Scott in late 2021 and has recently been implemented in different cryptographic libraries. We then generalize the result to both G1 and G2 and apply it to different pairing-friendly families of curves. This gives a simple and shared framework to prove membership tests for both cryptographic subgroups.

Encryption satisfying CCA2 security is commonly known to be unnecessarily strong for realizing secure channels. Moreover, CCA2 constructions in the standard model are far from being competitive practical alternatives to constructions via random oracle. A promising research area to alleviate this problem are weaker security notions—like IND-RCCA secure encryption or IND-atag-wCCA secure tag-based encryption—which are still able to facilitate secure message transfer (SMT) via authenticated channels. In this paper we introduce the concept of sender-binding encryption (SBE), unifying prior approaches of SMT construction in the universal composability (UC) model. We furthermore develop the corresponding non-trivial security notion of IND-SB-CPA and formally prove that it suffices for realizing SMT in conjunction with authenticated channels. Our notion is the weakest so far in the sense that it generically implies the weakest prior notions—RCCA and atag-wCCA—without additional assumptions, while the reverse is not true. A direct consequence is that IND-stag-wCCA, which is strictly weaker than IND-atag-wCCA but stronger than our IND-SB-CPA, can be used to construct a secure channel. Finally, we give an efficient IND-SB-CPA secure construction in the standard model from IND-CPA secure double receiver encryption (DRE) based on McEliece. This shows that IND-SB-CPA security yields simpler and more efficient constructions in the standard model than the weakest prior notions, i.e., IND-atag-wCCA and IND-stag-wCCA.

Thesecurityofmanyprotocolssuchasvotingandblockchains relies on a secure source of randomness. Decentralised Randomness Beacon (DRB) has been considered as a promising approach, where a set of participants jointly generates a sequence of random outputs. While the DRBs have been extensively studied, they failed to capture the advantage that some participants learn random outputs earlier than other participants. In time-sensitive protocols whose execution depends on the randomness from a DRB, such an advantage allows the adversary to behave adaptively according to random outputs, compromising the fairness and/or security in these protocols. In this paper, we formalise a new property, delivery-fairness, to quantify the advantage. In particular, we distinguish two aspects of delivery-fairness, namely length-advantage, i.e., how many random outputs an adversary can learn earlier than correct participants, and time-advantage, i.e., how much time an adversary can learn a given random output earlier than correct participants. In addition, we prove the lower bound of delivery-fairness showing optimal guarantee. We further analyse the delivery-fairness guarantee of state-of-the-art DRBs and discuss insights, which, we show through case studies, could help improve delivery-fairness of existing systems to its optimal.

This paper combines techniques from several previous papers with some modifications to improve the previous cryptanalysis of 3-round Keccak-256. Furthermore, we propose a fast rebuilding method to improve the efficiency of solving equation systems. As a result, the guessing times of finding a preimage for 3-round Keccak-256 are decreased from $2^{65}$ to $2^{52}$, and the solving time of each guess is decreased from $2^{9}$ 3-round Keccak calls to $2^{5.3}$ 3-round Keccak calls. We identify a preimage of all '0' digest for 3-round Keccak-256 to support the effectiveness of our methodology.

State-separating proofs (SSP) is a recent methodology for structuring game-based cryptographic proofs in a modular way, by using algebraic laws to exploit the modular structure of composed protocols. While promising, this methodology was previously not fully formalized and came with little tool support. We address this by introducing SSProve, the first general verification framework for machine-checked state-separating proofs. SSProve combines high-level modular proofs about composed protocols, as proposed in SSP, with a probabilistic relational program logic for formalizing the lower-level details, which together enable constructing fully machine-checked cryptographic proofs in the Coq proof assistant. Moreover, SSProve is itself formalized in Coq, including the algebraic laws of SSP, the soundness of the program logic, and the connection between these two verification styles. To illustrate SSProve we use it to mechanize the simple security proofs of ElGamal and PRF-based encryption. We also validate the SSProve approach by conducting two more substantial case studies: First, we mechanize an SSP security proof of the KEM-DEM public key encryption scheme, which led to the discovery of an error in the original paper proof that has since been fixed. Second, we use SSProve to formally prove security of the sigma-protocol zero-knowledge construction, and we moreover construct a commitment scheme from a sigma-protocol to compare with a similar development in CryptHOL. We instantiate the security proof for sigma-protocols to give concrete security bounds for Schnorr's sigma-protocol.

Secure neural network inference has been a promising solution to private Deep-Learning-as-a-Service, which enables the service provider and user to execute neural network inference without revealing their private inputs. However, the expensive overhead of current schemes is still an obstacle when applied in real applications. In this work, we present \textsc{Meteor}, an online communication-efficient and fast secure 3-party computation neural network inference system aginst semi-honest adversary in honest-majority. The main contributions of \textsc{Meteor} are two-fold: \romannumeral1) We propose a new and improved 3-party secret sharing scheme stemming from the \textit{linearity} of replicated secret sharing, and design efficient protocols for the basic cryptographic primitives, including linear operations, multiplication, most significant bit extraction, and multiplexer. \romannumeral2) Furthermore, we build efficient and secure blocks for the widely used neural network operators such as Matrix Multiplication, ReLU, and Maxpool, along with exploiting several specific optimizations for better efficiency. Our total communication with the setup phase is a little larger than SecureNN (PoPETs'19) and \textsc{Falcon} (PoPETs'21), two state-of-the-art solutions, but the gap is not significant when the online phase must be optimized as a priority. Using \textsc{Meteor}, we perform extensive evaluations on various neural networks. Compared to SecureNN and \textsc{Falcon}, we reduce the online communication costs by up to $25.6\times$ and $1.5\times$, and improve the running-time by at most $9.8\times$ (resp. $8.1\times$) and $1.5\times$ (resp. $2.1\times$) in LAN (resp. WAN) for the online inference.

TLS termination, which is essential to network and security infrastructure providers, is an extremely latency sensitive operation that benefits from access to sensitive key material close to the edge. However, increasing regulatory concerns prompt customers to demand sophisticated controls on where their keys may be accessed. While traditional access-control solutions rely on a highly available centralized process to enforce access, the round-trip latency and decreased fault tolerance make this approach unappealing. Furthermore, the desired level of customer control is at odds with customizing the distribution process for each key. To solve this dilemma, we have designed and implemented Portunus, a cryptographic storage and access control system built using a variant of public-key cryptography called attribute-based encryption (ABE). Using Portunus, TLS keys are protected using ABE under a policy chosen by the customer. Each server is issued unique ABE keys based on its attributes, allowing it to decrypt only the TLS keys for which it satisfies the policy. Thus, the encrypted keys can be stored at the edge, with access control enforced passively through ABE. If a server receives a TLS connection but is not authorized to decrypt the necessary TLS key, the request is forwarded directly to the nearest authorized server, further avoiding the need for a centralized coordinator. In comparison, a trivial instantiation of this system using standard public-key cryptography might wrap each TLS key with the key of every authorized data center. This strategy, however, multiplies the storage overhead by the number of data centers. We have deployed Portunus on Cloudflare's global network of over 400 data centers. Our measurements indicate that we can handle millions of requests per second globally, making it one of the largest deployments of ABE.

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can not realistically accommodate large numbers of parties. In this work we present the first global-scale multiparty garbling protocol. The per-party communication complexity of our protocol decreases as the number of parties participating in the protocol increases---for the first time matching the asymptotic communication complexity of non-constant round MPC protocols. Our protocol achieves malicious security in the honest-majority setting and relies on the hardness of the Learning Party with Noise assumption.

FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions. In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model. Through the MILP analysis, we were able to find differential and linear distinguishers for up to 5 rounds of FUTURE, extending the known distinguishers of the cipher by one round.

Recent years have witnessed a push to bring multi-party computation (MPC) to practice and make it accessible to the end user/programmer. Despite novel ideas, on frontend language design (e.g., Wysteria, Viaduct), backend protocol design and implementation (e.g., ABY, MOTION), or both (e.g., SPDZ), classical compiler optimizations remain largely under-utilized (if not completely unused) in MPC programming. A likely reason is that such optimizations are often applied on a middle-end intermediate representation such as SSA. We put forth a methodology for an MPC programming compilation toolchain, which by mimicking the compilation methodology of standard imperative languages enables middle-end optimizations on MPC, yielding significant improvements. To this direction we devise an MPC circuit compiler that allows MPC programming in what is essentially Python, and inherits the structure (and therefore optimization opportunities) of the classical compilation pipeline. Our key conceptual contribution is advancing an intermediate language, which we call MPC-IR, that can be viewed as the analogue, in an MPC program’s compilation, of (enriched) SSA form. MPC-IR is a particularly appealing intermediate language as it allows backend-independent optimizations, a close analogy to machine independent optimizations in classical compilers. Demonstrating the power of our approach, we focus on a specific backend-independent optimization, SIMD-vectorization: We devise a novel classical-compiler-inspired automatic SIMD-vectorization on MPC-IR, which we show leads to significant speedup in circuit generation time and running time, as well as significant reduction in communication size and number of gates over the corresponding iterative schedule. We implement and benchmark our compiler from a Python-like program to an optimized circuit that can be fed into an MPC backend (for our benchmarks we make use of the MOTION backend for MPC). We view our exhaustive benchmarks as both a way to validate our optimization and end-to-end compiler, and as a contribution, by itself, to a more complete benchmarks suite for MPC programming—such benchmarks suites are common in classical compilers.

We present a new construction for secure logistic regression training, which enables two parties to train a model on private secret-shared data. Our goal is to minimize online communication and round complexity, while still allowing for an efficient offline phase. As part of our construction we develop many building blocks of independent interest. These include a new approximation technique for the sigmoid function, which results in a secure protocol with better communication; secure spline evaluation and secure powers computation protocols for fixed-point values; and a new comparison protocol that optimizes online communication. We also present a new two-party protocol for generating keys for distributed point functions (DPFs) over arithmetic sharing, where previous constructions do this only for Boolean outputs. We implement our protocol in an end-to-end system and benchmark its efficiency. We can securely evaluate a sigmoid in $18$ ms online time and $0.5$ KB of online communication. Our system can train a model over a database with $70,000$ samples and $15$ features with online communication of $208.09$ MB and online time of $2.24$ hours at the cost of $6.11$c over WAN. Our benchmarks demonstrate that we reduce online communication over state of the art by $\approx 10 \times$ for sigmoid and $\approx38\times$ for logistic regression training.

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods -- we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities. Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. has briefly noticed this issue, we present the first comprehensive study of correctness in UC PAKE. Our contributions are four-fold: 1. We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE; 2. We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable; 3. We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible; 4. Finally, we show how to naturally incorporate correctness by changing the model — we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party. In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.

Non-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (so called zk-SNARKs) increasingly see real-world adoption in large and complex systems. A requirement that turns out to be important for NIZKs is ensuring non-malleability of proofs, which can be achieved via the property of simulation extractability (SE). Moreover, many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and in practice it is desirable to reduce the trust in the CRS generation. Latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large and complex systems is the secure composition of protocols, e.g., via using the Universal Composability (UC) framework. Relying on the UC frameworks allows to arbitrarily and securely compose protocols in a modular way. In this work, we are interested in whether zk-SNARKs can provide all these desired properties. This is a tricky task as the UC framework rules out several natural techniques for such a construction. Our main result is to show that achieving these properties is indeed possible in a generic and modular way when slightly relaxing the succinctness properties of zk-SNARKs to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness $w$. We will argue that for various practical applications of zk-SNARKs this overhead is perfectly tolerable. Our starting point is a framework by Abdolmaleki et al. called Lamassu (ACM CCS'20) which we extend in several directions. Moreover, we implement our compiler on top of Sonic (ACM CCS'19) and provide benchmarks as well as a discussion on the choice of the required primitives.

While the efficiency of secure multi-party computation protocols has greatly increased in the last few years, these improvements and protocols are often based on rather unrealistic, idealised, assumptions about how technology is deployed in the real world. In this work we examine multi-party computation protocols in the presence of two major constraints present in deployed systems. Firstly, we consider the situation where the parties are connected not by direct point-to-point connections, but by a star-like topology with a few central post-office style relays. Secondly, we consider MPC protocols with a strong honest majority ($n \gg t/2$) in which we have stragglers (some parties are progressing slower than others). We model stragglers by allowing the adversary to delay messages to and from some parties for a given length of time. We first show that having only a single honest rely is enough to ensure consensus of the messages sent within a protocol; secondly, we show that special care must be taken to describe multiplication protocols in the case of relays and stragglers and that some well known protocols do not guarantee privacy and correctness in this setting; thirdly, we present an efficient honest-majority MPC protocol which can be run on top of the relays and which provides active-security with abort in the case of a strong honest majority, even when run with stragglers. We back up our protocol presentation with both experimental evaluations and simulations of the effect of the relays and delays on our protocol.

The TLS (Transport Layer Security) protocol is the most important, most attacked, most analysed and most used cryptographic protocol in the world today. TLS is critical to the integrity of the Internet, and if it were to be broken e-commerce would become impossible, with very serious implications for the global economy. Furthermore TLS is likely to assume even greater significance in the near future with the rapid growth of an Internet of Things (IoT) -- a multiplicity of internet connected devices all engaged in secure inter-communication. However the impending invention of a Cryptographically Relevant Quantum Computer (CRQC) would represent an existential threat to TLS in its current form. As it stands the latest version TLS1.3, benefiting as it does from years of research and study, provides effective security, but it must soon be updated to resist this new threat. In this research we first undertake a new clean-room implementation of a small-footprint open source TLS1.3, written in C++ and Rust, and suitable for IoT applications. Our implementation is designed to be cryptographically agile, so that it can easily accomodate new post-quantum cryptographic primitives. Next we use this new implementation as a vehicle to study the impact of going post-quantum, with a particular emphasis on the impact on the Internet of Things. Finally we showcase the flexibility of our implementation by proposing an implementation of TLS that uses identity-based encryption to mitigate this impact.

Learning parity with noise (LPN) has been widely studied and used in cryptography. It was recently brought to new prosperity since Boyle et al. (CCS'18), putting LPN to a central role in designing secure multi-party computation, zero-knowledge proofs, private set intersection, and many other protocols. In this paper, we thoroughly studied the concrete security of LPN problems in these settings. We found that many conclusions from classical LPN cryptanalysis do not apply to this new setting due to the low noise rates, extremely high dimensions, various types (in addition to $\mathbb{F}_2$) and noise distributions. 1. For LPN over field $\mathbb{F}_q$, we give a parameterized reduction from an exact noise distribution to a regular one that not only generalizes the recent result by Feneuil, Joux and Rivain (Crypto'22), but also significantly reduces the security loss by paying only an additive price in dimension and number of samples. 2. We analyze the security of LPN over a ring $\mathbb{Z}_{2^\lambda}$. Although existing protocols based on LPN over integer rings use parameters as if they are over fields, we found an attack that effectively reduces the weight of a noise by half compared to LPN over fields. Consequently, prior works that use LPN over $\mathbb{Z}_{2^\lambda}$ overestimate up to 40 bits of security. 3. We provide a complete picture of the hardness of LPN over integer rings by showing: 1) the equivalence between its search and decisional versions; 2) an efficient reduction from LPN over $\mathbb{F}_2$ to LPN over $\mathbb{Z}_{2^\lambda}$; and 3) generalization of our results to any integer ring. 4. For LPN over finite fields, we found that prior analysis ignored some important differences between classical LPN cryptanalysis and the new setting, leading to overly conservative parameters. We show that even after bringing all classical LPN cryptanalysis, including the latest SD $2.0$ analysis (Asiacrypt'22), to the setting over finite fields, much less weight of noises is needed for the same level of security. To improve the use of LPN assumptions for a wide range of cryptographic protocols, we provide an open-sourced script that estimates the concrete security of LPN over integer rings and finite fields.

The usage of convolutional neural networks (CNNs) to break cryptographic systems through hardware side-channels has enabled fast and adaptable attacks on devices like smart cards and TPMs. Current literature proposes fixed CNN architectures designed by domain experts to break such systems, which is time-consuming and unsuitable for attacking a new system. Recently, an approach using neural architecture search (NAS), which is able to acquire a suitable architecture automatically, has been explored. These works use the secret key information in the attack dataset for optimization and only explore two different search strategies using one-dimensional CNNs. We propose a NAS approach that relies only on using the profiling dataset for optimization, making it fully black-box. Using a large-scale experimental parameter study, we explore which choices for NAS, such as 1-D or 2-D CNNs and search strategy, produce the best results on 10 state-of-the-art datasets for Hamming weight and identity leakage models. We show that applying the random search strategy on 1-D inputs results in a high success rate and retrieves the correct secret key using a single attack trace on two of the datasets. This combination matches the attack efficiency of fixed CNN architectures, outperforming them in 4 out of 10 datasets. Our experiments also point toward the need for repeated attack evaluations of machine learning-based solutions in order to avoid biased performance estimates.

The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. This is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Accelerating the MSM over these curves on mobile devices is critical for deployment of recursive proof systems on mobile applications. This work is implemented in Go and uses hand-written arm64 assembly for accelerating the finite field arithmetic (bigint). This work was implemented as part of a submission to the ZPrize competition in the open division “Accelerating MSM on Mobile” (https://www.zprize.io/). We achieved a 78% speedup over the ZPrize baseline implementation in Rust.

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. In the largest case, $N=511$ was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024-bit and 2048-bit integers. In our estimation, Shor's quantum circuit for factoring 1024-bit integers requires $2.78 \times 10^{11}$ gates, and with depth $2.24 \times 10^{11}$, while $2.23 \times 10^{12}$ gates, and with depth $1.80 \times 10^{12}$ for 2048-bit integers.

We study satisfiability modulo the theory of finite fields and give a decision procedure for this theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this theory, we construct SMT queries that verify the correctness of various zero knowledge proof compilers on various input programs. Our experiments show that our implementation is vastly superior to previous approaches (which encode field arithmetic using integers or bit-vectors).

Because of the rapid growth of Internet of Things (IoT), embedded systems have become an interesting target for experienced attackers. ESP32~\cite{tech-ref-man} is a low-cost and low-power system on chip (SoC) series created by Espressif Systems. The firmware extraction of such embedded systems is a real threat to the manufacturer as it breaks its intellectual property and raises the risk of creating equivalent systems with less effort and resources. In 2019, LimitedResults~\cite{LimitedResultsPown} published power glitch attacks which resulted in dumping secure boot and flash encryption keys stored in the eFuses of ESP32. Therefore, Espressif patched this vulnerability and then advised its customers to use ESP32-V3, which is an updated SoC revision. This new version is hardened against fault injection attacks in hardware and software as announced by Espressif~\cite{ESPpatch}. In this paper, we present for the first time a deep hardware security evaluation for ESP32-V3. The main goal of this evaluation is to extract the firmware encryption key stored in the eFuses. This evaluation includes Fault Injection (FI) and Side-Channel (SC) attacks. First, we use Electromagnetic FI (EMFI) in order to show that ESP32-V3 doesn't resist EMFI. However, by experimental results, we show that this version contains a revised bootloader compared to ESP32-V1, which hardens dumping the eFuse keys by FI. Second, we perform a full SC analysis on the AES accelerator of ESP32-V3. We show that an attacker with a physical access to the device can extract all the keys of the hardware AES-256 after collecting 60K power measurements during the execution of the AES block. Third, we present another SC analysis for the firmware decryption mechanism, by targeting the decryption operation during the power up. Using this knowledge, we demonstrate that the full 256-bit AES firmware encryption key, which is stored in the eFuses, can be recovered by SC analysis using 300K power measurements. Finally, we apply practically the firmware encryption attack on Jade hardware wallet \cite{jade}.

We initiate a formal study of individual cryptography Informally speaking, an algorithm Alg is individual if in every implementation of Alg there always exists an individual user that has full knowledge of the cryptographic secrets S used by Alg. In particular, it should be infeasible to design implementations of this algorithm that would hide the secret S by distributing it between a group of parties using an MPC protocol, or via outsourcing it to a trusted execution environment.

Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland, France, and Australia. Practical protocols usually rely on tested designs such as the mixing-and-decryption paradigm. There, multiple servers verifiably shuffle encrypted ballots, which are then decrypted in a distributed manner. While several efficient protocols implementing this paradigm exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because the design ideas of the discrete log-based voting protocols do not carry over easily to the lattice setting, due to specific problems such as noise growth and approximate relations. In this work, we propose a new verifiable secret shuffle for BGV ciphertexts and a compatible verifiable distributed decryption protocol. The shuffle is based on an extension of a shuffle of commitments to known values which is combined with an amortized proof of correct re-randomization. The verifiable distributed decryption protocol uses noise drowning, proving the correctness of decryption steps in zero-knowledge. Both primitives are then used to instantiate the mixing-and-decryption electronic voting paradigm from lattice-based assumptions. We give concrete parameters for our system, estimate the size of each component and provide implementations of all important sub-protocols. Our experiments show that the shuffle and decryption protocol is suitable for use in real-world e-voting schemes.

This paper describes a formalization of the specification and the algorithm of the public key encryption scheme CRYSTALS-KYBER as well as the verification of its $\delta$-correctness and indistinguishability under chosen plaintext attack (IND-CPA) security proof. The algorithms and proofs were formalized with only minimal assumptions in a modular way to verify the proofs for all possible parameter sets. During the formalization in this flexible setting, problems in the correctness proof were uncovered. Furthermore, the security of CRYSTALS-KYBER under IND-CPA was verified using a game-based approach. As the security property does not hold for the original version of CRYSTALS-KYBER, we only show the IND-CPA security for the latest versions. The security proof was verified under the hardness assumption of the module Learning-with-Errors Problem. The formalization was realized in the theorem prover Isabelle and is foundational.

As the number of blockchain projects grows, efficient cross-chain interoperability becomes more necessary. A common cross-chain protocol is the two-way peg, which is typically used to transfer assets between blockchains and their sidechains. The criticality of cross-chain protocols require that they are designed with strong security models, which can reduce usability in the form of long transfer times. In this paper, we present Flyover, a repayment protocol to speed up the transfer of bitcoins over federated pegs by allowing untrusted liquidity providers to advance funds for the users. Transfer times are reduced because liquidity providers do not have the same security requirements as the underlying cross-chain protocol. We illustrate the Flyover protocol on the cross-chain interoperability protocol that connects Bitcoin to the RSK sidechain and show how Flyover can reduce transfer times without reducing security. In addition to this, Flyover extends the cross-chain protocol by allowing liquidity providers to make smart contract calls on RSK on behalf of the user.

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.

We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-SIS assumption. We also give a construction of a ``keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. The signature size in this case is only $48$ bytes, but more work needs to be done to explore the efficiency of the protocol which generates the signature.

Ring signatures enable a user to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity property guarantees that the signature does not reveal which member of the ring signed the message. The notion of linkable ring signatures (LRS) is an extension of the concept of ring signatures such that there is a public way of determining whether two signatures have been produced by the same signer. Lattice-based LRS is an important and active research line since lattice-based cryptography has attracted more attention due to its distinctive features, especially the quantum-resistant. However, all the existing lattice-based LRS relied on random oracle heuristics, i.e., no lattice-based LRS in the standard model has been introduced so far. In this paper, we present a lattice-based LRS scheme in the standard model. Toward our goal, we present a lattice basis extending algorithm which is the key ingredient in our construction, that may be of indepen- dent interest

Since the invention of Bitcoin, cryptocurrencies have gained huge popularity. Crypto wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency funds. Deterministic wallet is an advanced wallet mech- anism that has been proposed to achieve some appealing virtues, such as low-maintenance, easy backup and recovery, supporting functionali- ties required by cryptocurrencies, and so on. But deterministic wallets still have a long way to be practical in quantum world, and there are also some gaps in the classic world, since there are the following prob- lems waiting to be solved. Firstly, the relying on the state, i.e., stateful. The stateful deterministic wallet scheme must internally maintain and keep refreshing synchronously a state which makes the implementation in practice become more complex. And once one of the states is leaked, thereafter the security notion of unlinkability is cannot be guaranteed (referred to as the weak security notion of forward unlinkability). The second problem is vulnerable. There are security shortfalls in previous works, they suffer a vulnerability when a minor fault happens (say, one derived key is compromised somehow), then the damage is not limited to the leaked derived key, instead, it spreads to the master key and the whole system collapses. Thirdly, the falling short in supporting hot/cold setting. The hot/cold setting is a widely adopted method to effectively reduce the exposure chance of secret keys and hence improving the se- curity of the deterministic wallet system. The last problem is the relying on the weak security notion of unforgeability, in which the adversary is only allowed to query and forge the signatures w.r.t. the public keys that were assigned by the challenger. In this work, we present a new deterministic wallet scheme in quantum world, which is stateless, supports hot/cold setting, satisfiies stronger security notions, and is more efficient. In particular, we reformalize the syntax and security models for deterministic wallets, capturing the func- tionality and security requirements imposed by the practice in cryptocur- rency. Then we propose a deterministic wallet construction and prove its security in the quantum random oracle model. Finally, we show our wal- let scheme is more practicable by analyzing an instantiation of our wallet scheme based on the signature scheme Falcon.

The Secure-Boot is a critical security feature in modern devices based on System-on-Chips (SoC). It ensures the authenticity and integrity of the code before its execution, avoiding the SoC to run malicious code. To the best of our knowledge, this paper presents the first bypass of an Android Secure-Boot by using an Electromagnetic Fault Injection (EMFI). Two hardware characterization methods are combined to conduct this experiment. A real-time Side-Channel Analysis (SCA) is used to synchronize an EMFI during the Linux Kernel authentication step of the Android Secure-Boot of a smartphone-grade SoC. This new synchronization method is called Synchronization by Frequency Detection (SFD). It is based on the detection of the activation of a characteristic frequency in the target electromagnetic emanations. In this work we present a proof-of-concept of this new triggering method. By triggering the attack upon the activation of this characteristic frequency, we successfully bypassed this security feature, effectively running Android OS with a compromised Linux Kernel with one success every 15 minutes.

We propose a single-tiered hybrid Proof-of-Work consensus protocol to encourage decentralization in bitcoin. Our new mechanism comprises coupled puzzles of which properties differ from each other; the one is the extant outsourceable bitcoin puzzle while the other is non-outsourceable. Our new protocol enables miners to solve either puzzle as they want; therefore, blocks can be generated by either puzzle. Our hybrid consensus can be successfully implemented in bitcoin, because it is backward-compatible with existing bitcoin mining equipment(more precisely, existing bitcoin mining ASICs)

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM queries is necessary assuming $O(1)$ client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure. In this work, we construct the first maliciously secure ORAM protocol with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

Flow is a high-throughput blockchain with a dedicated step for executing the transactions in a block and a subsequent verification step performed by Verification Nodes. To enforce integrity of the blockchain, the protocol requires a component that prevents Verification Nodes from approving execution results without checking. In our preceding work, we have sketched out an approach called Specialized Proof of Confidential Knowledge (SPoCK). Using SPoCK, nodes can provide evidence to a third party that they both executed the same transaction sequence without revealing the resulting execution trace. The previous Flow white paper presented a basic implementation of such scheme. In this note, we introduce a new SPoCK implementation that is more concise and more efficient than the previous proposal. We first provide a formal generic description of a SPoCK scheme as well as its security definition. Then we propose a new construction of SPoCK based on the BLS signature scheme. We support the new scheme with its proof of security under the appropriate computation assumptions.

Encryption alone is not enough for secure end-to-end encrypted messaging: a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components: (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store. To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed ''compaction'', as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks.

We propose a novel methodology to obtain $B$lind signatures that is fundamentally based on the idea of hiding part of the underlying plain signatures under a $Z$ero-knowledge argument of knowledge of the whole signature (hence the shorthand, $BZ$). Our proposal is necessarily non-black-box and stated in the random oracle model. We illustrate the technique by describing two instantiations: a classical setting based on the traditional discrete logarithm assumption, and a post-quantum setting based on the commutative supersingular isogeny Diffie-Hellman (CSIDH) assumption.

The private heavy-hitters problem is a data-collection task where many clients possess private bit strings, and data-collection servers aim to identify the most popular strings without learning anything about the clients' inputs. The recent work of Poplar constructed a protocol for private heavy hitters but their solution was susceptible to additive attacks by a malicious server, compromising both the correctness and the security of the protocol. In this paper, we introduce PLASMA, a private analytics framework that addresses these challenges by using three data-collection servers and a novel primitive, called verifiable incremental distributed point function (VIDPF). PLASMA allows each client to non-interactively send a message to the servers as its input and then go offline. Our new VIDPF primitive employs lightweight techniques based on efficient hashing and allows the servers to non-interactively validate client inputs and preemptively reject malformed ones. PLASMA drastically reduces the communication overhead incurred by the servers using our novel batched consistency checks. Specifically, our server-to-server communication depends only on the number of malicious clients, as opposed to the total number of clients, yielding a $182\times$ and $235\times$ improvement over Poplar and other state-of-the-art sorting-based protocols respectively. Compared to recent works, PLASMA enables both client input validation and succinct communication, while ensuring full security. At runtime, PLASMA computes the 1000 most popular strings among a set of 1 million client-held 32-bit strings in 67 seconds and 256-bit strings in less than 20 minutes respectively.

The increasing popularity of blockchain technology has affected the way we view many fields related to computer science, with E-commerce being no exception. The distributed nature and transparency of blockchain-based systems is one of its main perks, but it also raises some issues when it comes to privacy. Zero-knowledge proofs are very powerful building blocks when it comes to building privacy-preserving protocols, so, naturally, they have attracted a lot of attention in the last years. Following the recent collapse of the very popular crypto exchange FTX, we believe it is important to analyse how such events can be prevented in the future. This paper aims to highlight solutions that use zero-knowledge to prove solvency.

Blockchain is a newly emerging technology, however, it has proven effective in many applications because it provides multiple advantages, mainly as it represents a trust system in which data is encrypted in a way that cannot be tampered with or forged. Because it contains many details such as smart contracts, consensus, authentication, etc. the blockchain is a fertile ground for researchers where they can continually improve previous versions of these concepts. This paper introduces a new multi-signature scheme based on RSA. This scheme is designed to reduce the blockchain's size and prevent known attacks and is also applicable in many other settings that require multi-signatures. Our scheme is in the plain public key model, which means nodes do not need to prove knowledge or possession of their private key. In which, whatever the number of signers, the final signature size is equal to $O(k)$ where $k$ is a security parameter and no interaction between signers is needed. To verify that a number of parties have signed a shared message $m$, a verifier needs the signature, list of signers, and the message $m$. The presented practical short accountable-subgroup multi-signature (ASM) scheme allows a valid signature to disclose which subset generated the signature. It is worth noting that our multi-signatures with public key aggregation is an interactive two-round protocol and a multi-signature model applied to the entire block and not to individual transactions.

Threshold Fully Homomorphic Encryption (ThFHE) enables arbitrary computation over encrypted data while keeping the decryption key to be distributed across multiple parties at all time. ThFHE is a key enabler for threshold cryptography and, more generally, secure distributed computing. Existing ThFHE schemes inherently require highly inefficient parameters and are unsuitable for practical deployment. In this paper, we take the first step towards to make ThFHE practically usable by (i) proposing a novel ThFHE scheme with a new analysis resulting in significantly improved parameters; (ii) and providing the first ThFHE implementation benchmark based on Torus FHE. • We propose the first ThFHE scheme with a polynomial modulus-to-noise ratio that supports practically efficient parameters while retaining provable security based on standard quantum-safe assumptions. We achieve this via a novel Rényi divergence-based security analysis of our proposed threshold decryption mechanism. • We present a highly optimized software implementation of our proposed ThFHE scheme that builds upon the existing Torus FHE library and supports (distributed) decryption on highly resource-constrained ARM-based handheld devices. To the best of our knowledge, this is the first practically efficient implementation of any ThFHE scheme. Along the way, we implement several extensions to the Torus FHE library, including a Torus-based linear integer secret sharing subroutine to support ThFHE key sharing and distributed decryption for any threshold access structure. We illustrate the efficacy of our proposal via an end-to-end use case involving encrypted computations over a real medical database, and distributed decryptions of the computed result on resource-constrained handheld devices.

Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, while allowing arbitrary computations. Recent research has shown two side channel attacks on the client side running a popular HE library. However, no side channel attacks have yet been reported on the server side in existing literature. The current paper shows that it is possible for adversaries to inject perturbations in the ciphertexts stored in the cloud to result in decryption errors. Most importantly, we highlight that when the client reports of such aberrations to the cloud service provider the complete secret key can be extracted in few attempts. Technically, this implies a break of the IND-CVA (Indistinguishability against Ciphertext Verification Attacks) security of the FHE schemes. The core idea of the attack is to extract the underlying error values for each homomorphically computed ciphertext and thereby construct an exact system of equations. As the security of the underlying Learning with Errors (LWE) collapse with the leakage of the errors, the adversary is capable of ascertaining the secret keys. We demonstrate this attack on two well-known FHE libraries, namely FHEW and TFHE. The objective of the server is to perform the attack in a stealthy manner, without raising any suspicion from the innocent client. Therefore in a practical scenario, the successful key retrieval from a client would require the server to perform the attack with as few queries as possible. Thus we craftily use timing information during homomorphic gate computations to optimise our attack and significantly reduce the required number of queries per ciphertext. More precisely, we need 8 and 23 queries to the client for each error recovery for FHEW and TFHE, respectively. We mount a full-key recovery attack 1 on TFHE (without and with bootstrapping) with key size of 630 bits and successfully faulted 739 and 930 ciphertexts to recover correct errors. This required a total of 19838 and 29200 client queries respectively. In case of FHEW with key size 500, we successfully faulted 766 ciphertexts to recover correct errors, which required 7565 client queries. The results serve as a stark reminder that FHE schemes need to be secured at the application level apart from being secure at the primitive level so that the security of participants against realistic attacks can be ensured.

Payment channel networks (PCNs) mitigate the scalability issues of current decentralized cryptocurrencies. They allow for arbitrarily many payments between users connected through a path of intermediate payment channels, while requiring interacting with the blockchain only to open and close the channels. Unfortunately, PCNs are (i) tailored to payments, excluding more complex smart contract functionalities, such as the oracle-enabling Discreet Log Contracts and (ii) their need for active participation from intermediaries may make payments unreliable, slower, expensive, and privacy-invasive. Virtual channels are among the most promising techniques to mitigate these issues, allowing two endpoints of a path to create a direct channel over the intermediaries without any interaction with the blockchain. After such a virtual channel is constructed, (i) the endpoints can use this direct channel for applications other than payments and (ii) the intermediaries are no longer involved in updates. In this work, we first introduce the Domino attack, a new DoS/griefing style attack that leverages virtual channels to destruct the PCN itself and is inherent to the design adopted by the existing Bitcoin-compatible virtual channels. We then demonstrate its severity by a quantitative analysis on a snapshot of the Lightning Network (LN), the most widely deployed PCN at present. We finally discuss other serious drawbacks of existing virtual channel designs, such as the support for only a single intermediary, a latency and blockchain overhead linear in the path length, or a non-constant storage overhead per user. We then present Donner, the first virtual channel construction that overcomes the shortcomings above, by relying on a novel design paradigm. We formally define and prove security and privacy properties in the Universal Composability framework. Our evaluation shows that Donner is efficient, reduces the on-chain number of transactions for disputes from linear in the path length to a single one, which is the key to prevent Domino attacks, and reduces the storage overhead from logarithmic in the path length to constant. Donner is Bitcoin-compatible and can be easily integrated in the LN.

The Rank Decoding problem (RD) is at the core of rank-based cryptography. Cryptosystems such as ROLLO and RQC, which made it to the second round of the NIST Post-Quantum Standardization Process, as well as the Durandal signature scheme, rely on it or its variants. This problem can also be seen as a structured version of MinRank, which is ubiquitous in multivariate cryptography. Recently, [1,2] proposed attacks based on two new algebraic modelings, namely the MaxMinors modeling which is specific to RD and the Support-Minors modeling which applies to MinRank in general. Both improved significantly the complexity of algebraic attacks on these two problems. In the case of RD and contrarily to what was believed up to now, these new attacks were shown to be able to outperform combinatorial attacks and this even for very small field sizes. However, we prove here that the analysis performed in [2] for one of these attacks which consists in mixing the MaxMinors modeling with the Support-Minors modeling to solve RD is too optimistic and leads to underestimate the overall complexity. This is done by exhibiting linear dependencies between these equations and by considering an Fqm version of these modelings which turns out to be instrumental for getting a better understanding of both systems. Moreover, by working over Fqm rather than over Fq, we are able to drastically reduce the number of variables in the system and we (i) still keep enough algebraic equations to be able to solve the system, (ii) are able to analyze rigorously the complexity of our approach. This new approach may improve the older MaxMinors approach on RD from [1,2] for certain parameters. We also introduce a new hybrid approach on the Support-Minors system whose impact is much more general since it applies to any MinRank problem. This technique improves significantly the complexity of the Support-Minors approach for small to moderate field sizes. References: [1] An Algebraic Attack on Rank Metric Code-Based Cryptosystems, Bardet, Briaud, Bros, Gaborit, Neiger, Ruatta, Tillich, EUROCRYPT 2020. [2] Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems, Bardet, Bros, Cabarcas, Gaborit, Perlner, Smith-Tone, Tillich, Verbel, ASIACRYPT 2020.

Being capable of updating cryptographic algorithms is an inevitable and essential practice in cryptographic engineering. This cryptographic agility, as it has been called, is a fundamental desideratum for long term cryptographic system security that still poses significant challenges from a modeling perspective. For instance, current formulations of agility fail to express the fundamental security that is expected to stem from timely implementation updates, namely the fact that the system retains some of its security properties provided that the update is performed prior to the deprecated implementation becoming exploited. In this work we put forth a novel framework for expressing updateability in the context of cryptographic primitives within the universal composition model. Our updatable ideal functionality framework provides a general template for expressing the security we expect from cryptographic agility capturing in a fine-grained manner all the properties that can be retained across implementation updates. We exemplify our framework over two basic cryptographic primitives, digital signatures and non-interactive zero-knowledge (NIZK), where we demonstrate how to achieve updateability with consistency and backwards-compatibility across updates in a composable manner. We also illustrate how our notion is a continuation of a much broader scope of the concept of agility introduced by Acar, Belenkiy, Bellare, and Cash in Eurocrypt 2010 in the context of symmetric cryptographic primitives.

In recent years there have been several attempts to build white-box block ciphers whose implementation aims to be incompressible. This includes the weak white-box ASASA construction by Bouillaguet, Biryukov and Khovratovich from Asiacrypt 2014, and the recent space-hard construction by Bogdanov and Isobe at CCS 2016. In this article we propose the first constructions aiming at the same goal while offering provable security guarantees. Moreover we propose concrete instantiations of our constructions, which prove to be quite efficient and competitive with prior work. Thus provable security comes with a surprisingly low overhead.

Masking has become one of the most effective approaches for securing hardware designs against side-channel attacks. Irrespective of the effort put into correctly implementing masking schemes on a field programmable gate array (FPGA), leakage can be unexpectedly observed. This is due to the fact that the assumption underlying all masked designs, i.e., the leakages of different shares are independent of each other, may no longer hold in practice. In this regard, extreme temperatures have been shown to be an important factor in inducing leakage, even in correctly-masked designs. This has previously been verified using an external heat generator (i.e., a climate chamber). In this paper, we examine whether the leakage can be induced using the circuit components themselves. Specifically, we target masked neural networks (NNs) in FPGAs, with one of the main building blocks being block random access memory (BRAM) and flip-flops (FFs). In this respect, thanks to the inherent characteristics of NNs, our novel internal heat generators leverage solely the memories devoted to storing the user’s input, especially when frequently writing alternating patterns into BRAMs and FFs. The possibility of observing first-order leakage is evaluated by considering one of the most recent and successful first-order secure masked NNs, namely ModuloNET. ModuloNET is specifically designed for FPGAs, where BRAMs are used for storing the inputs and intermediate computations. Our experimental results demonstrate that undesirable first-order leakage can be observed by increasing the temperature when an alternating input is applied to the masked NN. To give a better understanding of the impact of extreme heat, we further perform a similar test on the design with FFs storing the input, where the same conclusion can be drawn.

The threat of chip-level tampering and its detection is a widely researched field. Hardware Trojan insertions are prominent examples of such tamper events. Altering the placement and routing of a design or removing a part of a circuit for side-channel leakage/fault sensitivity amplification are other instances of such attacks. While semi- and fully-invasive physical verification methods can confidently detect such stealthy tamper events, they are costly, time-consuming, and destructive. On the other hand, virtually all proposed non-invasive side-channel methods suffer from noise and, therefore, have low confidence. Moreover, they require activating the tampered part of the circuit (e.g., the Trojan trigger) to compare and detect the modification. In this work, we introduce a general non-invasive post-silicon tamper detection technique applicable to all sorts of tamper events at the chip level without requiring the activation of the malicious circuit. Our method relies on the fact that all classes of physical modifications (regardless of their physical, activation, or action characteristics) alter the impedance of the chip. Hence, characterizing the impedance can lead to the detection of the tamper events. To sense the changes in the impedance, we deploy known RF tools, namely, scattering parameters, in which we inject sine wave signals with high frequencies to the power distribution network (PDN) of the system and measure the “echo” of the signal. The reflected signals in various frequency bands reveal different tamper events based on their impact size on the die. To validate our claims, we performed extensive measurements on several proof-of-concept tampered hardware implementations realized on an FPGA manufactured with a 28 nm technology. Based on these groundbreaking results, we demonstrate that stealthy hardware Trojans, as well as sophisticated modifications of P&R, can be detected with high confidence.

We consider multi-party information-theoretic private computation. Such computation inherently requires the use of local randomness by the parties, and the question of minimizing the total number of random bits used for given private computations has received considerable attention in the literature. In this work we are interested in another question: given a private computation, we ask how many of the players need to have access to a random source, and how many of them can be deterministic parties. We are further interested in the possible interplay between the number of random sources in the system and the total number of random bits necessary for the computation. We give a number of results. We first show that, perhaps surprisingly, $t$ players (rather than $t+1$) with access to a random source are sufficient for the information-theoretic $t$-private computation of any deterministic functionality over $n$ players for any $t<n/2$; by a result of (Kushilevitz and Mansour, PODC'96), this is best possible. This means that, counter intuitively, while private computation is impossible without randomness, it is possible to have a private computation even when the adversary can control all parties who can toss coins (and therefore sees all random coins). For randomized functionalities we show that $t+1$ random sources are necessary (and sufficient). We then turn to the question of the possible interplay between the number of random sources and the necessary number of random bits. Since for only very few settings in private computation meaningful bounds on the number of necessary random bits are known, we consider the AND function, for which some such bounds are known. We give a new protocol to $1$-privately compute the $n$-player AND function, which uses a single random source and $6$ random bits tossed by that source. This improves, upon the currently best known results (Kushilevitz et al., TCC'19), at the same time the number of sources and the number of random bits (KOPRT19 gives a $2$-source, $8$-bits protocol). This result gives maybe some evidence that for $1$-privacy, using the minimum necessary number of sources one can also achieve the necessary minimum number of random bits. We believe however that our protocol is of independent interest for the study of randomness in private computation.

This Paper proposes FssNN, a communication-efficient secure two-party computation framework for evaluating privacy-preserving neural network via function secret sharing (FSS) in semi-honest adversary setting. In FssNN, two parties with input data in secret sharing form perform secure linear computations using additive secret haring and non-linear computations using FSS, and obtain secret shares of model parameters without disclosing their input data. To decrease communication cost, we split the protocol into online and offline phases where input-independent correlated randomness is generated in offline phase while only lightweight ``non-cryptographic'' computations are executed in online phase. Specifically, we propose $\mathsf{BitXA}$ to reduce online communication in linear computation, DCF to reduce key size of the FSS scheme used in offline phase for nonlinear computation. To further support neural network training, we enlarge the input size of neural network to $2^{32}$ via ``MPC-friendly'' PRG. We implement the framework in Python and evaluate the end-to-end system for private training between two parties on standard neural networks. FssNN achieves on MNIST dataset an accuracy of 98.0%, with communication cost of 27.52GB and runtime of 0.23h per epoch in the LAN settings. That shows our work advances the state-of-the-art secure computation protocol for neural networks.

We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors. We give constructions of this primitive from a common template, which can be instantiated under either the LPN (with non-negligible correctness error) or the LWE (with negligible correctness error) assumptions. Our construction uses a novel twist on the standard non-interactive key exchange based on the Alekhnovich cryptosystem, which upgrades it to a non-interactive inner product protocol almost for free. In addition to being non-interactive, our constructions have linear communication (with constants smaller than all known alternatives) and small computation: using LPN or LWE with quasi-cyclic codes, we estimate that encoding a length-$2^{20}$ vector over a 32-bit field takes less that 2s on a standard laptop; decoding amounts to a single cheap inner-product. We show how to remove the non-negligible error in our LPN instantiation using a one-time, logarithmic-communication preprocessing. Eventually, we show to to upgrade its security to the malicious model using new sublinear-communication zero-knowledge proofs for low-noise LPN samples, which might be of independent interest.

In any real-life setting, side-channel secure implementations of public-key cryptography must be able to load and store their secret keys in a side-channel secure way. We describe WrapQ, a masking-friendly key management technique and compact encoding format for Kyber and Dilithium Critical Security Parameters (CSPs). WrapQ protects secret key integrity and confidentiality with a Key-Encrypting Key (KEK) and allows the keys to be stored on an untrusted medium. Importantly, its encryption and decryption processes avoid temporarily collapsing the masked asymmetric secret keys (which are plaintext payloads from the viewpoint of the wrapping primitive) into an unmasked format. We demonstrate that a masked Kyber or Dilithium private key can be loaded in a leakage-free fashion from a compact WrapQ format without updating the encoding in non-volatile memory. WrapQ has been implemented in a side-channel secure hardware module. Kyber and Dilithium wrapping and unwrapping functions were validated with 100K traces of TVLA-type leakage assessment.

This paper aims to provide a security analysis comparison between three popular instant messaging apps: Signal, WhatsApp and Telegram. The analysis will focus on the encryption protocols used by each app and the security features they offer. The paper will evaluate the strengths and weaknesses of each app, and provide a summary of their overall security posture. Additionally, this paper will discuss other considerations such as user base, data collection and usage policies, and other features which may impact the security of the apps. The results of this analysis will provide insights for individuals and organizations looking to choose a secure instant messaging app for their communication needs. In this paper we reviewed the main encryption standards and we compared the features, traffic analysis, protocols, performance and recent security breaches for WhatsApp, Signal and Telegram. The paper includes packet sniffing using Wireshark and Fiddler.

The purpose of this article is to present,illustrate and to put in evidence a new side- channel attack on RSA cryptosystem based on the generation of prime numbers. The vulnerability of the cryptosystem is spotted during the execution of the key generation step.The probability of success of the attack is around 10-15% in the case of realistic parameters

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry's compressed oracle technique.

The use of data as a product and service has given momentum to the extensive uptake of complex machine learning algorithms that focus on performing prediction with popular tree-based methods such as decision trees classifiers. With increasing adoption over a wide array of sensitive applications, a significant need to protect the confidentiality of the classifier model and user data is identified. The existing literature safeguards them using interactive solutions based on expensive cryptographic approaches, where an encrypted classifier model interacts with the encrypted queries and forwards the encrypted classification to the user. Adding to that, the state-of-art protocols for protecting the privacy of the model do not contain model-extraction attacks. We design an efficient virtual black-box obfuscator for binary decision trees and use the random oracle paradigm to analyze the security of our construction. To thwart model-extraction attacks, we restrict to evasive decision trees, as black-box access to the classifier does not allow a PPT adversary to extract the model. While doing so, we present an encoder for hiding parameters in an interval-membership function. Our exclusive goal behind designing the obfuscator is that, not only will the solution increase the class of functions that has cryptographically secure obfuscators, but also address the open problem of non-interactive prediction in privacy-preserving classification using computationally inexpensive cryptographic hash functions.

We present mining-based techniques to reduce the size of various cryptographic outputs without loss of security. Our approach can be generalized for multiple primitives, such as cryptographic key generation, signing, hashing and encryption schemes, by introducing a brute-forcing step to provers/senders aiming at compressing submitted cryptographic material. Interestingly, mining can result in record-size cryptographic outputs, and we show that 5%-12% shorter hash digests and signatures are practically feasible even with commodity hardware. As a result, our techniques make compressing addresses and transaction signatures possible in order to pay less fees in blockchain applications while decreasing the demand for blockchain space, a major bottleneck for initial syncing, communication and storage. Also, the effects of "compressing once - then reuse'' at mass scale can be economically profitable in the long run for both the Web2 and Web3 ecosystems. Our paradigm relies on a brute-force search operation in order to craft the primitive's output such that it fits into fewer bytes, while the "missing" fixed bytes are implied by the system parameters and omitted from the actual communication. While such compression requires computational effort depending on the level of compression, this cost is only paid at the source (i.e. in blockchains, senders are rewarded by lowered transaction fees), and the benefits of the compression are enjoyed by the whole ecosystem. As a starting point, we show how our paradigm applies to some basic primitives commonly used in blockchain applications but also traditional Web2 transactions (such as shorter digital certificates), and show how security is preserved using a bit security framework. Surprisingly, we also identified cases where wise mining strategies require proportionally less effort than naive brute-forcing, shorter hash-based signatures being one of the best examples. We also evaluate our approach for several primitives based on different levels of compression. Our evaluation concretely demonstrates the benefits both in terms of financial cost and storage if adopted by the community, and we showcase how our technique can achieve up to 83.21% reduction in smart contract gas fees at a cost of less than 4 seconds of computation on a single core.

There is a line of 'lookup' protocols to show that all elements of a sequence $f\in{\mathbb F}^n$ are contained in a table $t\in{\mathbb F}^d$, for some field ${\mathbb F}$. Lookup has become an important primitive in Zero Knowledge Virtual Machines, and is used for range checks and other parts of the proofs of a correct program execution. In this note we give several variants of the protocol. We adapt it to the situation when there are multiple lookups with the same table (as is usually the case with range checks), and handle also 'bounded lookup' that caps the number of repetitions.

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties. In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $P$. For that, we revisit the idea of working with supersingular elliptic curves. The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has provided all the tools to perform the necessary tasks efficiently. Our main ingredients are two new heuristic algorithms to compute the $j$-invariants of supersingular curves having an endomorphism ring contained in some set of isomorphism class of maximal orders. The first one is derived easily from the existing tools of isogeny-based cryptography, while the second introduces new ideas to perform that task efficiently for a big number of maximal orders. From there, we obtain two main results. First, we show that we can associate these two algorithms with some operations over the quaternion algebra ramified at $P$ and infinity to compute directly Hilbert and modular polynomials $\mod P$. In that manner, we obtain the first algorithms to compute Hilbert (resp. modular) polynomials modulo $P$ for a good portion of all (resp. all) primes $P$ with a complexity in $O(\sqrt{|D|})$ for the discriminant $D$ (resp. $O(\ell^2)$ for the level $\ell$). Due to the (hidden) complexity dependency on $P$, these algorithms do not outperform the best known algorithms for all prime $P$ but they still provide an asymptotic improvement for a range of prime going up to a bound that is sub-exponential in $|D|$ (resp. $\ell$). Second, we revisit the CRT method for both class and modular polynomials. We show that applying our second heuristic algorithm over supersingular curves to the CRT approach yields the same asymptotic complexity as the best known algorithms based on ordinary curves and we argue that our new approach might be more efficient in practice. The situation appears especially promising for modular polynomials, as our approach reduces the asymptotic cost of elliptic curve operations by a linear factor in the level $\ell$. We obtain an algorithm whose asymptotic complexity is now fully dominated by linear algebra and standard polynomial arithmetic over finite fields.

We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe. We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink's use in the wild) each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 97$\times$ larger, (ii) have aggregation times 311$\times$ worse, or (iii) have signature size 39$\times$ and verification gas costs 3.38$\times$ larger. We also provide an open-source implementation and a detailed evaluation.

Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this paper, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our results is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with key-and-signature compact without a restart during signing process.

We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit x_i by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i. Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable sym- metric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware. Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.