International Association
for Cryptologic Research

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 (amortized) 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 \emph{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 \emph{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 dif- ferent 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 (R)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 fast bootstrapping methods 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 runs in less than one second in a common personal computer. We also perform multi-value bootstrapping on non-binary message spaces achieving running times close to one second with modest memory requirements.

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 these researches, it is also indispensable to evaluate the practicality of PQC on constrained environments such as Hardware security module (HSM), which is designed to provide a trusted environment to perform cryptographic operations. In this paper, we assume the cases of using HSM for key management, and discuss the practicality of applying lattice-based cryptographies, which is one of the candidates of NIST’s PQC project on it. We focus on the efficiency of hash operations instead of asymmetric operations, with different constructions of cryptographic boundaries. Then we point out that the bottleneck of PQC operations can be hash operation instead of asymmetric operation. Especially for the cases of document signing and code signing, large files would be signed, and this bottleneck will affect their efficiency. We chose three lattice-based digital signature schemes from round 2 of NIST’s PQC project. We also analyses the bottleneck of these schemes and compare their performances under different constructions of cryptographic boundary when applied to HSM. After that, we propose the appropriate way to construct cryptographic boundaries for lattice-based cryptographic schemes when applied to HSM. We believe that our result helps to define cryptographic boundary for PQC, where theoretical proof and clearance of patents should be done.

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 Helios, our analysis is the first one to be, at the same time, fully automated (with the Tamarin protocol prover) and to precisely capture its end-to-end verifiability guarantees, allowing us to derive new security proofs and new attacks on deployed versions of it. For Belenios, similarly, we capture precisely the end-to-end verifiability guarantees when all election authorities are corrupted, which is outside the scope of previous formal definitions. We also find new attacks that apply in weaker corruption scenarios that are expected to be secure. In general, our framework allows a unified analysis and comparison of cryptographic voting protocols, corruption scenarios and verifiability procedures towards ensuring the end goal of election integrity.

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}$.