International Association
for Cryptologic Research

Secure cloud storage is considered as one of the most important problems that both businesses and end-users take into account before moving their private data to the cloud. Lately, we have seen some interesting approaches that are based either on the promising concept of Symmetric Searchable Encryption (SSE) or on the well-studied field of Attribute-Based Encryption (ABE). Our construction, MicroSCOPE, combines both ABE and SSE to utilize the advantages that each technique has to offer. We use an SSE scheme to ensure that data stored on the cloud will be protected against both internal and external attacks. Moreover, through the use of a Ciphertext-Policy ABE (CP-ABE) scheme, our construction allows efficient data sharing between multiple data owners and users. Finally, we enhance our construction with an access control mechanism by utilizing the functionality provided by SGX.

In 2016 and 2017, Shi et al first proposed two protocols for the communication parties to establish a quantum session key. Both work by rotating the angle of one communicator’s private key on the other party's quantum public key. In their approaches, the session key shared by each pair of communicators is fixed after the key generation phase. Thereafter, the key used in each communication does not change, but for security consideration, the session key should be changed in every time usage. In other words, those key agreement protocols do not satisfy the requirement of key security. In view of this, this paper develops a quantum session key establishment based on the Diffie-Hermann style key exchange to produce different quantum session keys in each communications. After analysis, we confirm that our method can resist various attacks and is therefore secure.

We show a reduction of integer (semiprimes) factorization problem to a $NP$-complete problem related to coding. Our results rigorously imply the existence of a quantum computer could possibly devastate existing security system relies on NP-hard problem.

In recent years, there has been exciting progress on building two-source extractors for sources with low min-entropy. Unfortunately, all known explicit constructions of two-source extractors in the low entropy regime suffer from non-negligible error, and building such extractors with negligible error remains an open problem. We investigate this problem in the computational setting, and obtain the following results.

We construct an explicit 2-source extractor, and even an explicit non-malleable extractor, with negligible error, for sources with low min-entropy, under computational assumptions in the Common Random String (CRS) model. More specifically, we assume that a CRS is generated once and for all, and allow the min-entropy sources to depend on the CRS. We obtain our constructions by using the following transformations.

1. Building on the technique of [BHK11], we show a general transformation for converting any computational 2-source extractor (in the CRS model) into a computational non-malleable extractor (in the CRS model), for sources with similar min-entropy. We emphasize that the resulting computational non-malleable extractor is resilient to arbitrarily many tampering attacks (a property that is impossible to achieve information theoretically). This may be of independent interest. This transformation uses cryptography, and relies on the sub-exponential hardness of the Decisional Diffie Hellman (DDH) assumption.

2. Next, using the blueprint of [BACDLT17], we give a general transformation converting any computational non-malleable seeded extractor (in the CRS model) into a computational 2-source extractor for sources with low min-entropy (in the CRS model). This transformation does not incur any additional assumptions. Our analysis makes a novel use of the leakage lemma of Gentry and Wichs [GW11].

The NIST-approved lightweight cryptography competition is an ongoing project to look for some algorithms as lightweight cryp- tographic standards. Recently, NIST chooses 32 algorithms from the 57 submissions as Round 2 candidates. Gimli and Ascon are both the Round 2 candidates. In this paper, we analyze the security of their hash mode against collision attacks. Con- cretely, we mount collision attacks on three hash functions: Gimli-Hash, Ascon-Xof and Ascon-Hash. These three hash functions are all based on sponge constructions. We give two attack strategies for searching collisions in sponge-based hash functions. Following one strategy, we give two non-practical collision attacks: a 6-round collision attack on Gimli-Hash with time complexity 2113and a 2-round collision attack on Ascon-Hash with time complexity 2125. Following the other strategy, we give a practical attack on 2-round Ascon-Xof with a 64-bit output. The time complexity is 215. We search for the differential characteristics using the MILP technique and the target differential algorithm.

The dual attack is one of the most efficient attack algorithms for the Learning with Errors (LWE) problem. Recently, an efficient variant of the dual attack for sparse and small secret LWE was reported by Albrecht [Eurocrypt 2017], which forces some LWE-based cryptosystems, especially fully homomorphic encryptions (FHE), to change parameters. In this work, we propose a new hybrid of dual and meet-in-the-middle (MITM) attack, which outperforms the improved variant on the same LWE parameter regime. To this end, we adapt the MITM attack for NTRU due to Odlyzko to LWE, and give a rigorous analysis for it. The performance of our MITM attack depends on the relative size of error and modulus, and hence for a large modulus LWE samples, our MITM attack works well for quite large error. We then combine our MITM attack with Albrecht's observation that understands the dual attack as dimension-error tradeoff, which finally yields our hybrid attack. We also implement a sage module that estimates the attack complexity of our algorithm upon {\sf LWE-estimator}, and our attack shows significant performance improvement for the LWE parameter for FHE. For example, for the LWE problem with dimension $n=2^{15}$, modulus $q=2^{628}$ and ternary secret key with Hamming weight 64 which is one parameter set used for {\sf HEAAN} bootstrapping [Eurocrypt 2018], our attack takes $2^{112.5}$ operations and $2^{70.6}$ bit memory while the previous best attack requires $2^{127.2}$ operations as reported by {\sf LWE-estimator}.

Machine Learning (ML) is today commonly employed in the Financial Services Sector (FSS) to create various models to predict a variety of conditions ranging from financial transactions fraud to outcomes of investments and also targeted upselling and cross-selling marketing campaigns. The common ML technique used for the modeling is supervised learning using regression algorithms and usually involves large amounts of data that needs to be shared and prepared before the actual learning phase. Compliance with recent privacy laws and confidentiality regulations requires that most, if not all, of the data and the computation must be kept in a secure environment, usually in-house, and not outsourced to cloud or multi-tenant shared environments. Our work focuses on how to apply advanced cryptographic schemes such as Homomorphic Encryption (HE) to protect the privacy and confidentiality of both the data during the training of ML models as well as the models themselves, and as a consequence, the prediction task can also be protected. We de-constructed a typical ML pipeline and applied HE to two of the important ML tasks, namely the variable selection phase of the supervised learning and the prediction task. Quality metrics and performance results demonstrate that HE technology has reached the inflection point to be useful in a financial business setting for a full ML pipeline.

Due to their nature, subliminal channels are mostly regarded as being malicious, but due to recent legislation efforts users' perception might change. Such channels can be used to subvert digital signature protocols without degrading the security of the underlying primitive. Thus, it is natural to find countermeasures and devise subliminal-free signatures. In this paper we discuss state-of-the-art countermeasures and introduce a generic method to bypass them.

Sybil attacks are a well-studied problem in peer-to-peer networking systems. However, their relevance to cryptocurrency mixers has received little attention in the literature, with only a few papers in recent times aiming to design mixers that are resistant to Sybil attacks. A lot of the research has been primarily driven by independent cryptocurrency enthusiasts. We attempt to provide a few characterizations of Sybil attacks as they pertain to mixers and provide mitigations based on economics in order to disincentive Sybil attacks against mixers. In doing so, we highlight that the security of mixers need not only be analyzed through the use of cryptographic techniques but also with the use of economic techniques. Moreover, we provide future research directions in determining heuristics for detecting Sybil identities in mixers.

Blockchain technologies have received a considerable amount of attention, and immutability is essential property of blockchain which is paramount to applications such as cryptocurrency. However, ``Right to be Fogotten" has been imposed in new European Union's General Data Protection Regulation, making legally impossible to use immutalbe blockchains. Moveover, illicit data stored in immutable blockchain poses numerous challenge for law enforcement agencies such as Interpol. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way.

In this paper, we present a redactable proof-of-stake blockchain protocol in the permissionless setting with fast confirmation. Our protocol uses a novel mechanism based on verifiable random functions to randomly select voters on different slots in a private and non-interactive way, and also offers public verifiability for redactable chains. Compared to previous solutions in permissionless setting, our redaction operation can be performed quickly, even only within one block in synchronous network, which is desirable for redacting harmful or sensitive data. Moreover, our protocol is compatible with current proof-of-stake blockchains requiring only minimal changes. Furthermore, we prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we implement our protocol and provide experimental results showing that compared to immutable blockchain, the overhead incurred for different numbers of redactions in the chain is minimal.

The ``Multivariate Ring Learning with Errors'' problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland \emph{et al.} has some important consequences on the security of the multivariate RLWE problem with ``non-coprime'' modular functions; this attack transforms instances of $m$-RLWE with power-of-two cyclotomic modular functions of degree $n = \prod_i n_i$ into a set of RLWE samples with dimension $\max_i{\{ n_i \}}$. This is especially devastating for low-degree modular functions (e.g., $\Phi_4(x) = 1 + x^2$). In this work, we revisit the security of multivariate RLWE and propose new alternative instantiations of the problem that avoid the attack while still preserving the advantages of the multivariate structure, especially when using low-degree modular functions. Additionally, we show how to parameterize these instances in a secure and practical way, therefore enabling constructions and strategies based on $m$-RLWE that bring notable space and time efficiency improvements over current RLWE-based constructions.

In this work, we consider the construction of oblivious RAMs (ORAM) in a setting with multiple servers and the adversary may corrupt a subset of the servers. We present an $\Omega(\log n)$ overhead lower bound for any $k$-server ORAM that limits any PPT adversary to distinguishing advantage at most $1/4k$ when only one server is corrupted. In other words, if one insists on negligible distinguishing advantage, then multi-server ORAMs cannot be faster than single-server ORAMs even with polynomially many servers of which only one unknown server is corrupted. Our results apply to ORAMs that may err with probability at most $1/8$ as well as scenarios where the adversary corrupts larger subsets of servers. We also extend our lower bounds to other important data structures including oblivious stacks, queues, deques, priority queues and search trees.

Keyed and unkeyed cryptographic permutations often iterate simple round functions. Substitution-Permutation Networks (SPNs) are an approach that is popular since the mid 1990s. One of the new directions in the design of these round functions is to reduce the substitution (S-Box) layer from a full one to a partial one, uniformly distributed over all the rounds. LowMC and Zorro are examples of this approach.

A relevant freedom in the design space is to allow for a highly non-uniform distribution of S-Boxes. However, choosing rounds that are so different from each other is very rarely done, as it makes security analysis and implementation much harder. We develop the design strategy Hades and an analysis framework for it, which despite this increased complexity allows for security arguments against many classes of attacks, similar to earlier simpler SPNs. The framework builds up on the wide trail design strategy for SPNs, and it additionally allows for security arguments against algebraic attacks, that are much more of a concern when algebraically simple S-Boxes are used.

Subsequently, this is put into practice by concrete instances and benchmarks for a use case that generally benefits from a smaller number of S-Boxes and showcases the diversity of design options we support: A candidate cipher natively working with objects in GF(p), for securing data transfers with distributed databases using secure multiparty computation (MPC). Compared to the currently fastest design MiMC, we observe significant improvements in online bandwidth requirements and throughput with a simultaneous reduction of preprocessing effort, while having a comparable online latency.

High-order masking countermeasures against side-channel attacks usually require plenty of randomness during their execution. For security against t probes, the classical ISW countermeasure requires O(t^2 s) random bits, where s is the circuit size. However running a True Random Number Generator (TRNG) can be costly in practice and become a bottleneck on embedded devices. In [IKL+13] the authors introduced the notion of robust pseudo-random number generator (PRG), which must remain secure even against an adversary who can probe at most t wires. They showed that when embedding a robust PRG within a private circuit, the number of random bits can be reduced to O(t^4), that is independent of the circuit size s (up to a logarithmic factor). Using bipartite expander graphs, this can be further reduced to O(t^(3+eps)); however the resulting construction is unpractical.

In this paper we describe a practical construction where the number of random bits is only O(t^2) for security against t probes, without expander graphs; moreover the running time of each pseudo-random generation goes down from O(t^4) to O(t). Our technique consists in using multiple independent PRGs instead of a single one. We show that for ISW circuits, the robustness property of the PRG is not required anymore, which leads to simple and efficient constructions. For example, for AES we only need 48 bytes of randomness to get second-order security (t=2), instead of 2880 in the original Rivain-Prouff countermeasure; when implemented on an ARM-based embedded device with a relatively slow TRNG, we obtain a 50% speed-up compared to Rivain-Prouff.

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$-bit signatures for $k$-bits of security. A Schnorr signature $\sigma$ over a group of size $q\approx 2^{2k}$ consists of a tuple $(s,e) $ where $e\in \mathbb{Z}_q$ is a hash output and $s$ must be computed using the secret key. Schnorr proposed the possibility of shorter Schnorr signatures with the same security level by truncating the hash output to $k$-bits, i.e., $e < 2^k$. A previous result showed that short Schnorr signatures provide $k$-bits of single-user security in the programmable random oracle model plus (a non-standard version of) the generic group model. Another prior result demonstrated that standard Schnorr signatures provide $k$-bits of multi-user security in the programmable random oracle model plus (another non-standard version of) the generic group model. As we discuss in the paper these non-standard versions of the generic group model do not capture all generic attacks, e.g., the generic preprocessing attacks of Corrigan-Gibbs and Kogan. In this paper, we prove that short Schnorr signatures provide $k$-bits of (multi-user) security under the (standard) generic group model and the programmable random oracle model.

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC protocols tolerating an arbitrary number of malicious corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain.

We improve the protocol for generating authenticated AND triples, which plays a crucial role in many recent works. -- We propose a multi-party authenticated bit protocol from bare IKNP OT extension, allowing us to 1) reduce the communication by $\approx 24\%$ with a small harmless leakage, and 2) eliminate many computation-heavy procedures like bit-matrix multiplications and consistency checks. This improvement also applies to the two-party setting. -- We reduce the cost of consistency check for multi-party authenticated shares by $\rho$ times where $\rho$ is the statistical security parameter, and also cut the number of hash function calls per party by a factor of $2\times$ when computing leaky authenticated AND triples.

We further improve the state-of-the-art multi-party authenticated garbling protocol. -- We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by $2\kappa$ bits per AND gate per garbler, where $\kappa$ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. -- We further reduce the size of garbled tables by about $4\rho$ bits per AND gate, by using an almost universal hash function to perform the circuit authentication in a batch. Prior solution with similar efficiency is only applicable in the two-party setting.

Along with other optimization, we reduce the communication complexity of the whole protocol (including both function-independent and function-dependent preprocessing phases that require the most resources) by $\approx 24\%$ and significantly improve the overall computational efficiency.

Biometric authentication is increasingly being used for large scale human authentication and identification, creating the risk of leaking the biometric secrets of millions of users in the case of database compromise. Powerful ``fuzzy'' cryptographic techniques for biometric template protection, such as secure sketches, could help in principle, but go unused in practice. This is because they would require new biometric matching algorithms with potentially much-diminished accuracy.

We introduce a new primitive called a multisketch that generalizes secure sketches. Multisketches can work with existing biometric matching algorithms to generate strong cryptographic keys from biometric data reliably. A multisketch works on a biometric database containing multiple biometrics --- e.g., multiple fingerprints --- of a moderately large population of users (say, thousands). It conceals the correspondence between users and their biometric templates, preventing an attacker from learning the biometric data of a user in the advent of a breach, but enabling derivation of user-specific secret keys upon successful user authentication.

We design a multisketch over tenprints --- fingerprints of ten fingers --- called TenSketch. We report on a prototype implementation of TenSketch, showing its feasibility in practice. We explore several possible attacks against TenSketch database and show, via simulations with real tenprint datasets, that an attacker must perform a large amount of computation to learn any meaningful information from a stolen TenSketch database.

Traceable range proofs enable regulators to trace the amounts of transactions in privacy-preserving blockchains, but it lacks adequate functionality in the application scenarios such as currency (assets) transfer, international trades and taxation, etc. In this paper, we give multiple modifications and applications on traceable Borromean range proof (TBoRP) and traceable Bulletproofs range proof (TBuRP), which realize functionalities including multi-currency regulation, regulatable private assets transfer, auxiliary privacy calculation and secure joint regulation by usage of zero-knowledge proofs, homomorphic commitments and MPC protocols. Our work can help regulators to choose the regulatory policy as they wish and help users to transfer assets, compute private amounts under the regulation efficiently and independently. Our solutions are well suited for the future applications of regulatable privacy-preserving cryptocurrencies.

Motivated by the fact that in the quantum random oracle model (QROM) introduced by Boneh et al. (Asiacrypt 2011), honest parties (i.e., the cryptosystems) typically use the random oracle (RO) in a classical way while the adversary can send quantum queries to the RO, we first reformalize the classical RO (CRO) and the quantum RO (QRO) by adapting the indifferentiability framework of Maurer et al. (TCC 2004), and equipping a RO with a private and a (quantum) public interface for the honest parties and the adversary, respectively. Then, we give a new separation between the QROM and the ROM by showing that QRO is differentiable from CRO, which is technically different from Boneh et al.'s separation and is based on a new information versus disturbance lemma (that may be of independent interest).

We further abstract a class of BB-reductions in the ROM under the notion of committed-programming reduction (CPRed) for which the simulation of the RO can be easily quantized to handle quantum queries (from the adversary in the QROM). We show that 1) some well-known schemes such as the FDH signature and the Boneh-Franklin identity-based encryption are provably secure under CPReds; and 2) a CPRed associated with an instance-extraction algorithm implies a reduction in the QROM, which subsumes several recent results such as the security of the FDH signature by Zhandry (Crypto 2012) and the KEM variants from the Fujisaki-Okamoto transform by Jiang et al. (Crypto 2018).

We finally show that CPReds are incomparable to non-programming reductions (NPReds) and randomly-programming reductions (RPReds) formalized by Fischlin et al. (Asiacrypt 2010), which gives new insights into the abilities (e.g., observability and programmability) provided by the (Q)ROM, and the hardness of proving security in the QROM.

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing.

This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, the constructions for three families of compartmented access structures, and the constructions for two families compartmented access structures with compartments.

On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to several families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of those families of access structures above, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing those families of multipartite access structures by efficient methods.