We prove that the module learning with errors (M-LWE) problem with arbitrary polynomial-sized modulus p is classically at least as hard as standard worst-case lattice problems, as long as the module rank d is not smaller than the number field degree n. Previous publications only showed the hardness under quantum reductions. We achieve this result in an analogous manner as in the case of the learning with errors (LWE) problem. First, we show the classical hardness of M-LWE with an exponential-sized modulus. In a second step, we prove the hardness of M-LWE using a binary secret. And finally, we provide a modulus reduction technique. The complete result applies to the class of power-of-two cyclotomic fields. However, several tools hold for more general classes of number fields and may be of independent interest.

We analyze the multi-user security of the streaming encryption in Google's Tink library via an extended version of the framework of nonce-based online authenticated encryption of Hoang et al. (CRYPTO'15) to support random-access decryption. We show that Tink's design choice of using random nonces and a nonce-based key-derivation function indeed improves the concrete security bound. We then give two better alternatives that are more robust against randomness failure. In addition, we show how to efficiently instantiate the key-derivation function via AES, instead of relying on HMAC-SHA256 like the current design in Tink. To accomplish this we give a multi-user analysis of the XOR-of-permutation construction of Bellare, Krovetz, and Rogaway (EUROCRYPT'98).

Let S = {1,...,n} be a set of integers and X be a subset of S. We study the boolean function f_X(Y) which outputs 1 if and only if Y is a small enough superset (resp., big enough subset) of X. Our purpose is to protect X from being known when the function is evasive, yet allow evaluations of f_X on any input Y \subseteq S. The corresponding research area is called function obfuscation. The two kinds of functions are called small superset functions (SSF) and big subset functions (BSF), respectively. In this paper, we obfuscate SSF and BSF in a very simple and efficient way. We prove both input-hiding security and virtual black-box (VBB) security based on the subset product problem. We also give a proof of input-hiding based on the discrete logarithm problem (DLP) for the conjunction obfuscation by Bartusek et al. [4] (see Appendix A) and propose a new conjunction obfuscation based on SSF and BSF obfuscation (see Appendix B). The security of our conjunction obfuscation is from our new computational problem called the twin subset product problem.

This paper contains an analysis of decentralized exchange governance as an effective framework for voting, profit sharing baking and partially updating the system with a possibility to create new pairs for decentralized exchange with automatic market-making. It will also review 2 alternative baker election and rotation mechanisms such as “Simple first-place voting protocol” and “First-place with veto protocol” and will provide a more in-depth look on these mechanisms. It will examine a proposed architectural software solution for monitoring the decentralized network to mediate deviant baker behavior - the watchtower.

The protection of intellectual property (IP) rights of well-trained deep learning (DL) models has become a matter of major concern, especially with the growing trend of deployment of Machine Learning as a Service (MLaaS). In this work, we demonstrate the utilization of a hardware root-of-trust to safeguard the IPs of such DL models which potential attackers have access to. We propose an obfuscation framework called Hardware Protected Neural Network (HPNN) in which a deep neural network is trained as a function of a secret key and then, the obfuscated DL model is hosted on a public model sharing platform. This framework ensures that only an authorized end-user who possesses a trustworthy hardware device (with the secret key embedded on-chip) is able to run intended DL applications using the published model. Extensive experimental evaluations show that any unauthorized usage of such obfuscated DL models result in significant accuracy drops ranging from 73.22 to 80.17% across different neural network architectures and benchmark datasets. In addition, we also demonstrate the robustness of proposed HPNN framework against a model fine-tuning type of attack.

Multivariate cryptography studies applications of endomorphisms of K[x_1, x_2, …, x_n] where K is a finite commutative ring. The importance of this direction for the construction of multivariate digital signature systems is well known. We suggest modification of the known digital signature systems for which some of cryptanalytic instruments were found . This modification prevents possibility to use recently developed attacks on classical schemes such as rainbow oil and vinegar system, and LUOV. Modification does not change the size of hashed messages and size of signatures. Basic idea is the usage of multivariate messages of unbounded degree and polynomial density for the construction of public rules. Modified algorithms are presented for standardization and certification studies.

In recent years, deep neural networks (DNN) have become an important type of intellectual property due to their high performance on various classification tasks. As a result, DNN stealing attacks have emerged. Many attack surfaces have been exploited, among which cache timing side-channel attacks are hugely problematic because they do not need physical probing or direct interaction with the victim to estimate the DNN model. However, existing cache-side-channel-based DNN reverse engineering attacks rely on analyzing the binary code of the DNN library that must be shared between the attacker and the victim in the main memory. In reality, the DNN library code is often inaccessible because 1) the code is proprietary, or 2) memory sharing has been disabled by the operating system. In our work, we propose GANRED, an attack approach based on the generative adversarial nets (GAN) framework which utilizes cache timing side-channel information to accurately recover the structure of DNNs without memory sharing or code access. The benefit of GANRED is four-fold. 1) There is no need for DNN library code analysis. 2) No shared main memory segment between the victim and the attacker is needed. 3) Our attack locates the exact structure of the victim model, unlike existing attacks which only narrow down the structure search space. 4) Our attack efficiently scales to deeper DNNs, exhibiting only linear growth in the number of layers in the victim DNN.

Gated Recurrent Unit (GRU) has broad application fields, such as sentiment analysis, speech recognition, malware analysis, and other sequential data processing. For low-cost deployment and efficient machine learning services, a growing number of model owners choose to deploy the trained GRU models through Machine-learning-as-a-service (MLaaS). However, privacy has become a significant concern for both model owners and prediction clients, including model weights privacy, input data privacy, and output results privacy. The privacy leakage may be caused by either external intrusion or insider attacks. To address the above issues, this research designs a framework for privacy-preserving GRU models, which aims for privacy scenarios such as predicting on textual data, network packets, heart rate data, and so on. In consideration of accuracy and efficiency, this research uses additive secret sharing to design the basic operations and gating mechanisms of GRU. The protocols can meet the security requirements of privacy and correctness under the Universal Composability framework with the semi-honest adversary. Additionally, the framework and protocols are realized with a proof-of-concept implementation. The experiment results are presented with respect to time consumption and inference accuracy.

Oblivious transfer (OT) is an essential cryptographic tool that can serve as a building block for almost all secure multiparty functionalities. The strongest security notion against malicious adversaries is universal composability (UC-secure). An important goal is to have post-quantum OT protocols. One area of interest for post-quantum cryptography is isogeny-based crypto. Isogeny-based cryptography has some similarities to Diffie-Hellman, but lacks some algebraic properties that are needed for discrete-log-based OT protocols. Hence it is not always possible to directly adapt existing protocols to the isogeny setting. We propose the first practical isogeny-based UC-secure oblivious transfer protocol in the presence of malicious adversaries. Our scheme uses the CSIDH framework and does not have an analogue in the Diffie-Hellman setting. The scheme consists of a constant number of isogeny computations. The underlying computational assumption is a problem that we call the computational reciprocal CSIDH problem, and that we prove polynomial-time equivalent to the computational CSIDH problem.

The private join and compute (PJC) functionality enables secure computation over data distributed across different databases, which is a functionality with a wide range of applications, many of which address settings where the input databases are of significantly different sizes. We introduce the notion of private information retrieval (PIR) with default, which enables two-party PJC functionalities in a way that hides the size of the intersection of the two databases and incurs sublinear communication cost in the size of the bigger database. We provide two constructions for this functionality, one of which requires offline linear communication, which can be amortized across queries, and one that provides sublinear cost for each query but relies on more computationally expensive tools. We construct inner-product PJC, which has applications to ads conversion measurement and contact tracing, relying on an extension of PIR with default. We evaluate the efficiency of our constructions, which can enable $\mathbf{2^{12}}$ PIR with default lookups on a database of size $\mathbf{2^{30}}$ (or inner-product PJC on databases with such sizes) with the communication of $\mathbf{945}$MB, which costs less than $\mathbf{\$0.04}$ for the client and $\mathbf{\$5.22}$ for the server.

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: - the Learning with Error (LWE) assumption (with subexponential modulus-to-noise ratio); - a circular security conjecture regarding the Gentry-Sahai-Water's (GSW) encryption scheme and a Packed version of Regev's encryption scheme. The circular security conjecture states that a notion of leakage-resilient security, that we prove is satisfied by GSW assuming LWE, is retained in the presence of an encrypted key-cycle involving GSW and Packed Regev. Our work thus places iO on qualitatively similar assumptions as (unlevelled) FHE, for which known constructions also rely on a circular security conjecture.

We construct a VBB and perfect circuit-hiding obfuscator for evasive deterministic finite automata using a matrix encoding scheme with a limited zero-testing algorithm. We construct the matrix encoding scheme by extending an existing matrix FHE scheme. Using obfuscated DFAs we can for example evaluate secret regular expressions or disjunctive normal forms on public inputs. In particular, the possibility of evaluating regular expressions solves the open problem of obfuscated substring matching.

Side-channel attacks exploit information that is leaked from hardware. The differential power analysis (DPA) attack aims at extracting sensitive information that is processed by the operations in a cryptographic primitive. Power traces are collected and subsequently processed using statistical methods. The ChipWhisperer Nano is a low-cost, open-source device that can be used to implement and study side-channel attacks. This paper describes how the DPA attack with the difference of means method can be used to extract the secret key from both an 8-bit and a 32-bit implementation of AES using the ChipWhisperer Nano. The results show that although it is possible to carry out the attack on both implementations, the attack on the 32-bit implementation requires more traces than the 8-bit implementation.

In 2019, Gu Chunsheng introduced Integer-RLWE, a variant of RLWE devoid of some of its efficiency flaws. Most notably, he proposes a setting where $n$ can be an arbitrary positive integer, contrarily to the typical construction $n = 2^k$. In this paper, we analyze the new problem and implement the classical meet-in-the-middle and lattice-based attacks. We then use the peculiarity of the construction of $n$ to build an improved lattice-based attack in cases where $n$ is composite with an odd divisor. For example, for parameters $n = 2000$ and $q = 2^{33}$, we reduce the estimated complexity of the attack from $2^{288}$ to $2^{164}$. We also present reproducible experiments confirming our theoretical results.

CSIDH is an isogeny-based post-quantum key establishment protocol proposed in 2018. In this work, we analyze attacking implementations of CSIDH which use dummy isogeny operations using fault injections from a mathematical perspective. We detail an attack by which the private key can be learned by the attacker up to sign with absolute certainty using $\sum \lceil \log_2(b_i) + 1 \rceil$ fault attacks on pairwise distinct group action evaluations under the same private key under ideal conditions using a binary search approach, where $\vec{b}$ is the bound vector defining the keyspace. As a countermeasure to this attack, we propose randomly mixing the real degree $\ell_j$ isogenies together with the dummy ones by means of a binary decision vector. To evaluate the efficacy of this countermeasure, we formulate a probability-based attack on this randomized scheme using a maximum likelihood approach and simulate the attack using 6 bound vectors used in previous CSIDH implementations. We found that the number of attacks required under our model to reach just 1% certainty about the key increased by a factor between 8--12 over the standard approach in the setting of signed private keys and a factor between 28--45 using non-negative private keys, depending on $\vec{b}$. We derive theoretical upper bounds on the number of attacks required to reach a specified certainty threshold about the key under our model. Based on our data and the minimal additional overhead required, we recommend all future implementations of CSIDH to employ a randomized decision vector approach. Finally since our model assumes fault attacks provide no information on the sign of the key, we use a technique based on Gray codes to optimize the standard meet-in-the-middle attack for learning the sign of the key values once their magnitudes have been learned through fault attacks. We estimate that, on average, this optimized technique uses approximately 88% fewer field-multiplication-equivalent operations over the standard approach.

The isogeny-based scheme CSIDH is a promising candidate for quantum-resistant static-static key exchanges with very small public keys, but is inherently difficult to implement in constant time. In the current literature, there are two directions for constant-time implementations: algorithms containing dummy computations and dummy-free algorithms. While the dummy-free implementations come with a 2x slowdown, they offer by design more resistance against fault attacks. In this work, we evaluate how practical fault injection attacks are on the constant-time implementations containing dummy calculations. We present three different fault attacker models. We evaluate our fault models both in simulations and in practical attacks. We then present novel countermeasures to protect the dummy isogeny computations against fault injections. The implemented countermeasures result in an overhead of 7% on the Cortex-M4 target, falling well short of the 2x slowdown for dummy-less variants.

WebAuthn, forming part of FIDO2, is a W3C standard for strong authentication, which employs digital signatures to authenticate web users whilst preserving their privacy. Owned by users, WebAuthn authenticators generate attested and unlinkable public-key credentials for each web service to authenticate users. Since the loss of authenticators prevents users from accessing web services, usable recovery solutions preserving the original WebAuthn design choices and security objectives are urgently needed. We examine Yubico's recent proposal for recovering from the loss of a WebAuthn authenticator by using a secondary backup authenticator. We analyse the cryptographic core of their proposal by modelling a new primitive, called Asynchronous Remote Key Generation (ARKG), which allows some primary authenticator to generate unlinkable public keys for which the backup authenticator may later recover corresponding private keys. Both processes occur asynchronously without the need for authenticators to export or share secrets, adhering to WebAuthn's attestation requirements. We prove that Yubico's proposal achieves our ARKG security properties under the discrete logarithm and PRF-ODH assumptions in the random oracle model. To prove that recovered private keys can be used securely by other cryptographic schemes, such as digital signatures or encryption schemes, we model compositional security of ARKG using composable games by Brzuska et al. (ACM CCS 2011), extended to the case of arbitrary public-key protocols. As well as being more general, our results show that private keys generated by ARKG may be used securely to produce unforgeable signatures for challenge-response protocols, as used in WebAuthn. We conclude our analysis by discussing concrete instantiations behind Yubico's ARKG protocol, its integration with the WebAuthn standard, performance, and usability aspects.

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Theorem: Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, $p$ is a $\lambda$-bit prime, and the parameters $\ell,k,n$ are large enough polynomials in $\lambda$: - the Learning With Errors ($\mathsf{LWE}$) assumption over $\mathbb{Z}_p$ with subexponential modulus-to-noise ratio $2^{k^\epsilon}$, where $k$ is the dimension of the $\mathsf{LWE}$ secret, - the Learning Parity with Noise ($\mathsf{LPN}$) assumption over $\mathbb{Z}_p$ with polynomially many $\mathsf{LPN}$ samples and error rate $1/\ell^\delta$, where $\ell$ is the dimension of the $\mathsf{LPN}$ secret, - the existence of a Boolean Pseudo-Random Generator ($\mathsf{PRG}$) in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$, where $n$ is the length of the $\mathsf{PRG}$ seed, - the Symmetric eXternal Diffie-Hellman ($\mathsf{SXDH}$) assumption on asymmetric bilinear groups of order $p$. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.

We present CrypTFlow2, a cryptographic framework for secure inference over realistic Deep Neural Networks (DNNs) using secure 2-party computation. CrypTFlow2 protocols are both correct -- i.e., their outputs are bitwise equivalent to the cleartext execution -- and efficient -- they outperform the state-of-the-art protocols in both latency and scale. At the core of CrypTFlow2, we have new 2PC protocols for secure comparison and division, designed carefully to balance round and communication complexity for secure inference tasks. Using CrypTFlow2, we present the first secure inference over ImageNet-scale DNNs like ResNet50 and DenseNet121. These DNNs are at least an order of magnitude larger than those considered in the prior work of 2-party DNN inference. Even on the benchmarks considered by prior work, CrypTFlow2 requires an order of magnitude less communication and 20x-30x less time than the state-of-the-art.

In distributed symmetric-key encryption (DiSE), a set of n distributed servers share a key (or key set) and any t, t <= n, servers can collectively use the shared key (or key set) in a DiSE transaction to encrypt a message or decrypt a ciphertext without reconstructing the shared key (or key set). Each participating server contributes one or more partial results and one participating server called the initiator combines all partial results into a final result. An adversary who has compromised up to (t-1) servers will not be able to access the shared key (or key set). Due to the distributed nature of DiSE, a DiSE server that has been compromised by an adversary may return wrong partial results to the initiator. Worse, multiple DiSE servers compromised by the same adversary may collude to send back wrong partial results. In this article we developed a robust DiSE that allows an honest initiator to detect wrong partial results by an adversary. The robustness of our DiSE is built through redundant computation. Our robust DiSE can detect wrong partial results by an adversary who has compromised up to min(t-1, n-t) servers. Next, the honest-initiator assumption is removed by rotating the initiator role among active servers across multiple DiSE transactions. A scalable, industry-level implementation for the robust DiSE has been developed and two cases, (t=3, n=5) and (t=16, n=24), have been tested to show the feasibility of robust DiSE. Our robust DiSE can be used to build intrusion-tolerant applications, such as intrusion-tolerant database encryption.

In relay attacks, a man-in-the-middle adversary impersonates a legitimate party and makes it this party appear to be of an authenticator, when in fact they are not. In order to counteract relay attacks, distance-bounding protocols provide a means for a verifier (e.g., an payment terminal) to estimate his relative distance to a prover (e.g., a bankcard). We propose FlexiDB, a new cryptographic model for distance bounding, parameterised by different types of fine-grained corruptions. FlexiDB allows to consider classical cases but also new, generalised corruption settings. In these settings, we exhibit new attack strategies on existing protocols. Finally, we propose a proof-of-concept mechanisation of FlexiDB in the interactive cryptographic prover EasyCrypt. We use this to exhibit a flavour of man-in-the-middle security on a variant of MasterCard's contactless-payment protocol.

Symmetric Searchable Encryption (SSE) is an encryption technique that allows users to search directly on their outsourced encrypted data while preserving the privacy of both the files and the queries. Unfortunately, majority of the SSE schemes allows users to either decrypt the whole ciphertext or nothing at all. In this paper, we propose a novel scheme based on traditional symmetric primitives, that allows data owners to bind parts of their ciphertexts with specific policies. Inspired by the concept of Attribute-Based Encryption (ABE) in the public setting, we design a scheme through which users can recover only certain parts of an encrypted document if and only if they retain a set of attributes that satisfy a policy. Our construction satisfies the important notion of forward privacy while at the same time supports the multi-client model by leveraging SGX functionality for the synchronization of users. To prove the correctness of our approach, we provide a detailed simulation-based security analysis coupled with an extensive experimental evaluation that shows the effectiveness of our scheme.

Blockchain systems have severe scalability limitations e.g., long confirmation delays. Layer-2 protocols are designed to address such limitations. The most prominent class of such protocols are payment channel networks e.g., the Lightning Network for Bitcoin where pairs of participants create channels that can be concatenated into networks. These allow payments across the network without interaction with the blockchain. A drawback is that all intermediary nodes within a payment path must be online. Virtual Channels, as recently proposed by Dziembowski et al. (CCS'18), allow payments without this limitation. However, these can only be implemented on blockchains with smart contract capability therefore limiting its applicability. Our work proposes the notion of --Lightweight-- Virtual Payment Channels, i.e. only requiring timelocks and multisignatures, enabling Virtual Channels on a larger range of blockchain systems of which a prime example is Bitcoin. More concretely, other contributions of this work are (1) to introduce a fully-fledged formalization of our construction, and (2) to present a simulation based proof of security in Canetti's UC Framework.

There once was a table of hashes That held extra items in stashes It all seemed like bliss But things went amiss When the stashes were stored in the caches The first Oblivious RAM protocols introduced the ``hierarchical solution,'' (STOC '90) where the servers store a series of hash tables of geometrically increasing capacities. Each ORAM query would read a small number of locations from each level of the hierarchy, and each level of the hierarchy would be reshuffled and rebuilt at geometrically increasing intervals to ensure that no single query was ever repeated twice at the same level. This yielded an ORAM protocol with polylogarithmic overhead. Future works extended and improved the hierarchical solution, replacing traditional hashing with cuckoo hashing (ICALP '11) and cuckoo hashing with a combined stash (Goodrich et al. SODA '12). In this work, we identify a subtle flaw in the protocol of Goodrich et al. (SODA '12) that uses cuckoo hashing with a stash in the hierarchical ORAM solution. We give a concrete distinguishing attack against this type of hierarchical ORAM that uses cuckoo hashing with a combined stash. This security flaw has propagated to at least 5 subsequent hierarchical ORAM protocols, including the recent optimal ORAM scheme, OptORAMa (Eurocrypt '20). In addition to our attack, we identify a simple fix that does not increase the asymptotic complexity. We note, however, that our attack only affects more recent hierarchical ORAMs, but does not affect the early protocols that predate the use of cuckoo hashing, or other types of ORAM solutions (e.g. Path ORAM or Circuit ORAM).

To prove computational complexity lower bounds in cryp- tography, one often resorts to so-called generic models of computation. For example, a generic algorithm for the discrete logarithm is one which works independently from the group representation—and thus works generically for all group representations. There are a multitude of different models in the literature making comparing different results—and even matching lower and upper bounds proven in different models— rather difficult. In this work we view a model as a set of games with the same type of interactions. Using a standard notion of reduction between two games, we establish a hierarchy between models. Different models may now be classified as weaker and stronger if a reduction between them exists. We propose different extensions of the generic group model with different queries, explicitly capturing different information that an algorithm may need to exploit. Finally, we use the hierarchy between these models to systematically compare and improve the results in the literature. First we strengthen the model in which the baby-step giant-step algorithm is proven and weaken the model in which the matching lower bound is proven. We then analyse the discrete logarithm with preprocessing. Upper and lower bounds have been proven in the literature in mismatching models. We weaken the model of the lower bound and strengthen the model of the upper bound to close the gap between the two.

One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors: (1) The prover’s (parallel) running time is T + polylog(T * p). (In other words, the prover’s running time is essentially T for large computation times!) (2) The prover uses at most p * polylog(T * p) processors, and (3) the communication and verifier complexity are both polylog(T * p). The combination of all three is desirable as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is T * polylog(T * p) when using p processors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct non-interactive argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to polylog(T * p) factors. We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.

A new approach to the security analysis of hardware-oriented masked ciphers against second-order side-channel attacks is developed. By relying on techniques from symmetric-key cryptanalysis, concrete security bounds are obtained in a variant of the probing model that allows the adversary to make only a bounded, but possibly very large, number of measurements. Specifically, it is formally shown how a bounded-query variant of robust probing security can be reduced to the linear cryptanalysis of masked ciphers. As a result, the compositional issues of higher-order threshold implementations can be overcome without relying on fresh randomness. From a practical point of view, the aforementioned approach makes it possible to transfer many of the desirable properties of first-order threshold implementations, such as their low randomness usage, to the second-order setting. For example, a straightforward application to the block cipher LED results in a masking using less than 700 random bits including the initial sharing. In addition, the cryptanalytic approach introduced in this paper provides additional insight into the design of masked ciphers and allows for a quantifiable trade-off between security and performance.

We propose single-trace side-channel attacks against lattice-based KEMs, the current candidates of the NIST's standardization project. More specifically, we analyze the message encoding in the encapsulation of lattice-based KEMs to obtain the ephemeral session keys, concluding that a single trace leakage allows a whole key recovery: our implementation on a ChipWhisperer UFO STM32F3 target board shows 100% success rates for Crystals-Kyber and Saber regardless of optimization level, and more than a 79% success rate for FrodoKEM. We further show that our attack methodologies are not restricted to the above algorithms but widely applicable to other NIST PQC candidates, including LAC, NewHope, NTRU Prime, and NTRU.

Hash functions serve as the fingerprint of a message. They also serve as an authentication mechanism in many applications. Nowadays, hash functions are widely used in blockchain technology and bitcoins. Today, most of the work concentrates on the design of lightweight hash functions which needs minimal hardware and software resources. This paper proposes a lightweight hash function which makes use of Cellular Automata (CA) and sponge functions. This hash function accepts arbitrary length message and produces fixed size hash digest. An additional property of this function is that the size of the hash digest may be adjusted based on the application because of the inherent property of varying length output of sponge function. The proposed hash function can be efficiently used in resource constraint environments in a secure and efficient manner. In addition, the function is resistant to all known generic attacks against hash functions and is also preimage resistant, second preimage resistant and collision resistant.

Post-QuantumCryptography(PQC)isregardedasaneffectivewaytoresistattackswithquantum computers. Since National Institute of Standards and Technology (NIST) proposed its PQC standardiza- tion project in 2016, many candidates have been submitted and their quantum-resistant capability has been measuring by researchers. Besides this research, this Migration issues of Post-Quantum Cryptography (PQC) has been attracting more and more at- tentions ever since the National Institute of Standards and Technology (NIST) published round 3 candidates of its PQC standardization project in July, 2020. Many candidates’ quantum-resistant capability had been measured by researchers. Meanwhile, it is also indispensable to point out limitations and give proposals to those candidates’ migration issues, especially for migrating PQC to constrained environments. In this paper, we assume the cases of using PQC on hardware security module (HSM), which is designed to provide a trusted environment to perform cryptographic operations. Our comparisons includes the cases of not only small data (e.g. less than Kilobytes data) which is often used for key encryption or authentication, but also large data (e.g. several Gigabytes data) which is often used for document signing or code signing. We focus on and evaluate hashing and asymmetric operations of three lattice-based cryptosystems which are strong candidates of NIST’s PQC standardization project. Then we construct two kinds of cryptographic bound- aries for those cryptosystems that make their hashing operations inside or outside of a HSM. We compare their performances with several data sizes under different cryptographic boundary constructions, and discuss how much efficiency versus security we gain or lose with internal or external hashing. This problem already exists today with RSA/ECC and our result indicates that it is also acute with the new lattice-based schemes from the NIST round 3 finalists.

SIS problem has numerous applications in cryptography. The known algorithms for solving that problem are exponential in complexity. A new algorithm is suggested in this note, its complexity is sub-exponential for a range of parameters.

In this work, we investigate a practical consideration for Electromagnetic (EM) side-channel analysis, namely, positioning EM probe at the best location for an efficient attack, requiring fewer traces to reveal the secret key of cryptographic engines. We present Multi-Layer Perceptron (MLP) based probe positioning and EM analysis method, defining it as a classification problem by dividing the chip surface scanned by the EM probe into virtual grids, and identifying each grid location by a class label. The MLP, trained to identify the location given a single EM trace, achieves $99.55\%$ accuracy on average for traces captured during different acquisition campaigns.

Password-Authenticated Key Exchange (PAKE) lets users with passwords exchange a cryptographic key. There have been two variants of PAKE which make it more applicable to real-world scenarios: - Asymmetric PAKE (aPAKE), which aims at protecting a client's password even if the authentication server is untrusted, and - Fuzzy PAKE (fPAKE), which enables key agreement even if passwords of users are noisy, but ``close enough''. Supporting fuzzy password matches eases the use of higher entropy passwords and enables using biometrics and environmental readings (both of which are naturally noisy). Until now, both variants of PAKE have been considered only in separation. In this paper, we consider both of them simultaneously. We introduce the notion of Fuzzy Asymmetric PAKE (fuzzy aPAKE), which protects against untrusted servers and supports noisy passwords. We formulate our new notion in the Universal Composability framework of Canetti (FOCS'01), which is the preferred model for password-based primitives. We then show that fuzzy aPAKE can be obtained from oblivious transfer and some variant of robust secret sharing (Cramer et al, EC'15). We achieve security against malicious parties while avoiding expensive tools such as non-interactive zero-knowledge proofs. Our construction is round-optimal, with message and password file sizes that are independent of the schemes error tolerance.

Inserting backdoors in encryption algorithms has long seemed like a very interesting, yet difficult problem. Most attempts have been unsuccessful for symmetric-key primitives so far and it remains an open problem how to build such ciphers. In this work, we propose the MALICIOUS framework, a new method to build tweakable block ciphers that have backdoors hidden which allows to retrieve the secret key. Our backdoor is differential in nature: a specific related-tweak differential path with high probability is hidden during the design phase of the cipher. We explain how any entity knowing the backdoor can practically recover the secret key of a user and we also argue why even knowing the presence of the backdoor and the workings of the cipher will not permit to retrieve the backdoor for an external user. We analyze the security of our construction in the classical black-box model and we show that retrieving the backdoor (the hidden high-probability differential path) is very difficult. We instantiate our framework by proposing the LowMC-M construction, a new family of tweakable block ciphers based on instances of the LowMC cipher, which allow such backdoor embedding. Generating LowMC-M instances is trivial and the LowMC-M family has basically the same efficiency as the LowMC instances it is based on.

We introduce a category of O-oriented supersingular elliptic curves and derive properties of the associated oriented and nonoriented $\ell$-isogeny supersingular isogeny graphs. As an application we introduce an oriented supersingular isogeny Diffie-Hellman protocol (OSIDH), analogous to the supersingular isogeny Diffie-Hellman (SIDH) protocol and generalizing the commutative supersingular isogeny Diffie-Hellman (CSIDH) protocol.

The intersection of Non-commutative and Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative ring K with the unit. We consider special subsemigroups (platforms) in a semigroup of all endomorphisms of K[x_1, x_2, …, x_n]. Efficiently computed homomorphisms between such platforms can be used in Post Quantum key exchange protocols when correspondents elaborate common transformation of (K*)^n. The security of these schemes is based on a complexity of decomposition problem for an element of a semigroup into a product of given generators. We suggest three such protocols (with a group and with two semigroups as platforms) for their usage with multivariate digital signatures systems. The usage of protocols allows to convert public maps of these systems into private mode, i.e. one correspondent uses the collision map for safe transfer of selected multivariate rule to his/her partner. The ‘’ privatisation’’ of former publicly given map allows the usage of digital signature system for which some of cryptanalytic instruments were found ( estimation of different attacks on rainbow oil and vinegar system, cryptanalytic studies LUOV) with the essentially smaller size of hashed messages. Transition of basic multivariate map to safe El Gamal type mode does not allow the usage of cryptanalytic algorithms for already broken Imai - Matsumoto cryptosystem or Original Oil and Vinegar signature schemes proposed by J.Patarin. So even broken digital signatures schemes can be used in the combination with protocol execution during some restricted ‘’trust interval’’ of polynomial size. Minimal trust interval can be chosen as a dimension n of the space of hashed messages, i. e. transported safely multivariate map has to be used at most n times. Before the end of this interval correspondents have to start the session of multivariate protocol with modified multivariate map. The security of such algorithms rests not on properties of quadratic multivariate maps but on the security of the protocol for the map delivery and corresponding NP hard problem.

We report the successful recovery of the key to a Zip archive containing only two encrypted files. The attack improves on our 2001 ciphertext-only attack, which required five encrypted files. The main innovations are a new differential meet-in-the-middle attack for the initial stages and the use of lattice reduction to recover the internal state of the truncated linear congruential generator.

Election verifiability aims to ensure that the outcome produced by electronic voting systems correctly reflects the intentions of eligible voters, even in the presence of an adversary that may corrupt various parts of the voting infrastructure. Protecting such systems from manipulation is challenging because of their distributed nature involving voters, election authorities, voting servers and voting platforms. An adversary corrupting any of these can make changes that, individually, would go unnoticed, yet in the end will affect the outcome of the election. It is, therefore, important to rigorously evaluate whether the measures prescribed by election verifiability achieve their goals. We propose a formal framework that allows such an evaluation in a systematic and automated way. We demonstrate its application to the verification of various scenarios in Helios and Belenios, two prominent internet voting systems, for which we capture features and corruption models previously outside the scope of formal verification. Relying on the Tamarin protocol prover for automation, we derive new security proofs and attacks on deployed versions of these protocols, illustrating trade-offs between usability and security.

The lightweight block cipher PRESENT has become viable for areas like IoT (Internet of Things) and RFID tags, due to its compact design and low power consumption, while providing a sufficient level of security for the aforementioned applications. However, the key scheduling algorithm of a cipher plays a major role in deciding how secure it is. In this paper we test the strength of the key scheduling algorithm (KSA) of the 80-bit key length variant of PRESENT by attempting to retrieve the main key register from the final round key register, using deep learning.

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors ($\mathsf{LWE}$) assumption. For a circuit $C:\{0,1\}^N\rightarrow\{0,1\}$ of size $S$ and depth $D$, the prover runs in time $\mathsf{poly}(S)$, the communication complexity is $D \cdot \mathsf{polylog} (S)$, and the verifier runs in time $(D+N) \cdot \mathsf{polylog} (S)$. To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the $\mathsf{GKR}$ protocol, assuming the sub-exponential hardness of $\mathsf{LWE}$. By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $\mathsf{PPAD}$, assuming the sub-exponential hardness of $\mathsf{LWE}$.

Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature $\sigma$ on a message $m$ under a public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent message $m'$ under an equivalent public key $\mathsf{pk}'$ for an appropriate notion of equivalence. For example, $\mathsf{pk}$ and $\mathsf{pk}'$ may be unlinkable pseudonyms of the same user, and $m$ and $m'$ may be unlinkable pseudonyms of a user to whom some capability is delegated. The only previously known construction of mercurial signatures suffers a severe limitation: in order to sign messages of length $n$, the signer's public key must also be of length $n$. In this paper, we eliminate this restriction and provide a signing protocol that admits messages of any length. This significantly improves the applicability of mercurial signatures to chains of anonymous credentials.

We propose a new cryptanalytic technique and key recovery attack for the Sparx cipher, Partly-Pseudo-Linear Cryptanalysis, a meet-in-the-middle attack combining linear and pseudo-linear approximations. We observe improvements over the linear hull attacks in the literature for Sparx 128/128 and 128/256. Additionally, we generate another attack for comparison purposes, using the Cho-Pieprzyk property for a fully-linear approximation and a corresponding key recovery attack. We observe improvements on the data complexity, bias, and number of recovered key bits, over all variants of Sparx, when compared to the use of only the Cho-Pieprzyk approximation.

The deep learning-based side-channel analysis represents a powerful and easy to deploy option for profiled side-channel attacks. A detailed tuning phase is often required to reach a good performance where one first needs to select relevant hyperparameters and then tune them. A common selection for the tuning phase are hyperparameters connected with the neural network architecture, while those influencing the training process are less explored. In this work, we concentrate on the optimizer hyperparameter, and we show that this hyperparameter has a significant role in the attack performance. Our results show that common choices of optimizers (Adam and RMSprop) indeed work well, but they easily overfit, which means that we must use short training phases, small profiled models, and explicit regularization. On the other hand, SGD type of optimizers works well on average (slower convergence and less overfit), but only if momentum is used. Finally, our results show that Adagrad represents a strong option to use in scenarios with longer training phases or larger profiled models.

Fitzi, Garay, Maurer, and Ostrovsky (Journal of Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we introduce a new $2$-party primitive $\mathcal{F}_{\mathsf{SyX}}$ (``synchronizable fair exchange'') and show that it is complete for realizing any $n$-party functionality with fairness in a setting where all $n$ parties are pairwise connected by independent instances of $\mathcal{F}_{\mathsf{SyX}}$. In the $\mathcal{F}_{\mathsf{SyX}}$-hybrid model, the two parties load $\mathcal{F}_{\mathsf{SyX}}$ with some input, and following this, either party can trigger $\mathcal{F}_{\mathsf{SyX}}$ with a suitable ``witness'' at a later time to receive the output from $\mathcal{F}_{\mathsf{SyX}}$. Crucially the other party also receives output from $\mathcal{F}_{\mathsf{SyX}}$ when $\mathcal{F}_{\mathsf{SyX}}$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $\mathcal{F}_{\mathsf{SyX}}$, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $\mathcal{F}_{\mathsf{SyX}}$ in any number of multiparty protocols (possibly involving different sets of parties).

We design Aardvark, a novel authenticated dictionary with short proofs of correctness for lookups and modifications. Our design reduces storage requirements for transaction validation in cryptocurrencies by outsourcing data from validators to untrusted servers, which supply proofs of correctness of this data as needed. In this setting, short proofs are particularly important because proofs are distributed to many validators, and the transmission of long proofs can easily dominate costs. A proof for a piece of data in an authenticated dictionary may change whenever any (even unrelated) data changes. This presents a problem for concurrent issuance of cryptocurrency transactions, as proofs become stale. To solve this problem, Aardvark employs a versioning mechanism to safely accept stale proofs for a limited time. On a dictionary with 100 million keys, operation proof sizes are about 1KB in a Merkle Tree versus 100–200B in Aardvark. Our evaluation shows that a 32-core validator processes 1492– 2941 operations per second, saving about 800× in storage costs relative to maintaining the entire state.

Modern public key encryption relies on various hardness assumptions for its security. Hardness assumptions may cause security uncertainty, for instance, when a hardness problem is no longer hard or the best solution to a hard problem might not be publicly released. In this paper, we propose a public key encryption scheme Compact-LWE-MQ^{H} to demonstrate the feasibility of constructing public key encryption without relying on hardness assumptions. Instead, its security is based on problems that are called factually hard. The two factually hard problems we propose in this work are stratified system of linear and quadratic equations, and layered learning with relatively big errors. The factually hard problems are characterized by their layered structures, which ensure that the secrets at a lower layer can only be recovered after the secrets in a upper layer have been found {\it correctly} (i.e., leading to consistent lower layer secrets, not necessarily the original upper layer ones). On the other hand, without knowing the secrets in the lower layer, the upper layer subproblem can only be solved by exhaustive search. Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or correct private key, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} with a number of lines of SageMath code. Simplicity of Compact-LWE-MQ^{H} makes it easy for understanding, cryptanalysis, and implementation. In our configuration for 128-bit security, the dimensional parameter is $n=4$ ($n$ has the same meaning as in LWE). For such a tiny parameter, the current analysis tools like LLL lattice reduction algorithm are already efficient enough to perform attacks if the security claim of Compact-LWE-MQ^{H} does not hold. That is, the security of Compact-LWE-MQ^{H} is not assumed with the capability of cryptanalysis tools. SageMath code of verifying Compact-LWE-MQ^{H} security is also included in Appendix.

Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that for direct 2PC evaluation of a Boolean circuit, it is necessary to transmit the entire GC, including garbled truth tables corresponding to subcomputations whose output is ultimately discarded by conditional logic. This folklore belief is false. We propose a novel GC technique, stacked garbling, that eliminates the communication cost of inactive conditional branches. We extend the ideas of conditional GC evaluation explored in (Kolesnikov, Asiacrypt 18) and (Heath and Kolesnikov, Eurocrypt 20). Unlike these works, ours is for general 2PC where no player knows which conditional branch is taken. Our garbling scheme, Stack, requires communication proportional to the longest execution path rather than to the entire circuit. Stack is compatible with state-of-the-art techniques, such as free XOR and half-gates. Stack is a garbling scheme. As such, it can be plugged into a variety of existing protocols, and the resulting round complexity is the same as that of standard GC. The approach does incur computation cost quadratic in the conditional branching factor vs linear in standard schemes, but the tradeoff is beneficial for most programs: GC computation even on weak hardware is faster than GC transmission on fast channels. We implemented Stack in C++. Stack reduces communication cost by approximately the branching factor: for 16 branches, communication is reduced by 10.5x. In terms of wall-clock time for circuits with branching factor 16 over a 50 Mbps WAN on a laptop, Stack outperforms state-of- the-art half-gates-based 2PC by more than 4x.

In this short note, we describe a practical optimization of the well-known extended binary GCD algorithm, for the purpose of computing modular inverses. The method is conceptually simple and is applicable to all odd moduli (including non-prime moduli). When implemented for inversion in the field of integers modulo the prime $2^{255}-19$, on a recent x86 CPU (Coffee Lake core), we compute the inverse in 6253 cycles, with a fully constant-time implementation.

Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true. We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bits albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing. We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function $f(x) = ax + b$, where a sender inputs the field elements $a,b$, and a receiver inputs $x$ and learns $f(x)$. OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more. In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al., Eurocrypt 2019), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al., Crypto 2018), and design new variants of zero-knowledge arguments that are necessary for some of our constructions. Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where $b$ is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring $\mathbb{Z}_m$, for a 120-bit modulus $m$, on standard hardware.

In this article we produce the simplified SWU encoding to some Barreto--Naehrig curves, including BN512, BN638 from the standards ISO/IEC 15946-5 and TCG Algorithm Registry respectively. Moreover, we show (for any $j$-invariant) how to implement the simplified SWU encoding in constant time of one exponentiation in the basic field, namely without quadratic residuosity tests and inversions. Thus in addition to the protection against timing attacks, the new encoding turns out to be much more efficient than the (universal) SWU encoding, which generally requires to perform two quadratic residuosity tests.

Presenting a new technology to fit quantum-randomness into a lump of matter where the randomness is held through the molecular bonds of seeded macro-molecules, and reliably measured in two or more sufficiently exact duplicates, serving as a large reservoir for quantum-grade randomness to support cryptographic protocols.

In 2017, Ward Beullenset al.submitted Lifted Unbalanced Oil andVinegar, which is a modification to the Unbalanced Oil and Vinegar Schemeby Patarin. Previously, Dinget al.proposed the Subfield Differential Attack which prompted a change of parameters by the authors of LUOV for the sec-ond round of the NIST post quantum standardization competition. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the pa-rameter sets put forward. We also show by experimentation that this attack ispractically possible to do in under 210 minutes for the level I security param-eters and not just a theoretical attack. The Nested Subset Differential attack isa large improvement of the Subfield differential attack which can be used inreal world circumstances. Moreover, we will only use what is called the "lifted"structure of LUOV, and our attack can be thought as a development of solving"lifted" quadratic systems.

We provide a novel electro-magnetic (EM) side-channel resistant symmetric-key authentication mechanism for small devices that uses a Benes network to permute the on-board authentication-key before computing a MAC of a challenge with the key. The permutation itself is derived from the challenge using a hash function acting as a random oracle. The solution has interesting applications such as forgery detection of currency bills.

This paper reports on the computation of a discrete logarithm in the finite field $\mathbb{F}_{2^{30750}}$, breaking by a large margin the previous record, which was set in January 2014 by a computation in $\mathbb{F}_{2^{9234}}$. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbrägel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about $2900$ core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately $3100$ core years expended for the discrete logarithm record for prime fields, set in a field of bit-length $795$, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Gröbner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the $L(\frac{1}{4} + o(1))$ complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.

The ability to query a database privately is nowadays ubiquitous via an encrypted channel. With the advent of homomorphic encryption, there is a want to expand the notion of privacy in this context to querying privately on the database with the database learning as little to no information of the query data or its result. The ability to compute the intersection from at least two parties’ sets that are kept private only to themselves is known as private set intersection (PSI) and should be considered a fundamental operation in several homomorphic computation scenarios to do useful work; not least for the ability to implement queries on a database. We outline in this paper a novel highly configurable PSI structure to be used in private querying providing the possibility that even the exact query itself can be protected from the database if required. As well as complex database lookups, there is also a more complex partial matching. The outline of the system design is discussed and we report preliminary results on some of the fundamental operations. We demonstrate that this technology is emerging as a viable given response to lookup queries and partially matching on an encrypted database with over a million entries in approximately 9 minutes.

Broadcast is a fundamental primitive in distributed computing. It allows a sender to consistently distribute a message among $n$ recipients. The seminal result of Pease et al. [JACM'80] shows that in a complete network of synchronous bilateral channels, broadcast is achievable if and only if the number of corruptions is bounded by $t < n/3$. To overcome this bound, a fascinating line of works, Fitzi and Maurer [STOC'00], Considine et al. [JC'05] and Raykov [ICALP'15], proposed strengthening the communication network by assuming partial synchronous broadcast channels, which guarantee consistency among a subset of recipients. We extend this line of research to the asynchronous setting. We consider reliable broadcast protocols assuming a communication network which provides each subset of $b$ parties with reliable broadcast channels. A natural question is to investigate the trade-off between the size $b$ and the corruption threshold $t$. We answer this question by showing feasibility and impossibility results: 1) A reliable broadcast protocol that: For $3 \le b \le 4$, is secure up to $t < n/2$ corruptions; For $b > 4$ even, is secure up to $t < \left(\frac{b-4}{b-2} n + \frac{8}{b-2}\right)$ corruptions; For $b > 4$ odd, is secure up to $t < \left(\frac{b-3}{b-1} n + \frac{6}{b-1}\right)$ corruptions. 2) A nonstop reliable broadcast, where parties are guaranteed to obtain output as in reliable broadcast but may need to run forever, secure up to $t < \frac{b-1}{b+1} n$ corruptions. 3) There is no protocol for (nonstop) reliable broadcast secure up to $t \ge \frac{b-1}{b+1} n$ corruptions, implying that the reliable broadcast protocol is asymptotically optimal, and the nonstop reliable broadcast protocol is optimal.

We present a computer-verified formalization of the post-quantum security proof of the Fujisaki-Okamoto transform (as analyzed by Hövelmanns, Kiltz, Schäge, and Unruh, PKC 2020). The formalization is done in quantum relational Hoare logic and checked in the qrhl-tool (Unruh, POPL 2019).

As cloud computing matures, Machine Learning as a Service(MLaaS) has received more attention. In many scenarios, sensitive information also has a demand for MLaaS, but it should not be exposed to others, which brings a dilemma. In order to solve this dilemma, many works have proposed some privacy-protected machine learning frameworks. Compared with plain-text tasks, cipher-text inference has higher computation and communication overhead. In addition to the difficulties caused by cipher-text calculations, the nonlinear activation functions in machine learning models are not friendly to Homomorphic Encryption(HE) and Secure Multi-Party Computation(MPC). The nonlinear activation function can effectively improve the performance of the network, and it seems that the high overhead brought by it is inevitable. In order to solve this problem, this paper re-explains the mechanism of the nonlinear activation function in forward propagation from another perspective, and based on this observation, proposed a dynamic parameters combination scheme as an alternative, called DPC. DPC allows the decoupling of nonlinear operations and linear operations in neural networks. This work further uses this feature to design the HE-based framework and MPC-based framework, so that non-linear operations can be completed locally by the user through pre-computation, which greatly improves the efficiency of privacy protection data prediction. The evaluation result shows that the linear neural networks with DPC can perform high accuracy. Without other optimizations, the HE-based proposed in this work shows 2x faster executions than CryptoNets only relying on the advantage of the DPC. The MPC-based framework proposed in this work can achieve similar efficiency to plain-text prediction, and has advantages over other work in terms of communication complexity and computational complexity.

The security of Internet of Things (IoT) devices relies on fundamental concepts such as cryptographically protected firmware updates. In this context attackers usually have physical access to a device and therefore side-channel attacks have to be considered. This makes the protection of required cryptographic keys and implementations challenging, especially for commercial off-the-shelf (COTS) microcontrollers that typically have no hardware countermeasures. In this work, we demonstrate how unprotected hardware AES engines of COTS microcontrollers can be efficiently protected against side-channel attacks by constructing a leakage resilient pseudo random function (LR-PRF). Using this side-channel protected building block, we implement a leakage resilient authenticated encryption with associated data (AEAD) scheme that enables secured firmware updates. We use concepts from leakage resilience to retrofit side-channel protection on unprotected hardware AES engines by means of software-only modifications. The LR-PRF construction leverages frequent key changes and low data complexity together with key dependent noise from parallel hardware to protect against side-channel attacks. Contrary to most other protection mechanisms such as time-based hiding, no additional true randomness is required. Our concept relies on parallel S-boxes in the AES hardware implementation, a feature that is fortunately present in many microcontrollers as a measure to increase performance. In a case study, we implement the protected AEAD scheme for two popular ARM Cortex-M microcontrollers with differing parallelism. We evaluate the protection capabilities in realistic IoT attack scenarios, where non-invasive EM probes or power consumption measurements are employed by the attacker. We show that the concept provides the side-channel hardening that is required for the long-term security of IoT devices.

In this paper we show several quantum chosen-plaintext attacks (qCPAs) on contracting Feistel structures. In the classical setting, a $d$-branch $r$-round contracting Feistel structure can be shown to be PRP-secure when $d$ is even and $r \geq 2d-1$, meaning it is secure against polynomial-time chosen-plaintext attacks. We propose a polynomial-time qCPA distinguisher on the $d$-branch $(2d-1)$-round contracting Feistel structure, which solves an open problem by Dong et al. In addition, we show a polynomial-time qCPA that recovers the keys of the $d$-branch $r$-round contracting Feistel structure when each round function $F^{(i)}_{k_i}$ has the form $F^{(i)}_{k_i}(x) = F_i(x \oplus k_i)$ for a public random function $F_i$. This is applicable to the Chinese block cipher standard {\texttt{SM4}}, which is a special case where $d=4$. Finally, in addition to quantum attacks under single-key setting, we also show related-key quantum attacks on balanced Feistel structures in the model that adversaries can only control part of the key difference in quantum superposition. Our related-key attacks on balanced Feistel structures can easily be extended to ones on contracting Feistel structures.

Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties $f$ is bounded by a single given threshold $t$. If $f > t$, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as $f \le t_v$, $f \le t_c$ and $f \le t_t$ respectively. For consensus, we consider both variants of $(1-\epsilon)$-consensus and \emph{almost-surely terminating} consensus, where termination is guaranteed with probability $(1-\epsilon)$ and $1$, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: -Multi-threshold reliable broadcast is possible if and only if $\max\{t_c,t_v\} + 2t_t < n$. -Multi-threshold almost-surely consensus is possible if $\max\{t_c, t_v\} + 2t_t < n$, $2t_v + t_t < n$ and $t_t < n/3$. Assuming a global coin, it is possible if and only if $\max\{t_c, t_v\} + 2t_t < n$ and $2t_v + t_t < n$. -Multi-threshold $(1-\epsilon)$-consensus is possible if and only if $\max\{t_c, t_v\} + 2t_t < n$ and $2t_v + t_t < n$.

Strong Physical Unclonable Functions (PUFs), as a promising security primitive, are supposed to be a lightweight alternative to classical cryptography for purposes such as device authentication. Most of the proposed candidates, however, have been plagued by machine-learning attacks breaking their security claims. The Interpose PUF (iPUF), which has been introduced at CHES 2019, was explicitly designed with state-of-the-art machine-learning attacks in mind and is supposed to be impossible to break by classical and reliability attacks. In this paper, we analyze its vulnerability to reliability attacks. Despite the increased difficulty, these attacks are still feasible, against the original authors’ claim. We explain how adding constraints to the machine-learning objective streamlines reliability attacks and allows us to model all individual components of an iPUF successfully. In order to build a practical attack, we give several novel contributions. First, we demonstrate that reliability attacks can be performed not only with CMA-ES but also with gradient-based optimization. Second, we show that the switch to gradient-based reliability attacks makes it possible to combine reliability attacks, weight constraints, and Logistic Regression (LR) into a single optimization objective. This framework makes machine-learning attacks more efficient, as it exploits knowledge of responses and reliability information at the same time. Third, we show that a differentiable model of the iPUF exists and how it can be utilized in a combined reliability attack. We confirm that iPUFs are harder to break than regular XOR Arbiter PUFs. However, we are still able to break (1,10)-iPUF instances, which were originally assumed to be secure, with less than 10^7 PUF response queries.

In this work various approaches for constant time conditional branching in Montgomery ladder have been studied. A previous method appearing in a code for implementing X25519 has been formalized algorithmically. This algorithm is based on a conditional select operation. We consider a variant of this algorithm which groups together operations in a more convenient manner. Further, we provide a new implementation of the conditional select operation using the cmov operation such that cmov works only on registers. This provides a better guarantee of constant time behavior.

The industrial Internet of Things (IIoT) integrates sensors, instruments, equipment, and industrial applications, enabling traditional industries to automate and intelligently process data. To reduce the cost and demand of required service equipment, IIoT relies on cloud computing to further process and store data. Public-key encryption with keyword search (PEKS) plays an important role, due to its search functionality, to ensure the privacy and confidentiality of the outsourced data and the maintenance of flexibility in the use of the data. Recently, Huang and Li proposed the ``public-key authenticated encryption with keyword search'' (PAEKS) to avoid the insider keyword guessing attacks (IKGA) in the previous PEKS schemes. However, all current PAEKS schemes are based on the discrete logarithm assumption and are therefore vulnerable to quantum attacks. In this study, we first introduce a generic PAEKS construction, with the assistance of a trusted authority, that enjoys the security against IKGA in the standard model, if all building blocks are secure under standard model. Based on the framework, we further propose a novel instantiation of quantum-resistant PAEKS that is based on NTRU assumption under random oracle. Compared with its state-of-the-art counterparts, the experiment result indicates that our instantiation is more efficient and secure.

The best existing pairing-based traitor tracing schemes have $O(\sqrt{N})$-sized parameters, which has stood since 2006. This intuitively seems to be consistent with the fact that pairings allow for degree-2 computations, yielding a quadratic compression. In this work, we show that this intuition is false by building a tracing scheme from pairings with $O(\sqrt[3]{N})$-sized parameters. We additionally give schemes with a variety of parameter size trade-offs, including a scheme with constant-size ciphertexts and public keys (but linear-sized secret keys). All of our schemes make black-box use of the pairings. We obtain our schemes by developing a number of new traitor tracing techniques, giving the first significant parameter improvements in pairings-based traitor tracing in over a decade.

While many similarities between Machine Learning and cryptanalysis tasks exists, so far no major result in cryptanalysis has been reached with the aid of Machine Learning techniques. One exception is the recent work of Gohr, presented at Crypto 2019, where for the first time, conventional cryptanalysis was combined with the use of neural networks to build a more efficient distinguisher and, consequently, a key recovery attack on Speck32/64. On the same line, in this work we propose two Deep Learning (DL) based distinguishers against the Tiny Encryption Algorithm (TEA) and its evolution RAIDEN. Both ciphers have twice block and key size compared to Speck32/64. We show how these two distinguishers outperform a conventional statistical distinguisher, with no prior information on the cipher, and a differential distinguisher based on the differential trails presented by Biryukov and Velichkov at FSE 2014. We also present some variations of the DL-based distinguishers, discuss some of their extra features, and propose some directions for future research.

In recent years, many papers have shown that deep learning can be beneficial for profiled side-channel analysis. However, in order to obtain good performances with deep learning, an attacker needs a lot of data for training. The training data should be as similar as possible to the data that will be obtained during the attack, a condition that may not be easily met in real-world scenarios. It is thus of interest to analyse different scenarios where the attack makes use of ``imperfect" training data. The typical situation in side-channel is that the attacker has access to an unlabelled dataset of measurements from the target device (obtained with the key he actually wants to recover) and, depending on the context, he may also take profit of a labelled dataset (say profiling data) obtained on the same device (with known or chosen key(s)). In this paper, we extend the attacker models and investigate the situation where an attacker additionally has access to a neural network that has been pre-trained on some other dataset not fully corresponding to the attack one. The attacker can then either directly use the pre-trained network to attack, or if profiling data is available, train a new network, or adapt a pre-trained one using transfer learning. We made many experiments to compare the attack metrics obtained in both cases on various setups (different probe positions, channels, devices, size of datasets). Our results show that in many cases, a lack of training data can be counterbalanced by additional "imperfect" data coming from another setup.

Security amplification is a fundamental problem in cryptography. In this work, we study security amplification for functional encryption (FE). We show two main results: 1) For any constant epsilon in (0,1), we can amplify any FE scheme for P/poly which is epsilon-secure against all polynomial sized adversaries to a fully secure FE scheme for P/poly, unconditionally. 2) For any constant epsilon in (0,1), we can amplify any FE scheme for P/poly which is epsilon-secure against subexponential sized adversaries to a fully subexponentially secure FE scheme for P/poly, unconditionally. Furthermore, both of our amplification results preserve compactness of the underlying FE scheme. Previously, amplification results for FE were only known assuming subexponentially secure LWE. Along the way, we introduce a new form of homomorphic secret sharing called set homomorphic secret sharing that may be of independent interest. Additionally, we introduce a new technique, which allows one to argue security amplification of nested primitives, and prove a general theorem that can be used to analyze the security amplification of parallel repetitions.

We introduce garbled encryption, a relaxation of secret-key multi-input functional encryption (MiFE) where a function key can be used to jointly compute upon only a particular subset of all possible tuples of ciphertexts. We construct garbled encryption for general functionalities based on one-way functions. We show that garbled encryption can be used to build a self-processing private sensor data system where after a one-time trusted setup phase, sensors deployed in the field can periodically broadcast encrypted readings of private data that can be computed upon by anyone holding function keys to learn processed output, without any interaction. Such a system can be used to periodically check, e.g., whether a cluster of servers are in an "alarm" state. We implement our garbled encryption scheme and find that it performs quite well, with function evaluations in the microseconds. The performance of our scheme was tested on a standard commodity laptop.

The ongoing COVID-19 pandemic has caused health organizations to consider using digital contact tracing to help monitor and contain the spread of COVID-19. Due to this urgent need, many different groups have developed secure and private contact tracing phone apps. However, these apps have not been widely deployed, in part because they do not meet the needs of healthcare officials. We present HABIT, a contact tracing system using a wearable hardware device designed specifically with the goals of public health officials in mind. Unlike current approaches, we use a dedicated hardware device instead of a phone app for proximity detection. Our use of a hardware device allows us to substantially improve the accuracy of proximity detection, achieve strong security and privacy guarantees that cannot be compromised by remote attackers, and have a more usable system, while only making our system minimally harder to deploy compared to a phone app in centralized organizations such as hospitals, universities, and companies. The efficacy of our system is currently being evaluated in a pilot study at Yale University in collaboration with the Yale School of Public Health.

A report on the selection process of the STARK friendly hash (SFH) function for standardization by the Ethereum Foundation. The outcome of this process, described here, is our recommendation to use the Rescue function over a prime field of size approximately $ 2^{61}$ in sponge mode with $12$ field elements per state. With an Appendix by Jean-Charles Faugere and Ludovic Perret of CryptoNext Security.

As secure processors such as Intel SGX (with hyperthreading) become widely adopted, there is a growing appetite for private analytics on big data. Most prior works on data-oblivious algorithms adopt the classical PRAM model to capture parallelism. However, it is widely understood that PRAM does not best capture realistic multicore processors, nor does it reflect parallel programming models adopted in practice. In this paper, we initiate the study of parallel data oblivious algorithms on realistic multicores, best captured by the binary fork-join model of computation. We first show that data-oblivious sorting can be accomplished by a binary fork-join algorithm with optimal total work and optimal (cache-oblivious) cache complexity, and in O(log n log log n) span (i.e., parallel time) that matches the best-known insecure algorithm. Using our sorting algorithm as a core primitive, we show how to data-obliviously simulate general PRAM algorithms in the binary fork-join model with non-trivial efficiency. We also present results for several applications including list ranking, Euler tour, tree contraction, connected components, and minimum spanning forest. For a subset of these applications, our data-oblivious algorithms asymptotically outperform the best known insecure algorithms. For other applications, we show data oblivious algorithms whose performance bounds match the best known insecure algorithms. Complementing these asymptotically efficient results, we present a practical variant of our sorting algorithm that is self-contained and potentially implementable. It has optimal caching cost, and it is only a log log n factor off from optimal work and about a log n factor off in terms of span; moreover, it achieves small constant factors in its bounds.

Montgomery’s and Barrett’s modular multiplication algorithms are widely used in modular exponentiation algorithms, e.g. to compute RSA or ECC operations. While Montgomery’s multiplication algorithm has been studied extensively in the literature and many side-channel attacks have been detected, to our best knowledge no thorough analysis exists for Barrett’s multiplication algorithm. This article closes this gap. For both Montgomery’s and Barrett’s multiplication algorithm, differences of the execution times are caused by conditional integer subtractions, so-called extra reductions. Barrett’s multiplication algorithm allows even two extra reductions, and this feature increases the mathematical difficulties significantly. We formulate and analyse a two-dimensional Markov process, from which we deduce relevant stochastic properties of Barrett’s multiplication algorithm within modular exponentiation algorithms. This allows to transfer the timing attacks and local timing attacks (where a second side-channel attack exhibits the execution times of the particular modular squarings and multiplications) on Montgomery’s multiplication algorithm to attacks on Barrett’s algorithm. However, there are also differences. Barrett’s multiplication algorithm requires additional attack substeps, and the attack efficiency is much more sensitive to variations of the parameters. We treat timing attacks on RSA with CRT, on RSA without CRT, and on Diffie-Hellman, as well as local timing attacks against these algorithms in the presence of basis blinding. Experiments confirm our theoretical results.

We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for l > log p dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension l with best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe-Okamoto, and conditional blind signatures such as ZGP17.

Conflict-free Replicated Data Types (CRDTs) are abstract data types that support developers when designing and reasoning about distributed systems with eventual consistency guarantees. In their core they solve the problem of how to deal with concurrent operations, in a way that is transparent for developers. However in the real world, distributed systems also suffer from other relevant problems, including security and privacy issues and especially when participants can be untrusted. In this paper we present the first formal cryptographic treatment of CRDTs, as well as proposals for secure implementations. We start by presenting a security notion that is compatible with standard definitions in cryptography. We then describe new privacy-preserving CRDT protocols that can be used to help secure distributed cloud-backed applications, including NoSQL geo-replicated databases. Our proposals are based on standard CRDTs, such as sets and counters, augmented with cryptographic mechanisms that allow operations to be performed on encrypted data. Our proposals are accompanied with formal security proofs and implement and integrate them in AntidoteDB, a geo-replicated NoSQL database that leverages CRDTs for its operations. Experimental evaluations based on the Danish Shared Medication Record dataset (FMK) exhibit the tradeoffs that our different proposals make and show that they are ready to be used in practical applications.

Sharding is a promising approach to scale permissionless blockchains. In a sharded blockchain, participants are split into groups, called shards, and each shard only executes part of the workloads. Despite its wide adoption in permissioned systems, transferring such success to permissionless blockchains is still an open problem. In permissionless networks, participants may join and leave the system at any time, making load balancing challenging. In addition, the adversary in such networks can launch the single-shard takeover attack by compromising a single shard’s consensus. To address these issues, participants should be securely and dynamically allocated into different shards. However, the protocol capturing such functionality – which we call shard allocation – is overlooked. In this paper, we study shard allocation protocols for permissionless blockchains. We formally define the shard allocation protocol and propose an evaluation framework. We apply the framework to evaluate the shard allocation subprotocols of seven state-of-the-art sharded blockchains, and show that none of them is fully correct or achieves satisfactory performance. We attribute these deficiencies to their extreme choices between two performance metrics: self-balance and operability. We observe and prove the fundamental trade-off between these two metrics, and identify a new property memory-dependency that enables parameterisation over this trade-off. Based on these insights, we propose Wormhole, a correct and efficient shard allocation protocol with minimal security assumptions and parameterisable self-balance and operability. We implement Wormhole and evaluate its overhead and performance metrics in a network with 128 shards and 32768 nodes. The results show that Wormhole introduces little overhead, achieves consistent self-balance and operability with our theoretical analysis, and allows the system to recover quickly from load imbalance.

Generating randomness collectively has been a long standing problem in distributed computing. It plays a critical role not only in the design of state-of-the-art BFT and blockchain protocols, but also for a range of applications far beyond this field. We present RandRunner, a random beacon protocol with a unique set of guarantees that targets a realistic system model. Our design avoids the necessity of a (Byzantine fault-tolerant) consensus protocol and its accompanying high complexity and communication overhead. We achieve this by introducing a novel extension to verifiable delay functions (VDFs) in the RSA setting that does not require a trusted dealer or distributed key generation (DKG) and only relies on well studied cryptographic assumptions. This design allows RandRunner to tolerate adversarial or failed leaders while guaranteeing safety and liveness of the protocol despite possible periods of asynchrony.

Grover’s search algorithm allows a quantum adversary to find a k-bit secret key of a block cipher by making O(2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the T-depth of its circuit implementation (time) and the number of qubits used by the circuit (space). Since the AES S-box is the only component which requires T-gates in the quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low T-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose four methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular,one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its T-depth.

Attribute-based encryption (ABE) is a promising type of cryptosystem achieving fine-grained access control on encrypted data. Revocable attribute-based encryption (RABE) is an extension of ABE that provides revocation mechanisms when user's attributes change, key exposure, and so on. In this paper, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from lattices, which support flexible threshold access policies on multi-valued attributes, achieving user-level and attribute-level user revocation, respectively. Specifically, the revocation list is defined and embedded into the ciphertext by the message sender to revoke a user in the user-level revocable scheme or revoke some attributes of a certain user in the attribute-level revocable scheme. We also discuss how to outsource decryption and reduce the workload for the end user. Our schemes are proved to be secure in the standard model, assuming the hardness of the learning with errors (LWE) problem.

Recently, research on deep learning based side-channel analysis (DLSCA) has received a lot of attention. Deep learning-based profiling methods similar to template attacks as well as non-profiling-based methods similar to differential power analysis have been proposed. DLSCA methods have been proposed for targets to which masking schemes or jitter-based hiding schemes are applied. However, most of them are methods for finding the secret key, except for methods for preprocessing, and there are no studies on the target to which the dummy-based hiding schemes or shuffling schemes are applied. In this paper, we propose a DLSCA for detecting dummy operations. In the previous study, dummy operations were detected using the method called BCDC, but there is a disadvantage in that it is impossible to detect dummy operations for commercial devices such as an IC card. We consider the detection of dummy operations as a multi-label classification problem and propose a deep learning method based on CNN to solve it. As a result, it is possible to successfully perform detection of dummy operations on an IC card, which was not possible in the previous study.

Revelio (CVCBT 2019) is a proof of reserves protocol for MimbleWimble-based cryptocurrencies which provides privacy to a cryptocurrency exchange by hiding the exchange-owned outputs in a larger anonymity set of unspent outputs. A drawback of Revelio is that the proof size scales linearly in the size of the anonymity set. To alleviate this, we design RevelioBP, a Bulletproofs-based proof of reserves protocol with proof sizes which scale logarithmically in the size of the anonymity set. This improvement allows us to use the set of all UTXOs as the anonymity set, resulting in better privacy for the exchange. On the downside, the higher proof generation and verification time of RevelioBP than that of Revelio might affect practical deployment of RevelioBP. Through implementation of RevelioBP, we quantitatively analyse trade-offs in design of MimbleWimble proofs of reserves in terms of scalability and performance. We conclude that unless proof size is a concern for exchanges, Revelio is a marginally better choice for proof of reserves. On the other hand, if an exchange is willing to pay in terms of proof generation time, RevelioBP offers proof sizes significantly smaller than Revelio.

Electromagnetic Fault Injection (EMFI) is a well-known technique for performing fault injection attacks. While such attacks may be easy demonstrated in a laboratory condition, information about the applicability of them to real-life environments is critical for designer of ECUs to understand the effort that should be spent on protecting against them. This work targets a recent (2019) automotive ECU, and analyzes the target microcontroller used in laboratory conditions, and then transitions the attack to a real-world “in-situ” attack similar to a garage bench. The specific work appears relevant to several devices in the MPC55xx and MPC56xx series, which are automotive-focused PowerPC devices.

Recently, He et al. proposed an anonymous authentication for wireless body area networks and prove that their scheme is secure in the random oracle model. In this paper, we cryptanalysis the He et al.’s scheme and design an attack model against their scheme, in which adversary replaces a user’s public key with a value of his choice and prove a key replacement attack besides client anonymity. Thus, their scheme is insecure and not suitable for implementing a secure WBAN system. Further, we point out a solution to improve their scheme.

The outbreak of coronavirus disease 2019 (covid-19) is imposing a severe worldwide lock-down. Contact tracing based on smartphones' applications (apps) has emerged as a possible solution to trace contagions and enforce a more sustainable selective quarantine. However, a massive adoption of these apps is required to reach the critical mass needed for effective contact tracing. As an alternative, geo-location technologies in next generation networks (e.g., 5G) can enable Mobile Operators (MOs) to perform passive tracing of users' mobility and contacts with a promised accuracy of down to one meter. To effectively detect contagions, the identities of positive individuals, which are known only by a Governmental Authority (GA), are also required. Note that, besides being extremely sensitive, these data might also be critical from a business perspective. Hence, MOs and the GA need to exchange and process users' geo-locations and infection status data in a privacy-preserving manner. In this work, we propose a privacy-preserving protocol that enables multiple MOs and the GA to share and process users' data to make only the final users discover the number of their contacts with positive individuals. The protocol is based on existing privacy-enhancing strategies that guarantee that users' mobility and infection status are only known to their MOs and to the GA, respectively. From extensive simulations, we observe that the cost to guarantee total privacy (evaluated in terms of data overhead introduced by the protocol) is acceptable, and can also be significantly reduced if we accept a negligible compromise in users' privacy.

We present CanDID, a platform for practical, user-friendly realization of decentralized identity, the idea of empowering end users with management of their own credentials. While decentralized identity promises to give users greater control over their private data, it burdens users with management of private keys, creating a significant risk of key loss. Existing and proposed approaches also presume the spontaneous availability of a credential-issuance ecosystem, creating a bootstrapping problem. They also omit essential functionality, like resistance to Sybil attacks and the ability to detect misbehaving or sanctioned users while preserving user privacy. CanDID addresses these challenges by issuing credentials in a user-friendly way that draws securely and privately on data from existing, unmodified web service providers. Such legacy compatibility similarly enables CanDID users to leverage their existing online accounts for recovery of lost keys. Using a decentralized committee of nodes, CanDID provides strong confidentiality for user's keys, real-world identities, and data, yet prevents users from spawning multiple identities and allows identification (and blacklisting) of sanctioned users. We present the CanDID architecture and its technical innovations and report on experiments demonstrating its practical performance.

We show two new results about instantiability of the classical random-oracle-model encryption transforms for upgrading ``weak'' trapdoor permutations and encryption to ``strong'' chosen-ciphertext (CCA) secure encryption, namely the OAEP trapdoor permutation based (Bellare and Rogaway, EUROCRYPT 1994) and Fujasaki Okamoto (FO) hybrid-encryption (EUROCRYPT 1998) transforms: - First, we propose a slight tweak to FO so that achieves the same goal in the RO model, but it is not ``admissible'' in the sense of Brzuska et al. (TCC 2015) and thus their uninstantiability result does not apply. We then show this modified transform is fully instantiable using extractable hash functions. - Second, we show that OAEP is partially instantiable using extractability assumptions on the round function when trapdoor permutation is partially one-way. This improves the prior work by Cao et al. (PKC 2020) who showed weaker results. This shed light on ``why'' RSA-OAEP may be secure whereas there exists one-way trapdoor permutations for which the OAEP transform fails (Shoup, J. Cryptology 2002).

ABSTRACT In 2017, D. Ezhilmaran & V. Muthukumaran (E&M [1]) have proposed key agreement protocols based on twisted conjugacy search problem in Near – ring and they have claimed that one can extend 3 party key agreement protocol (3PKAP) to any number of parties. Unfortunately their protocol is not an extension of 3PKAP and we present this weakness in this paper. We also show that their proposed 3PKAP is practically infeasible. Their protocol is not extendable to large number of parties like in banking system where number of parties is high. To overcome this problem we present an improved (or corrected) version of 3PKAP and for better understanding we extend it into 4PKAP with improvements in terms of number of passes, rounds, time complexity and run time. KEYWORDS Data communication, Key agreement, Near – ring, Twisted Conjugacy Search Problem (TCSP)

String search finds occurrences of patterns in a larger text. This general problem occurs in various application scenarios, f.e. Internet search, text processing, DNA analysis, etc. Using somewhat homomorphic encryption with SIMD packing, we provide an efficient string search protocol that allows to perform a private search in outsourced data with minimal preprocessing. At the base of the string search protocol lies a randomized homomorphic equality circuit whose depth is independent of the pattern length. This circuit not only improves the performance but also increases the practicality of our protocol as it requires the same set of encryption parameters for a wide range of patterns of different lengths. This constant depth algorithm is about 10 times faster than the prior work. It takes about 5 minutes on an average laptop to find the positions of a string with at most 50 UTF-32 characters in a text with 1000 characters. In addition, we provide a method that compresses the search results, thus reducing the communication cost of the protocol. For example, the communication complexity for searching a string with 50 characters in a text of length 10000 is about 347 KB and 13.9 MB for a text with 1000000 characters.

Secure, efficient execution of AES is an essential requirement on most computing platforms. Dedicated Instruction Set Extensions (ISEs) are often included for this purpose. RISC-V is a (relatively) new ISA that lacks such a standardised ISE. We survey the state-of-the-art industrial and academic ISEs for AES, implement and evaluate five different ISEs, one of which is novel. We recommend separate ISEs for 32 and 64-bit base architectures, with measured performance improvements for an AES-128 block encryption of 4× and 10× with a hardware cost of 1.1K and 8.2K gates respectivley, when compared to a software-only implementation based on use of T-tables. We also explore how the proposed standard bit-manipulation extension to RISC-V can be harnessed for efficient implementation of AES-GCM. Our work supports the ongoing RISC-V cryptography extension standardisation process.

Unification techniques have been proven to be useful for formal analysis of cryptographic systems. In this paper, we introduce a new unification problem called local XOR unification, motivated by formal analysis of security of modes of operation. The goal in local XOR unification is to find a substitution making two terms equivalent modulo the theory of exclusive-or, but each variable is only allowed to be mapped to a term from a given set of terms. We present two versions of the local XOR unification problem, and give algorithms to solve them, proving soundness, completeness and termination.

We present the first non-interactive zero-knowledge argument system for QMA with multi-theorem security. Our protocol setup constitutes an additional improvement and is constructed in the malicious designated-verifier (MDV-NIZK) model (Quach, Rothblum, and Wichs, EUROCRYPT 2019), where the setup consists of a trusted part that includes only a common uniformly random string and an untrusted part of classical public and secret verification keys, which even if sampled maliciously by the verifier, the zero knowledge property still holds. The security of our protocol is established under the Learning with Errors Assumption. Our main technical contribution is showing a general transformation that compiles any sigma protocol into a reusable MDV-NIZK protocol, using NIZK for NP. Our technique is classical but works for quantum protocols and allows the construction of a reusable MDV-NIZK for QMA.

Superlight clients enable the verification of proof-of-work-based blockchains by checking only a small representative number of block headers instead of all the block headers as done in simplified payment verification (SPV). Such clients can be embedded within other blockchains by implementing them as smart contracts, allowing for cross-chain verification. One such interesting instance is the consumption of Bitcoin data within Ethereum by implementing a Bitcoin superlight client in Solidity. While such constructions have demonstrated security and efficiency in theory, no practical implementation exists. In this work, we put forth the first practical Solidity implementation of a superlight client which implements the NIPoPoW superblocks protocol. Contrary to previous work, our Solidity smart contract achieves sufficient gas-efficiency to allow a proof and counter-proof to fit within the gas limit of a block, making it practical. We provide extensive experimental measurements for gas consumption. The optimizations that enable gas-efficiency heavily leverage a novel technique which we term hash-and-resubmit, which almost completely eliminates persistent storage requirements, the most expensive operation of smart contracts in terms of gas. Instead, the contract asks contesters to resubmit data and checks their veracity by hashing it. Other optimizations include off-chain manipulation of proofs in order to remove expensive look-up structures, and the usage of an optimistic schema. We show that such techniques can be used to bring down gas costs significantly and may be of independent interest. Lastly, our implementation allows us to calculate concrete cryptoeconomic parameters for the superblocks NIPoPoWs protocol and in particular to make recommendations about the monetary value of the collateral parameters. We provide such parameter recommendations over a variety of liveness settings.

Traditional threshold cryptosystems have decentralized core cryptographic primitives like key generation, decryption and signatures. Most threshold cryptosystems, however, rely on special purpose protocols that cannot easily be integrated into more complex multiparty protocols. In this work, we design and implement decentralized versions of lattice-based and elliptic-curve-based public-key cryptoystems using generic secure multiparty computation (MPC) protocols. These are standard cryptosystems, so we introduce no additional work for encrypting devices and no new assumptions beyond those of the generic MPC framework. Both cryptosystems are also additively homomorphic, which allows for secure additions directly on ciphertexts. By using generic MPC techniques, our multiparty decryption protocols compute secret-shares of the plaintext, whereas most special-purpose cryptosystems either do not support decryption or must reveal the decryptions in the clear. Our method allows complex functions to be securely evaluated after decryption, revealing only the results of the functions and not the plaintexts themselves. To improve performance, we present a novel oblivious elliptic curve multiplication protocol and a new noise-masking technique which may be of independent interest. We implemented our protocols using the SCALE-MAMBA secure multiparty computation platform, which provides security against malicious adversaries and supports arbitrary numbers of participants.

Efficient zero-knowledge (ZK) proofs for arbitrary boolean or arithmetic circuits have recently attracted much attention. Existing solutions suffer from either significant prover overhead (i.e., high memory usage) or relatively high communication complexity (at least &#954; bits per gate, for computational security parameter $\kappa$). In this paper, we propose a new protocol for constant-round interactive ZK proofs that simultaneously allows for an efficient prover with asymptotically optimal memory usage and significantly lower communication compared to protocols with similar memory efficiency. Specifically: • The prover in our ZK protocol has linear running time and, perhaps more importantly, memory usage linear in the memory needed to evaluate the circuit non-cryptographically. This allows our proof system to scale easily to very large circuits. • For statistical security parameter \rho = 40, our ZK protocol communicates roughly 9 bits/gate for boolean circuits and 2–4 field elements/gate for arithmetic circuits over large fields. Using 5 threads, 400 MB of memory, and a 200 Mbps network to evaluate a circuit with hundreds of billions of gates, our implementation (\rho = 40, \kappa = 128) runs at a rate of 0.45 \mu s/gate in the boolean case, and 1.6 \mu s/gate for an arithmetic circuit over a 61-bit field. We also present an improved subfield Vector Oblivious Linear Evaluation (sVOLE) protocol with malicious security that is of independent interest.

Correlated oblivious transfer (COT) is a crucial building block for secure multi-party computation (MPC) and can be generated efficiently via OT extension. Recent works based on the pseudorandom correlation generator (PCG) paradigm presented a new way to generate random COT correlations using only communication sublinear to the output length. However, due to their high computational complexity, these protocols are only faster than the classical IKNP-style OT extension under restricted network bandwidth. In this paper, we propose new COT protocols in the PCG paradigm that achieve unprecedented performance. With 50 Mbps network bandwidth, our maliciously secure protocol can produce one COT correlation in 22 nanoseconds. More specifically, our results are summarized as follows: - We propose a semi-honest COT protocol with sublinear communication and linear computation. This protocol assumes primal-LPN and is built upon a recent VOLE protocol with semi-honest security by Schoppmann et al. (CCS 2019). We are able to apply various optimizations to reduce its communication cost by roughly 15x, not counting a one-time setup cost that diminishes as we generate more COTs. - We strengthen our COT protocol to malicious security with no loss of efficiency. Among all optimizations, our new protocol features a new checking technique that ensures correctness and consistency essentially for free. In particular, our maliciously secure protocol is only 1-3 nanoseconds slower for each COT. - We implemented our protocols, and the code will be publicly available at EMP-toolkit. We observe at least 9x improvement in running time compared to the state-of-the-art protocol by Boyle et al. (CCS 2019) in both semi-honest and malicious settings under any network faster than 50 Mbps. With this new record of efficiency for generating COT correlations, we anticipate new protocol designs and optimizations will flourish on top of our protocol.

In 2012, Lyubashevsky introduced a framework for obtaining efficient digital signatures relying on lattice assumptions. Several works attempted to make this approach compliant with the coding theory setting, unsuccessfully. Recently, Song et al. proposed another adaptation of this framework, using denser and permuted secret keys, claiming immunity against existing attacks. This paper describes an efficient attack against Song et al. signature scheme. We show that it is possible to fully recover the secret key from a very limited number of signatures. As an example, it requires 32 signatures and 2 hours to recover the secret key of the parameter set targeting 80 bits of security. The attack affects both proposed parameter sets, and discourages patching such an approach.

In recent years, the conventional power grid system has been streamlined towards Smart grid infrastructure that empowers two-way communication between the consumers and the utility providers. This however also makes the grid more susceptible towards faults as well as physical and cyber attacks. In this work, we propose a Physically Unclonable Function (PUF) and Blockchain based detection and prevention mechanism to secure the Smart grid system against such faults and adversarial threats. In this context, we discuss a recently proposed Manipulation of demand via IoT (MadIoT) attacks, False Data Injection Attacks (FDIA) via Smart meters and Electric Fault Attacks (EFA) on Smart grid which can lead to localized blackout, falsified load forecasting, imbalance in demand-response, generator tripping, frequency instability and loss of equipment. To detect these threats and to trace back to the source of such attacks, we inspect the potential of the promising blockchain technology which gives a mechanism to authenticate and ensure the integrity of real power consumption information. However, the blockchain needs to be augmented with a root-of-trust, to bind the Smart meter with a unique hardware fingerprint. This can be achieved through Physically Unclonable Functions (PUFs) which is considered to be an unconventional cryptographic primitive and used for keyless authentication. The proposed PUF based authentication scheme would further prevent the system from injection of any false data by an illegitimate Smart meter that aids to false power estimation. The novelty of the proposed work is to blend these two technologies in developing a robust and secure framework which detects and prevents all of the above mentioned security vulnerabilities and can be easily integrated with the Smart grid infrastructure. Finally an end-to-end demonstration of the attack has been presented using MATLAB and Power World simulator and the proposed framework has been prototyped using commercial off-the-shelf products such as Raspberry Pi and Artix 7 FPGA along with an in-house blockchain simulator.

Dynamic group signatures (DGS) enable a user to generate a signature on behalf of a group of users, allowing a prospective user to join via an appropriate join protocol. A natural security requirement in the dynamic setting is to permit an adversary to concurrently perform join protocol executions. To date, most of DGS schemes do not provide the efficient concurrent join protocols in their security analysis, because of the need to use knowledge extractors. Also, DGS schemes have to provide efficient batch verifications for practical applications such as Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication, where a large number of group signatures should be verified in a very short time. In this paper, we propose a new practical DGS scheme that supports not only efficient concurrent joins but also batch verifications. The concurrent security is proven by showing that our join protocols are simulated without any knowledge extractor in security analysis. To do this, we introduce a modified Pointcheval-Sanders (PS) problem that can guarantee efficiently checking equality of discrete logarithms. In terms of efficiency, when considering a type-3 pairing, our DGS scheme has the advantages that the signature generation and verification are faster and especially our batch verification is at least 7 times faster in case of verifying 100 signatures, compared to other comparable pairing-based DGS schemes in the literature.