Due to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantum-secure signature proposal LegRoast. However, its security is not yet extensively studied. The Legendre PRF computes for a key $k$ on input $x$ the Legendre symbol $L_k(x) = \left( \frac {x+k} {p} \right)$ in some finite field $\F_p$. As standard notion, PRF security is analysed by giving an attacker oracle access to $L_k(\cdot)$. Khovratovich's collision-based algorithm recovers $k$ using $L_k(\cdot)$ in time $\sqrt{p}$ with constant memory. It is a major open problem whether this birthday-bound complexity can be beaten. We show a somewhat surprising wide-ranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting. More precisely, we present a small memory multiple-key attack on $m$ Legendre keys $k_1, \ldots, k_m$ in time $\sqrt{mp}$, i.e. with amortized cost $\sqrt{p/m}$ per key. This multiple-key attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker's profit. Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public $p$ only -- and not on a key $k$. Namely, an attacker may compute e.g. in precomputation time $p^{\frac 2 3}$ a hint of size $p^{\frac 1 3}$. On receiving access to $L_k(\cdot)$ in an online phase, the attacker then uses the hint to recover the desired key $k$ in time only $p^{\frac 1 3}$. Thus, the attacker's online complexity again beats the birthday-bound. In addition, our precomputation attack can also be combined with our multiple-key attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking $m$ keys one may spend time $mp^{\frac 2 3}$ in the precomputation phase for constructing a hint of size $m^2 p^{\frac 1 3}$. In an online phase, one then finds {\em all $m$ keys in total time} only $p^{\frac 1 3}$. Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy key-independent precomputation pays off.

It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings $R[G]$, where $R$ is a commutative ring and $G$ is a non-abelian group, are examples of non-commutative rings that satisfy these conditions.

With the introduction of the division trail, the bit-based division property (BDP) has become the most efficient method to search for integral distinguishers. The notation of the division trail allows us to automate the search process by modelling the propagation of the DBP as a set of constraints that can be solved using generic Mixed-integer linear programming (MILP) and SMT/SAT solvers. The current models for the basic operations and Sboxes are efficient and accurate. In contrast, the two approaches to model the propagation of the BDP for the non-bit-permutation linear layer are either inaccurate or inefficient. The first approach relies on decomposing the matrix multiplication of the linear layer into COPY and XOR operations. The model obtained by this approach is efficient, in terms of the number of the constraints, but it is not accurate and might add invalid division trails to the search space, which might lead to missing the balanced property of some bits. The second approach employs a one-to-one map between the valid division trails through the primitive matrix represented the linear layer and its invertible sub-matrices. Despite the fact that the current model obtained by this approach is accurate, it is inefficient, i.e., it produces a large number of constraints for large linear layers like the one of Kuznyechik. In this paper, we address this problem by utilizing the one-to-one map to propose a new MILP model and a search procedure for large non-bit-permutation layers. As a proof of the effectiveness of our approach, we improve the previous 3- and 4-round integral distinguishers of Kuznyechik and the 4-round one of PHOTON's internal permutation ($P_{288}$). We also report, for the fist time, a 4-round integral distinguisher for Kalyna block cipher and a 5-round integral distinguisher for PHOTON's internal permutation ($P_{288}$).

Offline deniability is the ability to a-posteriori deny having participated in a particular communication session. This property has been widely assumed for the Signal messaging application, yet no formal proof has appeared in the literature. In this paper, we present what we believe is the first formal study of the offline deniability of the Signal protocol. Our analysis shows that building a deniability proof for Signal is non-trivial and requires strong assumptions on the underlying mathematical groups where the protocol is run. To do so, we study various *implicitly authenticated* key exchange protocols including MQV, HMQV and 3DH/X3DH, the latter being the core key agreement protocol in Signal. We first present examples of mathematical groups where running MQV results in a provably non-deniable interaction. While the concrete attack applies only to MQV, it also exemplifies the problems in attempting to prove the deniability of other implicitly authenticated protocols, such as 3DH. In particular, it shows that the intuition that the minimal transcript produced by these protocols suffices for ensuring deniability does not hold. We then provide a characterization of the groups where deniability holds, defined in terms of a knowledge assumption that extends the Knowledge of Exponent Assumption (KEA). We conclude the paper by showing two additional positive results. The first is a general theorem that links the deniability of a communication session to the deniability of the key agreement protocol starting the session. This allows us to extend our results on the deniability of 3DH/X3DH to the entire Signal communication session.

We present advancements for interactive arguments with Hydra, a novel verifiable computation system. Hydra introduces two new disjoint interactive argument scheme protocols geared towards the efficient pipelining of circuit verification. The first is specific to subcircuits, where a deep circuit is broken up into smaller parts and proven concurrently. The second is a more general scheme where all layers of the circuit can be proven in parallel, removing the dependency on the layer-wise synchronous execution of the protocol. Compared to non-interactive SNARKs which rely on knowledge type assumptions (or the Random Oracle model) and theoretical non-interactive arguments based on standard assumptions that are not useful in practice, Hydra achieves a sweet spot with a practical approach. From standard assumptions, Hydra collapses the round complexity to polylogarithmic to the width of the circuit, but only incurs polylogarithmic blowup in bandwidth and verifier time complexity. We implement the full verification flow, including both protocols and a logic parser used to convert traditional logic circuit compilation outputs into provable layered arithmetic representations. We perform experimental evaluations of our proposals and demonstrate protocol time efficiency improvements of up to 34.8 times and 4.3 times respectively compared to traditional approaches on parallel hardware.

Using passwords for authentication has been proven vulnerable in countless security incidents. Hardware authentication tokens effectively prevent most password-related security issues and improve security indisputably. However, we would like to highlight that there are new threats from attackers with physical access which need to be discussed. Supply chain adversaries may manipulate devices on a large scale and install backdoors before they even reach end users. In evil maid scenarios, specific devices may even be attacked while already in use. Hence, we thoroughly investigate the security and trustworthiness of eight commercially available open source authentication tokens, including devices from the two market leaders: SoloKeys and Nitrokey. Unfortunately, we identify and practically verify significant vulnerabilities in all eight examined tokens. Some of them based on severe, previously undiscovered, vulnerabilities of three major microcontroller products which are used at a large scale in various products. Our findings clearly emphasize the significant threat from supply chain and evil maid scenarios since the attacks are practical and only require moderate attacker efforts. Fortunately, we are able to describe software-based countermeasures as effective improvements to retrofit the examined devices. To improve the security and trustworthiness of future authentication tokens, we also derive important general design recommendations.

Digital signatures have been widely used as building blocks for constructing complex cryptosystems. To facilitate the security analysis of a complex system, we expect the underlying building blocks to achieve desirable composability. Notably, Canetti (FOCS 2001) and then Maurer et al (TCC 2004) propose analysis frameworks, the Universal Composability framework for cryptographic protocols, and the indifferentiability framework for cryptographic objects. In this paper, we develop a “lifting strategy”, which allows us to compile multiple existing practical signature schemes using cyclic group (e.g., Schnorr, Boneh-Boyen), to achieve a very stringent security guarantee, in an idealized model of the generic (bilinear) group, without introducing much extra efficiency loss. What's more interesting is that, in our design, even the involved idealized model does not exist, our compiled construction will still be able to achieve the classical notion of unforgeability. To achieve both indifferentiability and good efficiency, we develop new techniques in generic (bilinear) group model.

Cryptographic accumulators are a crucial building block for a variety of applications where you need to represent a set of elements in a compact format while still being able to provide proofs of (non)membership. In this work, we give a number of accumulator constructions for the bilinear pairing setting in the trapdoor-based scenario, where a trusted manager maintains the accumulator. Using modular accumulator techniques, we first present the first optimally efficient (in terms of communication cost) dynamic, positive accumulators in the pairing setting. Additionally, we present a novel modular approach to construct universal accumulators that avoid costly non-membership proofs. We instantiate our generic construction and present the first universal accumulator in the bilinear pairing setting, that achieves constant parameter size, constant cost for element additions/deletions and witness generation by the manager, constant witness updates by the users and constant (non)membership verification. We finally show how our proposed universal accumulator construction can give rise to efficient ZK accumulators with constant non-membership witness updates.

In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and $\textit{reusable}$ IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are $\textit{stateless}$ and $\textit{locally computable at the optimal rate}$, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use. Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports $\textit{everlasting privacy}$ and $\textit{post-application security}$ of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model. Both of these results come from nearly optimal constructions of so called $\textit{doubly-affine extractors}$: locally-computable, seeded extractors $\textbf{Ext}$(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may $\textit{adaptively depend}$ on the extracted key R = $\textbf{Ext}$(X, S); and (b) the seed S is only $\textit{computationally}$ secure. Neither of properties are possible with general-leakage extractors.

The private simultaneous messages (PSM) model is a non-interactive version of the multiparty secure computation (MPC), which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum message from the private input $x_i$ and the shared random string (entangled states), and then sends it to the referee $R$. Receiving the messages from the $k$ parties, $R$ computes $F(x_1,\ldots,x_k)$ from the messages. Then, $R$ learns nothing except for $F(x_1,\ldots,x_k)$ as the privacy condition. We obtain the following results for this PSQM model. ($i$) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz [Journal of Cryptology 33(3), 916--953 (2020)]. In particular, we prove a lower bound $(3-o(1))n$ of the communication complexity in PSQM protocols with a shared random string for random Boolean functions of $2n$-bit input, which is larger than the trivial upper bound $2n$ of the communication complexity without the privacy condition. ($ii$) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. ($iii$) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

Symmetric-key cryptography is used widely due to its capability to provide a strong defense against diverse attacks; however, it is prone to cryptanalysis attacks. Therefore, we propose a novel and highly secure symmetric-key cryptography, symKrypt for short, to defend against diverse attacks and provide absolute security. Our proposed algorithm changes private keys in each block of communication, i.e., symKrypt uses multiple private keys to encrypt a single block of a message. Moreover, symKrypt keeps secret the bit mixing of the original message with the private keys. Also, the number of private keys is kept secret. In addition, the private keys are generated dynamically based on the initial inputs using a pseudo-random number generator which is highly unpredictable and secure. In this article, we theoretically analyze the capabilities of symKrypt and provide experimental demonstration using millions of private keys to prove its correctness. Furthermore, we demonstrate the proposed pseudo-random number generator algorithm experimentally in NIST SP 800-22 statistical test suite. Our propose pseudo-random number generator passes all 15 tests in the said test suite. symKrypt is the first model to use multiple private keys in encryption yet lightweight and powerful.

Unlike traditional and/or standardized ciphers, TFHE offers much space for the setup of its parameters. Not only the parameter choice affects the plaintext space size and security, it also greatly impacts the performance of TFHE, in particular, its bootstrapping. In this paper, we provide an exhaustive description of TFHE, including its foundations, (functional) bootstrapping and error propagation during all operations. In addition, we outline a bootstrapping scenario without the key switching step. Based on our thorough summary, we suggest an approach for the setup of TFHE parameters with particular respect to bootstrapping efficiency. Finally, we propose twelve setups of real-world TFHE parameters for six different scenarios with and without key switching, respectively, and we compare their performance. N.b.: This is a technical paper, which is mainly intended for researchers interested in TFHE. However, due to its self-containment, it shall be accessible also for readers with a basic knowledge of TFHE.

This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.

We present the Internet Computer Consensus (ICC) family of protocols for atomic broadcast (a.k.a., consensus), which underpin the Byzantine fault-tolerant replicated state machines of the Internet Computer. The ICC protocols are leader-based protocols that assume partial synchrony, and that are fully integrated with a blockchain. The leader changes probabilistically in every round. These protocols are extremely simple and robust: in any round where the leader is corrupt (which itself happens with probability less than $1/3$), each ICC protocol will effectively allow another party to take over as leader for that round, with very little fuss, to move the protocol forward to the next round in a timely fashion. Unlike in many other protocols, there are no complicated subprotocols (such as "view change'' in PBFT) or unspecified subprotocols (such as "pacemaker'' in HotStuff). Moreover, unlike in many other protocols (such as PBFT and HotStuff), the task of reliably disseminating the blocks to all parties is an integral part the protocol, and not left to some other unspecified subprotocol. An additional property enjoyed by the ICC protocols (just like PBFT and HotStuff, and unlike others, such as Tendermint) is optimistic responsiveness, which means that when the leader is honest, the protocol will proceed at the pace of the actual network delay, rather than some upper bound on the network delay. We present three different protocols (along with various minor variations on each). One of these protocols (ICC1) is designed to be integrated with a peer-to-peer gossip sub-layer, which reduces the bottleneck created at the leader for disseminating large blocks, a problem that all leader-based protocols, like PBFT and HotStuff, must address, but typically do not. Our Protocol ICC2 addresses the same problem by substituting a low-communication reliable broadcast subprotocol (which may be of independent interest) for the gossip sub-layer.

Decentralized token exchanges allow for secure trading of tokens without a trusted third party. However, decentralization is mostly achieved at the expense of transaction privacy. For a fair exchange, transactions must remain private to hide the participants and volumes while maintaining the possibility for non-interactive execution of trades. In this paper we present a swap confidential transaction system (SwapCT) which is related to ring confidential transactions (e.g. used in Monero) but supports multiple token types to trade among and enables secure, partial transactions for non-interactive swaps. We prove that SwapCT is secure in a strict, formal model and present its efficient performance in a prototype implementation with logarithmic signature sizes for large anonymity sets. For our construction we design an aggregatable signature scheme which might be of independent interest. Our SwapCT system thereby enables a secure and private exchange for tokens without a trusted third party.

We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.

Blockchain is a disruptive technology that promises a multitude of benefits such as transparency, traceability, and immutability. However, this unique bundle of key characteristics rapidly proved to be a double-edged sword that can put user privacy at risk. Unlike traditional systems, Bitcoin transactions are publicly and permanently recorded, and anyone can access the full history of the records. Despite using pseudonymous identities, an adversary can undermine the financial privacy of users and reveal their actual identities using advanced heuristics and techniques to identify eventual links between transactions, senders, receivers, and consumed services (e.g., online purchases). In this regard, a multitude of approaches has been proposed in an attempt to overcome financial transparency and enhance user anonymity. These techniques range from using mixing services to off-chain transactions and address different privacy issues. In this survey, we particularly focus on comparing and evaluating mixing techniques in the Bitcoin blockchain, present their limitations, and highlight the new challenges.

For applications of Byzantine fault tolerant (BFT) consensus protocols where the participants are economic agents, recent works highlighted the importance of accountability: the ability to identify participants who provably violate the protocol. At the same time, being able to reach consensus under dynamic levels of participation is desirable for censorship resistance. We identify an availability-accountability dilemma: in an environment with dynamic participation, no protocol can simultaneously be accountably-safe and live. We provide a resolution to this dilemma by constructing a provably secure optimally-resilient accountability gadget to checkpoint a longest chain protocol, such that the full ledger is live under dynamic participation and the checkpointed prefix ledger is accountable. Our accountability gadget construction is black-box and can use any BFT protocol which is accountable under static participation. Using HotStuff as the black box, we implemented our construction as a protocol for the Ethereum 2.0 beacon chain, and our Internet-scale experiments with more than 4000 nodes show that the protocol achieves the required scalability and has better latency than the current solution Gasper, which was shown insecure by recent attacks.

Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server. Registries must be audited to ensure global invariants are preserved, which, in turn, allows for efficient monitoring of individual registry entries by their owners. To this end, existing proposals either assume trusted third-party auditors or rely on incrementally verifiable computation (IVC) via expensive recursive SNARKs to make registries client-auditable. In this work, we give new client-auditable verifiable registries with throughputs up to $100\times$ greater than baseline IVC solutions. Our approach relies on an authenticated dictionary based on RSA accumulators for which we develop a new constant-size invariant proof. We use this as a replacement for Merkle trees to optimize the baseline IVC approach, but also provide a novel construction which dispenses with SNARKs entirely. This latter solution adopts a new checkpointing method to ensure client view consistency.

In response to ongoing discussions about data usage by companies and governments, and its implications for privacy, there is a growing demand for secure communication techniques. While during their advent, most messenger apps focused on features rather than security, this has changed in the recent years: Since then, many have adapted end-to-end encryption as a standard feature. One of the most popular solutions is the Signal messenger, which aims to guarantee forward secrecy (i.e. security of previous communications in case of leakage of long-term secrets) and future secrecy (i.e. security of future communications in case of leakage of short-term secrets). If every user uses exactly one device, it is known that Signal achieves forward secrecy and even post-compromise security (i.e. security of future communications in case of leakage of long-term secrets). But the Signal protocol also allows for the use of multiple devices via the Sesame protocol. This multi-device setting is typically ignored in the security analysis of Signal. In this work, we discuss the security of the Signal messenger in this multi-device setting. We show that the current implementation of the device registration allows an attacker to register an own, malicious device, which gives them unrestricted access to all future communication of their victim, and even allows full impersonation. This directly shows that the current Signal implementation does not guarantee post-compromise security. We discuss several countermeasures, both simple ones aiming to increase detectability of our attack, as well as a broader approach that seeks to solve the root issue, namely the weak device registration flow.

Plactic key agreement is a new key agreement scheme that uses Knuth’s multiplication of semistandard tableaus from combinatorial algebra. The security of plactic key agreement relies on the difficulty of some computational problems, such as division of semistandard tableaus. Division by erosion uses backtracking to divide tableaus. Division by erosion is estimated to be infeasible against public keys of 768 or more bytes. If division by erosion is the best attack against plactic key agreement, then secure plactic key agreement could be practical. Chris Monico found a new attack on plactic key agreement, which is fast, potentially polynomial-time, and could very well make plactic key agreement insecure.

Correlated random variables are a key tool in cryptographic applications like secure multi-party computation. We investigate the power of a class of correlations that we term group correlations: A group correlation is a uniform distribution over pairs $(x,y) \in G^2$ such that $x+y\in S$, where $G$ is a (possibly non-abelian) group and $S$ is a subset of $G$. We also introduce bi-affine correlations and show how they relate to group correlations. We present several structural results, new protocols, and applications of these correlations. The new applications include a completeness result for black-box group computation, perfectly secure protocols for evaluating a broad class of black box ``mixed-groups'' circuits with bi-affine homomorphism, and new information-theoretic results. Finally, we uncover a striking structure underlying OLE: In particular, we show that OLE over $\mathrm{GF}(2^n)$, is isomorphic to a group correlation over $\mathbb{Z}_4^n$.

Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can simply be discarded and are no longer stored by any miner. We show that all miners can be light miners with no harm to security. Our protocol is based on the notion of superblocks, blocks that have achieved an unusually high difficulty. We leverage them to represent underlying proof-of-work without ever illustrating it, storing it, or transmitting it. After our pruning is applied, the storage and communication requirements for consensus data is reduced exponentially. We develop new probabilistic mathematical methods to analyze our protocol in the random oracle model. We prove our protocol is both secure and succinct under an uninterrupted honest majority assumption for $1/3$ adversaries. Our protocol is the first to achieve always secure, always succinct, and online Non-Interactive Proofs of Proof-of-Work, all necessary components for a logarithmic space mining scheme. Our work has applications beyond mining and also constitutes an improvement in state-of-the-art superlight clients and cross-chain bridges.

Symmetric key cryptography is applied in almost all secure communications to protect all sensitive information from attackers, for instance, banking, and thus, it requires extra attention due to diverse applications. Moreover, it is vulnerable to various attacks, for example, cryptanalysis attacks. Cryptanalysis attacks are possible due to a single-keyed encryption system. The state-of-the-art symmetric communication protocol uses a single secret key to encrypt/decrypt the entire communication to exchange data/message that poses security threats. Therefore, in this paper, we present a new secure communication protocol based on Diffie-Hellman cryptographic algorithms, called Stealth. It is a symmetric-key cryptographic protocol to enhance the security of modern communication with truly random numbers. Additionally, it applies a pseudo-random number generator. Initially, Stealth uses the Diffie-Hellman algorithm to compute four shared secret keys. These shared secret keys are used to generate four different private keys to encrypt for the first block of the message for symmetric communication. Stealth changes its private keys in each communication, making it very hard to break the security protocol. Moreover, the four shared secret keys create additional complexity for the adversary to overcome, and hence, it can provide highly tight security in communications. Stealth neither replaces the existing protocol nor authentication mechanism, but it creates another security layer to the existing protocol to ensure the security measurement's tightness.

In this paper, we consider the problem of cross-chain transactions where parties that do not trust each other safely exchange digital assets across blockchains. Open blockchains models are decentralized ledgers that keep records of transactions. They are comparable with distributed account books. While they have proven their potential as a store of value, exchanging assets across several blockchains remains a challenge. Our paper proposes a new protocol, R-SWAP, for cross-chain swaps that outperforms existing solutions. Our protocol is built on top of two abstractions: relays and adapters that we formalize for the first time in this paper. Furthermore, we prove the correctness of R-SWAP and analytically evaluate its performances, in terms of cost and latency. Moreover, we evaluate the performances of R-SWAP in two case studies showing the generality of our approach: atomic swaps between Ethereum and Bitcoin (two popular permissionless blockchains) and atomic swaps between Ethereum and Tendermint (one permissionless and one permissioned blockchain).

This paper presents method for transformation of algebraic equations of symmetric cipher into the QUBO problem. After transformation of given equations $f_1, f_2, \dots, f_n$ to equations over integers $f'_1, f'_2, \dots, f'_n$, one has to linearize each, obtaining $f'_{lin_i}=lin(f'_i)$, where $lin$ denotes linearization operation. Finally, one can obtain problem in the QUBO form as $\left( f'_{lin_1} \right)^2+\dots+\left( f'_{lin_n} \right)^2+Pen$, where $Pen$ denotes penalties obtained during linearization of equations and $n$ is the number of equations. In this paper, we show examples of the transformation of some block ciphers to the QUBO problem. What is more, we present the results of the transformation of the full AES-128 cipher to the QUBO problem, where the number of variables of equivalent QUBO problem is equal to $237,915$, which means, at least theoretically, that problem may be solved using the D-Wave Advantage quantum annealing computer. Unfortunately, it is hard to estimate the time this process would require.

Cryptographic constructions based on $\textit{ring learning with errors}$ (RLWE) have emerged as one of the front runners for the standardization of post quantum public key cryptography. As the standardization process continues, optimizing specific parts of proposed schemes becomes a worthwhile endeavor. In this work we focus on using error correcting codes to alleviate a natural trade-off present in most schemes; namely, we would like a wider error distribution to increase security, but a wider error distribution comes at the cost of an increased probability of decryption error. The motivation of this work is to improve the security level of RLWE-based public key encryption (PKE) while keeping the target decryption failure rate (DFR) achievable using error-correcting codes. Specifically, we explore how to implement a family member of error correcting codes, known as polar codes, in RLWE-based PKE schemes in order to effectively lower the DFR. The dependency existing in the additive noise term is handled by mapping every error term (e.g., $e,t,s,e_1,e_2$) under canonical embedding to the space $H$ where a product in the number field $K$ gives rise to a coordinate-wise product in $H$. An attempt has been made to make the modulation constellation (message basis) fit in with the canonical basis. Furthermore, we exploit the actuality of some error terms known by the decoder to further lower the DFR. Using our method, the DFR is expected to be as low as $2^{-298}$ for code rate 0.25, $n=1024,q=12289$ and binomial parameter $k=8$ as is exactly the setting of the post-quantum scheme NewHope; DFR is $2^{-156}$ for code rate 0.25, $n=1024,q=12289,k=16$. This new DFR margin enables us to improve the security level by $9.4\%$ compared with NewHope. Moreover, polar encoding and decoding have quasi-linear complexity $O(N\log N)$ and they can be implemented in constant time.

Contact tracing has emerged as a powerful and effective measure to curb the spread of contagious diseases. It is a robust tool, but on the downside, it possesses a risk of privacy violations as contact tracing requires gathering a lot of personal information. So there is a need for a cryptographic primitive that obfuscate the personal data of the user. Taking everything into account, private set intersection seems to be the natural choice to address the problem. Nearly all of the existing PSI protocols are relying on the number theoretic assumption based hard problems. However, these problems are not secure in quantum domain. As a consequence, it becomes essential to designing PSI that can resist quantum attack and provide long-term security. One may apply quantum cryptography to develop such PSI protocol. This paper deals with the design of PSI using quantum cryptography (QC), where the security depends on the principles of basic quantum mechanics. Our scheme achieves long-term security and remains secure against quantum attacks due to the use of QC. As opposed to the existing quantum PSI protocols, the communication and computation costs of our scheme are independent of the size of universal set. In particular, the proposed protocol achieves optimal communication and computation costs in the domain of quantum PSI. Moreover, we require only single photon quantum resources and simple single-particle projective measurements, unlike most of the existing quantum PSI protocols.

Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Although their construction is information-theoretically secure, it is limited to the setting of one-time symmetric key encryption (SKE), where a sender and receiver have to share a common key in advance and the key can be used only once. Moreover, the sender has to generate a quantum state and send it to the receiver over a quantum channel in their construction. Although deletion certificates are privately verifiable, which means a verification key for a certificate has to be kept secret, in the definition by Broadbent and Islam, we can also consider public verifiability. In this work, we present various constructions of encryption with certified deletion. - Quantum communication case: We achieve (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE scheme with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE scheme with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function. These two schemes are privately verifiable. - Classical communication case: We also achieve PKE with certified deletion that uses only classical communication. We give two schemes, a privately verifiable one and a publicly verifiable one. The former is constructed assuming the LWE assumption in the quantum random oracle model. The latter is constructed assuming the existence of one-shot signatures and extractable witness encryption.

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt'19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

In this tutorial, we provide a brief overview of Concurrent Zero Knowledge and next present a simple proof of the existence of Concurrent Zero-knowledge arguments for N P based on one-way permutations.

In recent years, leakage-resilient cryptography---the design of cryptographic protocols resilient to bounded leakage of honest players' secrets---has received significant attention. A major limitation of known provably-secure constructions (based on polynomial hardness assumptions) is that they require the secrets to have sufficient actual (i.e., information-theoretic), as opposed to computational, min-entropy even after the leakage. In this work, we present barriers to provably-secure constructions beyond the ``information-theoretic barrier'': Assume the existence of collision-resistant hash functions. Then, no NP search problem with $(2^{n^{\epsilon}})$-bounded number of witnesses can be proven (even worst-case) hard in the presence of $O(n^{\epsilon})$ bits of computationally-efficient leakage of the witness, using a black-box reduction to any $O(1)$-round assumption. In particular, this implies that $O(n^{\epsilon})$-leakage resilient injective one-way functions, and more generally, one-way functions with at most $2^{n^{\epsilon}}$ pre-images, cannot be based on any ``standard'' complexity assumption using a black-box reduction.

Attribute-based conditional proxy re-encryption (AB-CPRE) allows delegators to carry out attribute-based control on the delegation of decryption by setting policies and attribute vectors. The fine-grained control of AB-CPRE makes it suitable for a variety of applications, such as cloud storage and distributed file systems. However, all existing AB-CPRE schemes are constructed under classical number-theoretic assumptions, which are vulnerable to quantum cryptoanalysis. Therefore, we propose the first AB-CPRE scheme based on the learning with errors (LWE) assumption. Constructed from fully key-homomorphic encryption (FKHE) and key-switching techniques, our scheme is unidirectional, single-hop, and enables a polynomial-deep boolean circuit as its policy. Furthermore, we split the ciphertext into two independent parts to avoid two-level or multi-level encryption/decryption mechanisms. Taking advantage of it, we then extend our single-hop AB-CPRE into an efficient and concise multi-hop one. No matter how many transformations are performed, the re-encrypted ciphertext is in constant size, and only one encryption/decryption algorithm is needed. Both of our schemes are proved to be selective secure against chosen-plaintext attacks (CPA) in the standard model.

Clustering is an unsupervised machine learning technique that outputs clusters containing similar data items. In this work, we investigate privacy-preserving density-based clustering which is, for example, used in financial analytics and medical diagnosis. When (multiple) data owners collaborate or outsource the computation, privacy concerns arise. To address this problem, we design, implement, and evaluate the first practical and fully private density-based clustering scheme based on secure two-party computation. Our protocol privately executes the DBSCAN algorithm without disclosing any information (including the number and size of clusters). It can be used for private clustering between two parties as well as for private outsourcing of an arbitrary number of data owners to two non-colluding servers. Our implementation of the DBSCAN algorithm privately clusters data sets with 400 elements in 7 minutes on commodity hardware. Thereby, it flexibly determines the number of required clusters and is insensitive to outliers, while being only factor 19x slower than today's fastest private K-means protocol (Mohassel et al., PETS'20) which can only be used for specific data sets. We then show how to transfer our newly designed protocol to related clustering algorithms by introducing a private approximation of the TRACLUS algorithm for trajectory clustering which has interesting real-world applications like financial time series forecasts and the investigation of the spread of a disease like COVID-19.

It is a well-known fact that the power consumption during certain stages of a cryptographic algorithm exhibits a strong correlation with the Hamming Weight of its underlying variables. This phenomenon has been widely exploited in the cryptographic literature in various attacks targeting a broad range of schemes such as block ciphers or public-key cryptosystems. A common way of breaking this correlation is through the inclusion of countermeasures involving additional randomness into the computation in the form of hidden (undisclosed) component functions or masking strategies that complicate the inference of any sensitive information from the gathered power traces. In this work, we revisit the tight correlation between the Hamming Weight and the observed power consumption of an algorithm and demonstrate, in the first part, a practical reverse-engineering attack of proprietary AES-like constructions with secret internal components like the SubBytes, MixColumns and ShiftRows functions. This approach is used in some commercial products such as the Dynamic Encryption package from the communication services provider Dencrypt as an extra layer of security. We recover the encryption key alongside the hidden substitution and permutation layer as well as the MixColumns matrix on both 8-bit and 32-bit architectures. In a second effort, we shift our attention to a masked implementation of AES, specifically the secAES proposal put forward by the French National Cybersecurity Agency (ANSSI) that concisely combines several side-channel countermeasure techniques. We show its insecurity in a novel side-channel-assisted statistical key-recovery attack that only necessitates a few hundreds of collected power traces.

A new ``Weighted Bit-flipping'' (WBF) iterative decoder is presented and analyzed with respect to its Decoding Failure Rate (DFR). We show that the DFR is indeed lower than that of the BGF decoder as suggested by the BIKE third round submission to the NIST PQC standardization process. The WBF decoder requires more iterations to complete than BGF, but by creating a hybrid decoder we show that a lower DFR compared to that of the BGF decoder can still be achieved while keeping the computational tradeoff to a minimum.

Frontrunning is a major problem in DeFi applications, such as blockchain-based exchanges. Albeit, existing solutions are not practical and/or they make external trust assumptions. In this work we propose a market-maker-based crypto-token exchange, which is both more efficient than existing solutions and offers provable resistance to frontrunning attack. Our approach combines in a clever way a game theoretic analysis of market-makers with new cryptography and blockchain tools to defend against all three ways by which an exchange might front-run, i.e., (1) reorder trade requests, (2) adaptively drop trade requests, and (3) adaptively insert (its own) trade requests. Concretely, we propose novel light- weight cryptographic tools and smart-contract-enforced incentives to eliminate reordering attacks and ensure that dropping requests have to be oblivious (uninformed) of the actual trade. We then prove that with these attacks eliminated, a so-called monopolistic market-maker has no longer incentives to add or drop trades. We have implemented and benchmarked our exchange and provide concrete evidence of its advantages over existing solutions.

Layering diverse cryptography is a general method to lower the risk of a future, or secret, cryptanalytic attack on a system. This report describes methods to quantifiably estimate this risk reduction. Diversity is especially helpful in forward security because future attackers have more time to discover new attacks, making attack independence of diverse cryptography the major contribution to risk reduction. Post-quantum security is a part of forward security. Estimates for highly sensitive data say that the security advantage of diverse layering is worth the extra usage cost, thus advising a decision to layer diverse cryptography.

We propose the first tight security proof for the ordinary two-message signed Diffie-Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie-Hellman assumption and the multi-user security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange. In contrast to a known tight three-message variant of the signed Diffie-Hellman protocol (Gjøsteen and Jager, CRYPTO 2018), we do not require any modification to the original protocol, and our tightness result is proven in the ``Single-Bit-Guess'' model which we know can be tightly composed with symmetric cryptographic primitives to establish a secure channel. Finally, we extend our approach to the group setting and construct the first tightly secure group authenticated key exchange protocol.

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC `97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC `14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity $q$ of the honest verifier, and the bound $q^*$ on the queries of a malicious verifier (i.e., $q=polylog(q^*)$), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when $q^*=q$, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely $q^*/q=O(sqrt(n))$ where $n$ is the input length. Our constructions combine the "MPC-in-the-head" technique (Ishai et al., STOC `07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.

We study the randomness complexity of interactive proofs and zero-knowledge proofs. In particular, we ask whether it is possible to reduce the randomness complexity, $R$, of the verifier to be comparable with the number of bits, $C_V$, that the verifier sends during the interaction. We show that such \emph{randomness sparsification} is possible in several settings. Specifically, unconditional sparsification can be obtained in the non-uniform setting (where the verifier is modelled as a circuit), and in the uniform setting where the parties have access to a (reusable) common-random-string (CRS). We further show that constant-round uniform protocols can be sparsified without a CRS under a plausible worst-case complexity-theoretic assumption that was used previously in the context of derandomization. All the above sparsification results preserve statistical-zero knowledge provided that this property holds against a \emph{cheating verifier}. We further show that randomness sparsification can be applied to honest-verifier statistical zero-knowledge (HVSZK) proofs at the expense of increasing the communication from the prover by $R-F$ bits, or, in the case of honest-verifier perfect zero-knowledge (HVPZK) by slowing down the simulation by a factor of $2^{R-F}$. Here $F$ is a new measure of \emph{accessible bit complexity} of an HVZK proof system that ranges from 0 to $R$, where a maximal grade of $R$ is achieved when zero-knowledge holds against a ``semi-malicious'' verifier that maliciously selects its random tape and then plays honestly. Consequently, we show that some classical HVSZK proof systems, like the one for the complete Statistical-Distance problem (Sahai and Vadhan, JACM 2003) admit randomness sparsification with no penalty. Along the way we introduce new notions of pseudorandomness against interactive proof systems, and study their relations to existing notions of pseudorandomness.

A classic approach to MPC uses preprocessed multiplication triples to evaluate arbitrary Boolean circuits. If the target circuit features conditional branching, e.g. as the result of a IF program statement, then triples are wasted: one triple is consumed per AND gate, even if the output of the gate is entirely discarded by the circuit's conditional behavior. In this work, we show that multiplication triples can be re-used across conditional branches. For a circuit with $b$ branches, each having $n$ AND gates, we need only a total of $n$ triples, rather than the typically required $b\cdot n$. Because preprocessing triples is often the most expensive step in protocols that use them, this significantly improves performance. Prior work similarly amortized oblivious transfers across branches in the classic GMW protocol (Heath et al., Asiacrypt 2020, [HKP20]). In addition to demonstrating conditional improvements are possible for a different class of protocols, we also concretely improve over [HKP20]: their maximum improvement is bounded by the topology of the circuit. Our protocol yields improvement independent of topology: we need triples proportional to the size of the program's longest execution path, regardless of the structure of the program branches. We implemented our approach in C++. Our experiments show that we significantly improve over a naive protocol and over prior work: for a circuit with $16$ branches and in terms of total communication, we improved over naive by $12\times$ and over [HKP20] by an average of $2.6\times$. Our protocol is secure against the semi-honest corruption of $p-1$ parties.

BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating a minority corruption, recently, in Crypto'19, a weaker synchrony assumption called mobile sluggish faults was introduced. In this work, we investigate the support for mobile sluggish faults in existing synchronous protocols such as Dfinity, Streamlet, Sync HotStuff, OptSync and the optimal latency BFT protocol. We identify key principles that can be used to ``compile'' these synchronous protocols to tolerate mobile sluggish faults.

We provide a new remote attestation scheme for secure processor technology, which is secure in the presence of an All Digital State Observing (ADSO) adversary. To accomplish this, we obfuscate session signing keys using a silicon Physical Unclonable Function (PUF) with an extended interface that combines the LPN-PUF concept with a repetition code for small failure probabilities, and we introduce a new signature scheme that only needs a message dependent subset of a session signing key for computing a signature and whose signatures cannot be successfully forged even if one subset per session signing key leaks. Our solution for remote attestation shows that results computed by enclaves can be properly verified even when an ADSO-adversary is present. For $N=2^l$ sessions, implementation results show that signing takes $934.9+0.6\cdot l$ ms and produces a signature of $8.2+0.03\cdot l$ KB, and verification by a remote user takes $118.2+0.4\cdot l$ ms. During initialization, generation of all session keys takes $819.3 \cdot N$ ms and corresponding storage is $3 \cdot 10^{-5} + 0.12 \cdot N$ MB.

We tackle the problems of private learning where an owner wishes to outsource a training task to an honest-but-curious server while keeping its data private, and private collaborative learning where two (or more) mutually distrusting owners outsource respective training data sets to an honest-but-curious server while keeping their data sets private from the server and each other. The privacy property we provide is information-theoretic in nature, Probably Approximately Correct (PAC) approximation resistance (abbreviated to PAC security). Each owner transforms its data and labels using a private transform. The server combines samples from each data set into expanded samples with corresponding expanded labels -- we refer to this step as Task Augmentation. The server can be used for inference by any owner by sending it transformed samples. Unlike most prior approaches, our transformed data approach maintains privacy for each entity, even in the case where the server colludes with all other entities. Importantly, we show the utility of collaborative learning typically exceeds the utility that can be achieved by any entity restricted to its own data set. Another important application we show is that the Task Augmentation approach can also be used in the single owner case by adding labeled, learnable noise to amplify privacy. This can be straightforwardly used to produce (Local) Differential Privacy ((L)DP) guarantees. We show that adding labeled noise as opposed to a conventional (L)DP additive noise mechanism significantly improves the privacy-utility tradeoff in private learning under the same setup.

Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring and module-based schemes such as Ring-LWE or Module-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversary’s benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor can be utilised to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an “easy” instance of SVP. It is important to note that the work on ideal SVP does not break Ring-LWE, since its security reduction is from worst case ideal SVP to average case Ring-LWE, and is one way.

We present Hyperproofs, the first vector commitment (VC) scheme that is efficiently maintainable and aggregatable. Similar to Merkle proofs, our proofs form a tree that can be efficiently maintained: updating all $n$ proofs in the tree after a single leaf change only requires $O(\log{n})$ time. Importantly, unlike Merkle proofs, Hyperproofs are efficiently aggregatable, anywhere from $10\times$ to $41\times$ faster than SNARK-based aggregation of Merkle proofs. At the same time, an individual Hyperproof consists of only $\log{n}$ algebraic hashes (e.g., 32-byte elliptic curve points) and an aggregation of $b$ such proofs is only $O(\log{(b\log{n})})$-sized. Hyperproofs are also reasonably fast to update when compared to Merkle trees with SNARK-friendly hash functions. As another benefit over Merkle trees, Hyperproofs are homomorphic: digests (and proofs) for two vectors can be homomorphically combined into a digest (and proofs) for their sum. Homomorphism is very useful in emerging applications such as stateless cryptocurrencies. First, it enables unstealability, a novel property that incentivizes proof computation. Second, it makes digests and proofs much more convenient to update. Finally, Hyperproofs have certain limitations: they are not transparent, have linear-sized public parameters, are slower to verify, and have larger aggregated proofs and slower verification than SNARK-based approaches. Nonetheless, end-to-end, aggregation and verification in Hyperproofs is $10\times$ to $41\times$ faster than in SNARK-based Merkle trees.

A great challenge for distributed payment systems is their compliance with regulations, such as anti-money laundering, insolvency legislation, countering the financing of terrorism and sanctions laws. After Bitcoin's MtGox scandal, one of the most needed auditing functionalities for financial solvency and tax reporting purposes is to prove ownership of blockchain reserves, a process known as Proof of Assets (PoA). This work formalizes the PoA requirements in account-based blockchains, focusing on the unique hierarchical account structure of the Diem blockchain, formerly known as Libra. In particular, we take into account some unique features of the Diem infrastructure to consider different PoA modes by exploring time-stamping edge cases, cold wallets, locked assets, spending ability delegation and account pruning, among the others. We also propose practical optimizations to the byte-size of PoA in the presence of light clients who cannot run a full node, including skipping Validator updates, while still maintaining the 66.7% Byzantine fault tolerance (BFT) guarantee.

Software implementations of cryptographic algorithms are slow but highly flexible and relatively easy to implement. On the other hand, hardware implementations are usually faster but provide little flexibility and require a lot of time to implement efficiently. In this paper, we develop a hybrid software-hardware implementation of the third round of Supersingular Isogeny Key Encapsulation (SIKE), a post-quantum cryptography algorithm candidate for NIST. We implement an isogeny field accelerator for the hardware and integrate it with a RISC-V processor which also acts as the main control unit for the field accelerator. The main advantage of this design is the high performance gain from the hardware implementation and the flexibility and fast development the software implementation provides. This is the first hybrid RISC-V and accelerator of SIKE. Furthermore, we provide one implementation for all NIST security levels of SIKE. Our design has the best area-time at NIST security levels 3 and 5 out of all hardware and hybrid designs provided in the literature.

Anonymous cryptographic primitives reduce the traces left by the users when interacting over a digital platform. However, they also prevent a platform owner to hold users accountable in case of malicious behaviour. Revocable anonymity offers a compromise by allowing only the manager (and not the other users) of the digital platform to de-anonymize user's activities when necessary. However, such de-anonymization power can be abused too, as a misbehaving manager can de-anonymize all the activities without user's awareness. Previous work propose to mitigate this issue by distributing the de-anonymization power across several entities. However, there is no comprehensive and formal treatment where both accountability and non-frameability (i.e., the inability to falsely accuse a party of misbehavior) for both the user and the manager are explicitly defined and provably achieved. In this paper we formally define mutual accountability: a user can be held accountable for her otherwise anonymous digital actions and a manager is held accountable for every de-anonymization attempt; plus, no honest party can be framed -- regardless of what malicious parties do. Instead of distributing the de-anonymization power across entities, instead, we decouple the power of de-anonymization from the power of monitoring de-anonymization attempts. This allows for greater flexibility, particularly in the choice of the monitoring entities. We show that our framework can be instantiated generically from threshold encryption schemes and succinct non-interactive zero-knowledge. We also show that the highly-efficient threshold group signature scheme by Camenisch et al.(SCN'20) can be modified and extended to instantiate our framework.

Several emerging proof-of-work (PoW) blockchain protocols rely on a “parallel-chain” architecture for scaling, where instead of a single chain, multiple chains are run in parallel and aggregated. A key requirement of practical PoW blockchains is to adapt to mining power variations over time (Bitcoin’s total mining power has increased by a $10^{14}$ factor over the decade). In this paper, we consider the design of provably secure parallel-chain protocols which can adapt to such mining power variations. The Bitcoin difficulty adjustment rule adjusts the difficulty target of block mining periodically to get a constant mean inter-block time. While superficially simple, the rule has proved itself to be sophisticated and successfully secure, both in practice and in theory [11, 13]. We show that natural adaptations of the Bitcoin adjustment rule to the parallel-chain case open the door to subtle, but catastrophic safety and liveness breaches. We uncover a meta-design principle that allow us to design variable mining difficulty protocols for three popular PoW blockchain proposals (Prism [3], OHIE [26], Fruitchains [21]) inside a common rubric. The principle has three components: (M1) a pivot chain, based on which blocks in all chains choose difficulty, (M2) a monotonicity condition for referencing pivot chain blocks and (M3) translating additional protocol aspects from using levels (depth) to using “difficulty levels”. We show that protocols employing a subset of these principles may have catastrophic failures. The security of the designs is also proved using a common rubric – the key technical challenge involves analyzing the interaction between the pivot chain and the other chains, as well as bounding the sudden changes in difficulty target experienced in non-pivot chains. We empirically investigate the responsivity of the new mining difficulty rule via simulations based on historical Bitcoin data, and find that the protocol very effectively controls the forking rate across all the chains.

Nowadays, neural networks have been widely used in many machine learning tasks. In practice, one might not have enough expertise to fine-tune a neural network model; therefore, it becomes increasingly popular to outsource the model training process to a machine learning expert. This activity brings out the needs of fair model exchange: if the seller sends the model first, the buyer might refuse to pay; if the buyer pays first, the seller might refuse to send the model or send an inferior model. In this work, we aim to address this problem so that neither the buyer nor the seller can deceive the other. We start from Zero Knowledge Contingent Payment (ZKCP), which is used for fair exchange of digital goods and payment over blockchain, and extend it to Zero Knowledge Contingent Model Payment (ZKCMP). We then instantiate our ZKCMP with two state-of-the-art NIZK proofs: zk-SNARKs and Libra. We also propose a random sampling technique to improve the efficiency of zk-SNARKs. We extensively conduct experiments to demonstrate the practicality of our proposal.

Numerous high-profile works have shown that access patterns to even encrypted databases can leak secret information and sometimes even lead to reconstruction of the entire database. To thwart access pattern leakage, the literature has focused on {\it oblivious} algorithms, where obliviousness requires that the access patterns leak nothing about the input data. In this paper, we consider the {\tt Join} operator, an important database primitive that has been extensively studied and optimized. Unfortunately, any {\it fully oblivious} {\tt Join} algorithm would require {\it always} padding the result to the {\it worst-case} length which is {\it quadratic} in the data size $N$. In comparison, an insecure baseline incurs only $O(R + N)$ cost where $R$ is the true result length, and in the common case in practice, $R$ is relatively short. As a typical example, when $R = O(N)$, any fully oblivious algorithm must inherently incur a prohibitive, $N$-fold slowdown relative to the insecure baseline. Indeed, the (non-private) database and algorithms literature invariably focuses on studying the {\it instance-specific} rather than {\it worst-case} performance of database algorithms. Unfortunately, the stringent notion of full obliviousness precludes the design of efficient algorithms with non-trivial instance-specific performance. To overcome this worst-case performance barrier of full obliviousness and enable algorithms with good instance-specific performance, we consider a relaxed notion of access pattern privacy called $(\epsilon, \delta)$-differential obliviousness (DO), originally proposed in the seminal work of Chan et al. (SODA'19). Rather than insisting that the access patterns leak no information whatsoever, the relaxed DO notion requires that the access patterns satisfy $(\epsilon, \delta)$-differential privacy. We show that by adopting the relaxed DO notion, we can obtain efficient database {\tt Join} mechanisms whose instance-specific performance {\it approximately matches} the insecure baseline, while still offering a meaningful notion of privacy to individual users. Complementing our upper bound results, we also prove new lower bounds regarding the performance of any DO {\tt Join} algorithm. Differential obliviousness (DO) is a new notion and is a relatively unexplored territory. Following the pioneering investigations by Chan et al. and others, our work is among the very first to formally explore how DO can help overcome the worst-case performance curse of full obliviousness; moreover, we motivate our work with database applications. Our work shows new evidence why DO might be a promising notion, and opens up several exciting future directions.

In 2019, the ANSSI released a protected software implementation of AES running on an STM32 platform with ARM Cortex-M architecture, publicly available on Github. The release of the code was shortly followed by a first paper written by Bronchain et al. at Ches 2020, analyzing the security of the implementation and proposing some attacks. In order to propose fair comparisons for future attacks on this target device, this paper aims at presenting a new publicly available dataset, called ASCADv2 based on this implementation. Along with the dataset, we also provide a benchmark of deep learning based side-channel attacks, thereby extending the works of Bronchain et al. Our attacks revisit and leverage the multi-task learning approach, introduced by Maghrebi in 2020, in order to efficiently target several intermediate computations at the same time. We hope that this work will draw the community’s interest towards the evaluation of highly protected software AES, whereas some of the current public SCA datasets are nowadays reputed to be less and less challenging.

Currently most practical attacks on cryptographic protocols like TLS are based on side channels, such as padding oracles. Some well-known recent examples are DROWN, ROBOT and Raccoon (USENIX Security 2016, 2018, 2021). Such attacks are usually found by careful and time-consuming manual analysis by specialists. In this paper, we consider the question of how such attacks can be systematically detected and prevented before (large-scale) deployment. We propose a new, fully automated approach, which uses supervised learning to identify arbitrary patterns in network protocol traffic. In contrast to classical scanners, which search for known side channels, the detection of general patterns might detect new side channels, even “unexpected” ones, such as those from the ROBOT attack. To analyze this approach, we develop a tool to detect Bleichenbacher-like padding oracles in TLS server implementations, based on an ensemble of machine learning algorithms. We verify that the approach indeed detects known vulnerabilities successfully and reliably. The tool also provides detailed information about detected patterns to developers, to assist in removing a potential padding oracle. Due to the automation, the approach scales much better than manual analysis and could even be integrated with a CI/CD pipeline of a development environment, for example.

We introduce Checkable Subspace Sampling Arguments, a new information theoretic interactive proof system in which the prover shows that a vector has been sampled in a subspace according to the verifier's coins. We show that this primitive provides a unifying view that explains the technical core of most of the constructions of universal and updatable pairing-based (zk)SNARKs. This characterization is extended to a fully algebraic framework for designing such SNARKs in a modular way. We propose new constructions of CSS arguments that lead to SNARKs with different performance trade-offs. Our most efficient construction, Basilisk, seems to have the smallest proof size in the literature, although it pays a price in terms of structure reference string for the number of multiplicative gates whose fan-out exceeds a certain bound.

White-box cryptography is often used in embedded applications. Although white-box cryptography with provable security has been proposed recently, the circuit size is much larger than that of usual block ciphers. We address this problem in a different way from previous works. In particular, we propose a white-box symmetric cipher using quantum memory. The size of our cipher is a polynomial in input-length and output-length of an underlying function. The security against classical attacks is reduced to the security of the underlying classical pseudo-random function. We show that quantum attacks using the generalized Grover algorithm to our cipher are ineffective.

Shuffling is one of the most important techniques for privacy-preserving protocols. Its applications are manifold, including, for example, e-voting, anonymous broadcast, or privacy-preserving machine-learning. For many applications, such as secure e-voting, it is crucial that the correctness of the shuffling operation be (publicly) verifiable. To this end, numerous proofs of shuffle have been proposed in the literature. Several of these proofs are actually employed in the real world. In this work, we propose a generic compiler which can transform any "shuffle-compatible" Sigma-protocol (including, among others, Sigma-protocols for re-randomization, decryption, or key shifting) into a Sigma-protocol for permutations of the underlying relation. The resulting proof of shuffle is black-box, easily implementable, simple to explain, and comes with an acceptable computational overhead over the state-of-the-art. Because we machine-checked our compiler in Coq, the new proof of shuffle is particularly suitable for applications that require a superior level of security assurance (e.g., high-stake elections).

We construct a concretely efficient Zero Knowledge (ZK) Oblivious RAM (ORAM) that consumes $2 \log n$ oblivious transfers (OTs) of length-$2\sigma$ secrets per access of an arithmetic value, for statistical security parameter $\sigma$ and array size $n$. This is an asymptotic and concrete improvement over previous best (concretely efficient) ZK ORAM Bub- bleRAM of Heath and Kolesnikov ([HK20a], CCS 2020), whose access cost is $1/2 \log^2 n$ OTs of length-$2\sigma$ secrets. ZK ORAM is essential for proving statements that are best expressed as RAM programs, rather than Boolean or arithmetic circuits. Our construction is private-coin ZK. We integrate it with [HK20a]’s ZK Proof (ZKP) protocol and prove the resulting ZKP system secure. We implemented PrORAM in C++. Compared to the state-of-the-art BubbleRAM, our PrORAM is $~10\times$ faster for arrays of size $2^{20}$ of $40$-bit values.

We consider the problem of finding low-weight multiples of polynomials over binary fields, which arises in stream cipher cryptanalysis or in finite field arithmetic. We first devise memory-efficient algorithms based on the recent advances in techniques for solving the knapsack problem. Then, we tune our algorithms using the celebrated Parallel Collision Search (PCS) method to decrease the time cost at the expense of a slight increase in space. Both our memory-efficient and time-memory trade-off algorithms improve substantially the state-of-the-art. The gain is for instance remarkable for large weights; a situation which occurs when the available keystream is small, e.g. the Bluetooth keystream.

We propose a new framework for trapdoor sampling over lattices. Our framework can be instantiated in a number of ways. In a departure from classical samplers, it allows for example to sample from uniform, affine, ``product affine'' and exponential distributions. It allows for example to sample from uniform, affine and ``product affine'' distributions. Another salient point of our framework is that the output distributions of our samplers are perfectly indistinguishable from ideal ones, in contrast with classical samplers that are statistically indistinguishable. One caveat of our framework is that all our current instantiations entail a rather large standard deviation.

We consider the strong secret key (SK) agreement problem for the satellite communication setting, where a satellite chooses a common binary phase shift keying modulated input for three statistically independent additive white Gaussian noise measurement channels whose outputs are observed by two legitimate transceivers (Alice and Bob) and an eavesdropper (Eve), respectively. Legitimate transceivers have access to an authenticated, noiseless, two-way, and public communication link, so they can exchange multiple rounds of public messages to agree on a SK hidden from Eve. Without loss of essential generality, the noise variances for Alice's and Bob's measurement channels are both fixed to a value Q>1, whereas the noise over Eve's measurement channel has a unit variance, so Q represents a channel quality ratio. We show that when both legitimate transceivers apply a one-bit uniform quantizer to their noisy observations before SK agreement, the SK capacity decreases at least quadratically in Q.

A recent preprint [ePrint 2021/469] suggests the use of exponentiation in a non-associative algebraic structure called "entropoid" to construct post-quantum analogues of DLP-based cryptosystems. In this note, we show a polynomial-time reduction from the entropoid version of DLP to the conventional DLP in the underlying finite field. The resulting attack takes less than 10 minutes on a laptop against parameters suggested in [ePrint 2021/469] for 128-bit post-quantum secure key exchange and runs in polynomial time on a quantum computer. We briefly discuss how to generalize the attack to the generic setting.

This document is intended to accompany the ethSTARK codebase, describing the computational integrity statement proved by that code and the specific STARK construction used to prove the statement.

Logic locking is a prominent solution to protect against design intellectual property theft. However, there has been a decade-long cat-and-mouse game between defenses and attacks. A turning point in logic locking was the development of miter-based Boolean satisfiability (SAT) attack that steered the research in the direction of developing SAT-resilient schemes. These schemes, however achieved SAT resilience at the cost of low output corruption. Recently, cascaded locking (CAS-Lock) was proposed that provides non-trivial output corruption all-the-while maintaining resilience to the SAT attack. Regardless of the theoretical properties, we revisit some of the assumptions made about its implementation, especially about security-unaware synthesis tools, and subsequently expose a set of structural vulnerabilities that can be exploited to break these schemes. We propose our attacks on baseline CAS-Lock as well as mirrored CAS (M-CAS), an improved version of CAS-Lock. We furnish extensive simulation results of our attacks on ISCAS'85 and ITC'99 benchmarks, where we show that CAS-Lock/M-CAS can be broken with ~94% success rate. Further, we open-source all implementation scripts, locked circuits, and attack scripts for the community. Finally, we discuss the pitfalls of point function-based locking techniques including Anti-SAT and Stripped Functionality Logic Locking (SFLL-HD), which suffer from similar implementation issues.

In this work, we present a lightweight construction of verifiable two-party function secret sharing (FSS) for point functions and multi-point functions. Our verifiability method is lightweight in two ways. Firstly, it is concretely efficient, making use of only symmetric key operations and no public key or MPC techniques are involved. Our performance is comparable with the state-of-the-art non-verifiable DPF constructions, and we outperform all prior DPF verification techniques in both computation and communication complexity, which we demonstrate with an implementation of our scheme. Secondly, our verification procedure is essentially unconstrained. It will verify that distributed point function (DPF) shares correspond to some point function irrespective of the output group size, the structure of the DPF output, or the set of points on which the DPF must be evaluated. This is in stark contrast with prior works, which depend on at least one and often all three of these constraints. In addition, our construction is the first DPF verification protocol that can verify general DPFs while remaining secure even if one server is malicious. Prior work on maliciously secure DPF verification could only verify DPFs where the non-zero output is binary. As an additional feature, our verification procedure can be batched so that verifying a polynomial number of DPF shares requires the exact same amount of communication as verifying one pair of DPF shares. We combine this packed DPF verification with a novel method for packing DPFs into shares of a multi-point function where the evaluation time, verification time, and verification communication are independent of the number of non-zero points in the function. An immediate corollary of our results are two-server protocols for PIR and PSI that remain secure when any one of the three parties is malicious (either the client or one of the servers).

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys. We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while double encryption fails to be more secure than single encryption due to a meet-in-the-middle attack. In this work we provide positive results, with concrete and tight bounds, for the security of both of these constructions against quantum attackers in ideal models. For FX, we consider a partially-quantum model, where the attacker has quantum access to the ideal primitive, but only classical access to FX. This is a natural model and also the strongest possible, since effective quantum attacks against FX exist in the fully-quantum model when quantum access is granted to both oracles. We provide two results for FX in this model. The first establishes the security of FX against non-adaptive attackers. The second establishes security against general adaptive attackers for a variant of FX using a random oracle in place of an ideal cipher. This result relies on the techniques of Zhandry (CRYPTO '19) for lazily sampling a quantum random oracle. An extension to perfectly lazily sampling a quantum random permutation, which would help resolve the adaptive security of standard FX, is an important but challenging open question. We introduce techniques for partially-quantum proofs without relying on analyzing the classical and quantum oracles separately, which is common in existing work. This may be of broader interest. For double encryption, we show that it amplifies strong pseudorandom permutation security in the fully-quantum model, strengthening a known result in the weaker sense of key-recovery security. This is done by adapting a technique of Tessaro and Thiruvengadam (TCC '18) to reduce the security to the difficulty of solving the list disjointness problem and then showing its hardness via a chain of reductions to the known quantum difficulty of the element distinctness problem.

At SODA 2017 Lokshtanov et al. presented the first worst-case algorithms with exponential speedup over exhaustive search for solving polynomial equation systems of degree $d$ in $n$ variables over finite fields. These algorithms were based on the polynomial method in circuit complexity which is a technique for proving circuit lower bounds that has recently been applied in algorithm design. Subsequent works further improved the asymptotic complexity of polynomial method-based algorithms for solving equations over the field $\mathbb{F}_2$. However, the asymptotic complexity formulas of these algorithms hide significant low-order terms, and hence they outperform exhaustive search only for very large values of $n$. In this paper, we devise a concretely efficient polynomial method-based algorithm for solving multivariate equation systems over $\mathbb{F}_2$. We analyze our algorithm's performance for solving random equation systems, and bound its complexity by about $n^2 \cdot 2^{0.815n}$ bit operations for $d = 2$ and $n^2 \cdot 2^{\left(1 - 1/2.7d\right) n}$ for any $d \geq 2$. We apply our algorithm in cryptanalysis of recently proposed instances of the Picnic signature scheme (an alternate third-round candidate in NIST's post-quantum standardization project) that are based on the security of the LowMC block cipher. Consequently, we show that 2 out of 3 new instances do not achieve their claimed security level. As a secondary application, we also improve the best-known preimage attacks on several round-reduced variants of the Keccak hash function. Our algorithm combines various techniques used in previous polynomial method-based algorithms with new optimizations, some of which exploit randomness assumptions about the system of equations. In its cryptanalytic application to Picnic, we demonstrate how to further optimize the algorithm for solving structured equation systems that are constructed from specific cryptosystems.

Macroeconomic policy in a blockchain system concerns the algorithm that decides the payment schedule for miners and thus its money mint rate. It governs the amounts, distributions, beneficiaries and conditions required for money supply payments to participants by the system. While most chains today employ simple policies such as a constant amount per block, several cryptocurrencies have sprung up that put forth more interesting policies. As blockchains become a more popular form of money, these policies inevitably are becoming more complex. A chain with a simple policy will often need to switch over to a different policy. Until now, it was believed that such upgrades require a hard fork -- after all, they are changing the money supply, a central part of the system, and unupgraded miners cannot validate blocks that deviate from those hard-coded rules. In this paper, we present a mechanism that allows a chain to upgrade from one policy to another through a soft fork. Our proposed mechanism works in today's Ethereum blockchain without any changes and can support a very generic class of monetary policies that satisfy a few basic bounds. Our construction is presented in the form of a smart contract. We showcase the usefulness of our proposal by describing several interesting applications of policy changes. Notably, we put forth a mechanism that makes Non-Interactive Proofs of Proof-of-Work unbribable, a previously open problem.

This paper introduces Prio+, a privacy-preserving system for the collection of aggregate statistics, with the same model and goals in mind as the original and highly influential Prio paper by Henry Corrigan-Gibbs and Dan Boneh (USENIX 2017). As in the original Prio, each client holds a private data value (e.g. number of visits to a particular website) and a small set of servers privately compute statistical functions over the set of client values (e.g. the average number of visits). To achieve security against faulty or malicious clients, Prio+ clients use Boolean secret-sharing instead of zero-knowledge proofs to convince servers that their data is of the correct form and Prio+ servers execute a share conversion protocols as needed in order to properly compute over client data. This allows us to ensure that clients’ data is properly formatted essentially for free, and the work shifts to novel share-conversion protocols between servers, where some care is needed to make it efficient. While our overall approach is a fairly simple observation in retrospect, it turns out that Prio+ strategy reduces the client’s computational burden by up to two orders of magnitude (or more depending on the statistic) while keeping servers costs comparable to Prio. Prio+ permits computation of exactly the same wide range of complex statistics as the original Prio protocol, including high-dimensional linear regression over private values held by clients. We report detailed benchmarks of our Prio+ implementation and compare these to both the original Go implementation of Prio and the Mozilla implementation of Prio. Our Prio+ software is open-source and released with the same license as Prio.

The Meet-in-the-Middle approach is one of the most powerful cryptanalysis techniques, demonstrated by its applications in preimage attacks on the full MD4, MD5, Tiger, HAVAL, and Haraka-512 v2 hash functions, and key recovery of the full block cipher KTANTAN. The success relies on the separation of a primitive into two independent chunks, where each active cell of the state is used to represent only one chunk or is otherwise considered unusable once mixed. We observe that some of such cells are linearly mixed and can be as useful as the independent ones. This leads to the introduction of superposition states and a whole suite of accompanied techniques, which we incorporate into the MILP-based search framework proposed by Bao et al. at EUROCRYPT 2021 and Dong et al. at CRYPTO 2021, and find applications on a wide range of AES-like hash functions and block ciphers.

We found 5412 new quadartic APN on F28 with the QAM method, thus bringing the number of known CCZ-inequivalent APN functions on F28 to 26525. Unfortunately, none of these new functions are CCZ-equivalent to permutations. A (to the best of our knowledge) complete list of known quadratic APN functions, including our new ones, has been pushed to sboxU for ease of study by others. In this paper, we recall how to construct new QAMs from a known one, and present how used the ortho-derivative method to figure out which of our new functions fall into different CCZ-classes. Based on these results and on others on smaller fields, we make to conjectures: that the full list of quadratic APN functions on F28 could be obtained using the QAM approached (provided enormous computing power), and that the total number of CCZ-inequivalent APN functions may overcome 50000.

We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of $2n$-to-$n$-bit compression functions from non-compressing primitives with asymptotically optimal $2^{n/2-\epsilon}$-query collision resistance. Designing optimally efficient and secure hash functions for larger domains ($> 2n$ bits) is still an open problem. To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new \emph{compactness} efficiency notion. It allows us to focus on asymptotically optimally collision resistant hash function and normalize their parameters based on Stam's bound from CRYPTO 2008 to obtain maximal efficiency. We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. Our first construction is an \emph{Augmented Binary Tree} mode. The design is a $(2^{\ell}+2^{\ell-1} -1)n$-to-$n$-bit hash function making a total of $(2^{\ell}-1)$ calls to $2n$-to-$n$-bit compression functions for any $\ell\geq 2$. Our construction is optimally compact with asymptotically (optimal) $2^{n/2-\epsilon}$-query collision resistance in the ideal model. For a tree of height $\ell$, in comparison with Merkle tree, the Augmented Binary Tree mode processes additional $(2^{\ell-1}-1)$ data blocks making the same number of internal compression function calls. With our second design we focus our attention on the indifferentiability security notion. While the Augmented Binary Tree mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within $2^{n/3}$ queries. We show that a slightly different \emph{Augmented Binary Tree Plus} compresses only $1$ less data block than Augmented Binary Tree mode with the same number of compression calls and achieves in addition indifferentiability up to $2^{n/2-\epsilon}$ queries. Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.

While it is well known that the sawtooth function has a point-wise convergent Fourier series, the rate of convergence is not the best possible for the application of approximating the mod function in small intervals around multiples of the modulus. We show a different sine series, such that the sine series of order n has error O(epsilon^(2n+1)) for approximating the mod function in epsilon-sized intervals around multiples of the modulus. Moreover, the resulting polynomial, after Taylor series approximation of the sine series, has small coefficients, and the whole polynomial can be computed at a precision that is only slightly larger than -(2n+1)log epsilon, the precision of approximation being sought. This polynomial can then be used to approximate the mod function to almost arbitrary precision, and hence allows practical CKKS-HE bootstrapping with arbitrary precision. We validate our approach with an implementation and obtain 100 bit precision bootstrapping as well as improvements over earlier works at lower precision.

The advent of a full-scale quantum computer will severely impact most currently-used cryptographic systems. The most well-known aspect of this impact lies in the computational-hardness assumptions that underpin the security of most current public-key cryptographic systems: a quantum computer can factor integers and compute discrete logarithms in polynomial time, thereby breaking systems based on these problems. However, simply replacing these problems by other which are (believed to be) impervious even to a quantum computer does not completely solve the issue. Indeed, many security proofs of cryptographic systems are no longer valid in the presence of a quantum-capable attacker; while this does not automatically implies that the affected systems would be broken by a quantum computer, it does raises questions on the exact security guarantees that they can provide. This overview document aims to analyze all aspects of the impact of quantum computers on cryptographic, by providing an overview of current quantum-hard computational problems (and cryptographic systems based on them), and by presenting the security proofs that are affected by quantum-attackers, detailing what is the current status of research on the topic and what the expected effects on security are.

Lattice-based cryptography is one of the leading proposals for post-quantum cryptography. The Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography, and many lattice-based schemes have security claims based on its hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa16 PhD] and runs in (heuristic) time $2^{0.2653d + o(d)}$. In this article, we present an improvement over Laarhoven's result and present an algorithm that has a (heuristic) running time of $2^{0.2570 d + o(d)}$ where $d$ is the lattice dimension. We also present time-memory trade-offs where we quantify the amount of quantum memory and quantum random access memory of our algorithm. The core idea is to replace Grover's algorithm used in [Laa16 PhD] in a key part of the sieving algorithm by a quantum random walk in which we add a layer of local sensitive filtering.

Masking has been recognized as a sound and secure countermeasure for cryptographic implementations, protecting against physical side-channel attacks. Even though many different masking schemes have been presented over time, design and implementation of protected cryptographic Integrated Circuits (ICs) remains a challenging task. More specifically, correct and efficient implementation usually requires manual interactions accompanied by longstanding experience in hardware design and physical security. To this end, design and implementation of masked hardware often proves to be an error-prone task for engineers and practitioners. As a result, our novel tool for automated generation of masked hardware (AGEMA) allows even inexperienced engineers and hardware designers to create secure and efficient masked cryptograhic circuits originating from an unprotected design. More precisely, exploiting the concepts of Probe-Isolating Non-Interference (PINI) for secure composition of masked circuits, our tool provides various processing techniques to transform an unprotected design into a secure one, eventually accelerating and safeguarding the process of masking cryptographic hardware. Ultimately, we evaluate our tool in several case studies, emphasizing different trade-offs for the transformation techniques with respect to common performance metrics, such as latency, area, and randomness.

In this paper, we study efficient and authorized rewriting of transactions already written to a blockchain. Mutable transactions will make a fraction of all blockchain transactions, but will be a necessity to meet the needs of privacy regulations, such as the General Data Protection Regulation (GDPR). The state-of-the-art rewriting approaches have several shortcomings, such as lack of user anonymity, inefficiency, and absence of revocation mechanisms. We present ReTRACe, an efficient framework for blockchain rewrites. ReTRACe is designed by composing a novel revocable chameleon hash with ephemeral trapdoor scheme, a novel revocable fast attribute based encryption scheme, and a dynamic group signature scheme. We discuss ReTRACe, and its constituent primitives in detail, along with their security analyses, and present experimental results to demonstrate the scalability of ReTRACe.

As a solution to mitigate the key exposure problems in the digital signature, forward security has been proposed. The forward security guarantees the integrity of the messages generated in the past despite leaks of a current time period secret key by evolving a secret key on each time period. However, there is no forward secure signature scheme whose all metrics have constant complexities. Furthermore, existing works do not support multi-user aggregation of signatures. In this paper, we propose a forward secure aggregate signature scheme utilizing recursive zk-SNARKs (zero knowledge Succinct Non-interactive ARguments of Knowledge), whose all metrics including size and time have $O(1)$. The proposed forward secure signature scheme can aggregate signatures generated by not only a single user but also multiple users. The security of the proposed scheme is formally proven under zero-knowledge assumption and random oracle model.

We investigate the digital signature schemes in the indifferentiability framework. We show that the well-known Lamport one-time signature scheme and the tree-based signature scheme can be ``lifted'' to realize ideal one-time signature, and ideal signature, respectively, without using computational assumptions. We for the first time show that the ideal signatures, ideal one-time signatures, and random oracles are equivalent in the framework of indifferentiability.

Secure multiparty generation of an RSA biprime is a challenging task, which increasingly receives attention, due to the numerous privacy-preserving applications that require it. In this work, we construct a new protocol for the RSA biprime generation task, secure against a malicious adversary, who can corrupt any subset of protocol participants. Our protocol is designed for generic MPC, making it both platform-independent and allowing for weaker security models to be assumed (e.g., honest majority), should the application scenario require it. By carefully ``postponing" the check of possible inconsistencies in the shares provided by malicious adversaries, we achieve noteworthy efficiency improvements. Concretely, we are able to produce additive sharings of the prime candidates, from multiplicative sharings via a semi-honest multiplication, without degrading the overall (active) security of our protocol. This is the core of our sieving technique, increasing the probability of our protocol sampling a biprime. Similarly, we perform the first biprimality test, requiring several repetitions, without checking input share consistency, and perform the more costly consistency check only in case of success of the Jacobi symbol based biprimality test. Moreover, we propose a protocol to convert an additive sharing over a ring, into an additive sharing over the integers. Besides being a necessary sub-protocol for the RSA biprime generation, this conversion protocol is of independent interest. The cost analysis of our protocol demonstrated that our approach improves the current state-of-the-art (Chen et al. -- Crypto 2020), in terms of communication efficiency. Concretely, for the two-party case with malicious security, and primes of 2048 bits, our protocol improves communication by a factor of ~37.

In a set membership proof, the public information consists of a set of elements and a commitment. The prover then produces a zero-knowledge proof showing that the commitment is indeed to some element from the set. This primitive is closely related to concepts like ring signatures and ``one-out-of-many'' proofs that underlie many anonymity and privacy protocols. The main result of this work is a new succinct lattice-based set membership proof whose size is logarithmic in the size of the set. We also give a transformation of our set membership proof to a ring signature scheme. The ring signature size is also logarithmic in the size of the public key set and has size $16$ KB for a set of $2^5$ elements, and $22$ KB for a set of size $2^{25}$. At an approximately $128$-bit security level, these outputs are between 1.5X and 7X smaller than the current state of the art succinct ring signatures of Beullens et al. (Asiacrypt 2020) and Esgin et al. (CCS 2019). We then show that our ring signature, combined with a few other techniques and optimizations, can be turned into a fairly efficient Monero-like confidential transaction system based on the MatRiCT framework of Esgin et al. (CCS 2019). With our new techniques, we are able to reduce the transaction proof size by factors of about 4X - 10X over the aforementioned work. For example, a transaction with two inputs and two outputs, where each input is hidden among $2^{15}$ other accounts, requires approximately $30$KB in our protocol.

This paper demonstrates an architecture for accelerating the polynomial multiplication using number theoretic transform (NTT). Kyber is one of the finalists in the third round of the NIST post-quantum cryptography standardization process. Simultaneously, the performance of NTT execution is its main challenge, requiring large memory and complex memory access pattern. In this paper, an efficient NTT architecture is presented to improve the respective computation time. We propose several optimization strategies for efficiency improvement targeting different performance requirements for various applications. Our NTT architecture, including four butterfly cores, occupies only 798 LUTs and 715 FFs on a small Artix-7 FPGA, showing more than 44% improvement compared to the best previous work. We also implement a coprocessor architecture for Kyber KEM benefiting from our high-speed NTT core to accomplish three phases of the key exchange in 9, 12, and 19 \mus, respectively, operating at 200 MHz.

It follows from a result by Friedl, Ivanyos, Magniez, Santha and Sen from 2014 that, for any fixed integer $m > 0$ (thought of as being small), there exists a quantum algorithm for solving the hidden shift problem in an arbitrary finite abelian group $(G, +)$ with time complexity poly$( \log |G|) \cdot 2^{O(\sqrt{\log |mG|})}$. As discussed in the current paper, this can be viewed as a modest statement of Pohlig-Hellman type for hard homogeneous spaces. Our main contribution is a somewhat simpler algorithm achieving the same runtime for $m = 2^tp$, with $t$ any non-negative integer and $p$ any prime number, where additionally the memory requirements are mostly in terms of quantum random access classical memory; indeed, the amount of qubits that need to be stored is poly$( \log |G|)$. Our central tool is an extension of Peikert's adaptation of Kuperberg's collimation sieve to arbitrary finite abelian groups. This allows for a reduction, in said time, to the hidden shift problem in the quotient $G/2^tpG$, which can then be tackled in polynomial time, by combining methods by Friedl et al. for $p$-torsion groups and by Bonnetain and Naya-Plasencia for $2^t$-torsion groups.

Public-key cryptography based on the lattice problem is efficient and believed to be secure in a post-quantum era. In this paper, we introduce carefully optimized implementations of Kyber encryption schemes for 64-bit ARM Cortex-A processors. Our research contribution includes several optimizations for Number Theoretic Transform (NTT), noise sampling, and AES accelerator based symmetric function implementations. The proposed Kyber512 implementation on ARM64 improved previous works by 1.72×, 1.88×, and 2.29× for key generation, encapsulation, and decapsulation, respectively. Moreover, by using AES accelerator in the proposed Kyber512-90s implementation, it is improved by 8.57×, 6.94×, and 8.26× for key generation, encapsulation, and decapsulation, respectively. These results set new speed records for Kyber encryption on 64-bit ARM Cortex-A processors.

We use matrices over bit strings as platforms for Diffie-Hellman-like public key exchange protocols. When multiplying matrices like that, we use Boolean OR operation on bit strings in place of addition and Boolean AND operation in place of multiplication. As a result, (1) computations with these matrices are very efficient; (2) standard methods of attacking Diffie-Hellman-like protocols are not applicable.

Updatable encryption (UE) is symmetric encryption which additionally supports key rotation. UE was introduced for scenarios where a user stores encrypted data on a cloud and, in order to mitigate secret key leakage, periodically sends a short update token, which the cloud uses to re-encrypt stored data to a fresh key. A long line of research resulted in a wide variety of security properties UE schemes can provide, including confidentiality, integrity protection, and hiding metadata. Unfortunately, given the complexity and nuances in the definitions, different properties are difficult to compare for non-experts, making it hard to judge which scheme provides the best security-efficiency trade-off for a given application. In this work, we challenge the approach of defining UE as a primitive with a set of properties. As an alternative, we propose to treat UE as an interactive protocol, whose goal is to implement secure outsourced storage, using limited and imperfect resources (such as a small, leakable memory). To facilitate this approach, we introduce a framework that allows to easily formalize different security guarantees and available resources, making security-efficiency trade-offs of UE protocols easy to compare. We believe that our approach opens the way for many constructions of secure storage that are not compatible with the currently defined syntax of UE. Indeed, we propose two new protocols: one for the setting with adversaries who control randomness (an attack vector so far not considered for UE), and one for the setting with adversaries that actively tamper with memory. Both protocols provide stronger confidentiality guarantees than all existing UE schemes.

In this work we present a new approach to verifiable decryption which converts a 2-party passively secure distributed decryption protocol into a 1-party proof of correct decryption. To introduce our idea, we present a toy example for an ElGamal distributed decryption protocol that we also give a machine checked proof of, in addition to applying our method to lattices. This leads to an efficient and simple verifiable decryption scheme for lattice-based cryptography, especially for large sets of ciphertexts; it has small size and lightweight computations as we reduce the need of zero-knowledge proofs for each ciphertext. We believe the flexibility of the general technique is interesting and provides attractive trade-offs between complexity and security, in particular for the interactive variant with smaller soundness. Finally, the protocol requires only very simple operations, making it easy to correctly and securely implement in practice. We suggest concrete parameters for our protocol and give a proof of concept implementation, showing that it is highly practical.

The dual attack has long been considered a relevant attack on lattice-based cryptographic schemes relying on the hardness of learning with errors (LWE) and its structured variants. As solving LWE corresponds to finding a nearest point on a lattice, one may naturally wonder how efficient this dual approach is for solving more general closest vector problems, such as the classical closest vector problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP, and preprocessing versions of these problems. While primal, sieving-based solutions to these problems (with preprocessing) were recently studied in a series of works on approximate Voronoi cells, for the dual attack no such overview exists, especially for problems with preprocessing. With one of the take-away messages of the approximate Voronoi cell line of work being that primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one may wonder if the dual attack suffers the same drawbacks, or if it is a better method for solving BDD(P). In this work we provide an overview of cost estimates for dual algorithms for solving these ''classical'' closest lattice vector problems. Heuristically we expect to solve the search version of average-case CVPP in time and space $2^{0.293d + o(d)}$. For the distinguishing version of average-case CVPP, where we wish to distinguish between random targets and targets planted at distance approximately the Gaussian heuristic from the lattice, we obtain the same complexity in the single-target model, and we obtain query time and space complexities of $2^{0.195d + o(d)}$ in the multi-target setting, where we are given a large number of targets from either target distribution. This suggests an inequivalence between distinguishing and searching, as we do not expect a similar improvement in the multi-target setting to hold for search-CVPP. We analyze three slightly different decoders, both for distinguishing and searching, and experimentally obtain concrete cost estimates for the dual attack in dimensions $50$ to $80$, which confirm our heuristic assumptions, and show that the hidden order terms in the asymptotic estimates are quite small. Our main take-away message is that the dual attack appears to mirror the approximate Voronoi cell line of work -- whereas using approximate Voronoi cells works well for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales well for BDD(P) instances but performs poorly on approximate CVP(P).

During the last years, many Physical Zero-knowledge Proof(ZKP) protocols for Nikoli’s puzzles have been designed. In this paper, we propose two ZKP protocols for the two Nikoli’s puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since in their rules at least one condition requires that some cells are connected to each other, horizontally or vertically. The novelty in this paper is to propose two techniques that allow us to prove such connectivity without leaking any information about a solution.

By revisiting, improving, and extending recent neural-network based modeling attacks on XOR Arbiter PUFs from the literature, we show that XOR Arbiter PUFs, (XOR) Feed-Forward Arbiter PUFs, and Interpose PUFs can be attacked faster, up to larger security parameters, and with fewer challenge-response pairs than previously known both in simulation and in silicon data. To support our claim, we discuss the differences and similarities of recently proposed modeling attacks and offer a fair comparison of the performance of these attacks by implementing all of them using the popular machine learning framework Keras and comparing their performance against the well-studied Logistic Regression attack. Our findings show that neural-network-based modeling attacks have the potential to outperform traditional modeling attacks on PUFs and must hence become part of the standard toolbox for PUF security analysis; the code and discussion in this paper can serve as a basis for the extension of our results to PUF designs beyond the scope of this work.

Quantum computers can solve or accelerate specific problems that were not possible with classical computers. Grover's search algorithm, a representative quantum algorithm, finds a specific solution from $N$ unsorted data with $O(\sqrt{N})$ queries. This quantum algorithm can be used to recover the key of symmetric cryptography. In this paper, we present a practical quantum attack using Grover's search to recover the key of ciphers ({\tt Caesar} and {\tt Vigenère}). The proposed quantum attack is simulated with quantum programming tools (ProjectQ and Qiskit) provided by IBM. Finally, we minimize the use of quantum resources and recover the key with a high probability.

Protocols for password-based authenticated key exchange (PAKE) allow two users sharing only a short, low-entropy password to establish a secure session with a cryptographically strong key. The challenge in designing such protocols is that they must resist offline dictionary attacks in which an attacker exhaustively enumerates the dictionary of likely passwords in an attempt to match the used password. In this paper, we study the resilience of one particular PAKE against these attacks. Indeed, we focus on the Secure Remote Password (SRP) protocol that was designed by T. Wu in 1998. Despite its lack of formal security proof, SRP has become a de-facto standard. For more than 20 years, many projects have turned towards SRP for their authentication solution, thanks to the availability of open-source implementations with no restrictive licenses. Of particular interest, we mention the Stanford reference implementation (in C and Java) and the OpenSSL one (in C). In this paper, we analyze the security of the SRP implementation inside the OpenSSL library. In particular, we identify that this implementation is vulnerable to offline dictionary attacks. Indeed, we exploit a call for a function computing modular exponentiation of big numbers in OpenSSL. In the SRP protocol, this function leads to the call of a non-constant time function, thereby leaking some information about the used password when leveraging cache-based Flush+Reload timing attack. Then, we show that our attack is practical, since it only requires one single trace, despite the noise of cache measurements. In addition, the attack is quite efficient as the reduction of some common dictionaries is very fast using modern resources at negligible cost. We also prove that the scope of our vulnerability is not only limited to OpenSSL, since many other projects, including Stanford's, ProtonMail and Apple Homekit, rely on OpenSSL, which makes them vulnerable. We find that our flaw might also impact projects written in Python, Erlang, JavaScript and Ruby, as long as they load the OpenSSL dynamic library for their big number operations. We disclosed our attack to OpenSSL who acknowledged the attack and timely fixed the vulnerability.

The security of code-based cryptography usually relies on the hardness of the syndrome decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the $k$-way sorting network for any prime $k$ to reduce the depth in terms of comparison operation from $O(\log_2^2 n)$ to $O(k\log_k^2 n)$, thereby improving performance for $k$ slightly larger than $2$, such as $k=5$. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the $k$-way sorting network, the $k$-sorter, which sorts $k$-numbers with a minimal comparison depth, is used as a building block. The approximate homomorphic comparison, which is the only type of comparison working on approximate FHE, cannot be used for the construction of the $k$-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient $k$-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a $k$-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate $k$ that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting $5^6=15625$ data using $5$-way sorting network can be about $23.3\%$ faster than sorting $2^{14}=16384$ data using $2$-way.

Quadratic AB (almost bent) functions are characterized by the property that the duals of their component functions are bent functions. We prove that these duals are also quadratic and illustrate that these bent duals may give rise to vectorial bent functions (in certain cases having a maximal output dimension). It is then natural to investigate when the linear combinations of quadratic bent duals again yield quadratic bent functions. A necessary and sufficient condition for ensuring the bentness of these linear combinations is provided, by introducing a useful transform that acts on the Walsh spectrum of dual functions. Moreover, we provide a rather detailed analysis related to the structure of quadratic AB functions in the spectral domain, more precisely with respect to their Walsh supports, their intersection, and restrictions of these bent duals to suitable subspaces. It turns out that the AB property is quite complicated even in the quadratic case. However, using the established facts in this article, we could for the first time provide the design of quadratic AB functions in the spectral domain by identifying (using computer simulations) suitable sets of bent dual functions which give rise to possibly new quadratic AB functions in a generic manner. Using a simple non-exhaustive search for suitable sets of defining bent duals $f_1, \ldots,f_5$ on $\mathbb{F}_2^4$, we could easily identify 60 quadratic AB functions $F:\mathbb{F}_2^5 \rightarrow \mathbb{F}_2^5$. It turns out that all these functions are CCZ-equivalent to the Gold AB function but none of these functions is a permutation. On the other hand, when $n=7$, the same approach provides several AB functions which are \textbf{not} CCZ-equivalent to Gold functions.

The security of modern cryptography depends on multiple factors, from sound hardness assumptions to correct implementations that resist side-channel cryptanalysis. Curve-based cryptography is not different in this regard, and substantial progress in the last few decades has been achieved in both selecting parameters and devising secure implementation strategies. In this context, the security of implementations of field inversion is sometimes overlooked in the research literature, because (i) the approach based on Fermat's Little Theorem (FLT) suffices performance-wise for many parameters used in practice; (ii) it is typically invoked only at the very end of a cryptographic computation, with a small impact on performance; (iii) it is challenging to implement securely for general parameters without a significant performance penalty. However, field inversion can process sensitive information and must be protected with side-channel countermeasures like any other cryptographic operation, as illustrated by recent attacks. In this work, we focus on implementing field inversion for primes of cryptographic interest with security against timing attacks, irrespective of whether the FLT-based inversion can be efficiently implemented. We extend the Fiat-Crypto framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang inversion algorithm as a step towards this goal. This allows a correct implementation of prime field inversion to be synthesized for any prime. We benchmark the implementations across a range of primes for curve-based cryptography and they outperform traditional FLT-based approaches in most cases, with observed speedups up to 2 for the largest parameters. Our work is already used in production in the MirageOS unikernel operating system, $\mathtt{zig}$ programming language, and the ECCKiila framework.

Typically, unconditionally secure computation using a (k,n) threshold secret sharing scheme is considered impossible when n<2k-1. Therefore, in our previous work, we first took the approach of finding the conditions required for secure computation under the setting of n<2k-1 and showed that secure computation using a secret sharing scheme can be realized with a semi-honest adversary under the following three preconditions: (1) the result of secure computation does not include 0; (2) random numbers reconstructed by each server are fixed; and (3) each server holds random numbers unknown to the adversary and holds shares of random numbers that make up the random numbers unknown to the adversary. In this paper, we show that by leaving condition (3), secure computation with information-theoretic security against a semi-honest adversary is possible with k&#8804;n<2k-1. In addition, we clarify the advantage of using secret information that has been encrypted with a random number as input to secure computation. One of the advantages is the acceleration of the computation time. Namely, we divide the computation process into a preprocessing phase and an online phase and shift the cost of communication to the preprocessing phase. Thus, for computations such as inner product operations, we realize a faster online phase, compared with conventional methods.

Cube attack has recently been proved as the most effective approach of attacking Trivium. So far, the attack against the highest round-reduced Trivium was given in EUROCRYPT 2020, where key-recovery attacks on 840-, 841-, and 842-round Trivium were presented. By revealing the relation between three-subset division property without unknown subset and the monomials of superpolys, Hu et al. obtained more attacks on 840-, 841-, and 842-round Trivium with lower complexities in ASIACRYPT 2020. In this short paper, we will present a key-recovery cube attack against 843-round Trivium.

This paper presents distinguishing and key recovery attacks on the reduced-round SNOW-V and SNOW-Vi, which are stream ciphers proposed for standard encryption schemes for the 5G mobile communication system. First, we construct a Mixed-Integer Linear Programming (MILP) model to search for integral characteristics using the division property, and find the best integral distinguisher in the 3-, 4-, 5-round SNOW-V, and 5-round SNOW-Vi with time complexities of \(2^{8}\), \(2^{16}\), \(2^{48}\), and \(2^{16}\), respectively. Next, we construct a bit-level MILP model to efficiently search for differential characteristics, and find the best differential characteristics in the 3- and 4-round versions. These characteristics lead to the 3-round differential distinguishers for SNOW-V and SNOW-Vi with time complexities of \(2^{17}\) and \(2^{12}\) and the 4-round differential distinguishers for SNOW-V and SNOW-Vi with time complexities of \(2^{97}\) and \(2^{39}\), respectively. Then, we consider single-bit and dual-bit differential cryptanalysis, which is inspired by the existing study on Salsa and ChaCha. By carefully choosing the IV values and differences, we can construct practical bit-wise differential distinguishers for the 4-round SNOW-V, 4-, and 5-round SNOW-Vi with time complexities of \(2^{4.466}\), \(2^{1.000}\), and \(2^{14.670}\), respectively. Finally, we improve the existing differential attack based on probabilistic neutral bits, which is also inspired by the existing study on Salsa and ChaCha. As a result, we present the best key recovery attack on the 4-round SNOW-V and SNOW-Vi with time complexities of \(2^{153.97}\) and \(2^{233.99}\) and data complexities of \(2^{26.96}\) and \(2^{19.19}\), respectively. Consequently, we significantly improve the existing best attacks in the initialization phase by the designers.