This paper presents an analysis of the two lattice-based digital signature schemes, Dilithium and Falcon, which have been chosen by NIST for standardisation, on the ARM Cortex M7 using the STM32F767ZI NUCLEO-144 development board. This research is motivated by the ARM Cortex M7 device being the only processor in the Cortex-M family to offer a double precision (i.e., 64-bit) floating-point unit, making Falcon's implementations, requiring 53 bits of double precision, able to fully run native floating-point operations without any emulation. When benchmarking natively, Falcon shows significant speed-ups between 6.2-8.3x in clock cycles, 6.2-11.8x in runtime, and Dilithium does not show much improvement other than those gained by the slightly faster processor. We then present profiling results of the two schemes on the ARM Cortex M7 to show their respective bottlenecks and operations where the improvements are and can be made. This demonstrates, for example, that some operations in Falcon's procedures observe speed-ups by an order of magnitude. Finally, since Falcon's use of floating points is so rare in cryptography, we test the native FPU instructions on 4 different STM32 development boards with the ARM Cortex M7 and also a Raspberry Pi 3 which is used in some of Falcon's official benchmarking results. We find constant-time irregularities in all of these devices, which makes Falcon insecure on these devices for applications where signature generation can be timed by an attacker.

Dynamic participation support is an important feature of Bitcoin's longest-chain protocol and its variants. But these protocols suffer from long latency as a fundamental trade-off. Specifically, the latency depends at least on the following two factors: 1) the desired security level of the protocol, and 2) the actual participation level of the network. Classic BFT protocols, on the other hand, can achieve constant latency but cannot make progress under dynamic participation. In this work, we present a protocol that simultaneously supports dynamic participation and achieves constant latency. Our core technique is to extend the classic BFT approach from static quorum size to dynamic quorum size, i.e., according to the current participation level, while preserving important properties of static quorum. We also present a recovery mechanism for rejoining nodes that is efficient in terms of both communication and storage. Our experimental evaluation shows our protocol has much lower latency than a longest-chain protocol, especially when there is a sudden decrease of participation.

Zero-knowledge (ZK) applications form a large group of use cases in modern cryptography, and recently gained in popularity due to novel proof systems. For many of these applications, cryptographic hash functions are used as the main building blocks, and they often dominate the overall performance and cost of these approaches. Therefore, in the last years several new hash functions were built in order to reduce the cost in these scenarios, including Poseidon and Rescue among others. These hash functions often look very different from more classical designs such as AES or SHA-2. For example, they work natively over prime fields rather than binary ones. At the same time, for example Poseidon and Rescue share some common features, such as being SPN schemes and instantiating the nonlinear layer with invertible power maps. While this allows the designers to provide simple and strong arguments for establishing their security, it also introduces crucial limitations in the design, which may affect the performance in the target applications. In this paper, we propose the Horst construction, in which the addition in a Feistel scheme (x, y) -> (y + F(x), x) is extended via a multiplication, i.e., (x, y) -> (y * G(x) + F(x), x). By carefully analyzing the performance metrics in SNARK and STARK protocols, we show how to combine an expanding Horst scheme with a Rescue-like SPN scheme in order to provide security and better efficiency in the target applications. We provide an extensive security analysis for our new design Griffin and a comparison with all current competitors.

Rotational-XOR (RX) cryptanalysis is a cryptanalytic method aimed at finding distinguishable statistical properties in ARX-C ciphers, i.e., ciphers that can be described only by using modular addition, cyclic rotation, XOR, and the injection of constants. In this paper we extend RX-cryptanalysis to AND-RX ciphers, a similar design paradigm where the modular addition is replaced by vectorial bitwise AND; such ciphers include the block cipher families Simon and Simeck. We analyze the propagation of RX-differences through AND-RX rounds and develop a closed form formula for their expected probability. Inspired by the MILP verification model proposed by Sadeghi et al., we develop a SAT/SMT model for searching compatible RX-characteristics in Simon-like ciphers, i.e., that there are at least one right pair of messages/keys to satisfy the RK-characteristics. To the best of our knowledge, this is the first model that takes the RX-difference transitions and value transitions simultaneously into account in Simon-like ciphers. Meanwhile, we investigate how the choice of the round constants affects the resistance of Simon-like ciphers against RX-cryptanalysis. Finally, we show how to use an RX-distinguisher for a key recovery attack. Evaluating our model we find compatible RX-characteristics of up to 20, 27, and 34 rounds with respective probabilities of 2 −26 ,2 −44 , and 2 −56 for versions of Simeck with block sizes of 32, 48, and 64 bits, respectively, for large classes of weak keys in the related-key model. In most cases, these are the longest published distinguishers for the respective variants of Simeck. In the case of Simon, we present compatible RX-characteristics for round reduced versions of all ten instances. We observe that for equal block and key sizes, the RX-distinguishers cover fewer rounds in Simon than in Simeck. Concluding the paper, we present a key recovery attack on Simeck 64 reduced to 28 rounds using a 23-round RX-characteristic.

We provide the first mechanized post-quantum sound security protocol proofs. We achieve this by developing PQ-BC, a computational first-order logic that is sound with respect to quantum attackers, and corresponding mechanization support in the form of the PQ-Squirrel prover. Our work builds on the classical BC logic [Bana,Comon,CCS14] and its mechanization in the Squirrel prover [BDJKM,S&P21]. Our development of PQ-BC requires making the BC logic sound for a single interactive quantum attacker. We implement the PQ-Squirrel prover by modifying Squirrel , relying on the soundness results of PQ-BC and enforcing a set of syntactic conditions; additionally, we provide new tactics for the logic that extend the tool’s scope. Using PQ-Squirrel , we perform several case studies, thereby giving the first mechanical proofs of their computational post- quantum security. These include two generic constructions of KEM based key exchange, two sub-protocols from IKEv1 and IKEv2, and a proposed post-quantum variant of Signal’s X3DH protocol. Additionally, we use PQ-Squirrel to prove that several classical Squirrel case-studies are already post-quantum sound. We provide the sources of PQ-Squirrel and all our models for reproducibility, as well as a long version of this paper with full details.

We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guarantees (up to negligible additive factors in a security parameter). Our compiler uses any quantum homomorphic encryption scheme (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) satisfying a natural form of correctness with respect to auxiliary (quantum) input. The homomorphic encryption scheme is used as a cryptographic mechanism to simulate the effect of spatial separation, and is required to evaluate $k-1$ prover strategies (out of $k$) on encrypted queries. In conjunction with the rich literature on (entangled) multi-prover non-local games starting from the celebrated CHSH game (Clauser, Horne, Shimonyi and Holt, Physical Review Letters 1969), our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage.

At ASIACRYPT 2021, Liu et al. pointed out a weakness of the Rasta-like ciphers neglected by the designers. The main strategy is to construct exploitable equations of the $n$-bit $\chi$ operation denoted by $\chi_n$. However, these equations are all obtained by first studying $\chi_n$ for small $n$. In this note, we demonstrate that if the explicit formula of the inverse of $\chi_n$ denoted by $\chi_n^{-1}$ is known, all these exploitable equations would have been quite obvious and the weakness of the Rasta-like ciphers could have been avoided at the design phase. However, the explicit formula of $\chi_n^{-1}$ seems to be not well-known and the most relevant work was published by Biryukov et al. at ASIACRYPT 2014. In this work, we give a very simple formula of $\chi_n^{-1}$ that can be written down in only one line and we prove its correctness in a rigorous way. Based on its formula, the formula of exploitable equations for Rasta-like ciphers can be easily derived and therefore more exploitable equations are found.

Simple but mission-critical internet-based applications that require extremely high reliability, availability, and verifiability (e.g., auditability) could benefit from running on robust public programmable blockchain platforms such as Ethereum. Unfortunately, program code running on such blockchains is normally publicly viewable, rendering these platforms unsuitable for applications requiring strict privacy of application code, data, and results. In this work, we investigate using MPC techniques to protect the privacy of a blockchain computation. While our main goal is to hide both the data and the computed function itself, we also consider the standard MPC setting where the function is public. We describe GABLE (Garbled Autonomous Bots Leveraging Ethereum), a blockchain MPC architecture and system. The GABLE architecture specifies the roles and capabilities of the players. GABLE includes two approaches for implementing MPC over blockchain: Garbled Circuits (GC), evaluating universal circuits, and Garbled Finite State Automata (GFSA). We formally model and prove the security of GABLE implemented over garbling schemes, a popular abstraction of GC and GFSA from (Bellare et al, CCS 2012). We analyze in detail the performance (including Ethereum gas costs) of both approaches and discuss the trade-offs. We implement a simple prototype of GABLE and report on the implementation issues and experience.

Attribute-based Signatures (ABS) allow users to obtain attributes from issuing authorities, and sign messages whilst simultaneously proving compliance of their attributes with a verification policy. ABS demands that both the signer and the set of attributes used to satisfy a policy remain hidden to the verifier. Hierarchical ABS (HABS) supporting roots of trust and delegation were recently proposed to alleviate scalability issues in centralised ABS schemes. An important yet challenging property for privacy-preserving ABS is revocation, which may be applied to signers or some of the attributes they possess. Existing ABS schemes lack efficient revocation of either signers or their attributes, relying on generic costly proofs.Moreover, in HABS there is a further need to support revocation of authorities on the delegation paths, which is not provided by existing HABS constructions. This paper proposes a direct HABS scheme with a Verifier-Local Revocation (VLR) property. We extend the original HABS security model to address revocation and develop a new attribute delegation technique with appropriate VLR mechanism for HABS, which also implies the first ABS scheme to support VLR. Moreover, our scheme supports inner-product signing policies, offering a wider class of attribute relations than previous HABS schemes, and is the first to be based on lattices, which are thought to offer post-quantum security.

Side Channel Attacks (SCAs), an attack that exploits the physical information generated when an encryption algorithm is executed on a device to recover the key, have become one of the key threats to the security of encrypted devices. Recently, with the development of deep learning, deep learning techniques have been applied to side channel attacks with good results on publicly available dataset experiences. In this paper, we propose a power tracking decomposition method that divides the original power tracking into two parts, where the data-influenced part is defined as data power tracking and the other part is defined as device constant power tracking, and use the data power tracking for training the network model, which has more obvious advantages than using the original power tracking for training the network model. To verify the effectiveness of the approach, we evaluated the ATxmega128D4 microcontroller by capturing the power traces generated when implementing AES-128. Experimental results show that network models trained using data power traces outperform network models trained using raw power traces in terms of classification accuracy, training time, cross-subkey recovery key and cross-device recovery key.

Verifiable secret sharing (VSS) is a fundamental tool of cryptography and distributed computing in Internet of things (IoTs). Since network bandwidth is a scarce resource, minimizing the number of verification data will improve the performance of VSS. Existing VSS schemes, however, face limitations in meeting the number of verification data and energy consumptions for low-end devices, which make their adoption challenging in resource-limited IoTs. To address above limitations, we propose a VSS scheme according to Nyberg’s oneway accumulator for one-way hash functions (NAHFs). The proposed scheme has two distinguished features: first, the security of the scheme is based on NAHFs whose computational requirements are the basic criteria for known IoT devices and, second, upon receiving only one verification data, participants can verify the correctness of both their shares and the secret without any communication. Experimental results demonstrate that, compared to the Feldman scheme and Rajabi-Eslami scheme, the energy consumption of a participant in the proposed scheme is respectively reduced by at least 24% and 83% for a secret.

The ever-increasing usage and application of system-on-chips (SoCs) has resulted in the tremendous modernization of these architectures. For a modern SoC design, with the inclusion of numerous complex and heterogeneous intellectual properties (IPs), and its privacy-preserving declaration, there exists a wide variety of highly sensitive assets. These assets must be protected from any unauthorized access and against a diverse set of attacks. Attacks for obtaining such assets could be accomplished through different sources, including malicious IPs, malicious or vulnerable firmware/software, unreliable and insecure interconnection and communication protocol, and side-channel vulnerabilities through power/performance profiles. Any unauthorized access to such highly sensitive assets may result in either a breach of company secrets for original equipment manufactures (OEM) or identity theft for the end-user. Unlike the enormous advances in functional testing and verification of the SoC architecture, security verification is still on the rise, and little endeavor has been carried out by academia and industry. Unfortunately, there exists a huge gap between the modernization of the SoC architectures and their security verification approaches. With the lack of automated SoC security verification in modern electronic design automation (EDA) tools, we provide a comprehensive overview of the requirements that must be realized as the fundamentals of the SoC security verification process in this paper. By reviewing these requirements, including the creation of a unified language for SoC security verification, the definition of security policies, formulation of the security verification, etc., we put forward a realization of the utilization of self-refinement techniques, such as fuzz, penetration, and AI testing, for security verification purposes. We evaluate all the challenges and resolution possibilities, and we provide the potential approaches for the realization of SoC security verification via these self-refinement techniques.

The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover $P^*(x)$ on some theorem $x$, is able to produce a witness $w$ for $x$ with roughly the same probability that $P^*$ produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable computation where the goal is compressing a proof. Pass (CRYPTO '03) first showed how to achieve this property for NP using a cut-and-choose technique which incurred a $\lambda^2$-bit overhead in communication where $\lambda$ is a security parameter. Fischlin (CRYPTO '05) presented a more efficient technique based on ``proofs of work'' that sheds this $\lambda^2$ cost, but only applies to a limited class of Sigma Protocols with a ``quasi-unique response'' property, which for example, does not necessarily include the standard OR composition for Sigma protocols. With Schnorr/EdDSA signature aggregation as a motivating application, we develop new techniques to improve the computation cost of straight-line extractable proofs. Our improvements to the state of the art range from 70X--200X for the best compression parameters. This is due to a uniquely suited polynomial evaluation algorithm, and the insight that a proof-of-work that relies on multicollisions and the birthday paradox is faster to solve than inverting a fixed target. Our collision based proof-of-work more generally improves the Prover's random oracle query complexity when applied in the NIZK setting as well. In addition to reducing the query complexity of Fischlin's Prover, for a special class of Sigma protocols we can for the first time closely match a new lower bound we present. Finally we extend Fischlin's technique so that it applies to a more general class of strongly-sound Sigma protocols, which includes the OR composition. We achieve this by carefully randomizing Fischlin's technique---we show that its current deterministic nature prevents its application to certain multi-witness languages.

Onion routing is a popular approach towards anonymous communication. Practical implementations are widely used (for example, Tor has millions of users daily), but are vulnerable to various traffic correlation attacks, and the theoretical foundations, despite recent progress, still lag behind. In particular, all works that model onion routing protocols and prove their security only address a single run, where each party sends and receives a single message of fixed length, once. Moreover, they all assume a static network setting, where the parties are stable throughout the lifetime of the protocol. In contrast, real networks have a high rate of churn (nodes joining and exiting the network), real users want to send multiple messages, and realistic adversaries may observe multiple runs of the protocol. In this paper, we initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide the following contributions. -We define the cryptographic primitive of poly onion encryption, which is appropriate for a setting with churn. This primitive is inspired by duo onions, introduced by Iwanik, Klonowski, and Kutylowski (Communications and Multimedia Security, 2005) towards improving onion delivery rate. We generalize the idea, change it to add auxiliary helpers towards supporting better security, and propose formal definitions. -We construct an instantiation of poly onion encryption based on standard cryptographic primitives (CCA secure public key encryption with tags, PRP, MAC, and secret sharing). Our construction is secure against an active adversary, and is parameterized to allow flexible instantiations supporting a range of corruption thresholds and churn limits. -We formally model anonymous onion routing for multiple runs in the setting with churn, including a definition of strong anonymity, where the adversary has CCA-like access to oracles for generating and processing onions. -We prove that if an onion routing protocol satisfies a natural condition we define ("simulatability"), then strong single-run anonymity implies strong multiple-run anonymity. This condition is satisfied by existing onion routing schemes, such as the $\Pi_p$ protocol of Ando, Lysyanskaya, and Upfal (ICALP 2018). As a consequence, these schemes are anonymous also for multiple runs (although not when there is churn). -We provide an anonymous routing protocol, "Poly $\Pi_p$," and prove that it is anonymous in the setting with churn, against a passive adversary. We obtain this construction by using an instance of our poly onion encryption within the $\Pi_p$ protocol.

As a common consensus mechanism used in blockchain systems, DPoS uses voting to select committee members who will generate the corresponding blocks. In order to elect committee members as fairly as possible, the vague sets are introduced into the voting phase of DPoS. In the vague sets based model proposed by Xu et al., the voting nodes can vote for, oppose or abstain from it. In this paper, we improve this vague set based model by introducing a new mapping from the vague set to fuzzy set and considering the case that each voting node is assigned a weight. In addition, several nice properties of our improved model are proved and it makes the voting phase of DPoS more fair.

In order to analyze real-time power data without revealing user's privacy, privacy-preserving data aggregation has been extensively researched in smart grid. However, most of the existing schemes either have too much computation overhead and cannot achieve dynamic users, or require a trusted center. In this paper, we propose an efficient and robust multidimensional data aggregation scheme based on blockchain. In our scheme, a leader election algorithm in Raft protocol is used to select a mining node from all smart meters to aggregate data. A dynamically verifiable secret sharing homomorphism scheme is adopted to realize flexible dynamic user management. In addition, our scheme can not only resist internal and external attackers but also support multidimensional data aggregation and fault tolerance. Compared with other schemes, our scheme not only supports user fault tolerance, but also supports fault tolerance of the intermediate aggregation node. The security analysis shows that our proposed scheme is IND-CPA secure and can meet stronger security features. Our performance analyses show that compared with other schemes, our scheme can be implemented with lower computation cost and communication overhead.

Side-channel attacks are formidable threats to the cryptosystems deployed in the real world. An effective and provably secure countermeasure against side-channel attacks is masking. In this work, we present a detailed study of higher-order masking techniques for the key-encapsulation mechanism Saber. Saber is one of the lattice-based finalist candidates in the National Institute of Standards of Technology's post-quantum standardization procedure. We provide a detailed analysis of different masking algorithms proposed for Saber in the recent past and propose an optimized implementation of higher-order masked Saber. Our proposed techniques for first-, second-, and third-order masked Saber have performance overheads of 2.7x, 5x, and 7.7x respectively compared to the unmasked Saber. We show that compared to Kyber which is another lattice-based finalist scheme, Saber's performance degrades less with an increase in the order of masking. We also show that higher-order masked Saber needs fewer random bytes than higher-order masked Kyber. Additionally, we adapt our masked implementation to uSaber, a variant of Saber that was specifically designed to allow an efficient masked implementation. We present the first masked implementation of uSaber, showing that it indeed outperforms masked Saber by at least 12% for any order. We provide optimized implementations of all our proposed masking schemes on ARM Cortex-M4 microcontrollers.

A leading approach to enhancing the performance and scalability of permissionless blockchains is to use the payment channel, which allows two users to perform off-chain payments with almost unlimited frequency. By linking payment channels together to form a payment channel network, users connected by a path of channels can perform off-chain payments rapidly. However, payment channels risk encountering fund depletion, which threatens the availability of both the payment channel and network. The most recent method needs a cycle-based channel rebalancing procedure, which requires a fair leader and users with rebalancing demands forming directed cycles in the network. Therefore, its large-scale applications are restricted. In this work, we introduce Shaduf, a novel non-cycle off-chain rebalancing protocol that offers a new solution for users to shift coins between channels directly without relying on the cycle setting. Shaduf can be applied to more general rebalancing scenarios. We provide the details of Shaduf and formally prove its security under the Universal Composability framework. Our prototype demonstrates its feasibility and the experimental evaluation shows that Shaduf enhances the Lighting Network performance in payment success ratio and volume. Experimental results also show that our protocol prominently reduces users’ deposits in channels while maintaining the same amount of payments. Moreover, as a privacy enhancement of Shaduf, we propose Shaduf++. Shaduf++ not only retains all the advantages of Shaduf, but also preserves privacy for the rebalancing operations.

Phase-shift fault attack is a type of fault attack used for cryptanalysis of stream ciphers. It involves clocking a cipher’s feedback shift registers out of phase, in order to generate faulted keystream. Grain- 128 cipher is a 128-bit modification of the Grain cipher which is one of the finalists in the eSTREAM project. In this work, we propose a phase-shift fault attack against Grain-128 loaded with key-IV pairs that result in an all-zero LFSR after initialisation. We frame equations in terms of the input and output bits of the cipher and solve them using a SAT solver. By correctly guessing 40 internal state bits, we are able to recover the entire 128-bit key with just 2 phase-shift faults for keystreams of length 200 bits.

Secure multi-party computation can provide a solution for privacy protection and ensure the correctness of the final calculation results. Lattice-based algorithms are considered to be one of the most promising post-quantum cryptographic algorithms due to a better balance among security, key sizes and calculation speeds. The NTRUEncrypt is a lattice-based anti-quantum attack cryptographic algorithm. Since there haven't been much candidate post-quantum cryptographic algorithms for secure multi-party computation. In this paper, we propose a novel secure two-party computation scheme based on NTRUEncrypt and implement the polynomial multiplication operations under NTRUEncrypt-OT. Our secure two-party computation scheme mainly uses oblivious transfer and privacy set interaction. We prove the security of our scheme in the semi-honest model. Our scheme can be applied for multi-party computation scenarios, such as quantum attack-resisted E-votes or E-auctions.

Despite the growing demand for software implementations of ECDSA secure against attackers with full control of the execution environment, the scientific literature on white-box ECDSA design is scarce. To assess the state-of-the-art and encourage practical research on this topic, the WhibOx 2021 contest invited developers to submit white-box ECDSA implementations and attackers to break the corresponding submissions. In this work we describe several attack techniques and designs used during the WhibOx 2021 contest. We explain the attack methods used by the team TheRealIdefix, who broke the largest number of challenges, and we show the success of each method against all the implementations in the contest. Moreover, we describe the designs, submitted by the team zerokey, of the two winning challenges; these designs represent the ECDSA signature algorithm by a sequence of systems of low-degree equations, which are obfuscated with affine encodings and extra random variables and equations. The WhibOx contest has shown that securing ECDSA in the white-box model is an open and challenging problem, as no implementation survived more than two days. To this end, our designs provide a starting methodology for further research, and our attacks highlight the weak points future work should address.

Lazy blockchains decouple consensus from transaction verification and execution to increase throughput. Although they can contain invalid transactions (e.g., double spends) as a result, these can easily be filtered out by full nodes that check if there have been previous conflicting transactions. However, creating light (SPV) clients that do not see the whole transaction history becomes a challenge: A record of a transaction on the chain does not necessarily entail transaction confirmation. In this paper, we devise a protocol that enables the creation of efficient light clients for lazy blockchains. The number of interaction rounds and the communication complexity of our protocol are logarithmic in the blockchain execution time. Our construction is based on a bisection game that traverses the Merkle tree containing the ledger of all - valid or invalid - transactions. We prove that our proof system is succinct, complete and sound, and empirically demonstrate the feasibility of our scheme.

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfortunately, SNARKs with desirable features such as a transparent (public-coin) setup are known only in the random oracle model (ROM). In applications this oracle must be heuristically instantiated and used in a non-black-box way. In this paper we identify a natural oracle model, the low-degree random oracle model, in which there exist transparent SNARKs for all NP computations relative to this oracle. Informally, letting $\mathcal{O}$ be a low-degree encoding of a random oracle, and assuming the existence of (standard-model) collision-resistant hash functions, there exist SNARKs relative to $\mathcal{O}$ for all languages in $\mathsf{NP}^{\mathcal{O}}$. Such a SNARK can directly prove a computation about its own verifier. This capability leads to proof-carrying data (PCD) in the oracle model $\mathcal{O}$ based solely on the existence of (standard-model) collision-resistant hash functions. To analyze this model, we introduce a more general framework, the linear code random oracle model (LCROM). We show how to obtain SNARKs in the LCROM for computations that query the oracle, given an accumulation scheme for oracle queries in the LCROM. Then we construct such an accumulation scheme for the special case of a low degree random oracle.

We study witness-authenticated key exchange (WAKE), in which parties authenticate through knowledge of a witness to any NP statement. WAKE achieves generic authenticated key exchange in the absence of trusted parties; WAKE is most suitable when a certificate authority is either unavailable or undesirable, as in highly decentralized networks. In practice WAKE approximates witness encryption, its elusive non-interactive analogue, at the cost of minimal interaction. This work is the first to propose, model and build witness-authenticated key exchange amongst groups of more than two parties, as well as the first to provide practical and provably secure constructions in the two-party case for general NP statements. Specifically our contributions are: (1) both game-based and universally composable (Canetti, FOCS '01) definitions for WAKE along with equivalence conditions between the two definitions, (2) a highly general compiler that introduces witness-authentication to any key exchange protocol along with, as a direct consequence, a three-round group WAKE protocol from DDH and signatures of knowledge (SOK), and (3) an optimized two-round group WAKE construction from DDH and SOK along with experimental benchmarks to demonstrate concrete practicality. Additionally, we study the specialized two-party case and provide a critique of prior work on this topic (Ngo et al., Financial Crypto '21) by pinpointing nontrivial weaknesses in the model, constructions and security proofs seen therein. We rectify those limitations with this work, significantly diverging in our techniques, design and approach.

Homomorphic encryption (HE) is public key encryption that enables computation over ciphertexts without decrypting them, while it is known that HE cannot achieve IND-CCA2 security. To overcome this issue, the notion of keyed-homomorphic encryption (KH-PKE) was introduced, which has a separate homomorphic evaluation key and can achieve stronger security (Emura et al., PKC 2013). The contributions of this paper are twofold. First, the syntax of KH-PKE supposes that homomorphic evaluation is performed for single operations, and its security notion called KH-CCA security was formulated based on this syntax. Consequently, if the homomorphic evaluation algorithm is enhanced in a way of gathering up sequential operations as a single evaluation, then it is not obvious whether or not KH-CCA security is preserved. In this paper, we show that KH-CCA security is in general not preserved under such modification, while KH-CCA security is preserved when the original scheme additionally satisfies circuit privacy. Secondly, Catalano and Fiore (ACM CCS 2015) proposed a conversion method from linearly HE schemes into two-level HE schemes, the latter admitting addition and a single multiplication for ciphertexts. In this paper, we extend the conversion to the case of linearly KH-PKE schemes to obtain two-level KH-PKE schemes. Moreover, based on the generalized version of Catalano-Fiore conversion, we also construct a similar conversion from d-level KH-PKE schemes into 2d-level KH-PKE schemes.

We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of the underlying Additively Homomorphic cryptosystem and generic secure computation schemes for comparison and equality testing.

We design several new protocols for private set intersection (PSI) with active security: one for the two party setting, and two protocols for the multi-party setting. In recent years, the state-of-the-art protocols for two party PSI have all been built from OT-extension. This has led to extremely efficient protocols that provide correct output to one party;~seemingly inherent to the approach, however, is that there is no efficient way to relay the result to the other party with a provable correctness guarantee. Furthermore, there is no natural way to extend this line of works to more parties. We consider a new instantiation of an older approach. Using the MPC-in-the-head paradigm of Ishai et al [IPS08], we construct a polynomial with roots that encode the intersection, without revealing the inputs. Our reliance on this paradigm allows us to base our protocol on passively secure Oblivious Linear Evaluation (OLE) (requiring 4 such amortized calls per input element). Unlike state-of-the-art prior work, our protocols provide correct output to all parties. We have implemented our protocols, providing the first benchmarks for PSI that provides correct output to all parties. Additionally, we present a variant of our multi-party protocol that provides output only to a central server.

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $n$=$2t+1$ players of which $t$ are corrupt, that achieve guaranteed output delivery (GOD), and operate in a single initial round of broadcast (BC), followed by steps of asynchronous peer-to-peer (P2P) messages. The power of closely related ``hybrid networks'' was studied in [Fitzi-Nielsen, Disc'09], [BHN, Podc'10] and [Patra-Ravi, IEEE Tr. Inf. Theory'18]. The interest of such protocols is that they go at the actual speed of the network, and security is preserved under arbitrary network conditions (past the initial BC). We first complete the picture of this model with an impossibility result showing that some setup is required to achieve honest majority MPC with GOD. We then consider a bare bulletin-board PKI setup, and leverage recent advances in multi-key homomorphic encryption [BJMS, Asiacrypt'20], to state the feasibility of MPC in a tight 1-BC-then-1 single step of asynchronous P2P messages. We then consider efficiency. The only protocols adaptable to such a network model and setup are [BJMS, Asiacrypt'20], which does not scale well for many players, and [GLS, Crypto'15], which does not support input delegation from external resource-constrained owners (such as IoT devices or smartphones), limiting its practical use. Our main contribution is a generic design that enables MPC in 1BC-then-asynchronous P2P. It operates over ciphertexts encrypted under a (threshold) single-key encryption scheme, resulting in the smallest sizes expectable and efficient evaluation. It can be implemented from any homomorphic encryption scheme built from linear maps (e.g., GSW, CL, ...). Our main building block is the squishing of the verifiable input sharing (``Share''), in parallel with the distributed key generation (DKG) in the single BC, followed by threshold encryption (``Shrink'') in one asynchronous step. Interestingly, it can be compiled as the first constant-round YOSO protocol in 1 BC.

Predictable arguments introduced by Faonio, Nielsen and Venturi (PKC17) are private-coin argument systems where the answer of the prover can be predicted in advance by the verifier. In this work, we study predictable arguments with additional privacy properties. While the authors in [PKC17] showed compilers for transforming PAs into PAs with zero-knowledge property, they left the construction of witness indistinguishable predictable arguments (WI-PA) in the plain model as an open problem. In this work, we first propose more efficient constructions of zero-knowledge predictable arguments (ZK-PA) based on trapdoor smooth projective hash functions (TSPHFs). Next, we consider the problem of WI-PA construction in the plain model and show how to transform PA into WI-PA using non-interactive witness-indistinguishable proofs. As a relaxation of predictable arguments, we additionally put forth a new notion of predictability called Commit-and-Prove Predictable Argument (CPPA), where except the first (reusable) message of the prover, all the prover’s responses can be predicted. We construct an efficient zero-knowledge CPPA in the non-programmable random oracle model for the class of all polynomial-size circuits. Finally, following the connection between predictable arguments and witness encryption, we show an application of CPPAs with privacy properties to the design of witness encryption schemes, where in addition to standard properties, we also require some level of privacy for the decryptors who own a valid witness for the statement used during the encryption process.

We model and analyze the Signal end-to-end secure messaging protocol within the Universal Composability (UC) framework. Specifically: (1) We formulate an ideal functionality that captures end-to-end secure messaging in a setting with Public Key Infrastructure (PKI) and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time, obtaining their entire internal states. Our analysis captures the forward secrecy and recovery-of-security properties of Signal and the conditions under which they break. (2) We model the main components of the Signal architecture (PKI and long-term keys, the backbone continuous-key-exchange or "asymmetric ratchet", epoch-level symmetric ratchets, authenticated encryption) as individual ideal functionalities. These components are realized and analyzed separately, and then composed using the UC and Global-State UC theorems. (3) We show how the ideal functionalities representing these components can be realized using standard cryptographic primitives with minimal hardness assumptions. Our modeling introduces additional innovations that enable arguing about the security of Signal, irrespective of the underlying communication medium, and facilitate the secure composition of dynamically generated modules that share state. These features, in conjunction with the basic modularity of the UC framework, will hopefully facilitate the use of both Signal-as-a-whole and its individual components within cryptographic applications.

Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs achieve beyond-birthday-bound (BBB) security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus etc. Recently, Shen et al. (Crypto 2021) proposed a security framework for two-key DbHtS MACs in the multi-user setting, stating that when the underlying blockcipher is ideal and the universal hash function is regular and almost universal, the two-key DbHtS MACs achieve 2n/3-bit security. Unfortunately, the regular and universal properties can not guarantee the BBB security of two-key DbHtS MACs. We propose three counter-examples which are proved to be 2n/3-bit secure in the multi-user setting by the framework, but can be broken with probability 1 using only O(2^{n/2}) queries even in the single-user setting. We also point out the miscalculation in their proof leading to such a flaw. However, we haven’t found attacks against 2k-SUM-ECBC, 2k-PMAC_Plus and 2k-LightMAC_Plus proved 2n/3-bit security in their paper.

In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) utilize non-standard assumptions of different types in their proofs of security. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures and prove its security. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities). In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses.

We present a novel cryptographic primitive, blind accumulator, aimed at constructing e-voting systems. Blind accumulators collect private keys of eligible voters in a decentralized manner not getting information about the keys. Once the accumulation is complete, a voter processes the resulting accumulator and derives a public key which refers to a private key previously added by this voter. Public keys are derived deterministically and can therefore stand as fixed voter pseudonyms. The voter can prove that the derived key refers to some accumulated private key without revealing neither that key nor the voter itself. The voter uses the accumulated private key to sign a ballot. The corresponding public key is used to verify the signature. Since the public key is fixed, it is easy to achieve verifiability, to protect against multiple submissions of ballots by the same voter or, conversely, to allow multiple submissions but count only the last one. We suggest a syntax of blind accumulators and security requirements for them. We embed blind accumulators in the Pseudonymous Key Generation (PKG) protocol which details the use of accumulators in practical settings close to e-voting. We propose an instantiation of the blind accumulator scheme whose main computations resemble the Diffie-Hellman protocol. We justify the security of the proposed instantiation.

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works arXiv:1612.01011 and arXiv:1612.02689, we show that taking probabilistic mixtures of channels to solve fallback (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$\sqrt{T}$ gate set we achieve an average non-Clifford gate count of 0.23log2(1/$\varepsilon$)+2.13 and T-count 0.56log2(1/$\varepsilon$)+5.3 with mixed fallback approximations for diamond norm accuracy $\varepsilon$. This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$\sqrt{T}$). We also provide detailed numerical results for Clifford+T and Clifford+$\sqrt{T}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

In this paper, we present a high-performance architecture for elliptic curve cryptography (ECC) over Curve448, which to the best of our knowledge, is the fastest implementation of ECC point multiplication over Curve448 to date. Firstly, we introduce a novel variant of the Karatsuba formula for asymmetric digit multiplier, suitable for typical DSP primitive with asymmetric input. It reduces the number of required DSPs compared to previous work and preserves the performance via full parallelization and pipelining. We then construct a 244-bit pipelined multiplier and interleaved fast reduction algorithm, yielding a total of 12 stages of pipelined modular multiplication with four stages of input delay. Additionally, we present an efficient Montgomery ladder scheduling with no additional register is required. The implementation on the Xilinx 7-series FPGA: Virtex-7, Kintex-7, Artix-7, and Zynq 7020 yields execution times of 0.12, 0.13, 0.24, and 0.24 ms, respectively. It increases the throughput by 242% compared to the best previous work on Zynq 7020 and by 858% compared to the best previous work on Virtex-7. Furthermore, the proposed architecture optimizes nearly 63% efficiency improvement in terms of Area×Time tradeoff. Lastly, we extend our architecture with well-known side-channel protections such as scalar blinding, base-point randomization, and continuous randomization.

All existing works building non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from the Learning With Errors (LWE) assumption have studied instantiating the Fiat-Shamir paradigm on a parallel repetition of an underlying honest-verifier zero knowledge (HVZK) $\Sigma$ protocol, via an appropriately built correlation-intractable (CI) hash function from LWE. This technique has inherent efficiency losses that arise from parallel repetition. In this work, we show how to make use of the more efficient ``MPC in the Head'' technique for building an underlying honest-verifier protocol upon which to apply the Fiat-Shamir paradigm. To make this possible, we provide a new and more efficient construction of CI hash functions from LWE, using efficient algorithms for polynomial reconstruction as the main technical tool. We stress that our work provides a new and more efficient ``base construction'' for building LWE-based NIZK arguments for $\mathsf{NP}$. Our protocol can be the building block around which other efficiency-focused bootstrapping techniques can be applied, such as the bootstrapping technique of Gentry et al. (Journal of Cryptology 2015).

This paper considers a problem of identifying matching attacks against Romulus-M, one of the ten finalists of NIST Lightweight Cryptography standardization project. Romulus-M is provably secure, i.e., there is a theorem statement showing the upper bound on the success probability of attacking the scheme as a function of adversaries' resources. If there exists an attack that matches the provable security bound, then this implies that the attack is optimal, and that the bound is tight in the sense that it cannot be improved. We show that the security bounds of Romulus-M are tight for a large class of parameters by presenting concrete matching attacks.

We introduce the Spiral family of single-server private information retrieval (PIR) protocols. Spiral relies on a composition of two lattice-based homomorphic encryption schemes: the Regev encryption scheme and the Gentry-Sahai-Waters encryption scheme. We introduce new ciphertext translation techniques to convert between these two schemes and in doing so, enable new trade-offs in communication and computation. Across a broad range of database configurations, the basic version of Spiral simultaneously achieves at least a 4.5x reduction in query size, 1.5x reduction in response size, and 2x increase in server throughput compared to previous systems. A variant of our scheme, SpiralStreamPack, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SpiralStreamPack to be only 1.9x greater than that of the no-privacy baseline where the client directly downloads the desired record.

We propose a novel approach that generalizes interleaved modular multiplication algorithms for the computation of sums of products over large prime fields. This operation has widespread use and is at the core of many cryptographic applications. The method reformulates the widely used lazy reduction technique, crucially avoiding the need for storage and computation of "double-precision" operations. Moreover, it can be easily adapted to the different methods that exist to compute modular multiplication, producing algorithms that are significantly more efficient and memory-friendly. We showcase the performance of the proposed approach in the computation of multiplication over an extension field $\mathbb{F}_{p^k}$, and demonstrate its impact with record-breaking implementations of bilinear pairings. Specifically, we accomplish a full optimal ate pairing computation over the popular BLS12-381 curve, designed for the 128-bit security level, in under half a millisecond on a 3.2GHz Intel Coffee Lake processor, which is about $1.40\times$ faster than the state-of-the-art. Similarly, we perform the same computation over the BLS24-509 curve, targeting the 192-bit security level, in $\sim$ 2.6 milliseconds, achieving a speedup of more than $1.30\times$. We also report a significant impact on other applications, including protocols based on supersingular isogenies.

New symmetric primitives are being designed to address a novel set of design criteria. Instead of being executed on regular processors or smartcards, they are instead intended to be run in abstract settings such as multi-party computations or zero-knowledge proof systems. This implies in particular that these new primitives are described using operations over large finite fields. As the number of such primitives grows, it is important to better understand the properties of their underlying operations. In this paper, we investigate the algebraic degree of one of the first such block ciphers, namely MiMC. It is composed of many iterations of a simple round function, which consists of an addition and of a low-degree power permutation applied to the full state, usually $x \mapsto x^{3}$. We show in particular that, while the univariate degree increases predictably with the number of rounds, the algebraic degree (a.k.a multivariate degree) has a much more complex behaviour, and simply stays constant during some rounds. Such plateaus slightly slow down the growth of the algebraic degree. We present a full investigation of this behaviour. First, we prove some lower and upper bounds for the algebraic degree of an arbitrary number of iterations of MiMC and of its inverse. Then, we combine theoretical arguments with simulations to prove that the upper bound is tight for up to 16265 rounds. Using these results, we slightly improve the higher-order differential attack presented at Asiacrypt 2020 to cover one or two more rounds. More importantly, our results provide some precise guarantees on the algebraic degree of this cipher, and then on the minimal complexity for a higher-order differential attack.

In known security reductions for the Fujisaki-Okamoto transformation, decryption failures are handled via a reduction solving the rather unnatural task of finding failing plaintexts \emph{given the private key}, resulting in a Grover search bound. Moreover, they require an implicit rejection mechanism for invalid ciphertexts to achieve a reasonable security bound in the QROM. We present a reduction that has neither of these deficiencies: We introduce two security games related to finding decryption failures, one capturing the \emph{computationally hard} task of \emph{using the public key} to find a decryption failure, and one capturing the \emph{statistically hard} task of searching the random oracle for \emph{key-independent} failures like, e.g., large randomness. As a result, our security bounds in the QROM are tighter than previous ones with respect to the generic random oracle search attacks: The attacker can only partially compute the search predicate, namely for said key-independent failures. In addition, our entire reduction works for the explicit-reject variant of the transformation and improves significantly over all of its known reductions. Besides being the more natural variant of the transformation, security of the explicit reject mechanism is also relevant for side channel attack resilience of the implicit-rejection variant. Along the way, we prove several technical results characterizing preimage extraction and certain search tasks in the QROM that might be of independent interest.

In this paper, the recommended implementation of the post-quantum key exchange SIKE for Cortex-M4 is attacked through power analysis with a single trace by clustering with the $k$-means algorithm the power samples of all the invocations of the elliptic curve point swapping function in the constant-time coordinate-randomized three point ladder. Because each sample depends on whether two consecutive bits of the private key are the same or not, a successful clustering (with $k=2$) leads to the recovery of the entire private key. The attack is naturally improved with better strategies, such as clustering the samples in the frequency domain or processing the traces with a wavelet transform, using a simpler clustering algorithm based on thresholding, and using metrics to prioritize certain keys for key validation. The attack and the proposed improvements were experimentally verified using the ChipWhisperer framework. Splitting the swapping mask into multiple shares is suggested as an effective countermeasure.

Recently, number-theoretic assumptions including DDH, DCR and QR have been used to build powerful tools for secure computation, in the form of homomorphic secret-sharing (HSS), which leads to secure two-party computation protocols with succinct communication, and pseudorandom correlation functions (PCFs), which allow non-interactive generation of a large quantity of correlated randomness. In this work, we present a group-theoretic framework for these classes of constructions, which unifies their approach to computing distributed discrete logarithms in various groups. We cast existing constructions in our framework, and also present new constructions, including one based on class groups of imaginary quadratic fields. This leads to the first construction of two-party homomorphic secret sharing for branching programs from class group assumptions. Using our framework, we also obtain pseudorandom correlation functions for generating oblivious transfer and vector-OLE correlations from number-theoretic assumptions. These have a trustless, public-key setup when instantiating our framework using class groups. Previously, such constructions either needed a trusted setup in the form of an RSA modulus with unknown factorisation, or relied on multi-key fully homomorphic encryption from the learning with errors assumption. We also show how to upgrade our constructions to achieve active security using appropriate zero-knowledge proofs. In the random oracle model, this leads to a one-round, actively secure protocol for setting up the PCF, as well as a 3-round, actively secure HSS-based protocol for secure two-party computation of branching programs with succinct communication.

We show how to backdoor the McEliece cryptosystem such that a backdoored public key is indistinguishable from a usual public key, but allows to efficiently retrieve the underlying secret key. For good cryptographic reasons, McEliece uses a small random seed 𝛅 that generates via some pseudo random generator (PRG) the randomness that determines the secret key. Our backdoor mechanism works by encoding an encryption of 𝛅 into the public key. Retrieving 𝛅 then allows to efficiently recover the (backdoored) secret key. Interestingly, McEliece can be used itself to encrypt 𝛅, thereby protecting our backdoor mechanism with strong post-quantum security guarantees. Our construction also works for the current Classic McEliece NIST standard proposal for non-compressed secret keys, and therefore opens the door for widespread maliciously backdoored implementations. Fortunately, our backdoor mechanism can be detected by the owner of the (backdoored) secret key if 𝛅 is stored after key generation as specified by the Classic McEliece proposal. Thus, our results provide strong advice for implementers to store 𝛅 inside the secret key and use 𝛅 to guard against backdoor mechanisms.

Base64 encoding has been a popular method to encode binary data into printable ASCII characters. It is commonly used in several serialization protocols, web, and logging applications, while it is oftentimes the preferred method for human-readable database fields. However, while convenient and with a better compression rate than hex-encoding, the large number of base64 variants in related standards and proposed padding-mode optionality have been proven problematic in terms of security and cross-platform compatibility. This paper addresses a potential attack vector in the base64 decoding phase, where multiple different encodings can successfully decode into the same data, effectively breaking string uniqueness guarantees. The latter might result to log mismatches, denial of service attacks and duplicated database entries, among the others. Apart from documenting why canonicity can be broken by a malleable encoder, we also present an unexpected result, where most of today's base64 decoder libraries are not 100% compatible in their default settings. Some surprising results include the non-compatible behavior of major Rust base64 crates and between popular Javascript and NodeJS base64 implementations. Finally, we propose ways and test vectors for mitigating these issues until a more permanent solution is widely adopted.

We present the first algorithm that combines privacy-preserving technologies and state-of-the-art explainable AI to enable privacy-friendly explanations of black-box AI models. We provide a secure algorithm for contrastive explanations of black-box machine learning models that securely trains and uses local foil trees. Our work shows that the quality of these explanations can be upheld whilst ensuring the privacy of both the training data, and the model itself.

Estimating the probability, as well as the profitability, of different attacks is of utmost importance when assessing the security and stability of prevalent cryptocurrencies. Previous modeling attempts of classic chain-racing attacks have different drawbacks: they either focus on theoretical scenarios such as infinite attack durations, do not account for already contributed blocks, assume honest victims which immediately stop extending their chain as soon as it falls behind, or rely on computationally heavy approaches which render them ill-suited when fast decisions are required. In this paper, we present a simple yet practical model to calculate the success probability of finite attacks, while considering already contributed blocks and victims that do not give up easily. Hereby, we introduce a more fine grained distinction between different actor types and the sides they take during an attack. The presented model simplifies assessing the profitability of forks in practical settings, while also enabling fast and more accurate estimations of the economic security grantees in certain scenarios. By applying and testing our model in the context of bribing attacks, we further emphasize that approaches where the attacker compensates already contributed attack-chain blocks are particularly cheap. Better and more realistic attack models also help to spot and explain certain events observed in the empirical analysis of cryptocurrencies, or provide valuable directions for future studies. For better reproducibility and to foster further research in this area, all source code, artifacts and calculations are made available on GitHub.

Private set union (PSU) protocol enables two parties, each holding a set, to compute the union of their sets without revealing anything else to either party. So far, there are two known approaches for constructing PSU protocols. The first mainly depends on additively homomorphic encryption (AHE), which is generally inefficient since it needs to perform a non-constant number of homomorphic computations on each item. The second is mainly based on oblivious transfer and symmetric-key operations, which is recently proposed by Kolesnikov et al. (ASIACRYPT 2019). It features good practical performance, which is several orders of magnitude faster than the first one. However, neither of these two approaches is optimal in the sense that their computation and communication complexity are not both $O(n)$, where $n$ is the size of the set. Therefore, the problem of constructing the optimal PSU protocol remains open. In this work, we resolve this open problem by proposing a generic framework of PSU from oblivious transfer and a newly introduced protocol called multi-query reverse private membership test (mq-RPMT). We present two generic constructions of mq-RPMT. The first is based on symmetric-key encryption and general 2PC techniques. The second is based on re-randomizable public-key encryption. Both constructions lead to PSU with linear computation and communication complexity. We implement our two PSU protocols and compare them with the state-of-the-art PSU. Experiments show that our PKE-based protocol has the lowest communication of all schemes, which is $3.7-14.8\times$ lower depending on set size. The running time of our PSU scheme is $1.2-12\times$ faster than that of state-of-the-art depending on network environments.

In this article, we prove a generic lower bound on the number of $\mathfrak{O}$-orientable supersingular curves over $\mathbb{F}_{p^2}$, i.e curves that admit an embedding of the quadratic order $\mathfrak{O}$ inside their endomorphism ring. Prior to this work, the only known effective lower-bound is restricted to small discriminants. Our main result targets the case of fundamental discriminants and we derive a generic bound using the expansion properties of the supersingular isogeny graphs. Our work is motivated by isogeny-based cryptography and the increasing number of protocols based on $\mathfrak{O}$-oriented curves. In particular, our lower bound provides a complexity estimate for the brute-force attack against the new $\mathfrak{O}$-uber isogeny problem introduced by De Feo, Delpech de Saint Guilhem, Fouotsa, Kutas, Leroux, Petit, Silva and Wesolowski in their recent article on the SETA encryption scheme.

While the convergence of Artificial Intelligence (AI) techniques with improved information technology systems ensured enormous benefits to the Internet of Vehicles (IoVs) systems, it also introduced an increased amount of security and privacy threats. To ensure the security of IoVs data, privacy preservation methodologies have gained significant attention in the literature. However, these strategies also need specific adjustments and modifications to cope with the advances in IoVs design. In the interim, Federated Learning (FL) has been proven as an emerging idea to protect IoVs data privacy and security. On the other hand, Blockchain technology is showing prominent possibilities with secured, dispersed, and auditable data recording and sharing schemes. In this paper, we present a comprehensive survey on the application and implementation of Blockchain-Enabled Federated Learning frameworks for IoVs. Besides, probable issues, challenges, solutions, and future research directions for BC-Enabled FL frameworks for IoVs are also presented. This survey can further be used as the basis for developing modern BC-Enabled FL solutions to resolve different data privacy issues and scenarios of IoVs.

Seminal works by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [EuroS&P 2017] and Alwen, Coretti and Dodis [EUROCRYPT 2019] provided the first formal frameworks for studying the widely-used Signal Double Ratchet (DR for short) algorithm. In this work, we develop a new Universally Composable (UC) definition F_DR that we show is provably achieved by the DR protocol. Our definition captures not only the security and correctness guarantees of the DR already identified in the prior state-of-the-art analyses of Cohn-Gordon et al. and Alwen et al., but also more guarantees that are absent from one or both of these works. In particular, we construct six different modified versions of the DR protocol, all of which are insecure according to our definition F_DR, but remain secure according to one (or both) of their definitions. For example, our definition is the first to capture CCA-style attacks possible immediately after a compromise — attacks that, as we show, the DR protocol provably resists, but were not captured by prior definitions. We additionally show that multiple compromises of a party in a short time interval, which the DR should be able to withstand, as we understand from its whitepaper, nonetheless introduce a new non-trivial (albeit minor) weakness of the DR. Since the definitions in the literature (including our F_DR above) do not capture security against this more nuanced scenario, we define a new stronger definition F_TR that does. Finally, we provide a minimalistic modification to the DR (that we call the Triple Ratchet, or TR for short) and show that the resulting protocol securely realizes the stronger functionality F_TR. Remarkably, the modification incurs no additional communication cost and virtually no additional computational cost. We also show that these techniques can be used to improve communication costs in other scenarios, e.g. practical Updatable Public Key Encryption schemes and the re-randomized TreeKEM protocol of Alwen et al. [CRYPTO 2020] for Secure Group Messaging.

Approximate Agreement (AA) allows a set of $n$ parties that start with real-valued inputs to obtain values that are at most within a parameter $\epsilon > 0$ from each other and within the range of their inputs. Existing AA protocols, both for the synchronous network model (where any message is delivered within a known delay $\Delta$ time) and the asynchronous network model, are secure when up to $t < n/3$ of the parties are corrupted and require no initial setup (such as a public-key infrastructure (PKI) for signatures). We consider AA protocols where a PKI is available, and show the first AA protocol that achieves simultaneously security against $t_s$ corruptions when the network is synchronous and $t_a$ corruptions when the network is asynchronous, for any $0\le t_a < n/3 \le t_s < n/2$ such that $t_a + 2 \cdot t_s < n$. We further show that our protocol is optimal by proving that achieving AA for $t_a + 2 \cdot t_s \ge n$ is impossible (even with setup). Remarkably, this is also the first AA protocol that tolerates more than $n/3$ corruptions in the synchronous network model.

We obtain publicly verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computation from standard group-based assumptions, without relying on pairings. In particular, assuming the sub-exponential hardness of both the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where $n$ denotes the length of the instance: 1. A SNARG for any language that can be decided in non-deterministic time $T$ and space $S$ with communication complexity and verifier runtime $(n + S) \cdot T^{o(1)}$. 2. A SNARG for any language that can be decided in deterministic time $T$ with communication complexity and verifier runtime $n \cdot T^{o(1)}$.

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.

In this work, we consider the formal verification of the public-key encryption scheme of Saber, one of the selected few post-quantum cipher suites currently considered for potential standardization. We formally verify this public-key encryption scheme's IND-CPA security and $\delta$-correctness properties, i.e., the properties required to transform the public-key encryption scheme into an IND-CCA2 secure and $\delta$-correct key encapsulation mechanism, in EasyCrypt. To this end, we initially devise hand-written proofs for these properties that are significantly more detailed and meticulous than the presently existing proofs. Subsequently, these hand-written proofs serve as a guideline for the formal verification. The results of this endeavor comprise hand-written and computer-verified proofs which demonstrate that Saber's public-key encryption scheme indeed satisfies the desired security and correctness properties.

Uniswap, like other DEXs, has gained much attention this year because it is a non-custodial and publicly verifiable exchange that allows users to trade digital assets without trusted third parties. However, its simplicity and lack of regulation also makes it easy to execute initial coin offering scams by listing non-valuable tokens. This method of performing scams is known as rug pull, a phenomenon that already existed in traditional finance but has become more relevant in DeFi. Various projects such as [34,37] have contributed to detecting rug pulls in EVM compatible chains. However, the first longitudinal and academic step to detecting and characterizing scam tokens on Uniswap was made in [44]. The authors collected all the transactions related to the Uniswap V2 exchange and proposed a machine learning algorithm to label tokens as scams. However, the algorithm is only valuable for detecting scams accurately after they have been executed. This paper increases their data set by 20K tokens and proposes a new methodology to label tokens as scams. After manually analyzing the data, we devised a theoretical classification of different malicious maneuvers in Uniswap protocol. We propose various machine-learning-based algorithms with new relevant features related to the token propagation and smart contract heuristics to detect potential rug pulls before they occur. In general, the models proposed achieved similar results. The best model obtained an accuracy of 0.9936, recall of 0.9540, and precision of 0.9838 in distinguishing non-malicious tokens from scams prior to the malicious maneuver.

We explore algorithmic aspects of a free and transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over $\mathbb{F}_q$ acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. Our proof-of-concept C++/NTL implementation only requires a fraction of a second on a standard computer. Also, we state a conjecture — supported by experiments — which implies that the current fastest algorithm to solve its inverse problem runs in exponential time. This action is therefore a promising candidate for the construction of Hard Homogeneous Spaces, which are the building blocks of several post-quantum cryptographic protocols. This demonstrates the relevance of using imaginary hyperelliptic curves and Drinfeld modules as an alternative to the standard setting of imaginary quadratic number fields and elliptic curves for isogeny-based cryptographic applications. Moreover, our function field setting enables the use of Kedlaya's algorithm and its variants for computing the order of the group in polynomial time when $q$ is fixed. No such polynomial-time algorithm for imaginary quadratic number fields is known. For $q=2$ and parameters similar to CSIDH-512, we compute this order more than 8500 times faster than the record computation for CSIDH-512 by Beullens, Kleinjung and Vercauteren.

Pairing-based cryptographic protocols are typically vulnerable to small-subgroup attacks in the absence of protective measures. To thwart them, one of feasible measures is to execute subgroup membership testings, which are generally considered expensive. Recently, Scott proposed an efficient method of subgroup membership testings for $\mathbb{G}_1$, $\mathbb{G}_2$ and $\mathbb{G}_T$ on the BLS family. In this paper, we generalize this method proposed by Scott and show that the new technique is applicable to a large class of pairing-friendly curves. In addition, we also confirm that the new method leads to a significant speedup for membership testings on many popular pairing-friendly curves.

Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner since computations can only be performed on ciphertexts encrypted under the same secret key. To resolve this issue, research is underway on Multi-Key Homomorphic Encryption (MKHE), which is a variant of HE supporting computations on ciphertexts possibly encrypted under different keys. Despite its ability to provide privacy for multiple parties, existing MKHE schemes suffer from poor performance due to the cost of multiplication which grows at least quadratically with the number of keys involved. In this paper, we revisit the work of Chen et al. (ACM CCS 2019) on MKHE schemes from CKKS and BFV and significantly improve their performance. Specifically, we redesign the multi-key multiplication algorithm and achieve an asymptotically optimal complexity that grows linearly with the number of keys. Our construction relies on a new notion of gadget decomposition, which we call homomorphic gadget decomposition, where arithmetic operations can be performed over the decomposed vectors with guarantee of its functionality. Finally, we implement our MKHE schemes and demonstrate their benchmarks. For example, our multi-key CKKS multiplication takes only 0.5, 1.0, and 1.9 seconds compared to 1.6, 5.9, and 23.0 seconds of the previous work when 8, 16, and 32 keys are involved, respectively.

In 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the $SPHINCS^{+}$ construction. This work gives a new tight security proof for $SPHINCS^{+}$. The flaw can be traced back to the security proof for the Winternitz one-time signature scheme (WOTS) used within $SPHINCS^{+}$. In this work, we give a standalone description of the WOTS variant used in SPHINCS+ that we call WOTS-TW. We provide a security proof for WOTS-TW and multi-instance WOTS-TW against non-adaptive chosen message attacks where the adversary only learns the public key after it made its signature query. Afterwards, we show that this is sufficient to give a tight security proof for $SPHINCS^{+}$. We recover almost the same bound for the security of $SPHINCS^{+}$, with only a factor $w$ loss compared to the previously claimed bound, where w is the Winternitz parameter that is commonly set to 16. On a more technical level, we introduce new lower bounds on the quantum query complexity for generic attacks against properties of cryptographic hash functions and analyse the constructions of tweakable hash functions used in $SPHINCS^{+}$ with regard to further security properties.

We show how the Weil pairing can be used to evaluate the assigned characters of an imaginary quadratic order $\mathcal{O}$ in an unknown ideal class $[\mathfrak{a}] \in \mathrm{Cl}(\mathcal{O})$ that connects two given $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E', \iota') = [\mathfrak{a}](E, \iota)$. When specialized to ordinary elliptic curves over finite fields, our method is conceptually simpler and often faster than a recent approach due to Castryck, Sot\'akov\'a and Vercauteren, who rely on the Tate pairing instead. The main implication of our work is that it breaks the decisional Diffie–Hellman problem for practically all oriented elliptic curves that are acted upon by an even-order class group. It can also be used to better handle the worst cases in Wesolowski's recent reduction from the vectorization problem for oriented elliptic curves to the endomorphism ring problem, leading to a method that always works in sub-exponential time.

We describe a simple MPC protocol in the preprocessing model for computing multivariate quadratic maps. This yields Mesquite, a KKW-style signature scheme which, to our knowledge, produces the shortest signatures of any based on the MQ assumption. For example, our compact parameter set targeting NIST security level I has an average signature size of 8.8KB and runtimes on par with Picnic3 L1.

A wiretap coding scheme (Wyner, Bell Syst. Tech. J. 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel chB, while at the same time hiding m from Eve who receives c over another noisy channel chE. Wiretap coding is clearly impossible when chB is a degraded version of chE, in the sense that the output of chB can be simulated using only the output of chE. A classic work of Csiszár and Körner (IEEE Trans. Inf. Theory, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs (chB, chE) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if chB is not a degraded version of chE. Our construction assumes the existence of virtual black-box (VBB) obfuscation of specific classes of ``evasive'' functions that generalize fuzzy point functions, and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice's algorithm depends only on chB and not on chE.

The area of multi-party computation (MPC) has recently increased in popularity and number of use cases. At the current state of the art, Ciminion, a Farfalle-like cryptographic function, achieves the best performance in MPC applications involving symmetric primitives. However, it has a critical weakness. Its security highly relies on the independence of its subkeys, which is achieved by using an expensive key schedule. Many MPC use cases involving symmetric pseudo-random functions (PRFs) rely on secretly shared symmetric keys, and hence the expensive key schedule must also be computed in MPC. As a result, Ciminion's performance is significantly reduced in these use cases. In this paper we solve this problem. Following the approach introduced by Ciminion's designers, we present a novel primitive in symmetric cryptography called Megafono. Megafono is a keyed extendable PRF, expanding a fixed-length input to an arbitrary-length output. Similar to Farfalle, an initial keyed permutation is applied to the input, followed by an expansion layer, involving the parallel application of keyed ciphers. The main novelty regards the expansion of the intermediate/internal state for "free", by appending the sum of the internal states of the first permutation to its output. The combination of this and other modifications, together with the impossibility for the attacker to have access to the input state of the expansion layer, make Megafono very efficient in the target application. As a concrete example, we present the PRF Hydra, an instance of Megafono based on the Hades strategy and on generalized versions of the Lai--Massey scheme. Based on an extensive security analysis, we implement Hydra in an MPC framework. The results show that it outperforms all MPC-friendly schemes currently published in the literature.

At CRYPTO'19, A. Gohr proposed neural distinguishers for the lightweight block cipher Speck32/64, achieving better results than the state-of-the-art at that point. However, the motivation for using that particular architecture was not very clear, leading us to investigate whether a smaller and/or better performing neural distinguisher exists. This paper studies the depth-10 and depth-1 neural distinguishers proposed by Gohr with the aim of finding out whether smaller or better-performing distinguishers for Speck32/64 exist. We first evaluate whether we can find smaller neural networks that match the accuracy of the proposed distinguishers. We answer this question in affirmative with the depth-1 distinguisher successfully pruned, resulting in a network that remained within one percentage point of the unpruned network's performance. Having found a smaller network that achieves the same performance, we examine if its performance can be improved as well. We also study whether processing the input before giving it to the pruned depth-1 network would improve its performance. To this end, convolutional autoencoders were found that managed to reconstruct the ciphertext pairs successfully, and their trained encoders were used as a preprocessor before training the pruned depth-1 network. We found that, even though the autoencoders achieve a perfect reconstruction, the pruned network did not have the necessary complexity anymore to extract useful information from the preprocessed input, motivating us to look at the feature importance to get more insights. To achieve this, we used LIME, with results showing that a stronger explainer is needed to assess it correctly.

Profiling side-channel analysis allows evaluators to estimate the worst-case security of a target. When security evaluations relax the assumptions about the adversary's knowledge, profiling models may easily be sub-optimal due to the inability to extract the most informative points of interest from the side-channel measurements. When used for profiling attacks, deep neural networks can learn strong models without feature selection with the drawback of expensive hyperparameter tuning. Unfortunately, due to very large search spaces, one usually finds very different model behaviors, and a widespread situation is to face overfitting with typically poor generalization capacity. Usually, overfitting or poor generalization would be mitigated by adding more measurements to the profiling phase to reduce estimation errors. This paper provides a detailed analysis of different deep learning model behaviors and shows that adding more profiling traces as a single solution does not necessarily help improve generalization. In fact, we recognize the main problem to be the sub-optimal selection of hyperparameters, which is then difficult to resolve by simply adding more measurements. Instead, we propose to use small hyperparameter tweaks or regularization as techniques to resolve the problem.

Every public-key encryption/decryption algorithm where the set of possible plain-texts is identical to the set of possible cipher-texts may be converted into a digital signature algorithm. That is quite different in the lattice (code)-based public-key cryptography. The decryption algorithm on a random input produces a valid plain-text, that is a signature, with a negligible probability. That explains why it is so difficult to construct a new secure and efficient lattice-based digital signature system. Though several solutions are known and taking part in the NIST Post Quantum Standardisation Process there is still a need to construct digital signature algorithms based on new principles. In this work, a new and efficient digital signature algorithm is suggested. Its design is simple and transparent. Its security is based on the hardness of an approximate closest vector problem in the maximum norm for some $q$-ary lattices. The signature is shorter than that provided by the NIST Selected Digital Signature Algorithms with a comparable security level, while the public key size is larger.

Private join and compute (PJC) is a paradigm where two parties owing their private database securely join their databases and compute a function over the combined database. Inner product PJC, introduced by Lepoint et al. (Asiacrypt'21), is a class of PJC that has a wide range of applications such as secure analysis of advertising campaigns. In this computation, two parties, each of which has a set of identifier-value pairs, compute the inner product of the values after the (inner) join of their databases with respect to the identifiers. They proposed inner product PJC protocols that are specialized for the unbalanced setting where the input sizes of both parties are significantly different and not suitable for the balanced setting where the sizes of two inputs are relatively close. We propose an inner product PJC protocol that is much more efficient than that by Lepoint et al. for balanced inputs in the setting where both parties are allowed to learn the intersection size additionally. Our protocol can be seen as an extension of the private intersection-sum protocol based on the decisional Diffie-Hellman assumption by Ion et al. (EuroS&P'20) and is especially communication-efficient as the private intersection-sum protocol. In the case where both input sizes are $2^{16}$, the communication cost of our inner-product PJC protocol is $46\times$ less than that of the inner product PJC protocol by Lepoint et al.

The NIST post-quantum cryptography (PQC) standardization project is probably the largest and most ambitious cryptography standardization effort to date, and as such it makes an excellent case study of cryptography standardization projects. It is expected that with the end of round 3 in early 2022, NIST will announce the first set of primitives to advance to standardization, so it seems like a good time to look back and see what lessons can be learned from this effort. In this paper, we take a look at one specific aspect of the NIST PQC project: software implementations. We observe that many implementations included as a mandatory part of the submission packages were of poor quality and ignored decades-old standard techniques from software engineering to guarantee a certain baseline quality level. As a consequence, it was not possible to readily use those implementations in experiments for post-quantum protocol migration and software optimization efforts without first spending a significant amount of time to clean up the submitted reference implementations. We do not mean to criticize cryptographers who submitted proposals, including software implementations, to NIST PQC: after all, it cannot reasonably be expected from every cryptographer to also have expertise in software engineering. Instead, we suggest how standardization bodies like NIST can improve the software-submission process in future efforts to avoid such issues with submitted software. More specifically, we present PQClean, an extensive (continuous-integration) testing framework for PQC software, which now also contains "clean" implementations of the NIST round 3 candidate schemes. We argue that the availability of such a framework---either in an online continuous-integration setup, or just as an offline testing system---long before the submission deadline would have resulted in much better implementations included in NIST PQC submissions and overall would have saved the community and probably also NIST a lot of time and effort.

Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a prover to convince a verifier of multiple NP statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance. In this work, we give the first construction of a non-interactive batch argument for NP from standard assumptions on groups with bilinear maps (specifically, from either the subgroup decision assumption in composite-order groups or from the $k$-Lin assumption in prime-order groups for any $k \ge 1$). Previously, batch arguments for NP were only known from LWE, or a combination of multiple assumptions, or from non-standard/non-falsifiable assumptions. Moreover, our work introduces a new direct approach for batch verification and avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches. As corollaries to our main construction, we obtain the first publicly-verifiable non-interactive delegation scheme for RAM programs (i.e., a succinct non-interactive argument (SNARG) for P) with a CRS of sublinear size (in the running time of the RAM program), as well as the first aggregate signature scheme (supporting bounded aggregation) from standard assumptions on bilinear maps.

Cybersecurity has become one of the focuses of organisations. The number of cyberattacks keeps increasing as Internet usage continues to grow. An intrusion detection system (IDS) is an alarm system that helps to detect cyberattacks. As new types of cyberattacks continue to emerge, researchers focus on developing machine learning (ML)-based IDS to detect zero-day attacks. Researchers usually remove some or all attack samples from the training dataset and only include them in the testing dataset when evaluating the performance of an IDS on detecting zero-day attacks. Although this method may show the ability of an IDs to detect unknown attacks; however, it does not reflect the long-term performance of the IDS as it only shows the changes in the type of attacks. In this paper, we focus on evaluating the long-term performance of ML-based IDS. To achieve this goal, we propose evaluating the ML-based IDS using a dataset that is created later than the training dataset. The proposed method can better assess the long-term performance of an ML-based IDS, as the testing dataset reflects the changes in the type of attack and the changes in network infrastructure over time. We have implemented six of the most popular ML models that are used for IDS, including decision tree (DT), random forest (RF), support vector machine (SVM), naïve Bayes (NB), artificial neural network (ANN) and deep neural network (DNN). Our experiments using the CIC-IDS2017 and the CSE-CIC-IDS2018 datasets show that SVM and ANN are most resistant to overfitting. Besides that, our experiment results also show that DT and RF suffer the most from overfitting, although they perform well on the training dataset. On the other hand, our experiments using the LUFlow dataset have shown that all models can perform well when the difference between the training and testing datasets is small.

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.

Verifiable Dynamic Searchable Symmetric Encryption (VDSSE) enables users to securely outsource databases (document sets) to cloud servers and perform searches and updates. The verifiability property prevents users from accepting incorrect search results returned by a malicious server. However, we discover that the community currently only focuses on preventing malicious behavior from the server but ignores incorrect updates from the client, which are very likely to happen since there is no record on the client to check. Indeed most existing VDSSE schemes are not sufficient to tolerate incorrect updates from the client. For instance, deleting a nonexistent keyword-identifier pair can break their correctness and soundness. In this paper, we demonstrate the vulnerabilities of a type of existing VDSSE schemes that fail them to ensure correctness and soundness properties on incorrect updates. We propose an efficient fault-tolerant solution that can consider any DSSE scheme as a black-box and make them into a fault-tolerant VDSSE in the malicious model. Forward privacy is an important property of DSSE that prevents the server from linking an update operation to previous search queries. Our approach can also make any forward secure DSSE scheme into a fault-tolerant VDSSE without breaking the forward security guarantee. In this work, we take FAST [1] (TDSC 2020), a forward secure DSSE, as an example, implement a prototype of our solution, and evaluate its performance. Even when compared with the previous fastest forward private construction that does not support fault tolerance, the experiments show that our construction saves 9× client storage and has better search and update efficiency.

The last decade has seen an explosion in the number of new secure multi-party computation (MPC) protocols that enable collaborative computation on sensitive data. No single MPC protocol is optimal for all types of computation. As a result, researchers have created hybrid-protocol compilers that translate a program into a hybrid protocol that mixes different MPC protocols. Hybrid-protocol compilers crucially rely on accurate cost models, which are handwritten by the compilers' developers, to choose the correct schedule of protocols. In this paper, we propose CostCO, the first automatic MPC cost modeling framework. CostCO develops a novel API to interface with a variety of MPC protocols, and leverages domain-specific properties of MPC in order to enable efficient and automatic cost-model generation for a wide range of MPC protocols. CostCO employs a two-phase experiment design to efficiently synthesize cost models of the MPC protocol’s runtime as well as its memory and network usage. We verify CostCO’s modeling accuracy for several full circuits, characterize the engineering effort required to port existing MPC protocols, and demonstrate how hybrid-protocol compilers can leverage CostCO’s cost models.

Authenticated encryption (AE) is a symmetric-key encryption function that provides confidentiality and authenticity of a message. One of the evaluation criteria for AE is state size, which is memory size needed for encryption. State size is especially important when cryptosystem is implemented in constrained devices, while trivial reduction by using a small primitive is not generally acceptable as it leads to a degraded security. In these days, the state size of AE has been very actively studied and a number of small-state AE schemes have been proposed, but they are inherently serial. It would be a natural question if we come up with a parallelizable AE with a smaller state size than the state-of-the-art. In this paper, we study the seminal OCB mode for parallelizable AE and propose a method to reduce its state size without losing the bit security of it. More precisely, while (the most small-state variant of) OCB has $3n$-bit state, by carefully treating the checksum that is halved, we can achieve $2.5n$-bit state, while keeping the $n/2$-bit security as original. We also propose an inverse-free variant of it based on OTR. While the original OTR has $4n$-bit state, ours has $3.5n$-bit state. To our knowledge these numbers are the smallest ones achieved by the blockcipher modes for parallel AE and inverse-free parallel AE.

Functional Encryption (FE) is a powerful notion of encryption which enables computations and partial message recovery of encrypted data. In FE, each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$ from an encryption of $m$. Informally, security states that a user with access to function keys $sk_{f_1}, sk_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ decryption keys. In the last decade, numerous works have proposed many FE constructions from a wide array of algebraic and general cryptographic assumptions, and proved their security in the bounded collusion model. However, until very recently, all these works studied bounded collusion resistance in a ``static model", where the collusion bound $q$ was a global system parameter. While the static collusion model led to great research progress in the community, it has many major drawbacks. Very recently, Agrawal et al. (Crypto 2021) and Garg et al. (Eurocrypt 2022) independently introduced the dynamic model for bounded collusion resistance, where the collusion bound $q$ was a fluid parameter that was not globally set but only chosen by each encryptor. The dynamic collusion model enabled harnessing the many virtues of the static collusion model, while avoiding its various drawbacks. In this work, we give a simple and generic approach to upgrade any scheme from the static collusion model to the dynamic collusion model. Our result captures all existing results in the dynamic model in the form of a single unified framework, and also gives new results as simple corollaries with a lot more potential in the future. An interesting artifact of our result is that it gives a generic way to match existing lower bounds in functional encryption.

Lattice cryptography uses fixed primes. Kolmogorov’s descriptional complexity of the primes might interest the numerically curious.

We investigate the susceptibility of the Texas Instruments SimpleLink platform microcontrollers to non-invasive physical attacks. We extracted the ROM bootloader of these microcontrollers and then analysed it using static analysis augmented with information obtained through emulation. We demonstrate a voltage fault injection attack targeting the ROM bootloader that allows to enable debug access on a previously locked microcontroller within seconds. Information provided by Texas Instruments reveals that one of our voltage fault injection attacks abuses functionality that is left over from the integrated circuit manufacturing process. The demonstrated physical attack allows an adversary to extract the firmware (i.e. intellectual property) and to bypass secure boot. Additionally, we mount side-channel attacks and differential fault analysis attacks on the hardware AES co-processor. To demonstrate the practical applicability of these attacks we extract the firmware from a Tesla Model 3 key fob. This paper describes a case study covering Texas Instruments SimpleLink microcontrollers. Similar attack techniques can be, and have been, applied to microcontrollers from other manufacturers. The goal of our work is to document our analysis methodology and to ensure that system designers are aware of these vulnerabilities. They will then be able to take these into account during the product design phase. All identified vulnerabilities were responsibly disclosed.

We evaluate eight implementations of provable secure side-channel masking schemes that were published in top-tier academic venues such as Eurocrypt, Asiacrypt, CHES and SAC. Specifically, we evaluate the side-channel attack resistance of eight open-source and first-order side-channel protected AES-128 software implementations on the Cortex-M4 platform. Using a T-test based leakage assessment we demonstrate that all implementations produce first-order leakage with as little as 10,000 traces. Additionally, we demonstrate that all except for two Inner Product Masking based implementations are vulnerable to a straightforward correlation power analysis attack. We provide an assembly level analysis showing potential sources of leakage for two implementations. Some of the studied implementations were provided for benchmarking purposes. We demonstrate several flaws in the benchmarking procedures and question the usefulness of the reported performance numbers in the face of the implementations’ poor side-channel resistance. This work serves as a reminder that practical evaluations cannot be omitted in the context of side-channel analysis.

This work extends the composable secure-emulation of Canetti et al. to dynamic settings. Our work builds on top of dynamic probabilistic I/O automata, a recent framework introduced to model dynamic probabilistic systems. Our extension is an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols etc).

Hardware obfuscation through redundancy addition is a well-known countermeasure against reverse engineering. For FPGA designs, such a technique can be implemented with a small overhead, however, its effectiveness is heavily dependent on the stealthiness of the redundant elements. Hardware opaque predicates can provide adequately stealthy constant values that can be used for obfuscation. However, in this report, we show that such obfuscation schemes can be defeated by ensuring the full controllability of each active look-up table input in a design via iterative bitstream modifications. We present an algorithm that works directly on the bitstream and does not require the possession of a netlist. The feasibility of our approach is verified with the example of an obfuscated SNOW 3G design implemented in a Xilinx 7-series FPGA.

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 investigate the use of the Dilithium post-quantum digital signature scheme on memory-constrained systems. Reference and optimized implementations of Dilithium in the benchmarking framework pqm4 (Cortex-M4) require 50 – 100 KiB of memory, demonstrating the significant challenge to use Dilithium on small IoT platforms. We show that compressing polynomials, using an alternative number theoretic transform, and falling back to the schoolbook method for certain multiplications reduces the memory footprint significantly. This results in the first implementation of Dilithium for which the recommended parameter set requires less than 7 KiB of memory for key and signature generation and less than 3 KiB of memory for signature verification. We also provide benchmark details of a portable implementation in order to estimate the performance impact when using these memory reduction methods.

We build a library SecFloat for secure 2-party computation (2PC) of 32-bit single-precision floating-point operations and math functions. The existing functionalities used in cryptographic works are imprecise and the precise functionalities used in standard libraries are not crypto-friendly, i.e., they use operations that are cheap on CPUs but have exorbitant cost in 2PC. SecFloat bridges this gap with its novel crypto-friendly precise functionalities. Compared to the prior cryptographic libraries, SecFloat is up to six orders of magnitude more precise and up to two orders of magnitude more efficient. Furthermore, against a precise 2PC baseline, SecFloat is three orders of magnitude more efficient. The high precision of SecFloat leads to the first accurate implementation of secure inference. All prior works on secure inference of deep neural networks rely on ad hoc float-to-fixed converters. We evaluate a model where the fixed-point approximations used in privacy-preserving machine learning completely fail and floating-point is necessary. Thus, emphasizing the need for libraries like SecFloat.

Decentralized Finance (DeFi) protocols have triggered a paradigm shift in the world of finance: intermediaries as known in traditional finance risk becoming redundant because DeFi creates an inherent state of “trustlessness”; financial transactions are executed in a deterministic, trustless and censorship resistant manner; the individual is granted verifiability, control and sovereignty. This creates challenges for compliance with jurisdictional Anti-Money Laundering and Combatting the Financing of Terrorism (AML/CFT) regulations, including Know-Your-Customer (KYC) policies, given that no personal information should be shared and stored on public, transparent blockchains. This paper presents a solution concept for where a DeFi protocol is required or finds it desirable to implement KYC policies. zkKYC in DeFi requires no personal identifiable information to be shared with DeFi protocols for the purpose of regulatory transparency. The presented approach extends the zkKYC solution concept (which leverages self-sovereign identity and zero-knowledge proofs) with the introduction of KYC Issuers and Decentralized Oracle Networks (DONs) as key solution components. KYC Issuers verify the identity of an individual, but have no knowledge about their digital asset wallets or DeFi activity. DeFi protocols interact with digital asset wallets, but have no knowledge about the identity of the individual controlling them. If and when deemed necessary, only a designated governance entity is able to reveal the identity of an individual that is under strong suspicion of being a bad actor in a DeFi protocol. The presented solution architecture demonstrates flexibility in being agnostic to blockchain platforms and SSI implementations and extensibility in being forward compatible with on-chain identity and reputation systems. Similar to the original zkKYC solution concept, zkKYC in DeFi breaks the regulatory transparency vs. user privacy trade-off.

We present new semi-honest and malicious secure PSI protocols that outperform all prior works by several times in both communication and running time. For example, our semi-honest protocol for $n=2^{20}$ can be performed in 0.37 seconds compared to the previous best of 2 seconds (Kolesnikov et al., CCS 2016). This can be further reduced to 0.16 seconds with 4 threads, a speedup of $12\times$. Similarly, our protocol sends $187n$ bits compared to $426n$ bits of the next most communication efficient protocol (Rindal et al., Eurocrypt 2021). Additionally, we apply our new techniques to the circuit PSI protocol of Rindal et al. and $6\times$ improvement in running time. These performance results are obtained by two types of improvements. The first is an optimization to the protocol of Rindal et al. to utilize sub-field vector oblivious linear evaluation. This optimization allows our construction to be the first to achieve a communication complexity of $\mathcal{O}(n\lambda + n\log n)$ where $\lambda$ is the statistical security parameter. In particular, the communication overhead of our protocol does not scale with the computational security parameter times $n$. Our second improvement is to the OKVS data structure which our protocol crucially relies on. In particular, our construction improves both the computation and communication efficiency as compared to prior work (Garimella et al., Crypto 2021). These improvements stem from algorithmic changes to the data structure along with new techniques for obtaining both asymptotic and tight concrete bounds on its failure probability. This in turn allows for a highly optimized parameter selection and thereby better performance.

Traditional time-stamping services confirm the existence time of data items by using a time-stamping authority. In order to eliminate trust requirements on this authority, decentralized Blockchain-based Time-Stamping (BTS) services have been proposed. In these services, a hash digest of users’ data is written into a blockchain transaction. The security of such services relies on the security of hash functions used to hash the data, and of the cryptographic algorithms used to build the blockchain. It is well-known that any single cryptographic algorithm has a limited lifespan due to the increasing computational power of attackers. This directly impacts the security of the BTS services from a long-term perspective. However, the topic of long-term security has not been discussed in the existing BTS proposals. In this paper, we propose the first formal definition and security model of a Blockchainbased Long-Term Time-Stamping (BLTTS) scheme. To develop a BLTTS scheme, we first consider an intuitive solution that directly combines the BTS services and a long-term secure blockchain, but we prove that this solution is vulnerable to attacks in the long term. With this insight, we propose the first BLTTS scheme supporting cryptographic algorithm renewal. We show that the security of our scheme over the long term is not limited by the lifespan of any underlying cryptographic algorithm, and we successfully implement the proposed scheme under existing BTS services.

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the $2$-out-of-$n$ threshold ECDSA.

Most blockchain-based cryptocurrencies suffer from a heavily limited transaction throughput, which is a barrier to their growing adoption. Payment channel networks (PCNs) are one of the promising solutions to this problem. PCNs reduce the on-chain load of transactions and increase the throughput by processing many payments off-chain. In fact, any two users connected via a path of payment channels (i.e., joint addresses between the two channel end-points) can perform payments, and the underlying blockchain is used only when there is a dispute between users. Unfortunately, payments in PCNs can only be conducted securely along a path, which prevents the design of many interesting applications. Moreover, the most widely used implementation, the Lightning Network in Bitcoin, suffers from a collateral lock time linear in the path length, it is affected by security issues, and it relies on specific scripting features called Hash Timelock Contracts that hinders the applicability of the underlying protocol in other blockchains. In this work, we present Thora, the first Bitcoin-compatible off-chain protocol that enables the atomic update of arbitrary channels (i.e., not necessarily forming a path). This enables the design of a number of new off-chain applications, such as payments across different PCNs sharing the same blockchain, secure and trustless crowdfunding, and channel rebalancing. Our construction requires no specific scripting functionalities other than digital signatures and timelocks, thereby being applicable to a wider range of blockchains. We formally define security and privacy in the Universal Composability framework and show that our cryptographic protocol is a realization thereof. In our performance evaluation, we show that our construction requires only constant collateral, independently from the number of channels, and has only a moderate off-chain communication as well as computation overhead.

The recent work of Agrawal et al., [Crypto '21] and Goyal et al. [Eurocrypt '22] concurrently introduced the notion of dynamic bounded collusion security for functional encryption (FE) and showed a construction satisfying the notion from identity based encryption (IBE). Agrawal et al., [Crypto '21] further extended it to FE for Turing machines in non-adaptive simulation setting from the sub-exponential learining with errors assumption (LWE). Concurrently, the work of Goyal et al. [Asiacrypt '21] constructed attribute based encryption (ABE) for Turing machines achieving adaptive indistinguishability based security against bounded (static) collusions from IBE, in the random oracle model. In this work, we significantly improve the state of art for dynamic bounded collusion FE and ABE for Turing machines by achieving adaptive simulation style security from a broad class of assumptions, in the standard model. In more detail, we obtain the following results: - We construct an adaptively secure (AD-SIM) FE for Turing machines, supporting dynamic bounded collusion, from sub-exponential LWE. This improves the result of Agrawal et al. which achieved only non-adaptive (NA-SIM) security in the dynamic bounded collusion model. - Towards achieving the above goal, we construct a ciphertext policy FE scheme (CPFE) for circuits of unbounded size and depth, which achieves AD-SIM security in the dynamic bounded collusion model from IBE and laconic oblivious transfer (LOT). Both IBE and LOT can be instantiated from a large number of mild assumptions such as the computational Diffie-Hellman assumption, the factoring assumption, and polynomial LWE. - We construct an AD-SIM secure FE for Turing machines, supporting dynamic bounded collusions, from LOT, ABE for NC1 (or NC) and private information retrieval (PIR) schemes which satisfy certain properties. This significantly expands the class of assumptions on which AD-SIM secure FE for Turing machines can be based. In particular, it leads to new constructions of FE for Turing machines including one based on polynomial LWE and one based on the combination of the bilinear decisional Diffie-Hellman assumption and the decisional Diffie-Hellman assumption on some specific groups. In contrast the only prior construction by Agrawal et al. achieved only NASIM security and relied on sub-exponential LWE. To achieve the above result, we define the notion of CPFE for read only RAM programs and succinct FE for LOT, which may be of independent interest. - We also construct an ABE scheme for Turing machines which achieves AD-IND security in the standard model supporting dynamic bounded collusions. Our scheme is based on IBE and LOT. Previously, the only known candidate that achieved AD-IND security from IBE by Goyal et al. relied on the random oracle model.

The SPDZ protocol for multi-party computation relies on a correlated randomness setup consisting of authenticated, multiplication triples. A recent line of work by Boyle et al. (Crypto 2019, Crypto 2020) has investigated the possibility of producing this correlated randomness in a silent preprocessing phase, which involves a “small” setup protocol with less communication than the total size of the triples being produced. These works do this using a tool called a pseudorandom correlation generator (PCG), which allows a large batch of correlated randomness to be compressed into a set of smaller, correlated seeds. However, existing methods for compressing SPDZ triples only apply to the 2-party setting. In this work, we construct a PCG for producing SPDZ triples over large prime fields in the multi-party setting. The security of our PCG is based on the ring-LPN assumption over fields, similar to the work of Boyle et al. (Crypto 2020) in the 2-party setting. We also present a corresponding, actively secure setup protocol, which can be used to generate the PCG seeds and instantiate SPDZ with a silent preprocessing phase. As a building block, which may be of independent interest, we construct a new type of 3-party distributed point function supporting outputs over arbitrary groups (including large prime order), as well as an efficient protocol for setting up our DPF keys with active security.

We show that it is possible to perform $n$ independent copies of $1$-out-of-$2$ oblivious transfer in two messages, where the communication complexity of the receiver and sender (each) is $n(1+o(1))$ for sufficiently large $n$. Note that this matches the information-theoretic lower bound. Prior to this work, this was only achievable by using the heavy machinery of rate-$1$ fully homomorphic encryption (Rate-$1$ FHE, Brakerski et al., TCC 2019). To achieve rate-$1$ both on the receiver's and sender's end, we use the LPN assumption, with slightly sub-constant noise rate $1/m^{\epsilon}$ for any $\epsilon>0$ together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive ``bootstrapping'' operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE). For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to ``emulate'' the binary group $\mathbb{Z}_2$ (or any other small-order group) inside a prime-order group $\mathbb{Z}_p$ in a function-private manner. That is, $\mathbb{Z}_2$ operations are mapped to $\mathbb{Z}_p$ operations such that the outcome of the latter do not reveal additional information beyond the $\mathbb{Z}_2$ outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.

We show a compiler that allows to prove the correct execution of RAM programs using any zero-knowledge system for circuit satisfiability. At the core of this work is an arithmetic circuit which verifies the consistency of a list of memory access tuples in zero-knowledge. Using such a circuit, we obtain the first constant-round and concretely efficient zero-knowledge proof protocol for RAM programs using any stateless zero-knowledge proof system for Boolean or arithmetic circuits. Both the communication complexity and the prover and verifier run times asymptotically scale linearly in the size of the memory and the run time of the RAM program; we demonstrate concrete efficiency with performance results of our C++ implementation. We concretely instantiate our construction with an efficient MPC-in-the-Head proof system, Limbo (ACM CCS 2021). The C++ implementation of our access protocol extends that of Limbo and provides interactive proofs with 40 bits of statistical security with an amortized cost of 0.42ms of prover time and 2.8KB of communication per memory access, independently of the size of the memory; with multi-threading, this cost is reduced to 0.12ms and 1.8KB respectively. This performance of our public-coin protocol approaches that of private-coin protocol BubbleRAM (ACM CCS 2020, 0.15ms and 1.5KB per access).

We study communication complexity in computational settings where bad inputs may exist, but they should be hard to find for any computationally bounded adversary. We define a model where there is a source of public randomness but the inputs are chosen by a computationally bounded adversarial participant after seeing the public randomness. We show that breaking the known communication lower bounds of the private coins model in this setting is closely connected to known cryptographic assumptions. We consider the simultaneous messages model and the interactive communication model and show that for any non trivial predicate (with no redundant rows, such as equality): 1. Breaking the $ \Omega(\sqrt n) $ bound in the simultaneous message case or the $ \Omega(\log n) $ bound in the interactive communication case, implies the existence of distributional collision-resistant hash functions (dCRH). This is shown using techniques from Babai and Kimmel (CCC '97). Note that with a CRH the lower bounds can be broken. 2. There are no protocols of constant communication in this preset randomness settings (unlike the plain public randomness model). The other model we study is that of a stateful ``free talk", where participants can communicate freely before the inputs are chosen and may maintain a state, and the communication complexity is measured only afterwards. We show that efficient protocols for equality in this model imply secret key-agreement protocols in a constructive manner. On the other hand, secret key-agreement protocols imply optimal (in terms of error) protocols for equality.

Updatable Encryption (UE) and Proxy Re-encryption (PRE) allow re-encrypting a ciphertext from one key to another in the symmetric-key and public-key settings, respectively, without decryption. A longstanding open question has been the following: do unidirectional UE and PRE schemes (where ciphertext re-encryption is permitted in only one direction) necessarily require stronger/more structured assumptions as compared to their bidirectional counterparts? Known constructions of UE and PRE seem to exemplify this "gap" -- while bidirectional schemes can be realized as relatively simple extensions of public-key encryption from standard assumptions such as DDH or LWE, unidirectional schemes typically rely on stronger assumptions such as FHE or indistinguishability obfuscation (iO), or highly structured cryptographic tools such as bilinear maps or lattice trapdoors. In this paper, we bridge this gap by showing the first feasibility results for realizing unidirectional UE and PRE from a new generic primitive that we call Key and Plaintext Homomorphic Encryption (KPHE) -- a public-key encryption scheme that supports additive homomorphisms on its plaintext and key spaces simultaneously. We show that KPHE can be instantiated from DDH. This yields the first constructions of unidirectional UE and PRE from DDH. Our constructions achieve the strongest notions of post-compromise security in the standard model. Our UE schemes also achieve "backwards-leak directionality" of key updates (a notion we discuss is equivalent, from a security perspective, to that of unidirectionality with no-key updates). Our results establish (somewhat surprisingly) that unidirectional UE and PRE schemes satisfying such strong security notions do not, in fact, require stronger/more structured cryptographic assumptions as compared to bidirectional schemes.

The Open Vote Network is a self-tallying decentralized e-voting protocol suitable for boardroom elections. Currently, it has two Ethereum-based implementations: the first, by McCorry et al., has a scalability issue since all the computations are performed on-chain. The second implementation, by Seifelnasr et al., solves this issue partially by assigning a part of the heavy computations to an off-chain untrusted administrator in a verifiable manner. As a side effect, this second implementation became not dispute-free; there is a need for a tally dispute phase where an observer interrupts the protocol when the administrator cheats, i.e., announces a wrong tally result. In this work, we propose a new smart contract design to tackle the problems in the previous implementations by (i) preforming all the heavy computations off-chain hence achieving higher scalability, and (ii) utilizing zero-knowledge Succinct Non-interactive Argument of Knowledge (zk-SNARK) to verify the correctness of the off-chain computations, hence maintaining the dispute-free property. To demonstrate the effectiveness of our design, we develop prototype implementations on Ethereum and conduct multiple experiments for different implementation options that show a trade-off between the zk-SNARK proof generation time and the smart contract gas cost, including an implementation in which the smart contract consumes a constant amount of gas independent of the number of voters.

We study the power of preprocessing adversaries in finding bounded-length collisions in the widely used Merkle-Damgård (MD) hashing in the random oracle model. Specifically, we consider adversaries with arbitrary $S$-bit advice about the random oracle and can make at most $T$ queries to it. Our goal is to characterize the advantage of such adversaries in finding a $B$-block collision in an MD hash function constructed using the random oracle with range size $N$ as the compression function (given a random salt). The answer to this question is completely understood for very large values of $B$ (essentially $\Omega(T)$) as well as for $B=1,2$. For $B\approx T$, Coretti et al.~(EUROCRYPT '18) gave matching upper and lower bounds of $\tilde\Theta(ST^2/N)$. Akshima et al.~(CRYPTO '20) observed that the attack of Coretti et al.\ could be adapted to work for any value of $B>1$, giving an attack with advantage $\tilde\Omega(STB/N + T^2/N)$. Unfortunately, they could only prove that this attack is optimal for $B=2$. Their proof involves a compression argument with exhaustive case analysis and, as they claim, a naive attempt to generalize their bound to larger values of B (even for $B=3$) would lead to an explosion in the number of cases needed to be analyzed, making it unmanageable. With the lack of a more general upper bound, they formulated the STB conjecture, stating that the best-possible advantage is $\tilde O(STB/N + T^2/N)$ for any $B>1$. In this work, we confirm the STB conjecture in many new parameter settings. For instance, in one result, we show that the conjecture holds for all constant values of $B$, significantly extending the result of Akshima et al. Further, using combinatorial properties of graphs, we are able to confirm the conjecture even for super constant values of $B$, as long as some restriction is made on $S$. For instance, we confirm the conjecture for all $B \le T^{1/4}$ as long as $S \le T^{1/8}$. Technically, we develop structural characterizations for bounded-length collisions in MD hashing that allow us to give a compression argument in which the number of cases needed to be handled does not explode.

We present $\textit{Colordag}$, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than $1/2$ of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an $\varepsilon$-Nash equilibrium as long as all miners have less than $1/2$ of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call $\varepsilon\textit{-sure Nash equilibrium}$ and does not suffer from this problem. Because it is an $\varepsilon$-sure Nash equilibrium, Colordag is an $\varepsilon$-Nash equilibrium and with probability $1-\varepsilon$ is a best response.

Broadcast Encryption is a fundamental cryptographic primitive, that gives the ability to send a secure message to any chosen target set among registered users. In this work, we investigate broadcast encryption with anonymous revocation, in which ciphertexts do not reveal any information on which users have been revoked. We provide a scheme whose ciphertext size grows linearly with the number of revoked users. Moreover, our system also achieves traceability in the black-box confirmation model. Technically, our contribution is threefold. First, we develop a generic transformation of linear functional encryption toward trace-and-revoke systems for 1-bit message space. It is inspired from the transformation by Agrawal {et al} (CCS'17) with the novelty of achieving anonymity. Our second contribution is to instantiate the underlying linear functional encryptions from standard assumptions. We propose a $\mathsf{DDH}$-based construction which does no longer require discrete logarithm evaluation during the decryption and thus significantly improves the performance compared to the $\mathsf{DDH}$-based construction of Agrawal {et al}. In the LWE-based setting, we tried to instantiate our construction by relying on the scheme from Wang {et al} (PKC'19) only to find an attack on this scheme. Our third contribution is to extend the 1-bit encryption from the generic transformation to $n$-bit encryption. By introducing matrix multiplication functional encryption, which essentially performs a fixed number of parallel calls on functional encryptions with the same randomness, we can prove the security of the final scheme with a tight reduction that does not depend on $n$, in contrast to employing the hybrid argument.

We consider finding as many faults as possible on the target device in the laser fault injection security evaluation. Since the search space is large, we require efficient search methods. Recently, an evolutionary approach using a memetic algorithm was proposed and shown to find more interesting parameter combinations than random search, which is commonly used. Unfortunately, once a variation on the bench or target is introduced, the process must be repeated to find suitable parameter combinations anew. To negate the effect of variation, we propose a novel method combining a memetic algorithm with a machine learning approach called a decision tree. Our approach improves the memetic algorithm by using prior knowledge of the target introduced in the initial phase of the memetic algorithm. In our experiments, the decision tree rules enhance the performance of the memetic algorithm by finding more interesting faults in different samples of the same target. Our approach shows more than two orders of magnitude better performance than random search and up to 60% better performance than previous state-of-the-art results with a memetic algorithm. Another advantage of our approach is human-readable rules, allowing the first insights into the explainability of target characterization for laser fault injection.