Diene, Thabet and Yusuf recently proposed a new multivariate signature scheme whose public key is a set of multivariate cubic polynomials over a finite field. This paper studies its security.

Contact discovery allows users of mobile messengers to conveniently connect with people in their address book. In this work, we demonstrate that severe privacy issues exist in currently deployed contact discovery methods. Our study of three popular mobile messengers (WhatsApp, Signal, and Telegram) shows that, contrary to expectations, large-scale crawling attacks are (still) possible. Using an accurate database of mobile phone number prefixes and very few resources, we have queried 10% of US mobile phone numbers for WhatsApp and 100% for Signal. For Telegram we find that its API exposes a wide range of sensitive information, even about numbers not registered with the service. We present interesting (cross-messenger) usage statistics, which also reveal that very few users change the default privacy settings. Regarding mitigations, we propose novel techniques to significantly limit the feasibility of our crawling attacks, especially a new incremental contact discovery scheme that strictly improves over Signal's current approach. Furthermore, we show that currently deployed hashing-based contact discovery protocols are severely broken by comparing three methods for efficient hash reversal of mobile phone numbers. For this, we also propose a significantly improved rainbow table construction for non-uniformly distributed inputs that is of independent interest.

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are brought about by relatively high approximation errors and the complexity of dealing with them. We present a reduced-error CKKS variant that removes the approximation errors due to the Learning With Errors (LWE) noise in the encryption and key switching operations. We propose and implement its Residue Number System (RNS) instantiation that has a lower error than the original CKKS scheme implementation based on multiprecision integer arithmetic. While formulating the RNS instantiation, we also develop an intermediate RNS variant that has a smaller approximation error than the prior RNS variant of CKKS. The high-level idea of our main RNS-related improvements is to remove the approximate scaling error using a novel procedure that computes level-specific scaling factors. The rescaling operations and scaling factor adjustments in our implementation are done automatically. We implement both RNS variants in PALISADE and compare their approximation error and efficiency to the prior RNS variant. Our results for uniform ternary secret key distribution, which is the most efficient setting included in the community homomorphic encryption security standard, show that the reduced-error CKKS RNS implementation typically has an approximation error that is 6 to 9 bits smaller for computations with multiplications than the prior RNS variant. The results for the sparse secret setting, which was used for the original CKKS scheme, imply that our reduced-error CKKS RNS implementation has an approximation error up to 12 bits smaller than the prior RNS variant.

Blockchain is the distributed system allowing multiple parties to host a service. Nakamoto Consensus, also named Proof of Work (PoW), is widely used in Bitcoin and other blockchain systems. PoW is an important consensus algorithm. It solves the Byzantine Generals problem in an open network. It also protects the blockchain security from longest chain attack. World widely virtual currency mining was commonly regarded as over energy consuming. How to make use of the computation capacity provided by mining, is one of the most important problems to solve in blockchain. We extend Proof of Work to be useful and economic. And discover a simple method to generate the proof of storing useful data with PoW. In a blockchain based distributed file storage system, any storage resource owner could freely join as a service provider. It requires the service provider to show the proof of honestly keeping the data content, because the malicious provers may use other's content to generate the proof in order to reduce their resource cost. This is out-sourcing attack. Furtherly, we proposed a novel technique to combine data replica process with Proof of Work's contributing to blockchain security.

Multivariate cryptography studies applications of endomorphisms of K[x_1, x_2, …, x_n] where K is a finite commutative ring given in the standard form x_i →f_i(x_1, x_2,…, x_n), i=1, 2,…, n. The importance of this direction for the constructions of multivariate digital signatures systems is well known. Close attention of researchers directed towards studies of perspectives of quadratic rainbow oil and vinegar system and LUOV presented for NIST postquantum certification. Various cryptanalytic studies of these signature systems were completed. Recently some options to modify theses algorithms as well as all multivariate signature systems which alow to avoid already known attacks were suggested. One of the modifications is to use protocol of noncommutative multivariate cryptography based on platform of endomorphisms of degree 2 and 3. The secure protocol allows safe transfer of quadratic multivariate map from one correspondent to another. So the quadratic map developed for digital signature scheme can be used in a private mode. This scheme requires periodic usage of the protocol with the change of generators and the modification of quadratic multivariate maps. Other modification suggests combination of multivariate map of unbounded degree of size O(n) and density of each f_i of size O(1). The resulting map F in its standard form is given as the public rule. We suggest the usage of the last algorithm on the secure El Gamal mode. It means that correspondents use protocols of Noncommutative Cryptography with two multivariate platforms to elaborate safely a collision endomorphism G: x_i → g_i of linear unbounded degree such that densities of each gi are of size O(n^2). One of correspondents generates mentioned above F and sends F+G to his/her partner. The security of the protocol and entire digital signature scheme rests on the complexity of NP hard word problem of finding decomposition of given endomorphism G of K[x_1,x_2,…,x_n ] into composition of given generators 1^G, 2^G, …t^G, t>1 of the semigroup of End(K[x_1 ,x_2 ,…,x_n]). Differently from the usage of quadratic map on El Gamal mode the case of unbounded degree allows single usage of the protocol because the task to approximate F via interception of hashed messages and corresponding signatures is unfeasible in this case.

Electromagnetic Fault Injection (EMFI) is considered as an effective fault injection technique for the purpose of conducting physical attacks against integrated circuits. It enables an adversary to inject errors on a circuit to gain knowledge of sensitive information or to bypass security features. The aim of this paper is to highlight the design and validation of SiliconToaster, which is a cheap and programmable platform for EM pulse injection. It has been designed using low-cost and accessible components that can be easily found. In addition, it can inject faults with a programmable voltage up to 1.2kV without the need to an external power supply as it is powered by the USB. The second part of the paper invests the SiliconToaster in order to bypass the firmware security protections of an IoT chip. Two security configurations were bypassed sequentially in a non-invasive way (without chip decapsulation).

Verifiable mix nets, and specifically proofs of (correct) shuffle, are a fundamental building block in numerous applications: these zero-knowledge proofs allow the prover to produce a public transcript which can be perused by the verifier to confirm the purported shuffle. They are particularly vital to verifiable electronic voting, where they underpin almost all voting schemes with non-trivial tallying methods. These complicated pieces of cryptography are a prime location for critical errors which might allow undetected modification of the outcome. The best solution to preventing these errors is to machine-check the cryptographic properties of the design and implementation of the mix net. Particularly crucial for the integrity of the outcome is the soundness of the design and implementation of the verifier (software). Unfortunately, several different encryption schemes are used in many different slight variations which makes t infeasible to machine-check every single case individually. However, a particular optimized variant of the Terelius-Wikstrom mix net is, and has been, widely deployed in elections including national elections in Norway, Estonia and Switzerland, albeit with many slight variations and several different encryption schemes. In this work, we develop the logical theory and formal methods tools to machine-check the design and implementation of all these variants of Terelius-Wikstrom mix nets, for all the different encryption schemes used; resulting in provably correct mix nets for all these different variations. We do this carefully to ensure that we can extract a formally verified implementation of the verifier (software) which is compatible with existing deployed implementations of the Terelius-Wikstrom mix net. This gives us provably correct implementations of the verifiers for more than half of the national elections which have used verifiable mix nets. Our implementation of a proof of correct shuffle is the first to be machine-checked to be cryptographically correct and able to verify proof transcripts from national elections. We demonstrate the practicality of our implementation by verifying transcripts produced by the Verificatum mix net system and the CHVote evoting system from Switzerland.

Almost perfect nonlinear functions possess the optimal resistance to the differential cryptanalysis and are widely studied. Most known APN functions are obtained as functions over finite fields $\mathbb{F}_{2^n}$ and very little is known about combinatorial constructions in $\mathbb{F}_2^n$. In this work we proposed two approaches for obtaining quadratic APN functions in $\mathbb{F}_2^n$. The first approach exploits a secondary construction idea, it considers how to obtain quadratic APN function in $n+1$ variables from a given quadratic APN function in $n$ variables using special restrictions on new terms. The second approach is searching quadratic APN functions that have matrix form partially filled with standard basis vectors in a cyclic manner. This approach allowed us to find a new APN function in 7 variables. Also, we conjectured that a quadratic part of an arbitrary APN function has a low differential uniformity. This conjecture allowed us to introduce a new subclass of APN functions, so-called stacked APN functions. We found cubic examples of such functions for dimensions up to 6.

Mixed Integer Linear Programming (MILP) is a powerful tool that helps to automate several cryptanalysis techniques for symmetric key primitives. $\textsf{Gurobi}$ is one of the most popular solvers used by researchers to obtain useful results from the MILP models corresponding to these cryptanalysis techniques. In this report, we provide a cautionary note on the use of $\textsf{Gurobi}$ in the context of bit-based division property integral attacks. In particular, we report four different examples in which $\textsf{Gurobi}$ gives contradictory results when solving the same MILP model by just changing the number of used threads or reordering some constraints.

An efficient scalar multiplication algorithm is a crucial component of elliptic curve cryptosystems. We propose a scalar multiplication algorithm based on scalar recodings that is regular in nature. Our scalar multiplication algorithm is made from two scalar recoding algorithms called $\Recode$ and $\Align$. $\Recode$ is the generalization of the signed non-zero bit recoding algorithm given by Hedabou, Pinel and Bénéteau in 2005. It recodes the $k$-ary representation of the given scalar into a signed non-zero form by means of a small lookup table. On the other hand, $\Align$ is the generalized $k$-ary version of the sign-aligned columns recoding algorithm given by Faz-Hernández, Longa and Sánchez in 2014. It recodes the $k$-ary representation of a scalar in such a way that the sign of each of its digits agrees with a given $\lbrace 1,-1 \rbrace$-valued sequence. When analyzing the choice of $k \in \lbrace 2,3 \rbrace$, we find some theoretical evidence that $k=3$ may offer better performance in certain scenarios.

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs. In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments. Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round $n$-out-of-$n$ distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.

At a combined computational expense of about $6{\ell}$ field operations, Vélu's formulas are used to construct and evaluate degree-$\ell$ isogenies in the vast majority of isogeny-based cryptographic schemes. By adapting to Vélu's formulas a baby-step giant-step approach, Bernstein, De Feo, Leroux, and Smith presented a procedure that can computes isogeny operations at a reduced cost of just $\tilde{O}(\sqrt{\ell})$ field operations. In this paper, we present a concrete computational analysis of these novel procedure along with several algorithmic tricks that helped us to further decrease its computational cost. We also report an optimized Python3-code implementation of several instantiations of two isogeny-based key-exchange protocols, namely, CSIDH and B-SIDH. Our software library uses a combination of the modified Vélu's formulas and an adaptation of the optimal strategies commonly used in the SIDH/SIKE protocols to produce significant speedups. Compared to a traditional Vélu constant-time implementation of CSIDH, our experimental results report a saving of 5.357\%, 13.68\% and 25.938\% base field operations for CSIDH-512, CSIDH-1024, and CSIDH-1792, respectively. Additionally, we present the first optimized implementation of B-SIDH ever reported in the open literature.

This paper introduces a new approach to computing isogenies called "radical isogenies" and a corresponding method to compute chains of $N$-isogenies that is very efficient for small $N$. The method is fully deterministic and completely avoids generating $N$-torsion points. It is based on explicit formulae for the coordinates of an $N$-torsion point $P'$ on the codomain of a cyclic $N$-isogeny $\varphi : E \to E'$, such that composing $\varphi$ with $E' \to E' / \langle P' \rangle$ yields a cyclic $N^2$-isogeny. These formulae are simple algebraic expressions in the coefficients of $E$, the coordinates of a generator $P$ of $\ker \varphi$, and an $N$th root $\sqrt[N]{\rho}$, where the radicand $\rho$ itself is given by an easily computable algebraic expression in the coefficients of $E$ and the coordinates of $P$. The formulae can be iterated and are particularly useful when computing chains of $N$-isogenies over a finite field $\mathbb{F}_q$ with $\gcd(q-1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the state-of-the-art, our method results in an order of magnitude speed-up for $N \leq 13$; for larger $N$, the advantage disappears due to the increasing complexity of the formulae. When applied to CSIDH, we obtain a speed-up of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF-512 parameters.

A $\mathit{multi\text{-}recipient}$ key encapsulation mechanism, or $\mathsf{mKEM}$, provides a scalable solution to securely communicating to a large group, and offers savings in both bandwidth and computational cost compared to the trivial solution of communicating with each member individually. All prior works on $\mathsf{mKEM}$ are only limited to classical assumptions and, although some generic constructions are known, they all require specific properties that are not shared by most post-quantum schemes. In this work, we first provide a simple and efficient generic construction of $\mathsf{mKEM}$ that can be instantiated from versatile assumptions, including post-quantum ones. We then study these $\mathsf{mKEM}$ instantiations at a practical level using 8 post-quantum $\mathsf{mKEM}$s (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our $\mathsf{mKEM}$ offers savings of at least one order of magnitude in the bandwidth, and make encryption time shorter by a factor ranging from 1.92 to 35. Additionally, we show that by combining $\mathsf{mKEM}$ with the TreeKEM protocol used by MLS $-$ an IETF draft for secure group messaging $-$ we obtain significant bandwidth savings.

We prove a tight lower bound on the number of group operations required for batch verification by any generic-group accumulator that stores a less-than-trivial amount of information. Specifically, we show that $\Omega(t \cdot (\lambda / \log \lambda))$ group operations are required for the batch verification of any subset of $t \geq 1$ elements, where $\lambda \in \mathbb{N}$ is the security parameter, thus ruling out non-trivial batch verification in the standard non-interactive manner. Our lower bound applies already to the most basic form of accumulators (i.e., static accumulators that support membership proofs), and holds both for known-order (and even multilinear) groups and for unknown-order groups, where it matches the asymptotic performance of the known bilinear and RSA accumulators, respectively. In addition, it complements the techniques underlying the generic-group accumulators of Boneh, B{ü}nz and Fisch (CRYPTO '19) and Thakur (ePrint '19) by justifying their application of the Fiat-Shamir heuristic for transforming their interactive batch-verification protocols into non-interactive procedures. Moreover, motivated by a fundamental challenge introduced by Aggarwal and Maurer (EUROCRYPT '09), we propose an extension of the generic-group model that enables us to capture a bounded amount of arbitrary non-generic information (e.g., least-significant bits or Jacobi symbols that are hard to compute generically but are easy to compute non-generically). We prove our lower bound within this extended model, which may be of independent interest for strengthening the implications of impossibility results in idealized models.

Private Set Intersection Cardinality (PSI-CA) allows two parties, each holding a set of items, to learn the size of the intersection of those sets without revealing any additional information. To the best of our knowledge, this work presents the first protocol that allows one of the parties to delegate PSI-CA computation to untrusted servers. At the heart of our delegated PSI-CA protocol is a new oblivious distributed key PRF (Odk-PRF) abstraction, which may be of independent interest. We explore in detail how to use our delegated PSI-CA protocol to perform privacy-preserving contact tracing. It has been estimated that a significant percentage of a given population would need to use a contact tracing app to stop a disease’s spread. Prior privacy-preserving contact tracing systems, however, impose heavy bandwidth or computational demands on client devices. These demands present an economic disincentive to participate for end users who may be billed per MB by their mobile data plan or for users who want to save battery life. We propose Catalic (ContAct TrAcing for LIghtweight Clients), a new contact tracing system that minimizes bandwidth cost and computation workload on client devices. By applying our new delegated PSI-CA protocol, Catalic shifts most of the client-side computation of contact tracing to untrusted servers, and potentially saves each user hundreds of megabytes of mobile data per day while preserving privacy.

High-assurance cryptography leverages methods from program verification and cryptography engineering to deliver efficient cryptographic software with machine-checked proofs of memory safety, functional correctness, provable security, and absence of timing leaks. Traditionally, these guarantees are established under a sequential execution semantics. However, this semantics is not aligned with the behavior of modern processors that make use of speculative execution to improve performance. This mismatch, combined with the high-profile Spectre-style attacks that exploit speculative execution, naturally casts doubts on the robustness of high-assurance cryptography guarantees. In this paper, we dispel these doubts by showing that the benefits of high-assurance cryptography extend to speculative execution, costing only a modest performance overhead. We build atop the Jasmin verification framework an end-to-end approach for proving properties of cryptographic software under speculative execution, and validate our approach experimentally with efficient, functionally correct assembly implementations of ChaCha20 and Poly1305, which are secure against both traditional timing and speculative execution attacks.

Higher-order masking countermeasures provide strong provable security against side-channel attacks at the cost of incurring significant overheads, which largely hinders its applicability. Previous works towards remedying cost mostly concentrated on ``local'' calculations, i.e., optimizing the cost of computation units such as a single AND gate or a field multiplication. This paper explores a complementary ``global'' approach, i.e., considering multiple operations in the masked domain as a batch and reducing randomness and computational cost via amortization. In particular, we focus on the amortization of $\ell$ parallel field multiplications for appropriate integer $\ell > 1$, and design a kit named {\it packed multiplication} for implementing such a batch. For $\ell+d\leq2^m$, when $\ell$ parallel multiplications over $\mathbb{F}_{2^{m}}$ with $d$-th order probing security are implemented, packed multiplication consumes $d^2+2\ell d + \ell$ bilinear multiplications and $2d^2 + d(d+1)/2$ random field variables, outperforming the state-of-the-art results with $O(\ell d^2)$ multiplications and $\ell \left \lfloor d^2/4\right \rfloor + \ell d$ randomness. To prove $d$-probing security for packed multiplications, we introduce some weaker security notions for multiple-inputs-multiple-outputs gadgets and use them as intermediate steps, which may be of independent interest. As parallel field multiplications exist almost everywhere in symmetric cryptography, lifting optimizations from ``local'' to ``global'' substantially enlarges the space of improvements. To demonstrate, we showcase the method on the AES Subbytes step, GCM and TET (a popular disk encryption). Notably, when $d=8$, our implementation of AES Subbytes in ARM Cortex M architecture achieves a gain of up to $33\%$ in total speeds and saves up to $68\%$ random bits than the state-of-the-art bitsliced implementation reported at ASIACRYPT~2018.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computers attacks like Shor and Grover algorithms. In this paper, we propose a method for designing post-quantum provable IND-CPA/IND-CCA2 public key cryptosystems based on polynomials over a non-commutative algebraic extension ring. The key ideas of our proposal is that (a) for a given non-commutative ring of rank-3 tensors, we can define polynomials and take them as the underlying work structure (b) we replace all numeric field arithmetic with GF(2^8) field operations. By doing so, it is easy to implement R-propped Diffie-Helman-like key exchange protocol and consequently ElGamal-like cryptosystems. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span or Roman’kov. The protocols have been proved to be semantically secure. Finally, we present numerical examples of the proposed R-Propped protocols.

First implemented in Bitcoin, Nakamoto Consensus (NC) is the most influential consensus protocol in cryptocurrencies despite all the alternative protocols designed afterward. Nevertheless, NC is trapped by a security-performance tradeoff. While existing efforts mostly attempt to break this tradeoff via abandoning or adjusting NC's backbone protocol, we alternatively forward the relevance of the network layer. We identify and experimentally prove that the crux resides with the prolonged block propagation latency caused by not-yet-propagated transactions. We thus present a two-step mechanism to confirm only fully-propagated transactions, and therefore remove the limits upon NC's performance imposed by its security demands, realizing NC's untapped potential. Implementing this two-step mechanism, we propose NC-Max, whose (1) security is analyzed, proving that it provides stronger resistance than NC against transaction withholding attacks, and (2) performance is evaluated, showing that it exhausts the full throughput supported by the network, and shortens the transaction confirmation latency by 3.0 to 6.6 times compared to NC without compromising security. NC-Max is implemented in Nervos CKB, a public permissionless blockchain.

Reducing the rounds of interaction in secure multiparty computation (MPC) protocols has been the topic of study of many works. One popular approach to reduce rounds is to construct *round compression compilers*. A round compression compiler is one that takes a highly interactive protocol and transforms it into a protocol with far fewer rounds. The design of round compression compilers has traditionally focused on preserving the security properties of the underlying protocol and in particular, not much attention has been given towards preserving their computational and communication efficiency. Indeed, the recent round compression compilers that yield round-optimal MPC protocols incur large computational and communication overhead. In this work, we initiate the study of *efficiency-preserving* round compression compilers, i.e. compilers that translate the efficiency benefits of the underlying highly interactive protocols to the fewer round setting. Focusing on the honest majority setting (with near-optimal corruption threshold $\frac{1}{2} - \varepsilon$, for any $\varepsilon > 0$), we devise a new compiler that yields two round (i.e., round optimal) semi-honest MPC with similar communication efficiency as the underlying (arbitrary round) protocol. By applying our compiler on the most efficient known MPC protocols, we obtain a two-round semi-honest protocol based on one-way functions, with total communication (and per-party computation) cost $\widetilde{O}(s+n^4)$ -- a significant improvement over prior two-round protocols with cost $\widetilde{O}(n^\tau s+n^{\tau+1}d)$, where $\tau\geq 2$, $s$ is the size of the circuit computing the function and $d$ the corresponding depth. Our result can also be extended to handle malicious adversaries, either using stronger assumptions in the public key infrastructure (PKI) model, or in the plain model using an extra round. An artifact of our approach is that the resultant protocol is ``unbalanced'' in the amount of computation performed by different parties. We give evidence that this is *necessary* in our setting. Our impossibility result makes novel use of the ``MPC-in-the-head" paradigm which has typically been used to demonstrate feasibility results.

We propose the first tightly secure and unbounded hierarchical identity-based encryption (HIBE) scheme based on standard assumptions. Our main technical contribution is a novel proof strategy that allows us to tightly randomize user secret keys for identities with arbitrary hierarchy depths using low entropy hidden in a small and hierarchy-independent master public key. The notion of unbounded HIBE is proposed by Lewko and Waters (Eurocrypt 2011). In contrast to most HIBE schemes, an unbounded scheme does not require any maximum depth to be specified in the setup phase, and user secret keys or ciphertexts can be generated for identities of arbitrary depths with hierarchy-independent system parameters. While all the previous unbounded HIBE schemes have security loss that grows at least linearly in the number of user secret key queries, the security loss of our scheme is only dependent on the security parameter, even in the multi-challenge setting, where an adversary can ask for multiple challenge ciphertexts. We prove the adaptive security of our scheme based on the Matrix Decisional Diffie-Hellman assumption in prime-order pairing groups, which generalizes a family of standard Diffie-Hellman assumptions such as k-Linear.

Bitcoin has introduced an open and decentralized consensus mechanism which in combination with an append-only ledger allows building so-called blockchain systems, often instantiated as permissionless cryptocurrencies. Bitcoin is surprisingly successful and its market capitalization has reached about 168 billion USD as of July 2020. Due to its high economic value, it became a lucrative target and the growing community has discovered various attacks, proposed promising improvements, and introduced contingency plans for handling catastrophic failures. Nonetheless, existing analysis and contingency plans are not formalized and are tailored only to handle a small specific subset of diverse attacks, and as such, they cannot resist unexpected emergency cases and it is hard to reason about their effectiveness and impact on the system. In this work, we provide a formalized framework to help evaluate a variety of attacks and their mitigations. The framework is based upon the universal composability (UC) framework to describe the attacker's power and the system's security goals. We propose the system in the context of Bitcoin and to the best of our knowledge, no similar work has been proposed previously. Besides, we demonstrate and evaluate our model with different case studies from the real world. Finally, we signal remaining challenges for the contingency plans and their formalization.

In EUROCRYPT '96, Aiello and Venkatesan proposed two candidates for $ 2n $-bit to $ 2n $-bit pseudorandom functions (PRFs), called Benes and modified Benes (or mBenes), based on $ n $-bit to $ n $-bit PRFs. While Benes is known to be secure up to $ 2^n $ queries (Patarin, AFRICACRYPT '08), the security of mBenes has only been proved up to $ 2^{n(1-\epsilon)} $ queries for all $ \epsilon > 0 $ by Patarin and Montreuil in ICISC '05. In this work, we show that the composition of a $ 2n $-bit hash function with mBenes is a secure variable input length (VIL) PRF up to $ 2^{n-2} $ queries (given appropriate hash function bounds). We extend our analysis with block ciphers as the underlying primitive and obtain two optimally secure VIL PRFs using block ciphers. The first of these candidates requires $ 6 $ calls to the block cipher. The second candidate requires just $ 4 $ calls to the block cipher, but here the proof is based on Patarin's mirror theory. Further, we instantiate the hash function with a PMAC+/LightMAC+ like hash, to get six candidates for deterministic message authentication codes with optimal security.

We present the first deep learning-based side-channel attack on AES-128 using far field electromagnetic emissions as a side channel. Our neural networks are trained on traces captured from five different Bluetooth devices at five different distances to target and tested on four other Bluetooth devices. We can recover the key from less than 10K traces captured in an office environment at 15 m distance to target even if the measurement for each encryption is taken only once. Previous template attacks required multiple repetitions of the same encryption. For the case of 1K repetitions, we need less than 400 traces on average at 15 m distance to target. This improves the template attack presented at CHES'2020 which requires 5K traces and key enumeration up to $2^{23}$.

This article gives a rigorous mathematical treatment of generalized and closed loop invariants (CLI) which extend the standard notion of (nonlinear) invariants used in the cryptanalysis of block ciphers. Employing the cycle structure of bijective S-box components, we precisely characterize the cardinality of both generalized and CLIs. We demonstrate that for many S-boxes used in practice quadratic invariants (especially useful for mounting practical attacks in cases when the linear layer is an orthogonal matrix) might not exist, whereas there are many quadratic invariants of generalized type (alternatively quadratic CLIs). In particular, it is shown that the inverse mapping $S(x)=x^{-1}$ over $GF(2^4)$ admits quadratic CLIs that additionally possess linear structures. The use of cycle structure is further refined through a novel concept of active cycle set, which turns out to be useful for defining invariants of the whole substitution layer. We present an algorithm for finding such invariants provided the knowledge about the cycle structure of the constituent S-boxes used.

Routing protocol for Low power and lossy network (RPL) is a standardized optimal protocol for routing in Internet of Things (IoT). The constrained wireless sensor network in IoT is characterized by lack of processing speed, low power and low memory. Sometimes various network attacks enabling the RPL network affect the network performance dismally. This leads to drastic variation in energy consumption at nodes and disturb the RPL network protocol structure. This leads to reduced processing speed and memory allocation in the network. We first illustrate the attacks and their impact in RPL network by simulation. To detect such attacks, we propose an Intrusion Detection System (IDS) scheme for RPL network based on trust computation. Trust based Neighbor notification IDS (TN-IDS) is a secure hierarchical distribution system which monitors the network intrusion and checks the performance of the network. The new TN-IDS system will track all nodes in the network and identify the malicious nodes. The activity list prepared by IDS indicates them to a sink node. This is achieved by introducing a distributed leader election algorithm to collect metrics related to the RPL network. Hence, the performance metrics of the RPL network together with TN-IDS module can identify the malicious node and isolate them.

Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations. Thus, unlike previous methods which focus on the propagation of the difference or $s$-difference, we redefine the impossible differentials and impossible $(s+1)$-polytopic transitions according to the propagation of state, which allow us to break through those limitations of the previous methods. Theoretically, we prove that traditional impossible differentials and impossible $(s+1)$-polytopic transitions are equivalent to part of our redefinitions, which have advantages from broader view. Technically, we renew the automatic search model and design an SAT-based tool to evaluate our redefined impossible differentials and impossible $(s+1)$-polytopic transitions efficiently. This tool is capable of searching for impossible differentials and impossible $(s+1)$-polytopic transitions not only in the single-key setting but also in the related-key setting. As a result, for GIFT64, we get the $6$-round impossible differentials which cannot be detected by all previous tools. For PRINTcipher, we propose the first modeling method for the key-dependent permutation and key-dependent S-box. For MISTY1, we derive 902 4-round impossible differentials by exploiting the differential property of S-boxes. For RC5, we present the first modeling method for the variable rotation and get 2.5-round impossible differentials for each version of it. We also get the results of impossible differentials for GIFT, CHAM and SPECK in related-key setting. More remarkable, our tool can be used to evaluate the security of given cipher against the impossible differentials, and we prove that there exists no 5-round 1 input active word and 1 output active word impossible differentials for AES-128 even consider the relations of 3-round keys. Besides, we also get the impossible $(s+1)$-polytopic transitions for PRINTcipher, GIFT64, PRESENT, and RC5, all of which can cover more rounds than their corresponding impossible differentials as far as we know.

We investigate the exact round complexity of secure multiparty computation (MPC) against *covert* adversaries who may attempt to cheat, but do not wish to be caught doing so. Covert adversaries lie in between semi-honest adversaries who follow protocol specification and malicious adversaries who may deviate arbitrarily. Recently, two round protocols for semi-honest MPC and four round protocols for malicious-secure MPC were constructed, both of which are optimal. While these results can be viewed as constituting two end points of a security spectrum, we investigate the design of protocols that potentially span the spectrum. Our main result is an MPC protocol against covert adversaries with variable round complexity: when the detection probability is set to the lowest setting, our protocol requires two rounds and offers same security as semi-honest MPC. By increasing the detecting probability, we can increase the security guarantees, with round complexity five in the extreme case. The security of our protocol is based on standard cryptographic assumptions. We supplement our positive result with a negative result, ruling out *strict* three round protocols with respect to black-box simulation.

The CAP theorem says that no blockchain can be live under dynamic participation and safe under temporary network partitions. To resolve this availability-finality dilemma, we formulate a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. The finalized ledger falls behind the full ledger when the network partitions but catches up when the network heals. Gasper, the current candidate protocol for Ethereum 2.0's beacon chain, combines the finality gadget Casper FFG with the LMD GHOST fork choice rule and aims to achieve this property. However, we discovered an attack in the standard synchronous network model, highlighting a general difficulty with existing finality-gadget-based designs. We present a construction of provably secure ebb-and-flow protocols with optimal resilience. Nodes run an off-the-shelf dynamically available protocol, take snapshots of the growing available ledger, and input them into a separate off-the-shelf BFT protocol to finalize a prefix. We explore connections with flexible BFT and improve upon the state-of-the-art for that problem.

We consider the security of two of the most commonly used cryptographic primitives—message authentication codes (MACs) and pseudorandom functions (PRFs)—in a multi-user setting with adaptive corruption. Whereas is it well known that any secure MAC or PRF is also multi-user secure under adaptive corruption, the trivial reduction induces a security loss that is linear in the number of users. Our main result shows that black-box reductions from “standard” assumptions cannot be used to provide a tight, or even a linear-preserving, security reduction for adaptive multi-user secure deterministic stateless MACs and thus also PRFs. In other words, a security loss that grows with the number of users is necessary for any such black-box reduction.

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: SPIX and SpoC. We improve the number of steps with respect to the previously known best results, that used rebound attack. We improve the techniques used for solving the middle part, called inbound, and we relax the external conditions in order to extend the previous attacks. The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

We propose a generic construction of 2-pass authenticated key exchange (AKE) scheme with explicit authentication from key encapsulation mechanism (KEM) and signature (SIG) schemes. We improve the security model due to Gjosteen and Jager [Crypto2018] to a stronger one. In the strong model, if a replayed message is accepted by some user, the authentication of AKE is broken. We define a new security notion named ''IND-mCPA with adaptive reveals'' for KEM. When the underlying KEM has such a security and SIG has unforgeability with adaptive corruptions, our construction of AKE equipped with counters as states is secure in the strong model, and stateless AKE without counter is secure in the traditional model. We also present a KEM possessing tight ''IND-mCPA security with adaptive reveals'' from the Computation Diffie-Hellman assumption in the random oracle model. When the generic construction of AKE is instantiated with the KEM and the available SIG by Gjosteen and Jager [Crypto2018], we obtain the first practical 2-pass AKE with tight security and explicit authentication. In addition, the integration of the tightly IND-mCCA secure KEM (derived from PKE by Han et al. [Crypto2019]) and the tightly secure SIG by Bader et al. [TCC2015] results in the first tightly secure 2-pass AKE with explicit authentication in the standard model.

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth. In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (Designs, Codes and Cryptography, 2021). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters' sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the $k$-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.'s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.'s scheme in the sense of the sizes of master public/secret keys.

In 2013, Tao et al. introduced the ABC Simple Matrix Encryption Scheme, a multivariate public key encryption scheme. The scheme boasts great efficiency in encryption and decryption, though it suffers from very large public keys. It was quickly noted that the original proposal, utilizing square matrices, suffered from a very bad decryption failure rate. As a consequence, the designers later published updated parameters, replacing the square matrices with rectangular matrices and altering other parameters to avoid the cryptanalysis of the original scheme presented in 2014 by Moody et al. In this work, we show that making the matrices rectangular, while decreasing the decryption failure rate, actually, and ironically, diminishes security. We show that the combinatorial rank methods employed in the original attack of Moody et al. can be enhanced by the same added degrees of freedom that reduce the decryption failure rate. Moreover, and quite interestingly, if the decryption failure rate is still reasonably high, as exhibited by the proposed parameters, we are able to mount a reaction attack to further enhance the combinatorial rank methods. To our knowledge this is the first instance of a reaction attack creating a significant advantage in this context.

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with an attribute vector and a receiver holding a secret-key associated to a predicate vector can recover the message from the ciphertext if the inner product between the attribute and predicate vectors is non-zero. The main focus is to hide messages in most of the existing NIPEs and the associated attribute is trivially included in the ciphertext. In this work, we investigate the design of NIPEs that are capable of hiding attributes along with messages and secure against active adversaries. In particular, we describe a generic ransformation of an attribute-hiding chosen-ciphertext attack (CCA) secure NIPE from an inner product functional encryption (IPFE) and a quasi-adaptive non-interactive zero-knowledge (QANIZK) proof system. This leads us to a set of attribute-hiding NIPEs (AHNIPE) with security based on several assumptions such as plain Decisional Diffie-Hellman (DDH), Learning With Errors (LWE) and Decision Composite Reciprocity (DCR). Furthermore, we build a more efficient and concrete construction of a CCA secure AHNIPE the security of which can be based on DDH and Kernel Matrix Diffie-Hellman (KerMDH) assumptions. As DDH implies the computational KerMDH assumption, the latter construction achieves a CCA secure AHNIPE from minimal assumption to date. We explore a few applications of AHNIPE. More specifically, we show that AHNIPE directly implies an anonymous identity-based revocation (IBR) scheme. Consequently, we get the first CCA secure IBR solely based on plain DDH assumption in the standard model, improving the security of any previous anonymous CCA secure IBR scheme which is proven secure relying on pairing-based assumptions in the random oracle model. Moreover, we add a tracing algorithm to our anonymous IBR scheme to convert it into an efficient anonymous trace and revoked scheme with CCA security.

Chameleon-hashes are collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash can be found. Recently, Derler et al. (PKC '20) introduced the notion of fully collision-resistant chameleon-hashes. Full collision-resistance requires the intractability of finding collisions, even with full-adaptive access to a collision-finding oracle. Their construction combines simulation-sound extractable (SSE) NIZKs with perfectly correct IND-CPA secure public-key encryption (PKE) schemes. We show that, instead of perfectly correct PKE, non-interactive commitment schemes are sufficient. For the first time, this gives rise to efficient instantiations from plausible post-quantum assumptions and thus candidates of chameleon-hashes with strong collision-resistance guarantees and long-term security guarantees. On the more theoretical side, our results relax the requirement to not being dependent on public-key encryption.

Ascon-p is the core building block of Ascon, the winner in the lightweight category of the CAESAR competition. With ISAP, another Ascon-p-based AEAD scheme is currently competing in the 2nd round of the NIST lightweight cryptography standardization project. In contrast to Ascon, ISAP focuses on providing hardening/protection against a large class of implementation attacks, such as DPA, DFA, SFA, and SIFA, entirely on mode-level. Consequently, Ascon-p can be used to realize a wide range of cryptographic computations such as authenticated encryption, hashing, pseudorandom number generation, with or without the need for implementation security, which makes it the perfect choice for lightweight cryptography on embedded devices. In this paper, we implement Ascon-p as an instruction extension for RISC-V that is tightly coupled to the processors register file and thus does not require any dedicated registers. This single instruction allows us to realize all cryptographic computations that typically occur on embedded devices with high performance. More concretely, with ISAP and Ascon's family of modes for AEAD and hashing, we can perform cryptographic computations with a performance of about 2 cycles/byte, or about 4 cycles/byte if protection against fault attacks and power analysis is desired. As we show, our instruction extension requires only 4.7 kGE, or about half the area of dedicated Ascon co-processor designs, and is easy to integrate into low-end embedded devices like 32-bit ARM Cortex-M or RISC-V microprocessors. Finally, we analyze the provided implementation security of ISAP, when implemented using our instruction extension.

Fresh rekeying is a well-established method to protect a primitive or mode against side-channel attacks: an easy to protect but cryptographically not so involved function generates a subkey from the master key, and this subkey is then used for the block encryption of a single or a few messages. It is an efficient way to achieve side-channel protection, but current solutions only achieve birthday bound security in the block size of the cipher and thus halve its security (except if more involved primitives are employed). We present generalized solutions to parallel block cipher rekeying that, for the first time, achieve security beyond the birthday bound in the block size $n$. The first solution involves, next to the subkey generation, one multiplication and the core block cipher call and achieves $2^{2n/3}$ security. The second solution makes two block cipher calls, and achieves optimal $2^n$ security. Our third solution uses a slightly larger subkey generation function but requires no adaptations to the core encryption and also achieves optimal security. The construction seamlessly generalizes to permutation based fresh rekeying. Central to our schemes is the observation that fresh rekeying and generic tweakable block cipher design are two very related topics, and we can take lessons from the advanced results in the latter to improve our understanding and development of the former. We subsequently use these rekeying schemes in a constructive manner to deliver three authenticated encryption modes that achieve beyond birthday bound security and are easy to protect against side-channel attacks.

Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal lattices than in arbitrary ones, in particular in the quantum setting. Our main contribution is to propose a new ``twisted'' version of the PHS (by Pellet-Mary, Hanrot and Stehlé 2019) algorithm, that we call Twisted-PHS. As a minor contribution, we also propose several improvements of the PHS algorithm. On the theoretical side, we prove that our Twisted-PHS algorithm reaches the same asymptotic trade-off between runtime and approximation factor as the original PHS algorithm. On the practical side though, we provide a full implementation of our algorithm which suggests that much better approximation factors are achieved, and that the given lattice bases are a lot more orthogonal than the ones used in PHS. This is the first time to our knowledge that this type of algorithm is completely implemented and tested for fields of degrees up to 60.

Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages. In this work, we explore the possibility of achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the k-challenge setting (i.e., the adversary can obtain k challenge ciphertexts for each public key) if its secret key contains less than k bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the k-challenge setting, where the ratio of the secret key length to k approaches the lower bound 1.

Motivated by the currently widespread concern about mass surveillance of encrypted communications, Bellare \emph{et al.} introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare \emph{et al.}, CRYPTO'14 \& ACM CCS'15; Ateniese \emph{et al.}, ACM CCS'15; Berndt and Liśkiewicz, ACM CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much progress, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key, and also previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Liśkiewicz, ACM CCS'17). In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more effective and dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practice. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box yet quite general attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack. Our attack relies on a novel identification and formalization of certain properties that yield practical ASAs on KEMs. More broadly, it points at and may shed some light on exploring structural weaknesses of other ``composed cryptographic primitives,'' which may make them susceptible to more dangerous ASAs with effectiveness that surpasses the known logarithmic upper bound (i.e., reviewing composition as an attack enabler).

Achieving fairness and soundness in non-simultaneous rational secret sharing schemes has proved to be challenging. On the one hand, soundness can be ensured by providing side information related to the secret as a check, but on the other, this can be used by deviant players to compromise fairness. To overcome this, the idea of incorporating a time delay was suggested in the literature: in particular, time-delay encryption based on memory-bound functions has been put forth as a solution. In this paper, we propose a different approach to achieve such delay, namely using homomorphic time-lock puzzles (HTLPs), introduced at CRYPTO 2019, and construct a fair and sound rational secret sharing scheme in the non-simultaneous setting from HTLPs. HTLPs are used to embed sub-shares of the secret for a predetermined time. This allows to restore fairness of the secret reconstruction phase, despite players having access to information related to the secret which is required to ensure soundness of the scheme. Key to our construction is the fact that the time-lock puzzles are homomorphic so that players can compactly evaluate sub-shares. Without this efficiency improvement, players would have to independently solve each puzzle sent from the other players to obtain a share of the secret, which would be computationally inefficient. We argue that achieving both fairness and soundness in a non-simultaneous scheme using a time delay based on CPU-bound functions rather than memory-bound functions is more cost effective and realistic in relation to the implementation of the construction.

Bit commitment is a primitive task of many cryptographic tasks. It has been proved that the unconditionally secure quantum bit commitment is impossible from Mayers-Lo-Chau No-go theorem. A variant of quantum bit commitment requires cheat sensible for both parties. Another results shows that these no-go theorem can be evaded using the non-relativistic transmission or Minkowski causality. Our goal in this paper is to revise unconditionally secure quantum bit commitment. We firstly propose new quantum bit commitments using distributed settings and quantum entanglement which is used to overcome Mayers-Lo-Chau No-go Theorems. Both protocols are perfectly concealing, perfectly binding, and cheating sensible in asymptotic model against entanglement-based attack and splitting attack from quantum networks. These schemes are then extended to commit secret bits against eavesdroppers. We further propose two new applications. One is to commit qubit states. The other is to commit unitary circuits. These new schemes are useful for committing several primitives including sampling model, randomness, and Boolean functions in cryptographic protocols.

In CRYPTO 2015, Cogliati et al. have proposed one-round tweakable Even-Mansour (\textsf{1-TEM}) cipher constructed out of a single $n$-bit public permutation $\pi$ and a uniform and almost XOR-universal hash function \textsf{H} as $(k, t, x) \mapsto \textsf{H}_k(t) \oplus \pi(\textsf{H}_k(t) \oplus x)$, where $t$ is the tweak, and $x$ is the $n$-bit message. Authors have shown that its two-round extension, which we refer to as \textsf{2-TEM}, obtained by cascading $2$-independent instances of the construction gives $2n/3$-bit security and $r$-round cascading gives $rn/r+2$-bit security. In ASIACRYPT 2015, Cogliati and Seurin have shown that four-round tweakable Even-Mansour cipher, which we refer to as \textsf{4-TEM}, constructed out of four independent $n$-bit permutations $\pi_1, \pi_2, \pi_3, \pi_4$ and two independent $n$-bit keys $k_1, k_2$, defined as $$k_1 \oplus t \oplus \pi_4(k_2 \oplus t \oplus \pi_3(k_1 \oplus t \oplus \pi_2(k_2 \oplus t \oplus \pi_1(k_1 \oplus t \oplus x)))),$$ is secure upto $2^{2n/3}$ adversarial queries. In this paper, we have shown that if we replace two independent permutations of \textsf{2-TEM} (Cogliati et al., CRYPTO 2015) with a single $n$-bit public permutation, then the resultant construction still guarrantees security upto $2^{2n/3}$ adversarial queries. Using the results derived therein, we also show that replacing the permutation $(\pi_4, \pi_3)$ with $(\pi_1, \pi_2)$ in the above equation preserves security upto $2^{2n/3}$ adversarial queries.

This paper studies constructions of pseudorandom functions (PRFs) from non-adaptive PRFs (naPRFs), i.e., PRFs which are secure only against distinguishers issuing all of their queries at once. Berman and Haitner (Journal of Cryptology, '15) gave a one-call construction which, however, is not hardness preserving -- to obtain a secure PRF (against polynomial-time distinguishers), they need to rely on a naPRF secure against superpolynomial-time distinguishers; in contrast, all known hardness-preserving constructions require $\omega(1)$ calls. This leaves open the question of whether a stronger superpolynomial-time assumption is necessary for one-call (or constant-call) approaches. Here, we show that a large class of one-call constructions (which in particular includes the one of Berman and Haitner) cannot be proved to be a secure PRF under a black-box reduction to the (polynomial-time) naPRF security of the underlying function. Our result complements existing impossibility results (Myers, EUROCRYPT '04; Pietrzak, CRYPTO '05) ruling out natural specific approaches, such as parallel and sequential composition. Furthermore, we show that our techniques extend to rule out a natural class of constructions making parallel but arbitrary number of calls which in particular includes parallel composition and the two-call, cuckoo-hashing based construction of Berman et al.\ (Journal of Cryptology, '19).

In this article we present the BB84 quantum key distribution scheme from two perspectives. First, we provide a theoretical discussion of the steps Alice and Bob take to reach a shared secret using this protocol, while an eavesdropper Eve is either involved or not. Then, we offer and discuss two distinct implementations that simulate BB84 using IBM’s Qiskit framework, the first being an exercise solved during the “IBM Quantum Challenge” event in early May 2020, while the other was developed independently to showcase the intercept-resend attack strategy in detail. We note the latter’s scalability and increased output verbosity, which allow for a statistical analysis to determine the probability of detecting the act of eavesdropping.

The tight security bound of the Key-Alternating Cipher (KAC) construction whose round permutations are independent from each other has been well studied. Then a natural question is how the security bound will change when we use fewer permutations in a KAC construction. In CRYPTO 2014, Chen et al. proved that 2-round KAC with a single permutation (2KACSP) has the same security level as the classic one (i.e., 2-round KAC). But we still know little about the security bound of incompletely-independent KAC constructions with more than 2 rounds. In this paper,we will show that a similar result also holds for 3-round case. More concretely, we prove that 3-round KAC with a single permutation (3KACSP) is secure up to $\varTheta(2^{\frac{3n}{4}})$ queries, which also caps the security of 3-round KAC. To avoid the cumbersome graphical illustration used in Chen et al.'s work, a new representation is introduced to characterize the underlying combinatorial problem. Benefited from it, we can handle the knotty dependence in a modular way, and also show a plausible way to study the security of $r$KACSP. Technically, we abstract a type of problems capturing the intrinsic randomness of $r$KACSP construction, and then propose a high-level framework to handle such problems. Furthermore, our proof techniques show some evidence that for any $r$, $r$KACSP has the same security level as the classic $r$-round KAC in random permutation model.

In this paper we present an analysis of the SpoC cipher, a second round candidate of the NIST Lightweight Crypto Standardization process. First we present a differential analysis on the sLiSCP-light permutation, a core element of SpoC. Then we propose a series of attacks on both versions of SpoC, namely round-reduced differential tag forgery and message recovery attacks, as well as a time-memory trade-off key-recovery attack on the full round version of Spoc-64. Finally, we present an observation regarding the constants used in the sLiSCP-light permutation. To the best of our knowledge, this paper represents the first third-party analysis on both SpoC cipher and the sLiSCP-light permutation.

Studying the security and efficiency of blind signatures is an important goal for privacy sensitive applications. In particular, for large-scale settings (e.g., cryptocurrency tumblers), it is important for schemes to scale well with the number of users in the system. Unfortunately, all practical schemes either 1) rely on (very strong) number theoretic hardness assumptions and/or computationally expensive pairing operations over bilinear groups, or 2) support only a polylogarithmic number of concurrent (i.e., arbitrarily interleaved) signing sessions per public key. In this work, we revisit the security of two pairing-free blind signature schemes in the Algebraic Group Model (AGM) + Random Oracle Model (ROM). Concretely, 1. We consider the security of Abe’s scheme (EUROCRYPT ‘01), which is known to have a flawed proof in the plain ROM. We adapt the scheme to allow a partially blind variant and give a proof of the new scheme under the discrete logarithm assumption in the AGM+ROM, even for (polynomially many) concurrent signing sessions. 2. We then prove that the popular blind Schnorr scheme is secure under the one-more discrete logarithm assumption if the signatures are issued sequentially. While the work of Fuchsbauer et al. (EUROCRYPT ‘20) proves the security of the blind Schnorr scheme for concurrent signing sessions in the AGM+ROM, its underlying assumption, ROS, is proven false by Benhamouda et al. (EUROCRYPT‘21) when more than polylogarithmically many signatures are issued. Given the recent progress, we present the first security analysis of the blind Schnorr scheme in the slightly weaker sequential setting. We also show that our security proof reduces from the weakest possible assumption, with respect to known reduction techniques.

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary elliptic $\mathbb{F}_{\!q}$-curve of $j$-invariant $0$ such that $\sqrt{b} \in \mathbb{F}_{\!q}$. In particular, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases $b=4$). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time encoding $h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q})$ of an absolutely new type for which $q/6 \leqslant \#\mathrm{Im}(h)$. We prove that at least for $q \equiv 4 \ (\mathrm{mod} \ 9)$ the hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ induced by $h$ is indifferentiable from a random oracle. The main idea of our encoding consists in extracting in $\mathbb{F}_{\!q}$ (for $q \equiv 1 \ (\mathrm{mod} \ 3)$) a cubic root instead of a square root as in the well known (universal) SWU encoding and in its simplified analogue. Besides, the new hashing can be implemented without quadratic and cubic residuosity tests (as well as without inversions) in $\mathbb{F}_{\!q}$. Thus in addition to the protection against timing attacks, $H$ is much more efficient than the SWU hash function, which generally requires to perform $4$ quadratic residuosity tests in $\mathbb{F}_{\!q}$. For instance, in the case of BW6-761 this allows to avoid approximately $4 \!\cdot\! 761 \approx 3000$ field multiplications.

We address the problem of constructing zkSNARKs whose SRS is $\mathit{universal}$ – valid for all relations within a size-bound – and $\mathit{updatable}$ – a dynamic set of participants can add secret randomness to it indefinitely thus increasing confidence in the setup. We investigate formal frameworks and techniques to design efficient universal updatable zkSNARKs with linear-size SRS and their commit-and-prove variants. We achieve a collection of zkSNARKs with different tradeoffs. One of our constructions achieves the smallest proof size and proving time compared to the state of art for proofs for arithmetic circuits. The language supported by this scheme is a variant of R1CS, called R1CS-lite, introduced by this work. Another of our constructions supports directly standard R1CS and improves on previous work achieving the fastest proving time for this type of constraint systems. We achieve this result via the combination of different contributions: (1) a new algebraically-flavored variant of IOPs that we call $\mathit{Polynomial}$ $\mathit{Holographic}$ $\mathit{IOPs}$ (PHPs), (2) a new compiler that combines our PHPs with $\mathit{commit}$-$\mathit{and}$-$\mathit{prove}$ $\mathit{\ zkSNARKs}$ for committed polynomials, (3) pairing-based realizations of these CP-SNARKs for polynomials, (4) constructions of PHPs for R1CS and R1CS-lite, (5) a variant of the compiler that yields a commit-and-prove universal zkSNARK.

Private Information Retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but- curious servers. The information-theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. To augment previous work, we propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database Private Block Retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information-theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. The proposed bit connection and trapdoor function combinations have achieved the following results. • Single Database information-theoretic PBR (SitPBR): The proposed combinations are used to construct SitPBR in which the user privacy is preserved through the generation of information-theoretic queries and data privacy is preserved using quadratic residuosity assumption. • Single Database computationally bounded PBR (ScPBR): The proposed combinations are used to construct ScPBR in which both user privacy and data privacy are preserved using a well-known intractability assumption called quadratic residuosity assumption. • Map(SitPBR)→ScPBR: The proposed combinations can be used to transform (or map) SitPBR into ScPBR scheme by choosing appropriate function parameters. • Map(ScPBR)→SitPBR: The proposed combinations can be used to transform (or map) ScPBR into SitPBR scheme by choosing appropriate function parameters. All the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).

This paper presents a constant time hardware implementation of the NIST round 2 post-quantum cryptographic algorithm Streamlined NTRU Prime. We implement the entire KEM algorithm, including all steps for key generation, encapsulation and decapsulation, and all en- and decoding. We focus on optimizing the resources used, as well as applying optimization and parallelism available due to the hardware design. We show the core en- and decapsulation requires only a fraction of the total FPGA fabric resource cost, which is dominated by that of the hash function, and the en- and decoding algorithm. For the NIST Security Level 3, our implementation uses a total of 1841 slices on a Xilinx Zynq Ultrascale+ FPGA, together with 14 BRAMs and 19 DSPs. The maximum achieved frequency is 271 MHz, at which the key generation, encapsulation and decapsulation take 4808 μs, 524 μs and 958 μs respectively. To our knowledge, this work is the first full hardware implementation where the entire algorithm is implemented.

In this work, we propose different techniques that can be used to implement the ROLLO, and partially RQC, family of algorithms in a standalone, efficient and constant time library. For simplicity, we focus our attention on one specific instance of this family, ROLLO-I-128. For each of these techniques, we present explicit code (with intrinsics when required), or pseudo-code and performance measures to show their impact. More precisely, we use a combination of original and known results and describe procedures for Gaussian reduction of binary matrices, generation of vectors of given rank, multiplication with lazy reduction and inversion of polynomials in a composite Galois field. We also carry out a global performance analysis to show the impact of these improvements on ROLLO-I-128. Through the SUPERCOP framework, we compare it to other 128-bit secure KEMs in the NIST competition. To our knowledge, this is the first optimized full constant time implementation of ROLLO-I-128.

Side-channel attacks based on machine learning have recently been introduced to recover the secret information from software and hardware implementations of mathematically secure algorithms. Convolutional Neural Networks (CNNs) have proven to outperform the template attacks due to their ability of handling misalignment in the symmetric algorithms leakage data traces. However, one of the limitations of deep learning algorithms is the requirement of huge datasets for model training. For evaluation scenarios, where limited leakage trace instances are available, simple machine learning with the selection of proper feature engineering, data splitting, and validation techniques, can be more effective. Moreover, limited analysis exists for public-key algorithms, especially on non-traditional implementations like those using Residue Number System (RNS). Template attacks are successful on RNS-based Elliptic Curve Cryptography (ECC), only if the aligned portion is used in templates. In this study, we present a systematic methodology for the evaluation of ECC cryptosystems with and without countermeasures against machine learning side-channel attacks using two attack models. RNS-based ECC datasets have been evaluated using four machine learning classifiers and comparison is provided with existing state-of-the-art template attacks. Moreover, we analyze the impact of raw features and advanced hybrid feature engineering techniques, along with the effect of splitting ratio. We discuss the metrics and procedures that can be used for accurate classification on the imbalance datasets. The experimental results demonstrate that, for ECC RNS datasets, the efficiency of simple machine learning algorithms is better than the complex deep learning techniques when such datasets are not so huge.

I describe a non-interactive transaction scheme for Mimblewimble protocol, so as to overcome the usability issue of the Mimblewimble wallet. With the Diffie–Hellman, we can use an Ephemeral Key shared between the sender and the receiver, a public nonce R is added to the output for that, removing the interactive cooperation procedure. And an additional one-time public key P' is used to lock the output to make it only spendable for the receiver, i.e. the owner of P'. Furtherly, to keep Mimblewimble privacy character, the Stealth Address is used in this new transaction scheme.

This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size O(n+d) bilinear group elements, where d is the depth and n is the input size of the circuit. Our technical contribution is to add unbounded simulation soundness to a recent NIZK of González and Ràfols (ASIACRYPT'19) with very small overhead. We give two different constructions: the first one is more efficient but not tight, and the second one is tight. Our new scheme can be used to construct Signatures of Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives. As an independent contribution we also detail a simple formula to encode Boolean circuits as Quadratic Arithmetic Programs.

We present the implementation of Grover's algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions, whose design only uses modular addition, word rotation, and bitwise exclusive or. Our implementation provides the means to assess with precision the scaling of the number of gates and depth of a full-fledged quantum circuit designed to find the preimages of a given hash digest. The detailed construction of the quantum oracle shows that the presence of AND gates, OR gates, shifts of bits and the reuse of the initial state along the computation, require extra quantum resources as compared with other hash functions based on modular additions, XOR gates and rotations. We also track the entanglement entropy present in the quantum register at every step along the computation, showing that it becomes maximal at the inner core of the first action of the quantum oracle, which implies that no classical simulation based on Tensor Networks would be of relevance. Finally, we show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover's algorithm can only provide some marginal practical advantage in terms of error mitigation.

In the conference “Fast Software Encryption 2015”, a new line of research was proposed by introducing the first small-state stream cipher (SSC). The goal was to design lightweight stream ciphers for hardware application by going beyond the rule that the internal state size must be at least twice the intended security level. Time-memory-data trade-off (TMDTO) attacks and fast correlation attacks (FCA) were successfully applied to all proposed SSCs which can be implemented by less than 1000 gate equivalents in hardware. It is possible to increase the security of stream ciphers against FCA by exploiting more complicated functions for the nonlinear feedback shift register and the output function, but we use lightweight functions to design the lightest SSC in the world while providing more security against FCA. Our proposed cipher provides 80-bit security against TMDTO distinguishing attacks, while Lizard and Plantlet provide only 60-bit and 58-bit security against distinguishing attacks, respectively. Our main contribution is to propose a lightweight round key function with a very long period that increases the security of SSCs against FCA.

Circular security is the most elementary form of key-dependent message (KDM) security, which allows us to securely encrypt only a copy of secret key bits. In this work, we show that circular security is complete for KDM security in the sense that an encryption scheme satisfying this security notion can be transformed into one satisfying KDM security with respect to all functions computable by a-priori bounded-size circuits (bounded-KDM security). This result holds in the presence of any number of keys and in any of secret-key/public-key and CPA/CCA settings. Such a completeness result was previously shown by Applebaum (EUROCRYPT 2011) for KDM security with respect to projection functions (projection-KDM security) that allows us to securely encrypt both a copy and a negation of secret key bits. Besides amplifying the strength of KDM security, our transformation in fact can start from an encryption scheme satisfying circular security against CPA attacks and results in one satisfying bounded-KDM security against CCA attacks. This result improves the recent result by Kitagawa and Matsuda (TCC 2019) showing a CPA-to-CCA transformation for KDM secure public-key encryption schemes.

When generating primes $p$ and $q$ for an RSA key, the algorithm specifies that they should be checked to see that $p-1$ and $q-1$ are relatively prime to the public exponent $e$, and regenerated if this is not the case. If this is not done, then the calculation of the decrypt exponent will fail. However, what if a software bug allows the generation of public parameters $N$ and $e$ of an RSA key with this property and then it is subsequently used for encryption? Though this may seem like a purely academic question, a software bug in the RSA key generation implementation in the CNG API of a preview release of the Windows 10 operating system makes this question of more than purely hypothetical value. Without a well defined decrypt exponent, plaintexts encrypted to such keys will be undecryptable thus potentially losing user data, a serious software defect. Though the decrypt exponent is no longer well defined, it is in fact possible to recover the plaintext, or a small number of potential plaintexts if the prime factors $p$ and $q$ of the public modulus $N$ are known. This paper presents an analysis of what steps fail in the RSA algorithm and use this to give a plaintext recovery algorithm. The runtime of the algorithm scales linearly in the magnitude of the public exponent, in practice this is manageable as there are only a few small public exponents that are used. This algorithm has been implemented in a publicly available python script. We further discuss the software bug that lead to this and derive lessons that can be used while testing randomized functions in cryptographic software. Specifically, we derive an explicit formula that describes the trade off between number of iterations of tests of a randomized cryptographic functions and the potential number of users affected by a bug dependent on the random values.

The Joux-Vitse Crossbred algorithm's aim is to efficiently solve a system of semi-regular multivariate polynomials. For random polynomials, this is thought to be at least hard for a classical computer to solve. In this work, the algorithm is described in detail, a bivariate generating series to test the admissibility of parameters in F_2 is investigated and from this, a new series for F_q, q > 2 is presented. In addition, a complexity estimate is given for both F_2 and F_q, q > 2, which is compared to an estimate presented by Samardijska et al. Their estimate is shown to be an upper bound for the Crossbred algorithm. By obtaining optimal parameters using the previous results, the cost of theoretically applying Crossbred, FES and Hybrid-F5 to polynomial systems of various sizes of various numbers of variables and q was plotted. Overall, it was determined that for larger fields, the Crossbred algorithm provides an improved asymptotic complexity over FES. However, it does not provide any improvement over Hybrid-F5.

MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC 6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal the user's secret key. In this paper, we propose a variant of MuSig in which signers generate their nonce deterministically as a pseudorandom function of the message and all signers' public keys and prove that they did so by providing a non-interactive zero-knowledge proof to their cosigners. The resulting scheme, which we call MuSig-DN, is the first Schnorr multi-signature scheme with deterministic signing. Therefore its signing protocol is robust against failures in the randomness generation as well as attacks trying to exploit the statefulness of the signing procedure, e.g., virtual machine rewinding attacks. As an additional benefit, a signing session in MuSig-DN requires only two rounds instead of three as required by all previous Schnorr multi-signatures including MuSig. To instantiate our construction, we identify a suitable algebraic pseudorandom function and provide an efficient implementation of this function as an arithmetic circuit. This makes it possible to realize MuSig-DN efficiently using zero-knowledge proof frameworks for arithmetic circuits which support inputs given in Pedersen commitments, e.g., Bulletproofs. We demonstrate the practicality of our technique by implementing it for the secp256k1 elliptic curve used in Bitcoin.

Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the identification of which is a measure of a block cipher’s security margins. This paper introduces an optimized GPU-based branch-and-bound framework for differential search. We optimize search efficiency by parallelizing all branch-and-bound operations, completing the entire search on the GPU without communicating with the CPU. The meet-in-the-middle (MITM) approach is also adopted for further performance gains. We analyze the financial and computational costs of the proposed framework using Google Cloud VM to showcase its practicality. When optimized for performance, we can attain up to 90x speedup while saving up to 47% of the running cost as compared to a single CPU core. When optimized for cost, the proposed framework can save up to 83% of financial costs while retaining a speedup of up to 40x. As a proof of concept, the proposed framework was then applied on 128-bit TRIFLE-BC, 64-bit PRESENT, and 64-bit GIFT. Notably, we identified the best differentials for PRESENT (16 rounds) and 64-bit GIFT (13 rounds) to date, with estimated probabilities of $2^{-61.7964}$ and $2^{-60.66}$ respectively. Although the differential results for TRIFLE-BC were incremental, the proposed framework was able to construct differentials for 43 rounds that consisted of approximately 5.8x more individual trails than previous work, making it one of the most efficient approaches for larger block ciphers.

A new post-quantum, hash-based signature (HBS) scheme is introduced. In known HBS, the size and cost of each signature increase as the total number of messages one wishes to authenticate increase. In real-world applications, requiring large volumes of signatures, they can become impractical. This paper studies HBS in a blockchain: a public, decentralized database. The proposed HBS scheme shows that, when all signatures are known, quite the opposite is possible: the signatures can become more efficient as the number of signatures grows. Authenticating large volumes of messages results less costly on average than authenticating only a few.

We show that verifiable voting systems require a security notion beyond individual- and universal-verifiability plus cast-as-intended.

At CRYPTO 2018, Cascudo et al. introduced Reverse Multiplication Friendly Embeddings (RMFEs). These are a mechanism to compute $\delta$ parallel evaluations of the same arithmetic circuit over a field $\mathbb{F}_q$ at the cost of a single evaluation of that circuit in $\mathbb{F}_{q^d}$, where $\delta < d$. Due to this inequality, RMFEs are a useful tool when protocols require to work over $\mathbb{F}_{q^d}$ but one is only interested in computing over $\mathbb{F}_q$. In this work we introduce Circuit Amortization Friendly Encodings (CAFEs), which generalize RMFEs while having concrete efficiency in mind. For a Galois Ring $R = GR(2^{k}, d)$, CAFEs allow to compute certain circuits over $\mathbb{Z}_{2^k}$ at the cost of a single secure multiplication in $R$. We present three CAFE instantiations, which we apply to the protocol for MPC over $\mathbb{Z}_{2^k}$ via Galois Rings by Abspoel et al. (TCC 2019). Our protocols allow for efficient switching between the different CAFEs, as well as between computation over $GR(2^{k}, d)$ and $\mathbb{F}_{2^{d}}$ in a way that preserves the CAFE in both rings. This adaptability leads to efficiency gains for e.g. Machine Learning applications, which can be represented as highly parallel circuits over $\mathbb{Z}_{2^k}$ followed by bit-wise operations. From an implementation of our techniques, we estimate that an SVM can be evaluated on 250 images in parallel up to $\times 7$ more efficiently using our techniques, compared to the protocol from Abspoel et al. (TCC 2019).

Threshold wallets leverage threshold signature schemes (TSS) to distribute signing rights across multiple parties when issuing blockchain transactions. These provide greater assurance against insider fraud, and are sometimes seen as an alternative to methods using a trusted execution environment to issue the signature. This new class of applications motivated researchers to discover better protocols, entrepreneurs to create start-up companies, and large organizations to deploy TSS-based solutions. For example, the leading cryptocurrency exchange (in transaction volume) adopted TSS to protect some of its wallets. Although the TSS concept is not new, this is the first time that so many TSS implementations are written and deployed in such a critical context, where all liquidity reserves could be lost in a minute if the crypto fails. Furthermore, TSS schemes are sometimes extended or tweaked to best adapt to their target use case---what could go wrong? This paper, based on the authors' experience with building and analyzing TSS technology, describes three different attacks on TSS implementations used by leading organizations. Unlike security analyses of on-paper protocols, this work targets TSS as deployed in real applications, and exploits logical vulnerabilities enabled by the extra layers of complexity added by TSS software. The attacks have concrete applications, and could for example have been exploited to empty an organization's cold wallet (typically worth at least an 8-digit dollar figure). Indeed, one of our targets is the cold wallet system of the biggest cryptocurrency exchange (which has been fixed after our disclosure).

Only the method to estimate the upper bound of the algebraic degree on block ciphers is known so far, but it is not useful for the designer to guarantee the security. In this paper we provide meaningful lower bounds on the algebraic degree of modern block ciphers.

The two traditional streams of multiparty computation (MPC) protocols consist of-- (a) protocols achieving guaranteed output delivery (god) or fairness (fn) in the honest-majority setting and (b) protocols achieving unanimous or selective abort (ua, sa) in the dishonest-majority setting. The favorable presence of honest majority amongst the participants is necessary to achieve the stronger notions of god or fn. While the constructions of each type are abound in the literature, one class of protocols does not seem to withstand the threat model of the other. For instance, the honest-majority protocols do not guarantee privacy of the inputs of the honest parties in the face of dishonest majority and likewise the dishonest-majority protocols cannot achieve god and fn, tolerating even a single corruption, let alone dishonest minority. The promise of the unconventional yet much sought-after species of MPC, termed as `Best-of-Both-Worlds' (BoBW), is to offer the best possible security depending on the actual corruption scenario. This work nearly settles the exact round complexity of two classes of BoBW protocols differing on the security achieved in the honest-majority setting, namely god and fn respectively, under the assumption of no setup (plain model), public setup (CRS) and private setup (CRS + PKI or simply PKI). The former class necessarily requires the number of parties to be strictly more than the sum of the bounds of corruptions in the honest-majority and dishonest-majority setting, for a feasible solution to exist. Demoting the goal to the second-best attainable security in the honest-majority setting, the latter class needs no such restriction. Assuming a network with pair-wise private channels and a broadcast channel, we show that 5 and 3 rounds are necessary and sufficient for the class of BoBW MPC with fn under the assumption of `no setup' and `public and private setup' respectively. For the class of BoBW MPC with god, we show necessity and sufficiency of 3 rounds for the public setup case and 2 rounds for the private setup case. In the no setup setting, we show the sufficiency of 5 rounds, while the known lower bound is 4. All our upper bounds are based on polynomial-time assumptions and assume black-box simulation. With distinct feasibility conditions, the classes differ in terms of the round requirement. The bounds are in some cases different and on a positive note at most one more, compared to the maximum of the needs of the honest-majority and dishonest-majority setting. Our results remain unaffected when security with abort and fairness are upgraded to their identifiable counterparts.

We show that the underlying permutation of ChaCha20 stream cipher does not behave as a random permutation for up to 17 rounds with respect to rotational cryptanalysis. In particular, we derive a lower and an upper bound for the rotational probability through ChaCha quarter round, we show how to extend the bound to a full round and then to the full permutation. The obtained bounds show that the probability to find what we call a parallel rotational collision is, for example, less than $2^{-488}$ for 17 rounds of ChaCha permutation, while for a random permutation of the same input size, this probability is $2^{-511}$. We remark that our distinguisher is not an attack to ChaCha20 stream cipher, but rather a theoretical analysis of its internal permutation from the point of view of rotational cryptanalysis.

Since it was proposed in 2015 as a generalization of integral properties, the division property has evolved into a powerful tool for probing the structures of Boolean functions whose algebraic normal forms are not available. We capture the most essential elements for the detection of division properties from a pure algebraic perspective, proposing a technique named as monomial prediction, which can be employed to determine the presence or absence of a monomial in any product of the coordinate functions of a vectorial Boolean function $\boldsymbol f$ by counting the number of the so-called monomial trails across a sequence of simpler functions whose composition is $\boldsymbol f$. Under the framework of the monomial prediction, we formally prove that most algorithms for detecting division properties in literature raise no false alarms but may miss. We also establish the equivalence between the monomial prediction and the three-subset bit-based division property without unknown subset presented at EUROCRYPT 2020, and show that these two techniques are perfectly accurate. The monomial prediction technique can be regarded as a purification of the definitions of the division properties without resorting to external multisets. This algebraic formulation gives more insights into division properties and inspires new search strategies. With the monomial prediction, we obtain the exact algebraic degrees of TRIVIUM up to 834 rounds for the first time. In the context of cube attacks, we are able to explore a larger search space in limited time and recover the exact algebraic normal forms of complex superpolies with the help of a divide-and-conquer strategy. As a result, we identify more cubes with smaller dimensions, leading to improvements of some near-optimal attacks against 840-, 841- and 842-round TRIVIUM.

Side-channel attacks are one of the greatest practical threats to security-related applications, because they are capable of breaking ciphers that are assumed to be mathematically secure. Lots of studies have been devoted to power or electro-magnetic (EM) analysis against desktop CPUs, mobile CPUs (including ARM, MSP, AVR, etc) and FPGAs, but rarely targeted modern GPUs. Modern GPUs feature their special and specific single instruction multiple threads (SIMT) execution fashion, which makes their power/EM leakage more sophisticated in practical scenarios. In this paper, we study side-channel attacks with leakage from SIMT systems, and propose leakage models suited to any SIMT systems and specifically to CUDA-enabled GPUs. Afterwards, we instantiate the models with a GPU AES implementation, which is also used for performance evaluations. In addition to the models, we provide optimizations on the attacks that are based on the models. To evaluate the models and optimizations, we run the GPU AES implementation on a CUDA-enabled GPU and, at the same time, collect its EM leakage. The experimental results show that the proposed models are more efficient and the optimizations are effective as well. Our study suggests that GPU-based cryptographic implementations may be much vulnerable to microarchitecture-based side-channel attacks. Therefore, GPU-specific countermeasures should be considered for GPU-based cryptographic implementations in practical applications.

At FSE 2020, a linear distinguishing attack is presented against the ZUC-256 stream cipher based on the $32$-bit word with a data/time complexity of about $2^{236.38}$. In this paper, we re-evaluate the complexity of this attack and discuss the applicability of such a distinguishing attack in 5G application scenarios, where each keystream frame is limited to $20000$, and up to $2^{32}$ bits. To assure a high success probability close to $1$, it is shown that the precise time complexity of the distinguishing attack is $2^{253.93}$ basic operations with a data complexity of $2^{241.38}$ bits keystream, which is far beyond the keystream length limit in 5G application settings in the single-frame setting. Besides, we also consider the multiple-frame scenario where a long keystream could be formed by concatenating many short keystream frames generated from different (Key, IV) pairs. We show that even in such a strong model of distinguishing attacks, the reported bias will not exist in 5G application scenarios and the linear distinguishing attack will not work due to the fact that the long linear combination relation derived from the polynomial multiple of the LFSR in ZUC-256 over $\mbox{GF}(2^{31}-1)$, which has been verified in experiments. It is concluded that the ZUC-256 stream cipher offers the full $256$-bit security in 5G application scenarios.

This paper presents the first third-party security analysis of \tinyjambu, which is one of 32 second-round candidates in NIST's lightweight cryptography standardization process. TinyJAMBU adopts an NLFSR based keyed-permutation that computes only a single NAND gate as a non-linear component per round. The designers evaluated the minimum number of active AND gates, however such a counting method neglects the dependency between multiple AND gates. There also exist previous works considering such dependencies with stricter models, however those are known to be too slow. In this paper, we present a new model that provides a good balance of efficiency and accuracy by only taking into account the first-order correlation of AND gates that frequently occurs in TinyJAMBU. With the refined model, we show a 338-round differential with probability $2^{-62.68}$ that leads to a forgery attack breaking 64-bit security. This implies that the security margin of TinyJAMBU with respect to the number of unattacked rounds is approximately 12%. We also show a differential on full 384 rounds with probability $2^{-70.64}$, thus the security margin of full rounds with respect to the data complexity, namely the gap between the claimed security bits and the attack complexity, is less than 8 bits. Our attacks also point out structural weaknesses of the mode that essentially come from the minimal state size to be lightweight.

We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/"PSK" mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework uses a multi-stage key exchange security model, where each of the many session keys derived in a single TLS 1.3 handshake is tagged with various properties (such as unauthenticated versus unilaterally authenticated versus mutually authenticated, whether it is intended to provide forward security, how it is used in the protocol, and whether the key is protected against replay attacks). We show that these TLS 1.3 handshake protocol modes establish session keys with their desired security properties under standard cryptographic assumptions.

Symmetric password-authenticated key exchange (sPAKE) can be seen as an extension of traditional key exchange where two parties agree on a shared key if and only if they share a common secret (possibly low-entropy) password. We present the first sPAKE protocol to simultaneously achieve the following properties: - only two exponentiations per party, the same as plain unauthenticated Diffie-Hellman key agreement (and likely optimal); - optimal round complexity: a single flow (one message from each party that can be sent in parallel) to achieve implicit authentication, or two flows to achieve explicit mutual authentication; - security in the random oracle model, rather than ideal cipher or generic group model; - UC security, rather than game-based. Our protocol is a generalization of the seminal EKE protocol of Bellovin & Merritt (S&P 1992). We also present a UC-secure 1-out-of-$N$ oblivious transfer (OT) protocol, for random payloads. Its communication complexity is independent of $N$, meaning that $N$ can even be exponential in the security parameter. Such a protocol can also be considered a kind of oblivious PRF (OPRF). Our protocol improves over the leading UC-secure 1-out-of-$N$ OT construction of Masny & Rindal (CCS 2019) for all $N>2$, and has essentially the same cost for $N=2$. The new technique underlying these results is a primitive we call programmable-once public function (POPF). Intuitively, a POPF is a function whose output can be programmed by one party on exactly one point. All other outputs of the function are outside of any party's control, in a provable sense. Update: dos Santos et al. (Eurocrypt 2023) showed that our POPF definition is not strong enough to prove security of EKE against a man-in-the-middle. See Januzelli et al. (Eurocrypt 2025) for a fixed POPF abstraction and EKE security proof.

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security. Our construction is based on the recent "split FHE" framework of Brakerski, Döttling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds \emph{and} that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudoradnom LWE samples using an encrypted pseudorandom function.

Often in cryptography one needs to make a consistent choice of square root in a finite field. We show that such a choice is equivalent to providing a reasonable sign function. Then we show that for $\mathbb{F}_{p^k}$ (with odd prime $p \neq 1$ and $k\neq 0$) such a sign function exists if and only if $k$ is odd.

Applied cryptographic protocols have to meet a rich set of security requirements under diverse environments and against diverse adversaries. However, currently used security specifications, based on either simulation (e.g., `ideal functionality' in UC) or games, are monolithic, combining together different aspects of protocol requirements, environment and assumptions. Such security specifications are complex, error-prone, and foil reusability, modular analysis and incremental design. We present the Modular Security Specifications (MoSS) framework, which cleanly separates the security requirements (goals) which a protocol should achieve, from the models (assumptions) under which each requirement should be ensured. This modularity allows us to reuse individual models and requirements across different protocols and tasks, and to compare protocols for the same task, either under different assumptions or satisfying different sets of requirements. MoSS is flexible and extendable, e.g., it can support both asymptotic and concrete definitions for security. So far, we confirmed the applicability of MoSS to two applications: secure broadcast protocols and PKI schemes.

Blockchain is a multiparty protocol to reach agreement on the order of events, and to record them consistently and immutably without centralized trust. In some cases, however, the blockchain can benefit from some controlled mutability. Examples include removing private information or unlawful content, and correcting protocol vulnerabilities which would otherwise require a hard fork. Two approaches to control the mutability are: moderation, where one or more designated administrators can use their private keys to approve a redaction, and voting, where miners can vote to endorse a suggested redaction. In this paper, we first present several attacks against existing redactable blockchain solutions. Next, we provide a definitional framework for moderated redactable blockchains. Finally, we propose a provable and efficient construct, which applies a single digital signature per redaction, achieving a much simpler and secure result compared to the prior art in the moderated setting.

The Number Theoretic Transform (NTT) is a critical sub-block used in several structured lattice-based schemes, including Kyber and Dilithium, which are finalist candidates in the NIST's standardization process for post-quantum cryptography. The NTT was shown to be susceptible to single trace side-channel attacks by Primas et al. in CHES 2017 and Pessl et al. in Latincrypt 2019 who demonstrated full key recovery from single traces on the ARM Cortex-M4 microcontroller. However, the cost of deploying suitable countermeasures to protect the NTT from these attacks on the same target platform has not yet been studied. In this work, we propose novel shuffling and masking countermeasures to protect the NTT from such single trace attacks. Firstly, we exploit arithmetic properties of twiddle constants used within the NTT computation to propose efficient and generic masking strategies for the NTT with configurable SCA resistance. Secondly, we also propose new variants of the shuffling countermeasure with varying granularity for the NTT. We perform a detailed comparative evaluation of the runtime performances for our proposed countermeasures within open source implementations of Kyber and Dilithium from the pqm4 library on the ARM Cortex-M4 microcontroller. Our proposed countermeasures yield a reasonable overhead in the range of 7%-78% across all procedures of Kyber, while the overheads are much more pronounced for Dilithium, ranging from 12%-197% for the key generation procedure and 32%-490% for the signing procedure.

Although large numbers of hardware and software implementations have been proposed to accelerate lattice-based cryptography, Saber, a module-LWR-based algorithm, which has advanced to second round of the NIST standardization process, has not been adequately supported by the current solutions. Based on these motivations, a high-performance crypto-processor is proposed based on an algorithm-hardware co-design in this paper. First, a hierarchical Karatsuba calculating framework, a hardware-efficient Karatsuba scheduling strategy and an optimized circuit structure are utilized to enable high-throughput polynomial multiplication. Furthermore, a task-level pipeline and truncated multipliers are proposed to enable algorithm-specific fine-grained processing. Enabled by all of the above optimizations, Avalon takes 943, 1156, and 408 clock cycles for key generation, encryption, and decryption, respectively. Enabled by these optimizations, our processor takes 943, 1156 and 408 clock cycles for key generation, encryption, and decryption of Saber768, achieving 5.4x, 5.2x and 4.2x reductions compared with the state-of-the-art FPGA solutions, respectively. The post-layout simulation of our design is implemented with TSMC 40nm CMOS process within 0.35 mm2. The throughput for Saber768 is up to 346k encryption operations per second and the energy efficiency is 0.12uJ/encryption while operating at 400MHz, achieving nearly 52x improvement and 30x improvement, respectively compared with current PQC hardware solutions.

We examine the security of the Australian card payment system by analysing existing cryptographic protocols. In this analysis, we examine TDES and DES-V key derivation and the use of secure cryptographic devices, then contrast this with alternative mechanisms to enable secure card payments. We compare current Australian cryptographic methods with their international counterparts, such as the ANSI methods, and then motivate alternative methods for authenticated encryption in card payment systems.

Komargodski et.al. introduced {\em Evolving Secret Sharing} which allows an imaprtial participant, called \emph{dealer}, to share a secret among unbounded number of participants over any given access structure. In their construction for evolving secret sharing over general access structure, the size of share of the $i^{th}$ participant happens to be exponential $(\mathcal{O}(2^{i-1}))$. They also provided constructions for $(k,\infty)$ threshold secret sharing. We consider the problem of evolving secret sharing with $t$ essential participants, namely, over $t$-$(k,\infty)$ access structure, a generalization of $(k,\infty)$ secret sharing $(t=0)$. We further generalize this access structure to a possible case of unbounded number of essential participants and provide a construction for secret sharing on it. Both the constructions are information theoretically secure and reduce the share size of the construction due to Komargodski et.al. over general access structure, exponentially. Moreover, the essential participants receive ideal (and hence, optimal) shares in the first construction.

In this paper, we revisit the difference enumeration technique for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks. In the original difference enumeration attack framework, an inevitable step is to precompute and store a set of intermediate state differences for efficient checking via the binary search. Our first observation is that Bar-On et al.'s general algebraic technique developed for SPNs with partial nonlinear layers can be utilized to fulfill the same task, which can make the memory complexity negligible as there is no need to store a huge set of state differences any more. Benefiting from this technique, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. at ToSC 2018. Combining both techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative third-round candidate in NIST's Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a concrete LowMC instance. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor cipher LowMC-M as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed $2^{64}$ data. The above mentioned attacks are all achieved with negligible memory.

We propose RANDCHAIN, a Decentralised Randomness Beacon (DRB) that is the first to achieve both scalability (i.e., a large number of participants can join) and fairness (i.e., each participant controls comparable power on deciding random outputs). Unlike existing DRBs where participants are collaborative, i.e., aggregating their local entropy into a single output, participants in RANDCHAIN are competitive, i.e., competing with each other to generate the next output. The competitive design reduces the communication complexity from at least O(n2) to O(n) without trusted party, breaking the scalability limit in existing DRBs. To build RANDCHAIN, we introduce Sequential Proof-of-Work (SeqPoW), a cryptographic puzzle that takes a random and unpredictable number of sequential steps to solve. We implement RANDCHAIN and evaluate its performance on up to 1024 nodes, demonstrating its superiority (1.3 seconds per output with a constant bandwidth of 200KB/s per node) compared to state-of-the-art DRBs RandHerd (S&P’18) and HydRand (S&P’20).

This note describes several attacks on the MALICIOUS framework for creating backdoored tweakable block ciphers. It is shown that, although the embedded malicious tweak pair itself is hard to recover, it is feasible to find additional weak tweak pairs that can be used to mount key-recovery attacks. Full-round attacks on most instances of LowMC-M are given. Our attacks are far from optimized and significant future improvements are to be expected. We focus on low-data attacks, since these are the most relevant for typical use-cases of LowMC. In addition, this implies that our attacks can not be prevented by limiting the amount of data that can be encrypted using the weak tweak pair. Despite our findings, we believe that the MALICIOUS framework can be used to create backdoored variants of LowMC provided that the parameters are modified.

In this paper we show that deep learning can be used to identify the shape of power traces corresponding to the responses of a protected arbiter PUF implemented in FPGAs. To achieve that, we combine power analysis with bitstream modification. We train a CNN classifier on two 28nm XC7 FPGAs implementing 128-stage arbiter PUFs and then classify the responses of PUFs from two other FPGAs. We demonstrate that it is possible to reduce the number of traces required for a successful attack to a single trace by modifying the bitstream to replicate PUF responses.

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions --- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on AES-MMO, AES-MP, and the first classical collision attacks on 4- and 5-round Grostl-512. Interestingly, the use of non-full-active super S-box differentials in the analysis of AES-MMO gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on AES-MMO and AES-MP (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity. To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

We give new, fully-quantitative and concrete bounds that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level. Prior work gave reductions of both protocols' security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical parameters. Adapting techniques by Cohn-Gordon et al. (Crypto 2019), we give reductions for SIGMA and TLS 1.3 to the strong Diffie-Hellman problem which are tight. Leveraging our tighter bounds, we meet the protocols' targeted security levels when instantiated with standardized curves and improve over prior bounds by up to over 90 bits of security across a range of real-world parameters.

Contact tracing is an effective tool in controlling the spread of infectious diseases such as COVID-19. It involves digital monitoring and recording of physical proximity between people over time with a central and trusted authority, so that when one user reports infection, it is possible to identify all other users who have been in close proximity to that person during a relevant time period in the past and alert them. One way to achieve this involves recording on the server the locations, e.g. by reading and reporting the GPS coordinates of a smartphone, of all users over time. Despite its simplicity, privacy concerns have prevented widespread adoption of this method. Technology that would enable the "hiding" of data could go a long way towards alleviating privacy concerns and enable contact tracing at a very large scale. In this article we describe a general method to hide data. By hiding, we mean that instead of disclosing a data value x, we would disclose an "encoded" version of x, namely E(x), where E(x) is easy to compute but very difficult, from a computational point of view, to invert. We propose a general construction of such a function E and show that it guarantees perfect recall, namely, all individuals who have potentially been exposed to infection are alerted, at the price of an infinitesimal number of false alarms, namely, only a negligible number of individuals who have not actually been exposed will be wrongly informed that they have.

With the emergence of the Industrial Internet of Things (IIoT), numerous operations based on smart devices contribute to producing convenience and comfortable applications for individuals and organizations. Considering the untrusted feature of the communication channels in IIoT, it is essential to ensure the authentication and incontestableness of the messages transmitted in the IIoT. In this paper, we firstly proposed a certificate-based parallel key-insulated aggregate signature (CB-PKIAS), which can resist the fully chosen-key attacks. Concretely, the adversary who can obtain the private keys of all signers in the system is able to forge a valid aggregate signature by using the invalid single signature. Furthermore, our scheme inherits the merits of certificate-based and key-insulated to avoid the certificate management problem, key escrow problems as well as the key exposures simultaneously. In addition, the rigorous analysis and the concrete simulation experiment demonstrated that our proposed scheme is secure under the random oracle and more suitable for the IIoT environment.

This paper presents the first functional encryption schemes for quadratic functions (or degree-2 polynomials) achieving simulation-based security in the semi-adaptive model with constant-size secret key. The unique prior construction with the same security guarantee by Gay [PKC 20] has secret keys of size linear in the message size. They also enjoy shorter ciphertexts: - our first scheme is based on bilateral DLIN (decisional linear) assumption as Gay's scheme and the ciphertext is 15% shorter; - our second scheme based on SXDH assumption and bilateral DLIN assumption is more efficient; it has 67% shorter ciphertext than previous SXDH-based scheme with selective indistinguishability security by Baltico et al. [CRYPTO 17]; the efficiency is comparable to their second scheme in the generic group model. Technically, we roughly combine Wee's ``secret-key-to-public-key'' compiler [TCC 17] with Gay's paradigm [PKC 20]. We avoid (partial) function-hiding inner-product functional encryption used in Gay's work and make our schemes conceptually simpler.

ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR, which achieve the best software performances in low-end microcontrollers. To evaluate the resistance of an ARX cipher against differential cryptanalysis and its variants, the recent automated methods employ constraint satisfaction solvers, such as SMT solvers, to search for optimal characteristics. The main difficulty to formulate this search as a constraint satisfaction problem is obtaining the differential models of the non-linear operations, that is, the constraints describing the differential probability of each non-linear operation of the cipher. While an efficient bit-vector differential model was obtained for the modular addition with two variable inputs, no differential model for the modular addition by a constant has been proposed so far, preventing ARX ciphers including this operation from being evaluated with automated methods. In this paper, we present the first bit-vector differential model for the n-bit modular addition by a constant input. Our model contains O(log_2(n)) basic bit-vector constraints and describes the binary logarithm of the differential probability. We also represent an SMT-based automated method to look for differential characteristics of ARX, including constant additions, and we provide an open-source tool ArxPy to find ARX differential characteristics in a fully automated way. To provide some examples, we have searched for related-key differential characteristics of TEA, XTEA, HIGHT, and LEA, obtaining better results than previous works. Our differential model and our automated tool allow cipher designers to select the best constant inputs for modular additions and cryptanalysts to evaluate the resistance of ARX ciphers against differential attacks.

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [ePrint 2020], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes --- specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a relaxed assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle.

Anonymous veto networks (AV-nets), originally proposed by Hao and Zielinski (2006), are particularly lightweight protocols for evaluating a veto function in a peer-to-peer network such that anonymity of all protocol participants is preserved. Prior to this work, anonymity in all AV-nets from the literature relied on the decisional Diffie-Hellman (DDH) assumption and can thus be broken by (scalable) quantum computers. In order to defend against this threat, we propose two practical and completely lattice-based AV-nets. The first one is secure against passive and the second one is secure against active adversaries. We prove that anonymity of our AV-nets reduces to the ring learning with errors (RLWE) assumption. As such, our AV-nets are the first ones with post-quantum anonymity. We also provide performance benchmarks to demonstrate their practicality.

This paper proposes new Polynomial IOPs for arithmetic circuits. They rely on the monomial coefficient basis to represent the matrices and vectors arising from the arithmetic constraint satisfaction system, and build on new protocols for establishing the correct computation of linear algebra relations such as matrix-vector products and Hadamard products. Our protocols give rise to concrete proof systems with succinct verification when compiled down with a cryptographic compiler whose role is abstracted away in this paper. Depending only on the compiler, the resulting SNARKs are either transparent or rely on a trusted setup.

Permissionless distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints on the resources available to an adversary relative to the resources of the participants that follow the protocol. Given their permissionless participation convention and their intended long-livedness, a critical open security question is their behavior---and potential resilience---to temporary spikes in adversarial resources. In this work we give the first thorough treatment of the self-healing properties of Nakamoto ledgers, addressing both proof-of-work (PoW) and proof-of-stake (PoS) protocols. First, we present a unified model that allows us to define self-healing for both of these protocol classes. Then we provide a formal analysis establishing self-healing with respect to both consistency and liveness in both classes, quantifying the resulting vulnerability period as a function of the magnitude of the spike. Finally, we provide numerical simulations giving explicit quantitative bounds relevant for practice.