International Association
for Cryptologic Research

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.

Most modern web browsers today sacrifice optimal TLS security for backward compatibility. They apply coarse-grained TLS configurations that support (by default) legacy versions of the protocol that have known design weaknesses, and weak ciphersuites that provide fewer security guarantees (e.g. non Forward Secrecy), and silently fall back to them if the server selects to. This introduces various risks including downgrade attacks such as the POODLE attack that exploits the browsers silent fallback mechanism to downgrade the protocol version in order to exploit the legacy version flaws. To achieve a better balance between security and backward compatibility, we propose a mechanism for fine-grained TLS configurations in web browsers based on the sensitivity of the domain name in the HTTPS request using a white listing technique. That is, the browser enforces optimal TLS configurations for connections going to sensitive domains while enforcing default configurations for the rest of the connections. We demonstrate the feasibility of our proposal by implementing a proof-of-concept as a Firefox browser extension. We envision this mechanism as a built-in security feature in web browsers, e.g. a button similar to the “Bookmark” button in Firefox browsers and as a standardised HTTP header, to augment browsers security.

We continue the study of Ben-Efraim (Asiacrypt 2018) on multiparty garbled circuits that contain both Boolean and arithmetic gates. Concretely, we extend the work of Ben-Efraim from the semi-honest, honest majority security model to the full-threshold actively secure equivalent. We further improve Ben-Efraim's selector gate. A selector gate is a gate that given two arithmetic inputs and one binary input, outputs one of the arithmetic inputs, based on the value of the selection bit input. Our new construction for the selector gate reduces the communication cost to almost half of that of Ben-Efraim's gate. This result applies both to the semi-honest and to the active security model.

In permissioned blockchain systems, participants are admitted to the network by receiving a credential from a certification authority. Each transaction processed by the network is required to be authorized by a valid participant who authenticates via their credential. Use case settings where privacy is a concern thus require proper privacy-preserving authentication and authorization mechanisms. Anonymous credential schemes are cryptographic mechanisms that allow a user to authenticate while showing only those attributes necessary in a given setting, which makes these schemes a great tool for authorizing transactions in permissioned blockchain systems based on the user's attributes. As in most setups of such systems there is one distinct certification authority for each organization in the network, the use of plain anonymous credential schemes still leaks the association of a user to their issuing organization. Camenisch, Drijvers, and Dubovitskaya (CCS 2017) therefore suggest the use of delegatable anonymous credential schemes, which allows to hide even that remaining piece of information. We implement private transaction authorization in Hyperledger Fabric based on delegatable anonymous credentials. To this end, we provide a production-grade open-source implementation of the Camenisch et al. scheme with several optimizations. We then extend Fabric to support the scheme as an additional mechanism for authorizing transactions. Our solution supports revocation and auditing, making it ready for real-world deployment. Our performance measurements show that the scheme, while incurring an overhead in comparison to the less privacy-preserving ones, is practical for settings with enhanced privacy requirements.

Proof-of-burn has been used as a mechanism to destroy cryptocurrency in a verifiable manner. Despite its well known use, the mechanism has not been previously formally studied as a primitive. In this paper, we put forth the first cryptographic definition of what a proof-of-burn protocol is. It consists of two functions: First, a function which generates a cryptocurrency address. When a user sends money to this address, the money is irrevocably destroyed. Second, a verification function which checks that an address is really unspendable. We propose the following properties for burn protocols. Unspendability, which mandates that an address which verifies correctly as a burn address cannot be used for spending; binding, which allows associating metadata with a particular burn; and uncensorability, which mandates that a burn address is indistinguishable from a regular cryptocurrency address. Our definition captures all previously known proof-of-burn protocols. Next, we design a novel construction for burning which is simple and flexible, making it compatible with all existing popular cryptocurrencies. We prove our scheme is secure in the Random Oracle model. We explore the application of destroying value in a legacy cryptocurrency to bootstrap a new one. The user burns coins in the source blockchain and subsequently creates a proof-of-burn, a short string proving that the burn took place, which she then submits to the destination blockchain to be rewarded with a corresponding amount. The user can use a standard wallet to conduct the burn without requiring specialized software, making our scheme user friendly. We propose burn verification mechanisms with different security guarantees, noting that the target blockchain miners do not necessarily need to monitor the source blockchain. Finally, we implement the verification of Bitcoin burns as an Ethereum smart contract and experimentally measure that the gas costs needed for verification are as low as standard Bitcoin transaction fees, illustrating that our scheme is practical.

We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al. (Crypto 2017), where our generalized variant uses FSS to achieve exponential efficiency improvement for useful types of gates.

By instantiating this general approach with efficient PRG-based FSS schemes of Boyle et al. (Eurocrypt 2015, CCS 2016), we can implement useful nonlinear gates for equality tests, integer comparison, bit-decomposition and more with optimal online communication and with a relatively small amount of correlated randomness. We also provide a unified and simplified view of several existing protocols in the preprocessing model via the FSS framework.

Our positive results provide a useful tool for secure computation tasks that involve secure integer comparisons or conversions between arithmetic and binary representations. These arise in the contexts of approximating real-valued functions, machine-learning classification, and more.

Finally, we study the necessity of the FSS machinery that we employ, in the simple context of secure string equality testing. First, we show that any "online-optimal" secure equality protocol implies an FSS scheme for point functions, which in turn implies one-way functions. Then, we show that information-theoretic secure equality protocols with relaxed optimality requirements would follow from the existence of big families of "matching vectors." This suggests that proving strong lower bounds on the efficiency of such protocols would be difficult.