International Association
for Cryptologic Research

Bitcoin relies on the Unspent Transaction Outputs (UTXO) set to efficiently verify new generated transactions. Every unspent out- put, no matter its type, age, value or length is stored in every full node. In this paper we introduce a tool to study and analyze the UTXO set, along with a detailed description of the set format and functionality. Our analysis includes a general view of the set and quantifies the difference between the two existing formats up to the date. We also provide an ac- curate analysis of the volume of dust and unprofitable outputs included in the set, the distribution of the block height in which the outputs where included, and the use of non-standard outputs.

*Constrained* pseudorandom functions allow for delegating ``constrained'' secret keys that let one compute the function at certain authorized inputs---as specified by a constraining predicate---while keeping the function value at unauthorized inputs pseudorandom. In the *constraint-hiding* variant, the constrained key hides the predicate. On top of this, *programmable* variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs.

Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors~(LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC'17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC'17].

In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $\exp(n^{\varepsilon})$ approximation factors. Our constructions follow straightforwardly from a new notion we call a *shift-hiding shiftable function*, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.

In this paper, we present an implementation scheme of a RTGS on Quorum using the Solidity language. It is heavily inspired by the Schnorr signature protocol to verify the identity of the participants. Our architecture mimics efficiently current market structures, and adds extra security and confidentiality. It also leaves room for regulation, while still running in a decentralised way with coordinating agents. We use non-interactive zero-knowledge algorithms, which are cryptographic protocols with numerous applications in the fields of cryptocurrencies. They allow an agent to verify that another agent holds a specific information, while the latter never discloses this information. For the sake of our experimentations, we had to use very small integers in our protocols. These integers are too small to comply with current security standards in finance, although the architectural principles can be easily transposed with better performing protocols. We present suggestions to improve our proof of concept and our architecture in the last part.

In this work we introduce the corruptible token model. This model generalizes the stateless tamper-proof token model introduced by Katz (EUROCRYPT '07) and relaxes the trust assumption. Our improved model is motivated by the real-world practice of outsourcing hardware production to possibly untrusted manufacturers and allows tokens created by honest parties to be corrupted at the time of their creation.

Assuming one-way functions, we show how to UC-securely realize the tamper-proof token functionality of Katz in the corruptible token model with $n$ stateless tokens assuming that the adversary corrupts at most $n-1$ of them. We then apply this transformation to existing two and MPC protocols to achieve a UC-secure 2PC/MPC protocol in the corruptible token model assuming only the existence of one-way functions.

Finally, we further transform the above protocol to only use tokens of small size that take only short inputs. The technique in the last transformation can also be used to improve the assumption of UC-secure hardware obfuscation by Nayak et al. (NDSS '17) from collision-resistant hash functions to one-way functions, which can then be transformed into a protocol with $n$ corruptible tokens in our model.

Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest.

We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX).

Unlike previous works that either penalize an aborting party or achieve weaker notions such as $\Delta$-fairness, we achieve complete fairness using existing infrastructure.

Vulnerability reward programs, a.k.a. bug bounties, are a popular tool that could help prevent software exploits. Today, however, they lack rigorous principles for setting bounty amounts and require high payments to attract economically rational hackers. Rather than claim bounties for serious bugs, hackers often sell or exploit them. We present the Hydra Framework, the first general, principled approach to modeling and administering bug bounties and boosting incentives for hackers to report bugs. The key idea is what we call an exploit gap, a program transformation that enables runtime detection of security-critical bugs. The Hydra Framework transforms programs via N-of-N-version programming (NNVP), a variant of classical N-version programming that executes multiple independent program instances. We apply the Hydra Framework to smart contracts, small programs that execute on blockchains. We show how Hydra contracts greatly amplify the power of bounties to incentivize bug disclosure by economically rational adversaries, establishing the first framework for economic evaluation of smart contract security. We also model powerful adversaries capable of bug withholding, exploiting race conditions in blockchains to claim bounties before honest users can. We present Submarine Commitments, a countermeasure of independent interest that conceals transactions on blockchains. We present a simple core Hydra Framework for Ethereum. We report the implementation of two Hydra contracts—an ERC20 token contract and a Monty-Hall-like game.

Cloud providers tend to save storage via cross-user deduplication, while users who care about privacy tend to encrypt their files on client-side. Secure deduplication of encrypted data (SDoE) is an active research topic. In this paper, we propose a formal security model for this problem. We also propose two single-server SDoE protocols and prove their security in our model. We evaluate their deduplication effectiveness via simulations with realistic datasets.

We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show that unlike standard ZK, promise ZK can be realized in three rounds in the simultaneous-message model under standard assumptions.

We demonstrate the following applications of our new technique:

-> We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard LWE and DDH. Previously, such protocols required sub-exponential-time hardness assumptions.

-> We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for ``list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on injective one-way functions. This result generalizes to randomized input-less functionalities assuming polynomially hard LWE.

Previously, four round MPC protocols required sub-exponential hardness assumptions and no multi-party three-round protocols with polynomial simulation were known for any relaxed security notions against malicious adversaries.

In order to base security on polynomial-time standard assumptions, we also develop a new leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving ``non-malleability'' across different primitives. This technique may be of independent interest.

This chapter describes the developments since 1970 in general purpose integer factoring and highlights the contributions of Peter L. Montgomery.

This article appeared as Chapter 5 of the book "Topics in Computational Number Theory inspired by Peter L. Montgomery", edited by Joppe W. Bos and Arjen K. Lenstra and published by Cambridge University Press. See www.cambridge.org/9781107109353.

Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted database (EDB) systems as secure cloud storage. In this work, we study the leakage of OPE and ORE and their forward security. We propose generic yet powerful file-injection attacks (FIAs) on OPE/ORE, aimed at the situations of possessing order by and range queries. The FIA schemes only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We also improve its efficiency with the frequency statistics using a hierarchical idea such that the high-frequency values will be recovered more quickly. Compared with other attacks against OPE/ORE proposed in recent years, our FIA attacks rely upon less demanding conditions and are more effective for attacking the systems with the function of data sharing or transferring like encrypted email system. We executed some experiments on real datasets to test the performance, and the results show that our FIA attacks can cause an extreme hazard on most of the existing OPE and ORE schemes with high efficiency and 100% recovery rate. In order to resist the perniciousness of FIA, we propose a practical compilation framework for achieving forward secure ORE. The compilation framework only uses some simple cryptographical tools like pseudo-random function, hash function and trapdoor permutation. It can transform most of the existing OPE/ORE schemes into forward secure ORE schemes, with the goal of minimizing the extra burden incurred on computation and storage. We also present its security proof and execute some experiments to analyze its performance.

Profiled side-channel attacks represent the most powerful category of side-channel attacks. In this context, the attacker gains ac- cess of a profiling device to build a precise model which is used to attack another device in the attacking phase. Mostly, it is assumed that the attacker has unlimited capabilities in the profiling phase, whereas the attacking phase is very restricted. We step away from this assumption and consider an attacker who is restricted in the profiling phase, while the attacking phase is less limited as in the traditional view. Clearly, in general, the attacker is not hindered to exchange any available knowledge between the profiling and attacking phase. Accordingly, we propose the concept of semi-supervised learning to side-channel analysis, in which the attacker uses the small amount of labeled measurements from the profil- ing phase as well as the unlabeled measurements from the attacking phase to build a more reliable model. Our results show that semi-supervised learning is beneficial in many scenarios and of particular interest when using template attack and its pooled version as side-channel attack tech- niques. Besides stating our results in varying scenarios, we discuss more general conclusions on semi-supervised learning for SCA that should help to transfer our observations to other settings in SCA.

Many block ciphers and hash functions require the diffusion property of Maximum Distance Separable (MDS) matrices. Serial matrices with the MDS property obtain a trade-off between area requirement and clock cycle performance to meet the needs of lightweight cryptography. In this paper, we propose a new class of serial-type matrices called Diagonal-Serial Invertible (DSI) matrices with the sparse property. These matrices have a fixed XOR count (contributed by the connecting XORs) which is half that of existing matrices. We prove that for matrices of order 4, our construction gives the matrix with the lowest possible fixed XOR cost. We also introduce the Reversible Implementation (RI) property, which allows the inverse matrix to be implemented using the similar hardware resource as the forward matrix, even when the two matrices have different finite field entries. This allows us to search for serial-type matrices which are lightweight in both directions by just focusing on the forward direction. We obtain MDS matrices which outperform existing lightweight (involutory) matrices.

The trend of supporting wide vector units in general purpose microprocessors suggests opportunities for developing a new and elegant compilation approach to mitigate the impact of faults to cryptographic implementations, which we present in this work. We propose a compilation flow, CAMFAS, to automatically and selectively introduce vectorization in a cryptographic library - to translate a vanilla library into a library with vectorized code that is resistant to glitches. Unlike in traditional vectorization, the proposed compilation flow uses the extent of the vectors to introduce spatial redundancy in the intermediate computations. By doing so, without significantly increasing code size and execution time, the compilation flow provides sufficient redundancy in the data to detect errors in the intermediate values of the computation. Experimental results show that the proposed approach only generates an average of 26\% more dynamic instructions over a series of asymmetric cryptographic algorithms in the Libgcrypt library.

Fault injection attacks alter the intended behavior of micro- controllers, compromising their security. These attacks can be mitigated using software countermeasures. A widely-used software-based solution to deflect fault attacks is instruction duplication and n-plication. We explore two main limitations with these approaches: first, we examine the effect of instruction duplication under fault attacks, demonstrating that as fault tolerance mechanism, code duplication does not provide a strong protection in practice. Second, we show that instruction duplication increases side-channel leakage of sensitive code regions using a multivariate exploitation technique both in theory and in practice.

Hitherto the duality between left-to-right and right-to-left exponentiation algorithms has been a loosely defined concept. Recently, the author made the definition precise by adding requirements on space usage and operation types. Here it is shown that the Montgomery and Joye powering ladders are dual in this sense. Several versions of these algorithms are derived naturally with a cost-free, natural, built-in blinding mechanism as a side channel counter-measure.

Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, investigate quantum lightning, a formalization of "collision-free quantum money" defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results:

- We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local.

- We give win-win results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this gives some indication that natural schemes do attain strong security guarantees.

- We construct quantum lightning under the assumed multi-collision resistance of random degree-2 systems of polynomials. Our construction is inspired by our win-win result for hash functions, and yields the first plausible standard model instantiation of a non-collapsing collision resistant hash function. This improves on a result of Unruh [Eurocrypt'16] that requires a quantum oracle.

- We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC'12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our win-win result for signatures, giving the first separation between two security notions for signatures from the literature.

Thus, we provide the first constructions of public key quantum money from several cryptographic assumptions. Along the way, we develop several new techniques including a new precise variant of the no-cloning theorem.

Side Channel Attacks are an important attack vector on secure AES implementations. The Correlation-Enhanced Power Analysis Collision Attack by Moradi et al. [13] is a powerful collision attack that exploits leakage caused by collisions in between S-Box computations of AES. The attack yields observations from which the AES key can be inferred. Due to noise, an insufficient number of collisions, or errors in the measurement setup, the attack does not find the correct AES key uniquely in practice, and it is unclear how to determine the key in such a scenario. Based on a theoretical analysis on how to quantify the remaining entropy, we derive a practical search algorithm. Both our theoretical analysis and practical experiments show that even in a setting with high noise or few available traces we can either successfully recover the full AES key or reduce its entropy significantly.

To protect database confidentiality even in the face of full compromise while supporting standard functionality, recent academic proposals and commercial products rely on a mix of encryption schemes. The common recommendation is to apply strong, semantically secure encryption to the “sensitive” columns and protect other columns with property-revealing encryption (PRE) that supports operations such as sorting. We design, implement, and evaluate a new methodology for inferring data stored in such encrypted databases. The cornerstone is the multinomial attack, a new inference technique that is analytically optimal and empirically outperforms prior heuristic attacks against PRE-encrypted data. We also extend the multinomial attack to take advantage of correlations across multiple columns. These improvements recover PRE-encrypted data with sufficient accuracy to then apply machine learning and record linkage methods to infer the values of columns protected by semantically secure encryption or redaction. We evaluate our methodology on medical, census, and union-membership datasets, showing for the first time how to infer full database records. For PRE-encrypted attributes such as demographics and ZIP codes, our attack outperforms the best prior heuristic by a factor of 16. Unlike any prior technique, we also infer attributes, such as incomes and medical diagnoses, protected by strong encryption. For example, when we infer that a patient in a hospital-discharge dataset has a mental health or substance abuse condition, this prediction is 97% accurate.

The KMOV scheme is a public key cryptosystem based on an RSA modulus $n=pq$ where $p$ and $q$ are large prime numbers with $p\equiv q\equiv 2\pmod 3$. It uses the points of an elliptic curve with equation $y^2\equiv x^3+b\pmod n$. In this paper, we propose a generalization of the KMOV cryptosystem with a prime power modulus of the form $n=p^{r}q^{s}$ and study its resistance to the known attacks.

Let $N=pq$ be an RSA modulus with unknown factorization. Some variants of the RSA cryptosystem, such as LUC, RSA with Gaussian primes and RSA type schemes based on singular elliptic curves use a public key $e$ and a private key $d$ satisfying an equation of the form $ed- k\left(p^2-1\right)\left(q^2-1\right)=1$. In this paper, we consider the general equation $ex-\left(p^2-1\right)\left(q^2-1\right)y=z$ and present a new attack that finds the prime factors $p$ and $q$ in the case that $x$, $y$ and $z$ satisfy a specific condition. The attack combines the continued fraction algorithm and Coppersmith's technique and can be seen as a generalization of the attacks of Wiener and Bl\"{o}mer-May on RSA.