Following the pioneering work of Boneh and Franklin (CRYPTO '01), the challenge of constructing an identity-based encryption scheme based on the Diffie-Hellman assumption remained unresolved for more than 15 years. Evidence supporting this lack of success was provided by Papakonstantinou, Rackoff and Vahlis (ePrint '12), who ruled out the existence of generic-group identity-based encryption schemes supporting an identity space of sufficiently large polynomial size. Nevertheless, the breakthrough result of D{ö}ttling and Garg (CRYPTO '17) settled this long-standing challenge via a non-generic construction. We prove a tight impossibility result for generic-group identity-based encryption, ruling out the existence of any non-trivial construction: We show that any scheme whose public parameters include $n_{\sf pp}$ group elements may support at most $n_{\sf pp}$ identities. This threshold is trivially met by any generic-group public-key encryption scheme whose public keys consist of a single group element (e.g., ElGamal encryption). In the context of algebraic constructions, generic realizations are often both conceptually simpler and more efficient than non-generic ones. Thus, identifying exact thresholds for the limitations of generic groups is not only of theoretical significance but may in fact have practical implications when considering concrete security parameters.

In this paper, we introduce a new method to prove the knowledge of an isogeny of given degree between two supersingular elliptic curves. Our approach can be extended to verify the evaluation of the secret isogeny on some points of the domain. The main advantage of this new proof of knowledge is its compactness which is orders of magnitude better than existing proofs of isogeny knowledge. The principle of our method is to reveal some well-chosen endomorphisms and does not constitute a zero-knowledge proof. However, when the degree is a large prime, we can introduce a new hardness assumption upon which we build the first verifiable random function (VRF) based on isogenies. Our protocol can be seen as a generalization of the BLS-style classical construction from elliptic curves and achieves one-time pseudo-randomness in the random oracle model. We propose concrete parameters for this new scheme which reach post-quantum NIST-1 level of security. Our VRF has an overall cost (proof size, key size and output size) of roughly $1$KB, which is shorter than all the other post-quantum instantiations based on lattices. In the process, we also develop several algorithmic tools to solve norm equations over quaternion orders that may be of independent interest.

We propose Manta, a plug and play private DeFi stack that consists of MantaDAP, a multi-asset decentralized anonymous payment scheme and MantaDAX, an automated market maker(AMM) based decentralized anonymous exchange scheme. Compared with existing privacy preserving cryptocurrencies such as Zcash and Monero,Manta supports multiple base assets and allows the privatized assets to be exchanged anonymously via MantaDAX. We think this is a major step forward towards building a privacy preserving DeFi stack. Thanks to the efficiency of modern NIZKs (non-interactive zero-knowledge proof systems) and our carefully crafted design,Manta is efficient: our benchmarks reports a 15 second, off-line zero-knowledge proof (ZKP) generation time, and a 6 millisecond, on-line proof verification time.

Proof-of-Stake (PoS) distributed ledgers are the most common alternative to Bitcoin’s Proof-of-Work (PoW) paradigm, replacing the hardware dependency with stake, i.e., assets that a party controls. Similar to PoW’s mining pools, PoS’s stake pools, i.e., collaborative entities comprising of multiple stakeholders, allow a party to earn rewards more regularly, compared to participating on an individual basis. However, stake pools tend to increase centralization, since they are typically managed by a single party that acts on behalf of the pool’s members. In this work we propose Conclave, a formal design of a Collective Stake Pool, i.e., a decentralized pool with no single point of authority. We formalize Conclave as an ideal functionality and implement it as a distributed protocol, based on standard cryptographic primitives. Among Conclave’s building blocks is a weighted threshold signature scheme (WTSS); to that end, we define a WTSS ideal functionality — which might be of independent interest — and propose two constructions based on threshold ECDSA, which enable (1) fast trustless setup and (2) identifiable aborts.

This short note shows that NTRU in NIST PQC Round~3 finalist is anonymous in the QROM if the underlying NTRU PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from NTRU as KEM and appropriate DEM is anonymous and robust. This solves the open problem to investigate anonymity and robustness of NTRU posed by Grubbs, Maram, and Paterson (Cryptography ePrint Archive 2021/708).

The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)). As applications, we can construct * pseudorandom and obliviously-samplable public-key encryption schemes from lattices and codes, * universally-composable non-interactive bit-commitment from lattices, * public-key steganography which is steganographically secure against adaptive chosen-covertext attacks and steganographic key-exchange from lattices and codes, * anonymous authenticated key exchange from lattices and codes, * public-key encryption secure against simulation-based, selective-opening chosen-ciphertext attacks from lattices and codes.

A garbling scheme is a fundamental cryptographic building block with a long list of applications. The study of different techniques for garbling a function, towards optimizing computation and communication complexity, has been an area of active research. Most common garbling techniques work by representing each gate in the circuit as a set of ciphertexts that encrypt its truth table row-by-row. In this work we present a new garbling scheme in the random oracle (RO) model that garbles circuits in the gate-by-gate paradigm by capturing the gate functionality (AND, XOR) as a whole rather than as a set of ciphertexts. The final gate garbling requires $4\kappa$ bits of communication in expectation, 4 RO calls for garbling and 1 RO call for evaluation. We prove that the scheme satisfies privacy in the non-programmable random oracle model and against PPT adversaries. We also show how this scheme can be extended to support free-XOR and garble any gate functionality over binary inputs.

The existence of one-way functions implies secure digital signatures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes. Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show: - the insecurity of all algebraic signature schemes in Maurer's generic group model (in pairing-free groups), as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions. - the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements. We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

GIFT-COFB is a finalist of NIST Lightweight cryptography project that aims at standardizing authenticated encryption schemes for constrained devices. It is a block cipher-based scheme and comes with a provable security result. This paper studies the tightness of the provable security bounds of GIFT-COFB, which roughly tells that, if instantiated by a secure $n$-bit block cipher, we need $2^{n/2}$ encrypted blocks or $2^{n/2}/n$ decryption queries to break the scheme. This paper shows that the former condition is indeed tight, by presenting forgery attacks that work with $2^{n/2}$ encrypted blocks with single decryption query. This fills the missing spot of previous attacks presented by Khairallah, and confirms the tightness of the security bounds with respect to encryption. We remark that our attacks work independent of the underlying block cipher.

Machine Learning (ML) algorithms, especially deep neural networks (DNN), have proven themselves to be extremely useful tools for data analysis, and are increasingly being deployed in systems operating on sensitive data, such as recommendation systems, banking fraud detection, and healthcare systems. This underscores the need for privacy-preserving ML (PPML) systems, and has inspired a line of research into how such systems can be constructed efficiently. We contribute to this line of research by proposing a framework that allows efficient and secure evaluation of full-fledged state-of-the-art ML algorithms via secure multi-party computation (MPC). This is in contrast to most prior works on PPML, which require advanced ML algorithms to be substituted with approximated variants that are ``MPC-friendly'', before MPC techniques are applied to obtain a PPML algorithm. A drawback of the latter approach is that it requires careful fine-tuning of the combined ML and MPC algorithms, and might lead to less efficient algorithms or inferior quality ML (such as lower prediction accuracy). This is an issue for secure training of DNNs in particular, as this involves several arithmetic algorithms that are thought to be ``MPC-unfriendly'', namely, integer division, exponentiation, inversion, and square root extraction. In this work, we propose secure and efficient protocols for the above seemingly MPC-unfriendly computations (but which are essential to DNN). Our protocols are three-party protocols in the honest-majority setting, and we propose both passively secure and actively secure with abort variants. A notable feature of our protocols is that they simultaneously provide high accuracy and efficiency. This framework enables us to efficiently and securely compute modern ML algorithms such as Adam (Adaptive moment estimation) and the softmax function ``as is'', without resorting to approximations. As a result, we obtain secure DNN training that outperforms state-of-the-art three-party systems; our \textit{full} training is up to $6.7$ times faster than just the \textit{online} phase of the recently proposed FALCON (Wagh et al. at PETS'21) on the standard benchmark network for secure training of DNNs. To further demonstrate the scalability of our protocols, we perform measurements on real-world DNNs, AlexNet and VGG16, which are complex networks containing millions of parameters. The performance of our framework for these networks is up to a factor of about $12\sim 14$ faster for AlexNet and $46\sim 48$ faster for VGG16 to achieve an accuracy of $70\%$ and $75\%$, respectively, when compared to FALCON.

We study masking countermeasures for side-channel attacks against signature schemes constructed from the MPC-in-the-head paradigm, specifically when the MPC protocol uses preprocessing. This class of signature schemes includes Picnic, an alternate candidate in the third round of the NIST post-quantum standardization project. The only previously known approach to masking MPC-in-the-head signatures suffers from interoperability issues and increased signature sizes. Further, we present a new attack to demonstrate that known countermeasures are not sufficient when the MPC protocol uses a preprocessing phase, as in Picnic3. We overcome these challenges by showing how to mask the underlying zero-knowledge proof system due to Katz--Kolesnikov--Wang (CCS 2018) for any masking order, and by formally proving that our approach meets the standard security notions of non-interference for masking countermeasures. As a case study, we apply our masking technique to Picnic. We then implement different masked versions of Picnic signing providing first order protection for the ARM Cortex M4 platform, and quantify the overhead of these different masking approaches. We carefully analyze the side-channel risk of hashing operations, and give optimizations that reduce the CPU cost of protecting hashing in Picnic by a factor of five. The performance penalties of the masking countermeasures ranged from 1.8 to 5.5, depending on the degree of masking applied to hash function invocations.

We provide three first-order hardware maskings of the AES, each allowing for a different trade-off between the number of shares and the number of register stages. All maskings use a generalization of the changing of the guards method enabling the re-use of randomness between masked S-boxes. As a result, the maskings do not require fresh randomness while still allowing for a minimal number of shares and providing provable security in the glitch-extended probing model. The low-area variant has five cycles of latency and a serialized area cost of $8.13~kGE$. The low-latency variant reduces the latency to three cycles while increasing the serialized area by $67.89\%$ compared to the low-area variant. The maskings of the AES encryption are implemented on FPGA and evaluated with Test Vector Leakage Assessment (TVLA).

We present a framework GenoPPML for privacy-preserving machine learning in the context of sensitive genomic data processing. The technology combines secure multiparty computation techniques based on the recently proposed Manticore secure multiparty computation framework for model training and fully homomorphic encryption based on TFHE for model inference. The framework was successfully used to solve breast cancer prediction problems on gene expression datasets coming from distinct private sources while preserving their privacy - the solution winning 1st place for both Tracks I and III of the genomic privacy competition iDASH'2020. Extensive benchmarks and comparisons to existing works are performed. Our 2-party logistic regression computation is $11\times$ faster than the one in De Cock et al. on the same dataset and it uses only a single CPU core.

In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ systems in order to make full use of variables. With the help of solving MQ systems, we successfully improve preimage attacks on Keccak-224/256 reduced to 4 rounds. Moreover, we implement the preimage attack on 4-round Keccak[$r = 640,c = 160,l = 80$], an instance in the Keccak preimage challenges, and find 78-bit matched \textit{near preimages}. Due to the fundamental rule of solving MQ systems, the complexity elaboration of Crossbred algorithm is of independent interest.

The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However, it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We address this situation in several ways. We build an open-source benchmarking framework involving several use cases covering three popular libraries. Using this framework, we explore properties of the respective HHE proposals. It turns out that even medium-sized use cases are infeasible, especially when involving integer arithmetic. Next, we propose Pasta, a cipher thoroughly optimized for integer HHE use cases. Pasta is designed to minimize the multiplicative depth, while also leveraging the structure of two state-of-the-art integer HE schemes (BFV and BGV) to minimize the homomorphic evaluation latency. Using our new benchmarking environment, we extensively evaluate Pasta in SEAL and HElib and compare its properties to 8 existing ciphers in two use cases. Our evaluations show that Pasta outperforms its competitors for HHE both in terms of homomorphic evaluation time and noise consumption, showing its efficiency for applications in real-world HE use cases. Concretely, Pasta outperforms Agrasta by a factor of up to 82, Masta by a factor of up to 6 and Hera up to a factor of 11 when applied to the two use cases.

Recent progress in interactive zero-knowledge (ZK) proofs has improved the efficiency of proving large-scale computations significantly. Nevertheless, real-life applications (e.g., in the context of private inference using deep neural networks) often involve highly complex computations, and existing ZK protocols lack the expressiveness and scalability to prove results about such computations efficiently. In this paper, we design, develop, and evaluate a ZK system (Mystique) that allows for efficient conversions between arithmetic and Boolean values, between publicly committed and privately authenticated values, and between fixed-point and floating-point numbers. Targeting large-scale neural-network inference, we also present an improved ZK protocol for matrix multiplication that yields a 7× improvement compared to the state-of-the-art. Finally, we incorporate Mystique in Rosetta, a TensorFlow-based privacy-preserving framework. Mystique is able to prove correctness of an inference on a private image using a committed (private) ResNet-101 model in 28 minutes, and can do the same task when the model is public in 5 minutes, with only a 0.02% decrease in accuracy compared to a non-ZK execution when testing on the CIFAR-10 dataset. Our system is the first to support ZK proofs about neural-network models with over 100 layers with virtually no loss of accuracy.

Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them, TFHE [CGGI17] has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts, i.e., reduce the noise. Indeed, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping, in addition to reducing the noise, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases. In this paper, we propose a solution to overcome this limitation, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV [FV12] that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision. All these improvements are particularly helpful in some applications such as the evaluation of Boolean circuits (where a bootstrap is no longer required in each evaluated gate) and, more generally, in the efficient evaluation of arithmetic circuits even with large integers. Those results improve TFHE circuit bootstrapping as well. Moreover, we show that bootstrapping large precision integers is now possible using much smaller parameters than those obtained by scaling TFHE ones.

Consider a server with a large set $S$ of strings $\{x_1,x_2, \dots,x_N\}$ that would like to publish a small hash $h$ of its set $S$ such that any client with a string $y$ can send the server a short message allowing it to learn $y$ if $y \in S$ and nothing otherwise. In this work, we study this problem of two-round private set intersection (PSI) with low (asymptotically optimal) communication cost, or what we call laconic private set intersection ($\ell$PSI) and its extensions. This problem is inspired by the recent general frameworks for laconic cryptography [Cho et al. CRYPTO 2017, Quach et al. FOCS'18]. We start by showing the first feasibility result for realizing $\ell$PSI based on the CDH assumption, or LWE with polynomial noise-to-modulus ratio. However, these feasibility results use expensive non-black-box cryptographic techniques leading to significant inefficiency. Next, with the goal of avoiding these inefficient techniques, we give a construction of $\ell$PSI schemes making only black-box use of cryptographic functions. Our construction is secure against semi-honest receivers, malicious senders and reusable in the sense that the receiver's message can be reused across any number of executions of the protocol. The scheme is secure under the $\phi$-hiding, decisional composite residuosity and subgroup decision assumptions. Finally, we show natural applications of $\ell$PSI to realizing a semantically-secure encryption scheme that supports detection of encrypted messages belonging to a set of ``illegal'' messages (e.g., an illegal video) circulating online. Over the past few years, significant effort has gone into realizing laconic cryptographic protocols. Nonetheless, our work provides the first black-box constructions of such protocols for a natural application setting.

Privacy is a huge concern for cryptocurrencies and blockchains as most of these systems log everything in the clear. This has resulted in several academic and industrial initiatives to address privacy. Starting with the UTXO model of Bitcoin, initial works brought confidentiality and anonymity to payments. Recent works have expanded to support more generalized forms of private computation. Such solutions tend to be highly involved as they rely on advanced cryptographic primitives and creative techniques to handle issues related to dealing with private records (e.g. concurrency and double spending). This situation makes it hard to comprehend the current state-of-the-art, much less build on top of it. To address these challenges, we develop a systematization of knowledge for privacy-preserving solutions in blockchain. To the best of our knowledge, our work is the first of its kind. After motivating design challenges, we devise two systematization frameworks---the first as a stepping stone to the second---and use them to study the state-of-the-art. For our first framework, we study the zero-knowledge proof systems used in surveyed solutions, based on their key features and limitations. Our second is for blockchain privacy-preserving solutions; we define several dimensions to categorize the surveyed schemes and, in doing so, identify two major paradigms employed to achieve private computation. We go on to provide insights to guide solutions' adoption and development. Finally, we touch upon challenges related to limited functionality, practicality, and accommodating new developments.

In this paper, we initiate a study of asymmetric all-or-nothing transforms (or asymmetric AONTs). A (symmetric) $t$-all-or-nothing transform is a bijective mapping defined on the set of $s$-tuples over a specified finite alphabet. It is required that knowledge of all but $t$ outputs leaves any $t$ inputs completely undetermined. There have been numerous papers developing the theory of AONTs as well as presenting various applications of AONTs in cryptography and information security. In this paper, we replace the parameter $t$ by two parameters $t_o$ and $t_i$, where $t_i \leq t_o$. The requirement is that knowledge of all but $t_o$ outputs leaves any $t_i$ inputs completely undetermined. When $t_i < t_o$, we refer to the AONT as asymmetric. We give several constructions and bounds for various classes of asymmetric AONTs, especially those with $t_i = 1$ or $t_i = 2$. We pay particular attention to linear transforms, where the alphabet is a finite field $F_q$ and the mapping is linear.

The recent KEMTLS protocol (Schwabe, Stebila and Wiggers,CCS’20) is a promising design for a quantum-safe TLS handshake protocol. Focused on the web setting, wherein clients learn server public-key certificates only during connection establishment, a drawback of KEMTLS compared to TLS 1.3 is that it introduces an additional round trip before the server can send data, and an extra one for the client as well in the case of mutual authentication. In many scenarios, including IoT and embedded settings, client devices may however have the targeted server certificate pre-loaded, so that such performance penalty seems unnecessarily restrictive. This work proposes a variant of KEMTLS tailored to such scenarios. Our protocol leverages the fact that clients know the server public keys in advance to decrease handshake latency while protecting client identities. It combines medium-lived with long-term server public keys to enable a delayed form of forward secrecy even from the first data flow on, and full forward secrecy upon the first round trip. The new protocol is proved to achieve strong security guarantees, based on the security of the underlying building blocks, in a new model for multi-stage key exchange with medium-lived keys.

In distributed computations and cryptography, it is desirable to record events on a public ledger, such that later alterations are computationally infeasible. An implementation of this idea is called blockchain, which is a distributed protocol that allows the creation of an immutable ledger. While such an idea is very appealing, the ledger may be contaminated with incorrect, illegal, or even dangerous data, and everyone running the blockchain protocol has no option but to store and propagate the unwanted data. The ledger is bloated over time, and it is not possible to remove redundant information. Finally, missing data cannot be inserted later. Redactable blockchains were invented to allow the ledger to be mutated in a controlled manner. To date, redactable blockchains support at most two types of redactions: block modification and removal. The next logical step is to support block insertions. However, we show that this seemingly innocuous enhancement renders all previous constructs insecure. We put forward a model for blockchains supporting all three redaction operations, and construct a blockchain that is provably secure under this formal definition.

Side-channel attacks exploit information from physical implementations of cryptographic systems. Cache attacks have improved at recovering information by combining observations of the victim's cache access and knowledge of the cipher’s structure. Cache attacks have been implemented for most Feistel- and SPN-structured block cipher algorithms, but the security of algorithms for special structures has seen little attention. We perform a Flush+Reload attack on MISTY1, a class of block cipher with a recursive structure. The function is performed before the plaintext input S-box and after the ciphertext output S-box, making it difficult to attack the first and last rounds. However, the key scheduling part of MISTY1 leaks many bits of the key, which, together with the leakage of partial bits of the round key during encryption, is sufficient to recover it. We design an algorithm that can recover the MISTY1 128-bit key after observing encryption one time, and then use leakage during encryption to reduce its complexity. We experiment on 32- and 64-byte cache line environments. An adversary need observe as little as 5 encryptions to recover the 128-bit key in 0.035 second in the first case, and 10 encryptions to recover the key in 2.1 hours in the second case.

Homomorphic encryption (HE) is a useful variant of public key encryption (PKE), but it has a drawback that HE cannot fully achieve IND-CCA2 security, which is a standard security notion for PKE. Beyond existing HE schemes achieving weaker IND-CCA1 security, Emura et al.\ (PKC 2013) proposed the notion of \lq\lq keyed\rq\rq{} version of HE, called KH-PKE, which introduces an evaluation key controlling the functionality of homomorphic operations and achieves security stronger than IND-CCA1 and as close to IND-CCA2 as possible. After Emura et al.'s scheme which can evaluate linear polynomials only, Lai et al.\ (PKC 2016) proposed a fully homomorphic KH-PKE, but it requires indistinguishability obfuscation and hence has a drawback in practical feasibility. In this paper, we propose a \lq\lq two-level\rq\rq{} KH-PKE scheme for evaluating degree-two polynomials, by cleverly combining Emura et al.'s generic framework with a recent efficient two-level HE by Attrapadung et al.\ (ASIACCS 2018). Our scheme is the first KH-PKE that can handle non-linear polynomials while keeping practical efficiency.

For a hyperelliptic curve defined over a finite field $\bbbf_{q^n}$ with $n>1$, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the curve to reduce the size of the factorization basis and hence improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but the experiences show that reducing the size of the factor basis allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.

In recent years machine learning has become increasingly mainstream across industries. Additionally, Graphical Processing Unit (GPU) accelerators are widely deployed in various neural network (NN) applications, including image recognition for autonomous vehicles and natural language processing, among others. Since training a powerful network requires expensive data collection and computing power, its design and parameters are often considered a secret intellectual property of their manufacturers. However, hardware accelerators can leak crucial information about the secret neural network designs through side-channels, like Electro-Magnetic (EM) emanations, power consumption, or timing. We propose and evaluate non-invasive and passive reverse engineering methods to recover NN designs deployed on GPUs through EM side-channel analysis. We employ a well-known technique of simple EM analysis and timing analysis of NN layers execution. We consider commonly used NN architectures, namely Multilayer Perceptron and Convolutional Neural Networks. We show how to recover the number of layers and neurons as well as the types of activation functions. Our experimental results are obtained on a setup that is as close as possible to a real-world device in order to properly assess the applicability and extendability of our methods. We analyze the NN execution of a PyTorch python framework implementation running on Nvidia Jetson Nano, a module computer embedding a Tegra X1 SoC that combines an ARM Cortex-A57 CPU and a 128-core GPU within a Maxwell architecture. Our results show the importance of side-channel protections for NN accelerators in real-world applications.

In CRYPTO 2019, Gohr shows that well-trained neural networks can perform cryptanalytic distinguishing tasks superior to traditional differential distinguishers. Moreover, applying an unorthodox key guessing strategy, an 11-round key-recovery attack on a modern block cipher Speck32/64 improves upon the published state-of-the-art result. This calls into the next questions. To what extent is the advantage of machine learning (ML) over traditional methods, and whether the advantage generally exists in the cryptanalysis of modern ciphers? To answer the first question, we devised ML-based key-recovery attacks on more extended round-reduced Speck32/64. We achieved an improved 12-round and the first practical 13-round attacks. The essential for the new results is enhancing a classical component in the ML-based attacks, that is, the neutral bits. To answer the second question, we produced various neural distinguishers on round-reduced Simon32/64 and provided comparisons with their pure differential-based counterparts.

In this work, we propose generic and novel side-channel assisted chosen-ciphertext attacks on NTRU-based key encapsulation mechanisms (KEMs). These KEMs are IND-CCA secure, that is, they are secure in the chosen-ciphertext model. Our attacks involve the construction of malformed ciphertexts. When decapsulated by the target device, these ciphertexts ensure that a targeted intermediate variable becomes very closely related to the secret key. An attacker, who can obtain information about the secret-dependent variable through side-channels, can subsequently recover the full secret key. We propose several novel CCAs which can be carried through by using side-channel leakage from the decapsulation procedure. The attacks instantiate three different types of oracles, namely a plaintext-checking oracle, a decryption-failure oracle, and a full-decryption oracle, and are applicable to two NTRU-based schemes, which are NTRU and NTRU Prime. The two schemes are candidates in the ongoing NIST standardization process for post-quantum cryptography. We perform experimental validation of the attacks on optimized and unprotected implementations of NTRU-based schemes, taken from the open-source pqm4 library, using the EM-based side-channel on the 32-bit ARM Cortex-M4 microcontroller. All of our proposed attacks are capable of recovering the full secret key in only a few thousand chosen ciphertext queries on all parameter sets of NTRU and NTRU Prime. Our attacks, therefore, stress on the need for concrete side-channel protection strategies for NTRU-based KEMs.

Deep learning-based side-channel analysis is an effective way of performing profiling attacks on power and electromagnetic leakages, even against targets protected with countermeasures. While many research papers have reported successful results, they typically focus on profiling and attacking a single device, assuming that leakages are similar between devices of the same type. However, this assumption is not always realistic due to variations in hardware and measurement setups, creating what is known as the portability problem. Profiling multiple devices has been proposed as a solution, but obtaining access to these devices may pose a challenge for attackers. This paper proposes a new approach to overcome the portability problem by introducing a neural network layer assessment methodology based on the ablation paradigm. This methodology evaluates the sensitivity and resilience of each layer, providing valuable knowledge to create a Multiple Device Model from Single Device (MDMSD). Specifically, it involves ablating a specific neural network section and performing recovery training. As a result, the profiling model, trained initially on a single device, can be generalized to leakage traces measured from various devices. By addressing the portability problem through a single device, practical side-channel attacks could be more accessible and effective for attackers.

Searchable Symmetric Encryption (SSE) enables a client to outsource a database to an untrusted server, while retaining the ability to securely search the data. The performance bottleneck of classic SSE schemes typically does not come from their fast, symmetric cryptographic operations, but rather from the cost of memory accesses. To address this issue, many works in the literature have considered the notion of locality, a simple design criterion that helps capture the cost of memory accesses in traditional storage media, such as Hard Disk Drives. A common thread among many SSE schemes aiming to improve locality is that they are built on top of new memory allocation schemes, which form the technical core of the constructions. The starting observation of this work is that for newer storage media such as Solid State Drives (SSDs), which have become increasingly common, locality is not a good predictor of practical performance. Instead, SSD performance mainly depends on page efficiency, that is, reading as few pages as possible. We define this notion, and identify a simple memory allocation problem, Data-Independent Packing (DIP), that captures the main technical challenge required to build page-efficient SSE. As our main result, we build a page-efficient and storage-efficient data-independent packing scheme, and deduce the Tethys SSE scheme, the first SSE scheme to achieve at once O(1) page efficiency and O(1) storage efficiency. The technical core of the result is a new generalization of cuckoo hashing to items of variable size. Practical experiments show that this new approach achieves excellent performance.

We put forth a keyless wallet, a cryptocurrency wallet in which money can be spent using a password alone, and no private keys are required. It requires a smart contract blockchain. We propose two schemes. In the first, the user sets a short wallet password and can spend their money at a prespecified maturity date using the password alone. Using this as a stepping stone, we propose a second scheme, in which the user uses an OTP authenticator seed to generate a long series of time-based OTP passwords for the foreseeable future. These are encrypted and organized in a Merkle tree whose root is stored in a smart contract. The user can spend funds at any time by simply visually providing the current OTP password from an air gapped device. These OTPs can be relatively short: Just $6$ alphanumeric characters suffice. Our OTP scheme can work in proof-of-stake as well as static and variable difficulty proof-of-work blockchains. The low-entropy in the passwords and OTPs in our scheme is protected from brute force attempts by requiring that an adversary accompany any brute force attempt by a transaction on the chain. This quickly incurs enormous economic costs for the adversary. Thus, we develop the first decentralized rate limiting scheme. We use Witness Encryption (WE) to construct a timelock encryption scheme in which passwords are encrypted from past into future blocks by leveraging the NP-language expressing proof-of-work or proof-of-stake performed as the witness. Witness Encryption is a currently impractical cryptographic primitive, but our scheme may become practical as these primitives are further developed.

Abstract—CARiMoL is a novel run-time Configurable Hardware Accelerator for Ring and Module Lattice-based postquantum cryptography. It’s flexible design can be configured to key-pair generation, encapsulation, and decapsulation for NewHope and CRYSTALS-Kyber schemes using same hardware. CARiMoL offers run-time configurability for multiple security levels of NewHope and CRYSTALS-Kyber schemes, supporting both Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack (CCA) secure implementations. To the best of our knowledge, it is the first systematically designed full scale hardware accelerator for CCA-complaint multiple LBC schemes that supports run-time reconfigurability without the use of processor such as ARM Cortex series or soft core such as popular RISC-V processors. CARiMol performs logic sequencing on runtime and eliminates the cycle overhead associated with fetch and decode instructions. For the simultaneous use of Ring-LWE and Module-LWE, CARiMoL’s single hardware accelerator has 7x less area overhead as compared to combined standalone design of these schemes. CARiMoL exploits parallelism and extensive resource sharing among the different LBC schemes to achieve high performance and efficiency. Despite its reconfigurability, CARiMoL offers substantial speedup compared to the state-ofthe- art, i.e., 9x over NewHope-1024, 10x over NewHope-512, 17x over CRYSTALS-Kyber-1024, and 18x over CRYSTALSKyber-512.

Many interesting applications of pattern matching (e.g. deep-packet inspection or medical data analysis) target very sensitive data. In particular, spotting illegal behaviour in internet traffic conflicts with legitimate privacy requirements, which usually forces users (e.g. children, employees) to blindly trust an entity that fully decrypts their traffic in the name of security. The compromise between traffic analysis and privacy can be achieved through searchable encryption. However, as the traffic data is a stream and as the patterns to search are bound to evolve over time (e.g. new virus signatures), these applications require a kind of searchable encryption that provides more flexibility than the classical schemes. We indeed need to be able to search for patterns of variable sizes in an arbitrary long stream that has potentially been encrypted prior to pattern identification. To stress these specificities, we call such a scheme a stream encryption supporting pattern matching. Recent papers use bilinear groups to provide public key constructions supporting these features. These solutions are lighter than more generic ones (e.g. fully homomorphic encryption) while retaining the adequate expressivity to support pattern matching without harming privacy more than needed. However, all existing solutions in this family have weaknesses with respect to efficiency and security that need to be addressed. Regarding efficiency, their public key has a size linear in the size of the alphabet, which can be quite large, in particular for applications that naturally process data as bytestrings. Regarding security, they all rely on a very strong computational assumption that is both interactive and specially tailored for this kind of scheme. In this paper, we tackle these problems by providing two new constructions using bilinear groups to support pattern matching on encrypted streams. Our first construction shares the same strong assumption but dramatically reduces the size of the public key by removing the dependency on the size of the alphabet, while nearly halving the size of the ciphertext. On a typical application with large patterns, our public key is two order of magnitude smaller that the one of previous schemes, which demonstrates the practicality of our approach. Our second construction manages to retain most of the good features of the first one while exclusively relying on a simple (static) variant of DDH, which solves the security problem of previous works.

Differential Fault Analysis (DFA) is a well known cryptanalytic technique that exploits faulty outputs of an encryption device. Despite its popularity and similarity with the classical Differential Analysis (DA), a thorough analysis explaining DFA from a designer's point of view is missing in the literature. To the best of our knowledge, no DFA immune cipher at an algorithmic level has been proposed so far. Furthermore, all known DFA countermeasures somehow depend on the device/protocol or on the implementation such as duplication/comparison. As all of these are outside the scope of the cipher designer, we focus on designing a primitive which can protect from DFA on its own. We present the first concept of cipher level DFA resistance which does not rely on any device/protocol related assumption, nor does it depend on any form of duplication. Our construction is simple, software/hardware friendly and DFA security scales up with the state size. It can be plugged before and/or after (almost) any symmetric key cipher and will ensure a non-trivial search complexity against DFA. One key component in our DFA protection layer is an SBox with linear structures. Such SBoxes have never been used in cipher design as they generally perform poorly against differential attacks. We argue that they in fact represent an interesting trade-off between good cryptographic properties and DFA resistance. As a proof of concept, we construct a DFA protecting layer, named DEFAULT-LAYER, as well as a full-fledged block cipher DEFAULT. Our solutions compare favourably to the state-of-the-art, offering advantages over the sophisticated duplication based solutions like impeccable circuits/CRAFT or infective countermeasures.

Lattice-based schemes are promising candidates to replace the current public-key cryptographic infrastructure in wake of the looming threat of quantum computers. One of the Round 3 candidates of the ongoing NIST post-quantum standardization effort is FrodoKEM. It was designed to provide conservative security, which comes with the caveat that implementations are often bigger and slower compared to alternative schemes. In particular, the most time-consuming arithmetic operation of FrodoKEM is the multiplication of matrices with entries in Z_q. In this work, we investigate the performance of different matrix multiplication approaches in the specific setting of FrodoKEM. We consider both optimized “naïve” matrix multiplication with cubic complexity, as well as the Strassen multiplication algorithm which has a lower asymptotic run-time complexity. Our results show that for the proposed parameter sets of FrodoKEM we can improve over the state-of-the-art implementation with a row-wise blocking and packing approach, denoted as RWCF in the following. For the matrix multiplication in FrodoKEM, this results in a factor two speed-up. The impact of these improvements on the full decapsulation operation is up to 22 percent. We additionally show that for batching use-cases, where many inputs are processed at once, the Strassen approach can be the best choice from batch size 8 upwards. For a practically-relevant batch size of 128 inputs the observed speed-up is in the range of 5 to 11 percent over using the efficient RWCF approach and this speed-up grows with the batch size.

The design of zkSNARKs is increasingly complicated and requires familiarity with a broad class of cryptographic and algebraic tools. This complexity in zkSNARK design also increases the difficulty in zkSNARK implementation, analysis, and optimization. To address this complexity, we develop a new workflow for designing and implementing zkSNARKs, called $\mathsf{VOProof}$. In $\mathsf{VOProof}$, the designer only needs to construct a \emph{Vector Oracle (VO) protocol} that is intuitive and straightforward to design, and then feeds this protocol to our \emph{VO compiler} to transform it into a fully functional zkSNARK. This new workflow conceals most algebraic and cryptographic operations inside the compiler, so that the designer is no longer required to understand these cumbersome and error prone procedures. Moreover, our compiler can be fine-tuned to compile one VO protocol into multiple zkSNARKs with different tradeoffs. We apply $\mathsf{VOProof}$ to construct three general-purpose zkSNARKs targeting three popular representations of arithmetic circuits: the Rank-1 Constraint System (R1CS), the Hadamard Product Relation (HPR), and the $\mathsf{PLONK}$ circuit. These zkSNARKs have shorter and more intuitive descriptions, thus are easier to implement and optimize compared to prior works. To evaluate their performance, we implement a Python framework for describing VO protocols and compiling them into working Rust code of zkSNARKs. Our evaluation shows that the $\mathsf{VOProof}$-based zkSNARKs have competitive performance, especially in proof size and verification time, e.g., both reduced by roughly $50\%$ compared to $\mathsf{Marlin}$ (Chiesa et al., EUROCRYPT 2020). These improvements make the $\mathsf{VOProof}$-based zkSNARKs more preferable in blockchain scenarios where the proof size and verification time are critical.

We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine $T$ before declaring a challenge string $w^*$ that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number $q = q(\lambda)$ of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to $q$-key adaptive security.

A core goal of the NIST PQC competition is to produce public-key encryption (PKE) schemes which, even if attacked with a large-scale quantum computer, maintain the security guarantees needed by applications. The main security focus in the NIST PQC context has been IND-CCA security, but other applications demand that PKE schemes provide 'anonymity' (Bellare et al., ASIACRYPT 2001), and 'robustness' (Abdalla et al., TCC 2010). Examples of such applications include anonymous communication systems, cryptocurrencies, anonymous credentials, searchable encryption, and auction protocols. Almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC candidates with respect to anonymity and robustness is unknown. This paper initiates a systematic study of anonymity and robustness for post-quantum PKE schemes. Firstly, we identify implicit rejection as a crucial design choice shared by most post-quantum KEMs, show that implicit rejection renders prior results on anonymity and robustness for KEM-DEM PKEs inapplicable, and transfer prior results to the implicit-rejection setting where possible. Secondly, since they are widely used to build post-quantum PKEs, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE. We then leverage our theoretical results to study the anonymity and robustness of three NIST KEM finalists---Saber, Kyber, and Classic McEliece---and one alternate, FrodoKEM. Overall, our findings for robustness are definitive: we provide positive robustness results for Saber, Kyber, and FrodoKEM, and a negative result for Classic McEliece. Our negative result stems from a striking property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for any message 'm', we can construct a single hybrid ciphertext 'c' which decrypts to the chosen 'm' under any Classic McEliece private key. Our findings for anonymity are more mixed: we identify barriers to proving anonymity for Saber, Kyber, and Classic McEliece. We also found that in the case of Saber and Kyber, these barriers lead to issues with their IND-CCA security claims. We have worked with the Saber and Kyber teams to fix these issues, but they remain unresolved. On the positive side, we were able to prove anonymity for FrodoKEM and a variant of Saber introduced by D'Anvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also identified technical gaps in their IND-CCA security claims, but we were able to fix them.

The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt'20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

Machine learning aided cryptanalysis is an interesting but challenging research topic. At CRYPTO'19, Gohr proposed a Neural Distinguisher (ND) based on a plaintext difference. The ND takes a ciphertext pair as input and outputs its class (a real or random ciphertext pair). At EUROCRYPTO'20, Benamira et al proposed a deeper analysis of how two specific NDs against Speck32/64 work. However, there are still three research gaps that researchers are eager to fill in. (1) what features related to a ciphertext pair are learned by the ND? (2) how to explain various phenomena related to NDs? (3) what else can machine learning do in conventional cryptanalysis? In this paper, we filled in the three research gaps: (1) we first propose the Extended Differential-Linear Connectivity Table (EDLCT) which is a generic tool describing a cipher. Features corresponding to the EDLCT are designed to describe a ciphertext pair. Based on these features, various machine learning-based distinguishers including the ND are built. To explore various NDs from the EDLCT view, we propose a Feature Set Sensitivity Test (FSST) to identify which features may have a significant influence on NDs. Features identified by FSST share the same characteristic related to the cipher's round function. Surrogate models of NDs are also built based on identified features. Experiments on Speck32/64 and DES confirm that features corresponding to the EDLCT are learned by NDs. (2) We explain phenomena related to NDs via EDLCT. (3) We show how to use machine learning to search differential-linear propagations &#8710; &#8594; &#955; with a high correlation, which is a tough task in the differential-linear attack. Applications in Chaskey and DES demonstrate the advantages of machine learning. Furthermore, we provide some optional inputs to improve ND

IBM Digital Health Pass (IDHP) is a technology developed by IBM offering the technical infrastructure to allow individuals to prove their COVID19-related health status (e.g., whether that individual was tested negative for COVID19, has been partially/fully vaccinated, or recovered from COVID19) to third parties in a secure and privacy-respectful way. In a nutshell, IBM Digital Health Pass technology enables issuers, i.e., authorised healthcare providers onboarded to the system by health authorities of a given country or jurisdiction, to produce digital attestations about individuals’ health status. These attestations, called Health Certificates are issued to individuals, called subjects or holders, and are stored on a piece of paper or within subjects’ mobile phone wallets. Subjects can then demonstrate the authenticity of one or more of their Health Certificates to third parties of their choice called verifiers, when the necessity of demonstrating COVID19 related health status arises. Subjects can also demonstrate their association with each of their Health Certificates. IBM Digital Health Pass is built around preserving individuals’ privacy as a first-class requirement, based on established public key cryptography concepts in a way that can easily scale to millions of Health Certificates.

In EUROCRYPT 2020, Hosoyamada and Sasaki found that differential paths with probability $2^{-2n/3}$ can be useful in quantum collision attacks, v.s. $2^{-n/2}$ for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikoli{\'c} at CRYPTO 2009, and propose quantum multi-collision distinguishers. We use CP-tool to automatically search for the configurations for multi-collision distinguishers and rebound attacks by taking into account related-key/single-key differentials of the underlying block cipher. We apply our method to AES-like primitives including block ciphers AES, Rijndael, Saturnin and AES-hashing modes AES-DM and AES-HCF.

We construct lightweight authenticated key exchange protocols based on pre-shared keys, which achieve full forward security and rely only on simple and efficient symmetric-key primitives. All of our protocols have rigorous security proofs in a strong security model, all have low communication complexity, and are particularly suitable for resource-constrained devices. We describe three protocols that apply linear key evolution to provide different performance and security properties. Correctness in parallel and concurrent protocol sessions is difficult to achieve for linearly key-evolving protocols, emphasizing the need for assurance of availability alongside the usual confidentiality and authentication security goals. We introduce synchronization robustness as a new formal security goal, which essentially guarantees that parties can re-synchronize efficiently. All of our new protocols achieve this property. Since protocols based on linear key evolution cannot guarantee that all concurrently initiated sessions successfully derive a key, we also propose two constructions with non-linear key evolution based on puncturable PRFs. These are instantiable from standard hash functions and require O( C log(|CTR|)) memory, where C is the number of concurrent sessions and |CTR| is an upper bound on the total number of sessions per party. These are the first protocols to simultaneously achieve full forward security, synchronization robustness, and concurrent correctness.

This paper presents Multidimentional ModDiv public key exchange protocol which security is based on the hardness of an LWR problem instance consisting on finding a secret vector $\textbf{X}$ in $\mathbb{Z}_{q}^{n}$ knowing vectors $\textbf{A}$ and $\textbf{B}$ respectively in $\mathbb{Z}_{p}^{m}$ and $\mathbb{Z}_{p-q}^{m-n}$, where elements of vector $\textbf{B}$ are defined as follows : $ B(i)$ = ($\sum_{j=1}^{j=n} A(i+n-j) \times X(j)$) $ Mod(P)Div(Q)$. Mod is integer modulo, Div is integer division, P and Q are known positive integers which sizes in bits are respectively p and q which satisfy $ p > 2 \times q $. m and n satisfy $ m >2 \times n $ .

Delegating heavy computations to auxiliary servers, while keeping the inputs secret, presents a practical solution for computationally limited devices to use resource-intense cryptographic protocols, such as those based on isogenies, and thus allows the deployment of post-quantum security on mobile devices and in the internet of things. We propose two algorithms for the secure and verifiable delegation of isogeny computations in the CSIDH setting. We then apply these algorithms to different instances of CSIDH and to the signing algorithms SeaSign and CSI-FiSh. Our algorithms present a communication-cost trade-off. Asymptotically (for high communication), the cost for the delegator is reduced by a factor 9 for the original CSIDH-512 parameter set and a factor 30 for SQALE'd CSIDH-4096, while the relative cost of SeaSign vanishes. Even for much lower communication cost, we come close to these asymptotic results. Using the knowledge of the class group, the delegation of CSI-FiSh is basically free (up to element generation) already at a very low communication cost.

We work on some open problems in radical isogenies. Radical isogenies are formulas to compute chains of $N$-isogenies for small $N$ and proposed by Castryck, Decru, and Vercauteren in Asiacrypt 2020. These formulas do not need to generate a point of order $N$ generating the kernel and accelerate some isogeny-based cryptosystems like CSIDH. On the other hand, since these formulas use Tate normal forms, these need to transform Tate normal forms to curves with efficient arithmetic, e.g., Montgomery curves. In this paper, we propose radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. Our formulas compute some values determining Montgomery curves, from which one can efficiently recover Montgomery coefficients. And our formulas are more efficient for some cryptosystems than the original radical isogenies. In addition, we prove a conjecture left open by Castryck et al. that relates to radical isogenies of degree 4.

In time-specific signatures (TSS) [Paterson \& Quaglia, SCN'10] [Ishizaka \& Kiyomoto, ISC'20] with $T$ numerical values, each signer is given a secret-key associated with a numerical value $t\in[0,T-1]$ and each signature on a message is generated under a numerical range $[L,R]$ s.t. $0\leq L\leq R\leq T-1$. A signer with $t$ can correctly generate a signature under $[L,R]$ if $t$ is truly included in $[L,R]$, i.e., $t\in[L,R]$. As a generalized primitive of TSS, we propose multi-dimensional \textit{sub}-range signatures (MDSBRS). As a related primitive, we also propose multi-dimensional \textit{super}-range signatures (MDSPRS). In MDSBRS (resp. MDSPRS) with $D\in\mathbb{N}$ dimensions, each secret-key is associated with a set of $D$ ranges $\{[l_i,r_i]\mid i\in[1,D]\}$ s.t. $0 \leq l_i\leq r_i\leq T_i-1$ and a threshold value $d\in[1,D]$, and it correctly produces a signature on any message under a set of $D$ ranges $\{[L_i,R_i]\mid i\in[1,D]\}$ s.t. $0 \leq L_i\leq R_i\leq T_i-1$, if and only if total number of key-ranges every one $[l_i,r_i]$ of which is a \textit{sub}-range (resp. \textit{super}-range) of the corresponded signature-range $[L_i,R_i]$, i.e., $L_i\leq l_i\leq r_i\leq R_i$ (resp. $l_i\leq L_i\leq R_i\leq r_i$), is more than $d-1$. We show that, by extending (or generalizing) an existing TSS scheme, we obtain MDSBRS and MDSPRS schemes each one of which is secure, i.e., existentially unforgeable and perfectly (signer-)private, under standard assumption and asymptotically efficient.

Decentralized storage systems are a crucial component of the rapidly growing blockchain ecosystem. They aim to achieve robustness by proving that they store multiple replicas of every file. They have a serious limitation, though: They cannot prove that file replicas are spread across distinct systems, e.g., different hard drives. Consequently, files are vulnerable to loss in a single, locally catastrophic event. We introduce a new primitive, Proof of Geo-Retrievability or PoGeoRet, that proves that a file is located within a strict geographic boundary. Using PoGeoRet, one can, for example, prove that a file is spread across several distinct geographic regions---and by extension across multiple systems, e.g., hard drives. We define what it means for a PoGeoRet scheme to be complete and sound, extending prior formalism in key ways. We also propose GoAT, a practical PoGeoRet scheme to prove file geolocation. Unlike previous geolocation systems that only offer nominal geolocation guarantees and require dedicated anchors, GoAT geolocates provers using any timestamping server on the internet with a fixed, known location as a geolocation anchor. GoAT's geolocation guarantees directly depend on the physical constraints of the internet, making them very reliable. GoAT internally uses a communication-efficient Proof-of-Retrievability (PoRet) scheme in a novel way to achieve constant-size PoRet-component in its proofs. We validate GoAT's practicality by conducting an initial measurement study to find usable anchors and perform a real-world experiment. The results show that a significant fraction of the internet can be used as anchors and that GoAT achieves geolocation radii as low as 500km.

During the Crypto Forum Research Group (CFRG)'s standardization of password-authenticated key exchange (PAKE) protocols, a novel property emerged: a PAKE scheme is said to be ``quantum-annoying'' if a quantum computer can compromise the security of the scheme, but only by solving one discrete logarithm for each guess of a password. Considering that early quantum computers will likely take quite long to solve even a single discrete logarithm, a quantum-annoying PAKE, combined with a large password space, could delay the need for a post-quantum replacement by years, or even decades. In this paper, we make the first steps towards formalizing the quantum-annoying property. We consider a classical adversary in an extension of the generic group model in which the adversary has access to an oracle that solves discrete logarithms. While this idealized model does not fully capture the range of operations available to an adversary with a general-purpose quantum computer, this model does allow us to quantify security in terms of the number of discrete logarithms solved. We apply this approach to the CPace protocol, a balanced PAKE advancing through the CFRG standardization process, and show that the CPaceBase variant is secure in the generic group model with a discrete logarithm oracle.

Revocable identity-based encryption (RIBE) is an extension of IBE that satisfies a key revocation mechanism to manage a number of users dynamically and efficiently. To resist quantum attacks, two adaptively secure lattice-based RIBE schemes are known in the (quantum) random oracle model ((Q)ROM). Wang et al.'s scheme that is secure in the ROM has large secret keys depending on the depth of a binary tree and its security reduction is not tight. Ma and Lin's scheme that is secure in the QROM has large ciphertexts depending on the length of identities and is not anonymous. In this paper, we propose an adaptively secure lattice-based RIBE scheme that is secure in the QROM. Our scheme has compact parameters, where the ciphertext-size is smaller than Wang et al.'s scheme and the secret key size is the same as Ma and Lin's scheme. Moreover, our scheme is anonymous and its security reduction is completely tight. We design the proposed scheme by modifying Ma-Lin's scheme instantiated by the Gentry-Peikert-Vaikuntanathan (GPV) IBE. We can obtain the advantages of our scheme by making use of Katsumata et al.'s proof technique of the GPV IBE in the QROM.

The framework of interactive oracle proofs (IOP) has been used with great success to construct a number of efficient transparent zk-SNARKs in recent years. However, these constructions are based on Reed-Solomon codes and can only be applied directly to statements given in the form of arithmetic circuits or R1CS over large fields $\mathbb{F}$ since their soundness error is at least $1/|\mathbb{F}|$. This motivates the question of what is the best way to apply these IOPs to statements that are naturally written as R1CS over small fields, and more concretely, the binary field $\mathbb{F}_2$. While one can just see the system as one over an extension field $\mathbb{F}_{2^e}$ containing $\mathbb{F}_2$, this seems wasteful, as it uses $e$ bits to encode just one ``information'' bit. In fact, the recent BooLigero has devised a way to apply the well-known Ligero while being able to encode $\sqrt{e}$ bits into one element of $\mathbb{F}_{2^e}$. In this paper, we introduce a new protocol for $\mathbb{F}_2$-R1CS which among other things relies on a more efficient embedding which (for practical parameters) allows to encode $\geq e/4$ bits into an element of $\mathbb{F}_{2^e}$. Our protocol makes then black box use of lincheck and rowcheck protocols for the larger field. Using the lincheck and rowcheck introduced in Aurora and Ligero respectively we obtain $1.31 - 1.65 \times$ smaller proofs for Aurora and $3.71 \times$ for Ligero. We also estimate the reduction of prover time by a factor of $24.7 \times$ for Aurora and between $6.9 - 32.5 \times$ for Ligero without interactive repetitions. Our methodology uses the notion of reverse multiplication friendly embeddings introduced in the area of secure multiparty computation, combined with a new IOPP to test linear statements modulo a subspace $V \leq \mathbb{F}_{2^e}$ which may be of independent interest.

Today’s society depends on interconnected electronic devices, which handle various sensitive information. Due to the knowledge needed to develop these devices and the economic advantage of reusable solutions, most of these systems contain Third-Party Intellectual Property (3PIP) cores that might not be trustworthy. If one of these 3PIP cores is vulnerable, the security of the entire device is potentially affected. As a result, sensitive data that is processed by the device can be leaked to an attacker. Competitions like Hack@DAC serve as a playground to develop and examine novel approaches and computer-aided tools that identify security vulnerabilities in System-on-Chip (SoC) Register-Transfer-Level (RTL) designs. In this paper, we present a successful divide and conquer approach to test SoC security which is illustrated by exemplary RTL vulnerabilities in the competition’s SoC design. Additionally, we craft real-world software attacks that exploit these vulnerabilities.

Signature schemes based on the MPC-in-the-head approach (MPCitH) have either been designed by taking a proof system and selecting a suitable symmetric-key primitive (Picnic, CCS16), or starting with an existing primitive such as AES and trying to find the most suitable proof system (BBQ, SAC19 or Banquet, PKC21). In this work we do both: we improve certain symmetric-key primitives to better fit existing signature schemes, and we also propose a new signature scheme that combines a new, minimalist one-way function with changes to a proof system to make their combination even more efficient. Our concrete results are as follows. First, we show how to provably remove the need to include the key schedule of block ciphers. This simplifies schemes like Picnic and it also leads to the fastest and smallest AES-based signatures, where we achieve signature sizes of around 10.8 to 14.2 KB using AES-128, on average 10% shorter than Banquet and 15% faster. Second, we investigate a variant of AES with larger S-boxes we call LSAES, for which we argue that it is likely to be at least as strong as AES, further reducing the size of AES-based signatures to 9.9 KB. Finally, we present a new signature scheme, Rainier, combining a new one-way function called Rain with a Banquet-like proof system. To the best of our knowledge, it is the first MPCitH-based signature scheme which can produce signatures that are less than 5 KB in size; it also outperforms previous Picnic and Banquet instances in all performance metrics.

We propose a new bootstrapping approach that works for all three Brakerski-Gentry-Vaikuntanathan (BGV), Brakerski/Fan-Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS) schemes. This approach adopts a blind rotation technique from FHEW-type schemes. For BGV and BFV, our bootstrapping does not have any restrictions on plaintext modulus unlike typical cases of the previous methods. For CKKS, our approach introduces an error comparable to a rescaling error which enables more than 70 bits of precision after bootstrapping while consuming only 1-2 levels. Due to the high precision of the proposed bootstrapping algorithm, it is the first bootstrapping resistant to the security vulnerability of CKKS found by Li and Micciancio (Eurocrypt 2021). In addition, we introduce methods to reduce the size of public keys required for blind rotations generated by a secret key holder.

Recently, a sequence of works have made strong advances in two-round (i.e., round-optimal) secure multi-party computation (MPC). In the honest-majority setting -- the focus of this work -- Ananth et al. [CRYPTO'18, EC'19], Applebaum et al. [TCC'18, EC'19] and Garg et al. [TCC'18] have established the feasibility of general two-round MPC in standard communication models involving broadcast (BC) and private point-to-point (P2P) channels. In this work, we set out to understand what features of the communication model are necessary for these results, and more broadly the design of two-round MPC. Focusing our study on the plain model -- the most natural model for honest-majority MPC -- we obtain the following results: 1. Dishonest majority from Honest majority: In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often equivalent. This follows from our results that the former implies 2-message oblivious transfer, in many settings. (i) We show that without private point-to-point (P2P) channels, i.e., when we use only broadcast (BC) channels, honest-majority MPC implies 2-message oblivious transfer. (ii) Furthermore, this implication holds even when we use both P2P and BC, provided that the MPC protocol is robust against ``fail-stop'' adversaries. 2. Best-Achievable Security: While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the ``next best'' security notion, namely, security with identifiable abort (IA). We show that IA is also impossible to achieve with honest-majority even if we use both P2P and BC channels. However, if we replace P2P channels with a ``bare'' (i.e., untrusted) public-key infrastructure (PKI), then even security with guaranteed output delivery (and hence IA) is possible to achieve. These results ``explain'' that the reliance on P2P channels (together with BC) in the recent two-round protocols in the plain model was in fact necessary, and that these protocols couldn't have achieved a stronger security guarantee, namely, IA. Overall, our results (put together with prior works) fully determine the best-achievable security for honest-majority MPC in different communication models in two rounds. As a consequence, they yield the following hierarchy of communication models: BC < P2P < BC+P2P < BC+PKI This shows that BC channel is the weakest communication model, and that BC+PKI model is strictly stronger than BC+PTP model.

Secure hash functions are widely used in cryptographic algorithms to secure against diverse attacks. A one-way secure hash function is used in the various research fields to secure, for instance, blockchain. Notably, most of the hash functions provide security based on static parameters and publicly known operations. Consequently, it becomes easier to attack by the attackers because all parameters and operations are predefined. The publicly known parameters and predefined operations make the oracle regenerate the key even though it is a one-way secure hash function. Moreover, the sensitive data is mixed with the predefined constant where an oracle may find a way to discover the key. To address the above issues, we propose a novel one-way secure hash algorithm, OSHA for short, to protect sensitive data against attackers. OSHA depends on a pseudo-random number generator to generate a hash value. Particularly, OSHA mixes multiple pseudo-random numbers to produce a secure hash value. Furthermore, OSHA uses dynamic parameters, which is difficult for adversaries to guess. Unlike conventional secure hash algorithms, OSHA does not depend on fixed constants. It replaces the fixed constant with the pseudo-random numbers. Also, the input message is not mixed with the pseudo-random numbers; hence, there is no way to recover and reverse the process for the adversaries.

We put forth a template for constructing statistical ZAPs for NP. Our template compiles NIZKs for NP in the hidden bit model (which exist unconditionally) into statistical ZAPs using a new notion of interactive hidden-bit generator (IHBG), which adapts the notion of hidden-bit generator to the plain model by building upon the recent notion of statistically-hiding extractable commitments. We provide a construction of IHBG from the explicit hardness of the decision Diffie-Hellman assumption (where explicit refers to requiring an explicit upper bound on the advantage of any polynomial-time adversary against the assumption) and the existence of statistical ZAPs for a specific simple language, building upon the recent construction of dual-mode hidden-bit generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations of the underlying simple ZAP: 1. Using the recent statistical ZAP for the Diffie-Hellman language of (Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP assuming (the explicit hardness of) DDH in $G_1$ and kernel-DH in $G_2$ (a search assumption which is weaker than DDH), where $(G_1,G_2)$ are groups equipped with an asymmetric pairing. This improves over the recent work of (Lombardi et al., EUROCRYPT 2020) which achieved a relaxed variant of statistical ZAP for NP, under a stronger assumption. 2. Using the recent work of (Couteau et al., EUROCRYPT 2020), we obtain statistical ZAPs for NP assuming the explicit hardness of DDH, together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size $2^\secpar$ with probability better than $\poly(\secpar)/2^{(c + o(1)) \cdot \secpar}$, denoted $2^{-c\secpar}$-\OWKDM, for a constant c = 1/2, in pairing-free groups. Note that the latter is a search discrete-log-style falsifiable assumption, incomparable to DDH (in particular, it is not known to imply public-key encryption).

Information-theoretical privacy relies on randomness. Representatively, Differential Privacy (DP) has emerged as the gold standard to quantify the individual privacy preservation provided by given randomness. However, almost all randomness in existing differentially private optimization and learning algorithms is restricted to noise perturbation. In this paper, we set out to provide a privacy analysis framework to understand the privacy guarantee produced by other randomness commonly used in optimization and learning algorithms (e.g., parameter randomness). We take mixup: a random linear aggregation of inputs, as a concrete example. Our contributions are twofold. First, we develop a rigorous analysis on the privacy amplification provided by mixup either on samples or updates, where we find the hybrid structure of mixup and the Laplace Mechanism produces a new type of DP guarantee lying between Pure DP and Approximate DP. Such an average-case privacy amplification can produce tighter composition bounds. Second, both empirically and theoretically, we show that proper mixup comes almost free of utility compromise.

Despite a long history of research and wide-spread applications to censorship resistant systems, practical steganographic systems capable of embedding messages into realistic communication distributions, like text, do not exist. We identify two primary impediments to deploying universal steganography: (1) prior work leaves the difficult problem of finding samplers for non-trivial distributions unaddressed, and (2) prior constructions have impractical minimum entropy requirements. We investigate using generative models as steganographic samplers, as they represent the best known technique for approximating human communication. Additionally, we study methods to overcome the entropy requirement, including evaluating existing techniques and designing a new steganographic protocol, called Meteor. The resulting protocols are provably indistinguishable from honest model output and represent an important step towards practical steganographic communication for mundane communication channels. We implement Meteor and evaluate it on multiple computation environments with multiple generative models.

Statistical Ineffective Fault Attacks (SIFA) have been recently proposed as very powerful key-recovery strategies on symmetric cryptographic primitives' implementations. Specically, they have been shown to bypass many common countermeasures against faults such as redundancy or infection, and to remain applicable even when side-channel countermeasures are deployed. In this work, we investigate combined side-channel and fault attacks and show that a profiled, SIFA-like attack can be applied despite not having any direct ciphertext knowledge. The proposed attack exploits the ciphertext's side-channel and fault characteristics to mount successful key recoveries, even in the presence of masking and duplication countermeasures, at the cost of both side-channel and fault profiling. We analyze the attack using simulations, discuss its requirements, strengths and limitations, and compare different approaches to distinguish the correct key. Finally, we demonstrate its applicability on an ARM Cortex-M4 device, utilizing a combination of laser-based fault injection and microprobe-based EM side-channel analysis.

We present fundamental (in-)feasibility results for the strongest security notion for Secure Multi-Party Computation (MPC) that is achievable when a majority of parties is malicious, i.e. security with Identifiable Abort. As general Universally Composable (UC) MPC requires a setup, typically in the form of a Common Reference String or Common-Randomness, we investigate whether the setup must provide randomness to all parties. Given broadcast, we give tight bounds for the necessary and sufficient setup cardinality, i.e. number of participating parties, for UC-MPC protocols with Identifiable Abort. Concretely, we improve previous upper bounds by constructing Secure Function Evaluation for \(n\) parties (\(h\) of which are honest) from setups of cardinality \(\beta := \min(n,\lfloor n/h\rfloor+\lfloor(n-1)/h\rfloor-1)\) and broadcast. Conversely, we present the first general lower bound on the minimal setup cardinality for Identifiable Abort by proving that setups of cardinality \(\beta-1\) plus broadcast are insufficient even for a commitment among \(n\) parties. Somewhat surprisingly, we show that Oblivious Transfer plus broadcast is sufficient for \(n = 2h \geq 2\) which is consistent with the fact that in two-party MPC Identifiable Abort comes for free. We present the results in the Universal Composibility (UC) framework and assume the setup functionalities to be secure with Identifiable Abort. Our constructions yield an efficient (poly-time) protocol for any \(n \in \mathrm{poly}(\lambda)\) where \(\lambda\) is the security parameter if at least a constant fraction \(h \in \Theta(n)\) of parties is honest. However for \(h \in \mathrm{o}(n)\) our results suggest that for efficient protocols the overall number of parties \(n\) is limited quite severely by \(\binom{n}{\beta} \in \mathrm{poly}(\lambda)\).

Secure deduplication allows removing duplicate content at third-party storage services while preserving the privacy of users’ data. However, current solutions are built with strict designs that cannot be adapted to storage service and applications with different security and performance requirements. We present S2Dedup, a trusted hardware-based privacy-preserving deduplication system designed to support multiple security schemes that enable different levels of performance, security guarantees and space savings. An in-depth evaluation shows these trade-offs for the distinct Intel SGX-based secure schemes supported by our prototype. Moreover, we propose a novel Epoch and Exact Frequency scheme that prevents frequency analysis leakage attacks present in current deterministic approaches for secure deduplication while maintaining similar performance and space savings to state-of-the-art approaches.

Protocols that make use of oblivious transfer (OT) rarely require just one instance. Usually a batch of OTs is required --- notably, when generating base OTs for OT extension. There is a natural way to optimize 2-round OT protocols when generating a batch, by reusing certain protocol messages across all instances. In this work we show that this batch optimization is error-prone. We catalog many implementations and papers that have an incorrect treatment of this batch optimization, some of them leading to catastrophic leakage in OT extension protocols. We provide a full treatment of how to properly optimize recent 2-round OT protocols for the batch setting. Along the way we show several performance improvements to the OT protocol of McQuoid, Rosulek, and Roy (ACM CCS 2020). In particular, we show an extremely simple OT construction that may be of pedagogical interest.

In this work, we prove that Multiplexer PUF~(MPUF) and $S_N$-PUF are learnable in the PAC model. First, we show that both the designs can be represented as a function of Linear Threshold Functions. We show that the noise sensitivity of $(n,k)$-MPUF and $S_N$-PUF can be bounded by $O(2^{k} \sqrt{\epsilon})$ and $O(N\sqrt{\epsilon})$ respectively. Finally, we show that as a result of bounded noise sensitivity, both the designs can be accurately approximated using low degree algorithm. Also, the number of labelled examples~(challenge-response pairs) required by the algorithm is polynomial in the input length and PAC model parameters.

We provide a new technique for secret sharing and reconstruction for Boolean circuits, applicable in ABE systems. We show that our construction holds for Key-policy ABE and can be adapted also to Ciphertext-policy ABE. This is the most efficient solution for Attribute Based Encryption for circuits access structures using bilinear maps. Our KP-ABE system has decryption key of linear size in the number of attributes, and public parameters linear in the circuit size (Two public values for each FO-gate). We prove that our scheme is secure under the decisional bilinear Diffie-Hellman Assumption in the Selective Set Model.

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure $n$-bit to $n$-bit PRF constructions, i.e., \textsf{SoEM22} and \textsf{SoKAC21}, which are built on public permutations, where $n$ is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based $n$-bit to $n$-bit beyond the birthday bound secure PRF, which they refer to as \textsf{PDMMAC}. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based $n$-bit to $n$-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose $\textsf{pEDM}$, a single permutation based $n$-bit to $n$-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to $2^{2n/3}$ construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

Let $\mathbb{F}_{\!q}$ be a finite field and $E\!: y^2 = x^3 + ax + b$ be an elliptic $\mathbb{F}_{\!q^2}$-curve of $j(E) \not\in \mathbb{F}_{\!q}$. This article provides a new constant-time hash function $\mathcal{H}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q^2})$ indifferentiable from a random oracle. Furthermore, $\mathcal{H}$ can be computed with the cost of $3$ exponentiations in $\mathbb{F}_{\!q}$. In comparison, the actively used (indifferentiable constant-time) simplified SWU hash function to $E(\mathbb{F}_{\!q^2})$ computes $2$ exponentiations in $\mathbb{F}_{\!q^2}$, i.e., it costs $4$ ones in $\mathbb{F}_{\!q}$. In pairing-based cryptography one often uses the hashing to elliptic $\mathbb{F}_{\!q^2}$-curves $E_b\!: y^2 = x^3 + b$ (of $j$-invariant $0$) having an $\mathbb{F}_{\!q^2}$-isogeny $\tau\!: E \to E_b$ of small degree. Therefore the composition $\tau \circ \mathcal{H}\!: \{0,1\}^* \to \tau\big( E(\mathbb{F}_{\!q^2}) \big)$ is also an indifferentiable constant-time hash function.

The main approaches currently used to construct identity based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is a well understood hard problem. The first such IBE scheme was constructed by Cocks and some of its deficiencies were addressed in subsequent works. In this paper, we will focus on two constructions that address the anonymity problem inherent in Cocks' scheme and we will tackle some of their incomplete theoretical claims. More precisely, we rigorously study Clear et. al and Zhao et. al's schemes and give accurate probabilities of successful decryption and identity detection in the non-anonymized version of the schemes. Also, in the case of Zhao \emph{et. al}'s scheme, we give a proper description of the underlying security assumptions.

Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} / \mathbb{F}_{q^\ell}\), and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\). Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

Luby and Rackoff used a Feistel cipher over bit strings to construct a pseudorandom permutation from pseudorandom functions in 1988 and in 2002, Patel, Ramzan, and Sundaram generalized the construction to arbitrary abelian groups. They showed that the 3-round Feistel cipher is not superpseudorandom over abelian groups but left as an open problem a proof for non-abelian groups. We give this proof. Keywords: Feistel, non-abelian group, pseudorandom.

In this work we investigate how the choice of the key-expansion algorithm and its interaction with the round function affect the resistance of Simon-like ciphers against rotational-XOR (RX) cryptanalysis. We observe that among the key-expansion algorithms we consider, Simon is most resistant, while Simeck is much less so. Implications on lightweight ciphers design are discussed and open questions are proposed.

Deep learning techniques with neural networks are developing prominently in recent years and have been deployed in numerous applications. Despite their great success, in many scenarios it is important for the users to validate that the inferences are truly computed by legitimate neural networks with high accuracy, which is referred to as the integrity of machine learning predictions. To address this issue, in this paper, we propose zkCNN, a zero knowledge proof scheme for convolutional neural networks (CNN). The scheme allows the owner of the CNN model to prove to others that the prediction of a data sample is indeed calculated by the model, without leaking any information about the model itself. Our scheme can also be generalized to prove the accuracy of a secret CNN model on a public dataset. Underlying zkCNN is a new sumcheck protocol for proving fast Fourier transforms and convolutions with a linear prover time, which is even faster than computing the result asymptotically. We also introduce several improvements and generalizations on the interactive proofs for CNN predictions, including verifying the convolutional layer, the activation function of ReLU and the max pooling. Our scheme is highly efficient in practice. It can support the large CNN of VGG16 with 15 million parameters and 16 layers. It only takes 88.3 seconds to generate the proof, which is 1264 times faster than existing schemes. The proof size is 341 kilobytes, and the verifier time is only 59.3 milliseconds. Our scheme can further scale to prove the accuracy of the same CNN on 20 images.

Post-quantum cryptography (PQC) has a well-deserved NIST status. Our approach (R-Propping) replaces all numeric field arithmetic with GF(2^8) field operations. This method yields both classical and quantum secure protocols. The present work is dedicated to strengthening a chaotic Wolfram Class III cellular automata and discuss its usability as a cryptographical secure PRBG (pseudorandom bit generator), a building block for stream-ciphers, hashing, and other random numbers requiring protocols.

Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present inherent trade-offs. Synchronous protocols tolerate up to $n/2$ Byzantine faults, while asynchronous or partially synchronous protocols tolerate only up to $n/3$ Byzantine faults. In this work, we generalize the fault thresholds of BFT and introduce a new problem called multi-threshold BFT. Multi-threshold BFT has four separate fault thresholds for safety and liveness under synchrony and asynchrony (or partial-synchrony), respectively. Decomposing the fault thresholds in this way allows us to design protocols that provide meaningful fault tolerance under both synchrony and asynchrony (or partial synchrony). We establish tight fault thresholds bounds for multi-threshold BFT and present protocols achieving them. As an example, we show a BFT state machine replication (SMR) protocol that tolerates up to $2n/3$ faults for safety under synchrony while tolerating up to $n/3$ faults for other scenarios (liveness under synchrony as well as safety and liveness under partial synchrony). This is strictly stronger than classic partially synchronous SMR protocols. We also present a general framework to transform known partially synchronous or asynchronous BFT SMR protocols to additionally enjoy the optimal $2n/3$ fault tolerance for safety under synchrony.

We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages. Using OT to deliver messages helps AOT resist blending (n&#8722;1) attacks and helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT. AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag, derived from a secret shared between the sender and receiver, with the public key of a Level-2 node and sends them to a Level-1 node. On a public bulletin board, Level-3 nodes publish tags associated with messages ready to be retrieved. Each receiver checks the bulletin board, identifies tags, and receives the associated messages using OT. A receiver can receive their messages even if the receiver is offline when messages are ready. Through what we call a "handshake" process, communicants can use the AOT protocol to establish shared secrets anonymously. Users play an active role in contributing to the unlinkability of messages: periodically, users initiate requests to AOT to receive dummy messages, such that an adversary cannot distinguish real and dummy requests.

Pravuil is a robust, secure, and scalable consensus protocol for a permissionless blockchain suitable for deployment in an adversarial environment such as the Internet. Pravuil circumvents previous shortcomings of other blockchains: - Bitcoin’s limited adoption problem: as transaction demand grows, payment confirmation times grow much lower than other PoW blockchains - higher transaction security at a lower cost - more decentralisation than other permissionless blockchains - impossibility of full decentralisation and the blockchain scalability trilemma: decentralisation, scalability, and security can be achieved simultaneously - Sybil-resistance for free implementing the social optimum - Pravuil goes beyond the economic limits of Bitcoin or other PoW/PoS blockchains, leading to a more valuable and stable crypto-currency

Grover search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. In order to perform Grover search algorithm, the target algorithm should be implemented in a quantum circuit. For this reason, we propose an optimal SM3 hash function (Chinese standard) in a quantum circuit. We focused on minimizing the use of qubits together with reducing the use of quantum gates. To do this, the on-the-fly approach is utilized for message expansion and compression functions. In particular, the previous value is restored and used without allocating new qubits in the permutation operation. Finally, we estimate quantum resources required for the quantum pre-image attack based on the proposed SM3 hash function implementation in the quantum circuit.

The SM4 block cipher is a Chinese domestic crpytographic that was introduced in 2003. Since the algorithm was developed for the use in wireless sensor networks, it is mandated in the Chinese National Standard for Wireless LAN WAPI (Wired Authentication and Privacy Infrastructure). The SM4 block cipher uses a 128-bit block size and a 32-bit round key. This consists of 32 rounds and one reverse translation \texttt{R}. In this paper, we present the optimized implementation of the SM4 block cipher on 8-bit AVR microcontrollers, which are widely used in wireless sensor devices, the optimized implementation of the SM4 block cipher on 32-bit RISC-V processors, which are open-source based computer architectures, and the optimized implementation of SM4 on 64-bit ARM processors with the parallel computation, which are widely used in smartphone and tablet. In the AVR microcontroller, it is implemented in three versions, including speed-optimization, memory-optimization, and code-optimization. As a result, speed-optimization, memory-optimization, and code-optimization achieved 205.2 cycles per byte, 213.3 cycles per byte and 207.4 cycles per byte, respectively. This is faster than the reference implementation written in C (1670.7 cycles per byte). The implementation on 32-bit RISC-V processors 128.8 cycles per byte. This is faster than the reference C code implementation (345.7 cycles per byte). The implementation on 64-bit ARM processors is 8.62 cycles per byte. This is faster than the reference C code implementation (120.07 cycles per byte).

Cloud storage services are top-rated, but there are often concerns about the security of the files there stored. Clouds-of-clouds or multi-clouds are being explored in order to improve that security. The idea is to store the files in several clouds, ensuring integrity and availability. Confidentiality, however, is obtained by encrypting the files with block ciphers that do not provide provable security. Secret sharing allows distributing files among the clouds providing information-theoretic security/secrecy. However, existing secret sharing schemes are space-inefficient (the size of the shares is much larger than the size of the secret) or purely theoretical. In this paper, we propose the first practical space-efficient secret sharing scheme that provides information-theoretic security, which we denominate PRactical Efficient Secret Sharing (PRESS). Moreover, we present the Secure CloUD storage (SCUD) service, a new cloud-of-clouds storage service that leverages PRESS to provide file confidentiality. Additionally, SCUD provides data integrity and availability, leveraging replication.

In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities. These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central in different cryptographic constructions such as stream ciphers, pseudorandom generators, and weak pseudorandom functions. We provide examples for each property and determine the exact algebraic immunity of candidate constructions.

Guillou-Quisquater (GQ) signature is an efficient RSA-based digital signature scheme amongst the most famous Fiat-Shamir follow-ons owing to its good simplicity. However, there exist two bottlenecks for GQ hindering its application in industry or academia: the RSA trapdoor $n=pq$ in the key generation phase and its high bandwidth caused by the storage-consuming representation of RSA group elements (3072 bits per one element in 128-bit security). In this paper, we first formalize the definition and security proof of class group based GQ signature (CL-GQ), which eliminates the trapdoor in key generation phase and improves the bandwidth efficiency from the RSA-based GQ signature. Then, we construct a trustless GQ multi-signature scheme by applying non-malleable equivocable commitments and our well-designed compact non-interactive zero-knowledge proofs (NIZK). Our scheme has a well-rounded performance compared to existing multiparty GQ, Schnorr and ECDSA schemes, in the aspects of bandwidth (no range proof or multiplication-to-addition protocol required), rather few interactions (only 4 rounds in signing), provable security in \textit{dishonest majority model} and identifiable abort property. Another interesting finding is that, our NIZK is highly efficient (only one round required) by using the Bezout formula, and this trick can also optimize the ZK proof of Paillier ciphertext which greatly improves the speed of Yi's Blind ECDSA (AsiaCCS 2019).

Today's microprocessors often rely on microcode updates to address issues such as security or functional patches. Unfortunately, microcode update flexibility opens up new attack vectors through malicious microcode alterations. Such attacks share many features with hardware Trojans and have similar devastating consequences for system security. However, due to microcode's opaque nature, little is known in the open literature about the capabilities and limitations of microcode Trojans. We introduce the design of a microcoded RISC-V processor architecture together with a microcode development and evaluation environment. Even though microcode typically has almost complete control of the processor hardware, the design of meaningful microcode Trojans is not straightforward. This somewhat counter-intuitive insight is due to the lack of information at the hardware level about the semantics of executed software. In three security case studies we demonstrate how to overcome these issues and give insights on how to design meaningful microcode Trojans that undermine system security. To foster future research and applications, we publicly release our implementation and evaluation platform.

In this paper, we study implementations of post-quantum signature schemes on resource-constrained devices. We focus on verification of signatures and cover NIST PQC round-3 candidates Dilithium, Falcon, Rainbow, GeMSS, and SPHINCS+. We assume an ARM CortexM3 with 8 kB of memory and 8 kB of flash for code; a practical and widely deployed setup in, for example, the automotive sector. This amount of memory is insufficient for most schemes. Rainbow and GeMSS public keys are too big; SPHINCS+ signatures do not fit in this memory. To make signature verification work for these schemes, we stream in public keys and signatures. Due to the memory requirements for efficient Dilithium implementations, we stream in the public key to cache more intermediate results. We discuss the suitability of the signature schemes for streaming, adapt existing implementations, and compare performance.

This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA when the underlying primitives are replaced with 16-round, 17-round, and 16-round versions of GIFT-128. The resistance of GIFT-128 against linear cryptanalysis is also evaluated. We present a 24-round key-recovery attack on GIFT-128 with a newly obtained 19-round linear approximation. We note that the attack results in this paper are far from threatening the security of GIFT-COFB, SUNDAE-GIFT, HyENA, and GIFT-128.

The proof-of-stake (PoS) protocols have been proposed to eliminate the unnecessary waste of computing power in Bitcoin. Multiple practical and provably secure designs have been developed, such as Ouroboros Praos (Eurocrypt 2018), Snow White (FC 2019), and more. However, an important security property called unpredictability has not been carefully studied in these provably secure PoS. Unpredictability property is critical for PoS since the attackers could use predictability to launch strengthened versions of multiple attacks (e.g., selfish-mining and bribing). Unpredictability has previously been investigated by Brown-Cohen et al. (EC 2019) in incentive-driven settings. In this paper, we investigate the property in the cryptographic setting, to achieve the ''best possible'' unpredictability for PoS. First, we present an impossibility result for all proof-of-stake protocols under the single-extension design framework. In this framework, each honest player is allowed to extend exactly one chain in each round; the state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than $73\%$ of stake is honest. Then, to overcome the impossibility result, we introduce a new design framework, called multi-extension PoS, which allows each honest player to extend multiple chains in a round. We develop a novel strategy called ''$D$-distance-greedy'' strategy (where $D$ is a positive integer), in which honest players are allowed to extend a set of best chains that are ''close'' to the longest chain. (Of course, malicious players are allowed to behave arbitrarily in the protocol execution.) This ''$D$-distance-greedy'' strategy enables us to construct a class of PoS protocols that achieve the best possible unpredictability. Plus, we design a new tiebreak rule for the multi-extension protocol to choose the best chain that can be extended faster. This ensures that the adversary cannot slowdown the chain growth of honest players. Note, these protocols can be proven secure, assuming a much smaller fraction (e.g., $57\%$) of stake to be honest. To enable a thorough security analysis in the cryptographic setting, we develop several new techniques. As the players are allowed to extend multiple chains, the analysis of chain growth is highly non-trivial. We introduce a new analysis framework to analyze the chain growth of a multi-extension protocol. To prove the common prefix property, we introduce a new concept called ''virtual chains'', and then present a reduction from the regular version of the common prefix to ''common prefix w.r.t. virtual chains''.

This technical report provides extensive information for designing, implementing, fabricating, and validating CoPHEE: A Co-Processor for Partially Homomorphic Encrypted Execution, complementing the publication appearing in the 2019 IEEE Hardware-Oriented Security and Trust symposium.

We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does not prevent adaptive key recovery attacks.

Non-malleable secret sharing (NMSS) schemes, introduced by Goyal and Kumar (STOC 2018), ensure that a secret $m$ can be distributed into shares $m_1,...,m_n$ (for some $n$), such that any $t$ (a parameter $<=n$) shares can be reconstructed to recover the secret $m$, any $t-1$ shares doesn't leak information about $m$ and even if the shares that are used for reconstruction are tampered, it is guaranteed that the reconstruction of these tampered shares will either result in the original $m$ or something independent of $m$. Since their introduction, non-malleable secret sharing schemes sparked a very impressive line of research. In this work, we introduce a feature of local reconstructability in NMSS, which allows reconstruction of any portion of a secret by reading just a few locations of the shares. This is a useful feature, especially when the secret is long or when the shares are stored in a distributed manner on a communication network. In this work, we give a compiler that takes in any non-malleable secret sharing scheme and compiles it into a locally reconstructable non-malleable secret sharing scheme. To secret share a message consisting of $k$ blocks of length $l$ each, our scheme would only require reading $l + log k$ bits (in addition to a few more bits, whose quantity is independent of $l$ and $k$) from each party's share (of a reconstruction set) to locally reconstruct a single block of the message. We show an application of our locally reconstructable non-malleable secret sharing scheme to a computational non-malleable secure message transmission scheme in the pre-processing model, with an improved communication complexity, when transmitting multiple messages.

Automatic modelling to search distinguishers with high probability covering as many rounds as possible, such as MILP, SAT/SMT, CP models, has become a very popular cryptanalysis topic today. In those models, the optimizing objective is usually the probability or the number of rounds of the distinguishers. If we want to recover the secret key for a round-reduced block cipher, there are usually two phases, i.e., finding an efficient distinguisher and performing key-recovery attack by extending several rounds before and after the distinguisher. The total attacked number of rounds is not only related to the chosen distinguisher, but also to the extended rounds before and after the distinguisher. In this paper, we try to combine the two phases in a uniform automatic model. Concretely, we apply this idea to automate the related-key rectangle attacks on SKINNY and ForkSkinny. We propose some new distinguishers with advantage to perform key-recovery attacks. Our key-recovery attacks on a few versions of round-reduced SKINNY and ForkSkinny cover 1 to 2 more rounds than the best previous attacks.

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor's attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new attack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent cryptanalysis.

We propose a novel primitive called NIVA that allows the distributed aggregation of multiple users' secret inputs by multiple untrusted servers. The returned aggregation result can be publicly verified in a non-interactive way, i.e. the users are not required to participate in the aggregation except for providing their secret inputs. NIVA allows the secure computation of the sum of a large amount of users' data and can be employed, for example, in the federated learning setting in order to aggregate the model updates for a deep neural network. We implement NIVA and evaluate its communication and execution performance and compare it with the current state-of-the-art, i.e. Segal et al. protocol (CCS 2017) and Xu et al. VerifyNet protocol (IEEE TIFS 2020), resulting in better user's communicated data and

We define smooth zero-knowledge hash functions (SZKHFs) as smooth projective hash functions (SPHFs) for which the completeness holds even when the language parameter lpar and the projection key HP were maliciously generated. We prove that blackbox SZKHF in the plain model is impossible even if lpar was honestly generated. We then define SZKHF in the registered public key (RPK) model, where both lpar and HP are possibly maliciously generated but accepted by an RPK server, and show that the CRS-model trapdoor SPHFs of Benhamouda et al. are also secure in the weaker RPK model. Then, we define and instantiate subversion-zero knowledge SZKHF in the plain model. In this case, both lpar and HP are completely untrusted, but one uses non-blackbox techniques in the security proof.

In this work, we present a novel approach, called Detector+ , to detect, isolate, and prevent timing-based side channel attacks (i.e., timing attacks) at runtime. The proposed approach is based on a simple observation that the time measurements required by the timing attacks differ from those required by the benign applications as these attacks need to measure the execution times of typically quite short-running operations. Detector+ , therefore, monitors the time readings made by processes and mark consecutive pairs of readings that are close to each other in time as suspicious. In the presence of suspicious time measurements, Detector+ introduces noise into the measurements to prevent the attacker from extracting information by using these measurements. The sequence of suspicious time measurements are then analyzed by using a sliding window based approach to pinpoint the malicious processes at runtime. We have empirically evaluated the proposed approach by using five well known timing attacks, including Meltdown, together with their variations, representing some of the mechanisms that an attacker can employ to become stealthier. In one evaluation setup, each type of attack was carried out concurrently by multiple processes. In the other setup, multiple types of attacks were carried out concurrently. In all the experiments, Detector+ detected all the malicious time measurements with almost a perfect accuracy, prevented all the attacks, and correctly pinpointed all the malicious processes involved in the attacks without any false positives after they have made a few time measurements with an average runtime overhead of 1.56%.

Decentralized ledgers that support rich applications suffer from three limitations. First, applications are provisioned tiny execution environments with limited running time, minimal stack size, and restrictive instruction sets. Second, applications must reveal their state transition, enabling miner frontrunning attacks and consensus instability. Third, applications offer weak guarantees of correctness and safety. We design, implement, and evaluate Leo, a new programming language designed for formally verified, zero-knowledge applications. Leo provisions a powerful execution environment that is not restricted in running time, stack size, or instruction sets. Besides offering application privacy and mitigating miner-extractable value (MEV), Leo achieves two fundamental properties. First, applications are formally verified with respect to their high-level specification. Second, applications can be succinctly verified by anyone, regardless of the size of application. Leo is the first known programming language to introduce a testing framework, package registry, import resolver, remote compiler, formally defined language, and theorem prover for general-purpose, zero-knowledge applications.

Many security properties of interest are captured by instrumented semantics that model the functional behavior and the leakage of programs. For several important properties, including cryptographic constant-time (CCT), leakage models are sufficiently abstract that one can define instrumented semantics for high-level and low-level programs. One important goal is then to relate leakage of source programs and leakage of their compilation---this can be used, e.g.\, to prove preservation of CCT. To simplify this task, we put forward the idea of structured leakage. In contrast to the usual modeling of leakage as a sequence of observations, structured leakage is tightly coupled with the operational semantics of programs. This coupling greatly simplifies the definition of leakage transformers that map the leakage of source programs to leakage of their compilation and yields more precise statements about the preservation of security properties. We illustrate our methods on the Jasmin compiler and prove preservation results for two policies of interest: CCT and cost.

Goldreich's pseudorandom generator is a well-known building block for many theoretical cryptographic constructions from multi-party computation to indistinguishability obfuscation. Its unique efficiency comes from the use of random local functions: each bit of the output is computed by applying some fixed public $n$-variable Boolean function $f$ to a random public size-$n$ tuple of distinct input bits. The characteristics that a Boolean function $f$ must have to ensure pseudorandomness is a puzzling issue. It has been studied in several works and particularly by Applebaum and Lovett (STOC 2016) who showed that resiliency and algebraic immunity are key parameters in this purpose. In this paper, we propose the first study on Boolean functions that reach together maximal algebraic immunity and high resiliency. 1) We assess the possible consequences of the asymptotic existence of such optimal functions. We show how they allow to build functions reaching all possible algebraic immunity-resiliency trade-offs (respecting the algebraic immunity and Siegenthaler bounds). We provide a new bound on the minimal number of variables~$n$, and thus on the minimal locality, necessary to ensure a secure Goldreich's pseudorandom generator. Our results come with a granularity level depending on the strength of our assumptions, from none to the conjectured asymptotic existence of optimal functions. 2) We extensively analyze the possible existence and the properties of such optimal functions. Our results show two different trends. On the one hand, we were able to show some impossibility results concerning existing families of Boolean functions that are known to be optimal with respect to their algebraic immunity, starting by the promising XOR-MAJ functions. We show that they do not reach optimality and could be beaten by optimal functions if our conjecture is verified. On the other hand, we prove the existence of optimal functions in low number of variables by experimentally exhibiting some of them up to $12$ variables. This directly provides better candidates for Goldreich's pseudorandom generator than the existing XOR-MAJ candidates for polynomial stretches from $2$ to $6$.

COFB is a lightweight Authenticated Encryption with Associated Data (AEAD) mode based on block ciphers. It was proposed in CHES 2017 and is the basis for GIFT-COFB, a finalist in the NIST lightweight standardization project. It comes with provable security results that guarantee its security up to the birthday bound in the nonce-respecting model. However, the designers offer multiple versions of the analysis with different details and the implications of attacks against the scheme are not discussed deeply. In this article, we look at a group of possible forgery and privacy attacks against COFB. We show that the security for both forgery and privacy is bounded by the number of forgery attempts. We show the existence of forgery and privacy attacks with success probability $q_d/2^{n/2}$, given $q_d$ forgery attempts. In particular, we show an attack with $2^{n/2}$ attempts using only a single known-plaintext encryption query against COFB. While these attacks do not contradict the claims made by the designers of GIFT-COFB, they show its limitations in terms of the number of forgery attempts. They also show that, while COFB generates a 128-bit tag, it behaves in a very similar manner to an AEAD scheme with 64-bit tag. As a result of independent interest, our analysis provides a contradiction to the main theorem of {\it Journal of Cryptology volume 33, pages 703–741 (2020)}, which includes an improved security proof of COFB compared to the CHES 2017 version. Finally, we discuss the term $nq_d/2^{n/2}$ that appears in the security proof of GIFT-COFB and CHES 2017, showing why there is a security gap between the provable results and the attacks. We emphasize that the results in this article do not threaten the security of GIFT-COFB in the scope of the NIST lightweight cryptography requirements or the claims made by the designers in the specification document of the design.

RSA cryptography is an asymmetric communication protocol, and it is facing diverse issues. Recent research works suggest that RSA security has already broken. On the contrary, AES is the most used symmetric-key cryptography protocol, and it is also facing issues. Literature search suggests that there is an issue of cryptanalysis attacks. A shared secret key requires for AES cryptography. The most famous key exchange protocol is Diffie-Hellman; however, it has an issue of the number field sieve discrete log algorithm attacks. Moreover, recent research suggested that Diffie-Hellman is less secure than widely perceived. Moreover, there is another issue of Logjam attack that allows man-in-middle attack in Diffie-Hellman. Thus, we combine RSA, AES, and Diffie-Hellman algorithm to provide security on the key exchange protocol, called privateDH. Our key objective is to provide security to the Diffie-Hellman Algorithm. Therefore, privateDH does not share the data publicly with the intended party. Instead, privateDH encrypts all shareable data in the time of key exchange by encrypting using the AES algorithm. privateDH uses the RSA algorithm and retrieves the public key to avoid a man-in-the-middle attack. Thus, we demonstrate how to provide security to the Diffie-Hellman algorithm to defeat various kinds of attacks.

Graphics processing units (GPUs) are specially designed for parallel applications and perform parallel operations much faster than central processing units (CPUs). In this work, we focus on the performance of the Advanced Encryption Standard (AES) on GPUs. We present optimizations which remove bank conflicts in shared memory accesses and provide 878.6 Gbps throughput for AES-128 encryption on an RTX 2070 Super, which is equivalent to 4.1 Gbps per Watt. Our optimizations provide more than 2.56x speed-up against the best GPU results in the literature. Our optimized AES implementations on GPUs even outperform any CPU using the hardware level AES New Instructions (AES-NI) and legacy FPGA-based cluster architectures like COPACOBANA and RIVYERA. Even on a low-end GPU like MX 250, we obtained 60.0 Gbps throughput for AES-256 which is generally faster than the read/write speeds of solid disks. Thus, transition from AES-128 to AES-256 when using GPUs would provide military grade security with no visible performance loss. With these breakthrough performances, GPUs can be used as a cryptographic co-processor for file or full disk encryption to remove performance loss coming from CPU encryption. With a single GPU as a co-processor, busy SSL servers can be free from the burden of encryption and use their whole CPU power for other operations. Moreover, these optimizations can help GPUs to practically verify theoretically obtained cryptanalysis results or their reduced versions in reasonable time.