International Association
for Cryptologic Research

At CRYPTO 2018 Cramer et al. presented SPDZ2k, a new secret-sharing based protocol for actively secure multi-party computation against a dishonest majority, that works over rings instead of fields. Their protocol uses slightly more communication than competitive schemes working over fields. However, their approach allows for arithmetic to be carried out using native 32 or 64-bit CPU operations rather than modulo a large prime. The authors thus conjectured that the increased communication would be more than made up for by the increased efficiency of implementations.

In this work we answer their conjecture in the affirmative. We do so by implementing their scheme, and designing and implementing new efficient protocols for equality test, comparison, and truncation over rings. We further show that these operations find application in the machine learning domain, and indeed significantly outperform their field-based competitors. In particular, we implement and benchmark oblivious algorithms for decision tree and support vector machine (SVM) evaluation.

Information ratio of an access structure is an important measure for efficiency of the best secret sharing scheme realizing it. The most common notion of secret sharing security is that of total (perfect) realization. Two well-known relaxations are the notions of statistical and quasi-total secret sharing. In this paper, we study the relation between different security notions. The most significant and technical result of this paper is that quasi-total and total information ratios coincide for linear schemes. To this end, we employ some tools from linear algebra in companion with a newly introduced relaxed security notion, called partial realization. We provide some intuition that why proving coincidence/separation between total and quasi-total information ratios for the class of abelian schemes is probably much more challenging.

We also present some additional results which shed further light on our understanding of different security notions. In particular, one of our results, in combination with a recent result, shows that statistical and total security notions coincide for the class of group-homomorphic schemes, or maybe even a larger class.

The contribution vector (convec) of a secret sharing scheme is the vector of all share sizes divided by the secret size. A measure on the convec (e.g., its maximum or average) is considered as a criterion of efficiency of secret sharing schemes, which is referred to as the information ratio.

It is generally believed that there exists a family of access structures such that the information ratio of any secret sharing scheme realizing it is $2^{\mathrm{\Omega}(n)}$, where the parameter $n$ stands for the number of participants. The best known lower bound, due to Csirmaz (1994), is $\mathrm{\Omega}(n/\log n)$. Closing this gap is a long-standing open problem in cryptology.

Using a technique called \emph{substitution}, we recursively construct a family of access structures by starting from that of Csirmaz, which might be a candidate for super-polynomial information ratio. We provide support for this possibility by showing that our family has information ratio ${n^{\mathrm{\Omega}(\frac{\log n}{\log \log n})}}$, assuming the truth of a well-stated information-theoretic conjecture, called the \emph{substitution conjecture}. The substitution method is a technique for composition of access structures, similar to the so called block composition of Boolean functions, and the substitution conjecture is reminiscent of the Karchmer-Raz-Wigderson conjecture on depth complexity of Boolean functions. It emerges after introducing the notion of convec set for an access structure, a subset of $n$-dimensional real space, which includes all achievable convecs. We prove some topological properties about convec sets and raise several open problems.

A statistical framework applicable to Ring-LWE was outlined by Murphy and Player (IACR eprint 2019/452). Its applicability was demonstrated with an analysis of the decryption failure probability for degree-1 and degree-2 ciphertexts in the homomorphic encryption scheme of Lyubashevsky, Peikert and Regev (IACR eprint 2013/293). In this paper, we clarify and extend results presented by Murphy and Player. Firstly, we make precise the approximation of the discretisation of a Normal random variable as a Normal random variable, as used in the encryption process of Lyubashevsky, Peikert and Regev. Secondly, we show how to extend the analysis given by Murphy and Player to degree-k ciphertexts, by precisely characterising the distribution of the noise in these ciphertexts.

Monero has emerged as one of the leading cryptocurrencies with privacy by design. However, this comes at the price of reduced expressiveness and interoperability as well as severe scalability issues. First, Monero is restricted to coin exchanges among individual addresses and no further functionality is supported. Second, transactions are authorized by linkable ring signatures, a digital signature scheme only available in Monero, hindering thereby the interoperability with the rest of cryptocurrencies. Third, Monero transactions require high on-chain footprint, which leads to a rapid ledger growth and thus scalability issues.

In this work, we extend Monero expressiveness and interoperability while mitigating its scalability issues. We present \emph{Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)}, a novel linkable ring signature scheme that enables for the first time \emph{refund transactions} natively in Monero: DLSAG can seamlessly be implemented along with other cryptographic tools already available in Monero such as commitments and range proofs. We formally prove that DLSAG achieves the same security and privacy notions introduced in the original linkable ring signature~\cite{Liu2004} namely, unforgeability, signer ambiguity, and linkability. We have evaluated DLSAG and showed that it imposes even slightly lower computation and similar communication overhead than the current digital signature scheme in Monero, demonstrating its practicality. We further show how to leverage DLSAG to enable off-chain scalability solutions in Monero such as payment channels and payment-channel networks as well as atomic swaps and interoperable payments with virtually all cryptocurrencies available today. DLSAG is currently being discussed within the Monero community as an option for possible adoption as a key building block for expressiveness, interoperability, and scalability.

We analyze the structure of finite commutative rings with respect to its idempotent and nilpotent elements. Based on this analysis we provide a quantum-classical IND-CCA^1 attack for ring homomorphic encryption schemes. Moreover, when the plaintext space is a finite reduced ring, i.e. a product of finite fields, we present a key-recovery attack based on representation problem in black-box finite fields. In particular, if the ciphertext space has smooth characteristic the key-recovery attack is effectively computable. We also extend the work of Maurer and Raub on representation problem in black-box finite fields to the case of a black-box product of finite fields of equal characteristic.

Noncommutative cryptography is based on applications of algebraic structures like noncommutative groups, semigroups and non-commutative rings. Its inter-section with Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined overfinite commutative rings. Efficiently computed homomorphisms between stable subsemigroups of affine Cremona semigroups can be used in tame homomorphisms protocols schemes and their inverse versions. The implementation scheme with the sequence of subgroups of affine Cremona group, which defines projective limit was already suggested. We present the implementation of other scheme which uses two projective limits which define two different infinite groups and the homomorphism between them. The security of corresponding algorithm is based on a complexity of decomposition problem for an element of affine Cremona semigroup into product of given generators. These algorithms may be used in postquantum technologies.

Tor is a network based on the onion routing infrastructure and provides many advantages, including tracking avoidance, research, wider access and, unfortunately, illegal activities. To achieve this, the client will connect to a TOR circuit consisting of nodes chosen under certain restrictions. The purpose of this paper is to draw attention of the narrow range of available and constraints obedient nodes. This is of interest because it impacts the anonymity and the privacy of users and their internet traffic.

Convolutional neural networks (CNNs) is a category of deep neural networks that are primarily used for classifying image data. Yet, their continuous gain in popularity poses important privacy concerns for the potentially sensitive data that they process. A solution to this problem is to combine CNNs with Fully Homomorphic Encryption (FHE) techniques. In this work, we study this approach by focusing on two popular FHE schemes, TFHE and HEAAN, that can work in the approximated computational model. We start by providing an analysis of the noise after each principal homomorphic operation, i.e. multiplication, linear combination, rotation and bootstrapping. Then, we provide a theoretical study on how the most important non-linear operations of a CNN (i.e. max, Abs, ReLU), can be evaluated in each scheme. Finally, we measure via practical experiments on the plaintext the robustness of different neural networks against perturbations of their internal weights that could potentially result from the propagation of large homomorphic noise. This allows us to simulate homomorphic evaluations with large amounts of noise and to predict the effect on the classification accuracy without a real evaluation of heavy and time-consuming homomorphic operations. In addition, this approach enables us to correctly choose smaller and more efficient parameter sets for both schemes.

We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE). We give new, tighter security reductions for several constructions. Our main result is a tight reduction for the security of the $U^{\not\bot}$-transform of Hofheinz, H\"ovelmanns, and Kiltz (TCC'17) which turns OW-CPA secure deterministic PKEs into IND-CCA secure KEMs. This result is enabled by a new one-way to hiding (O2H) lemma which gives a tighter bound than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the $U^{\not\bot}$-transform discussed in the literature on the security of the final scheme. We consider the difference between explicit ($U^\bot$) and implicit ($U^{\not\bot}$) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext ($U^{\not\bot}$) or just from the message ($U^{\not\bot}_m$).

The striking growth in cryptocurrencies is revealing several scalability issues that go beyond the growing size of the blockchain. Payment channel hubs (PCHs) constitute a promising scalability solution by performing off-chain payments between sender and receiver through an intermediary, called the tumbler. While currently proposed PCHs provide security and privacy guarantees against a malicious tumbler, they fall short of other fundamental properties, such as interoperability and fungibility.

In this work, we present A${^2}$L, the first secure, privacy-preserving, interoperable, and fungibility-preserving PCH. A${^2}$L builds on a novel cryptographic primitive that realizes a three-party protocol for conditional transactions, where the intermediary pays the receiver only if the latter solves a cryptographic challenge with the help of the sender. We prove the security and privacy guarantees of A${^2}$L in the Universal Composability framework and present two provably secure instantiations based on Schnorr and ECDSA signatures.

We implemented A${^2}$L and our evaluation shows that it outperforms TumbleBit, the state-of-the-art PCH in terms of interoperability, which is one of the central goals of this work. In particular, we show that in a commodity hardware as well as in a more realistic, distributed setting where sender, receiver and tumbler sit at different geographical locations worldwide, our ECDSA-based construction is 3x faster and requires 15x less bandwidth, while our Schnorr-based construction is 8x faster and requires 21x less bandwidth. These results demonstrate that A${^2}$L is the most efficient Bitcoin-compatible PCH.

Homomorphic encryption enables computations with encrypted data, however, in its plain form, it does not guarantee that the computation has been performed honestly. For the Fully Homomorphic Encryption (FHE), a verifiable variant emerged soon after the introduction of FHE itself, for a single-operation homomorphic encryption (HE), particular verifiable variant has been introduced recently, called the VeraGreg Framework. In this paper, we identify a weakness of List Non-Malleability as defined for the VeraGreg Framework—an analogy to the classical Non-Malleability—and suggest its improvement which we show not to be extendable any more in certain sense. Next, we suggest a decomposition of the abstract VeraGreg framework, introduce novel notions of security for the resulting components and show some reductions between them and/or their combinations. Finally, we conjecture that VeraGreg achieves the strongest (and desirable) security guarantee if and only if its building blocks achieve certain, much more tangible properties, in a specific case together with an assumption on hardness of particular kind of the famous Shortest Vector Problem for lattices.

In this paper, we introduce \emph{Polygraph}, the first accountable Byzantine consensus algorithm for partially synchronous systems. If among $n$ users $t<\frac{n}{3}$ are malicious then it ensures consensus, otherwise it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchain applications as it allows them, if $t<\frac{n}{3}$, to totally order blocks in a chain, hence avoiding forks and double spending and, otherwise, to punish malicious users when a fork occurs. We first show that stronger forms of the problem including a fixed time detection are impossible to solve before proving our solution. We also show that Polygraph has a bounded justification size so that each of its asynchronous rounds exchanges only $O(n^2)$ messages. Finally, we use a blockchain application to evaluate Polygraph on a geodistributed system of 80 machines and show that accountability reduces the performance of the non-accountable baseline by about a third, still committing thousands of transactions per second.

The pairing-based simulation-extractable succinct non-interactive arguments of knowledge (SE-SNARKs) are attractive since they enable a prover to generate a proof with the knowledge of the witness to an instance in a manner which is succinct - proofs are short and the verifier's computation is small, zero-knowledge - proofs do not reveal the witness, and simulation-extractable - it is only possible to prove instances to which a witness is known although a number of simulated proofs are provided. The state-of-the-art pairing-based SE-SNARK is based on a square arithmetic program (SAP), instead of a more generalized quadratic arithmetic program (QAP). In order to add simulation extractability, the SE-SNARK requires to verify an additional equation compared to the state-of-the-art SNARKs.

In this paper, we propose a QAP-based SE-SNARK which consists of only 3 group elements for a QAP circuit and a single verification equation in asymmetric groups (Type III pairing). The proposed scheme is secure under concrete intractability assumptions in the random oracle model. Moreover, we propose a scheme with two elements as a proof and a single verifying equation, based on SAP in a symmetric group (Type I pairing).

In this paper, we study DFA attacks on some of the CAESAR competition winners. We study the challenges imposed by the design of these modes, such as masking of the ciphertext. We also show that a very small number of nonce repetition and faults is required, which makes it very practical. We show that OCB and COLM need 1 nonce repetition and 3 faults only to uniquely identify the Key.

In a secret sharing scheme, a secret value is encrypted into several shares, which are distributed among corresponding participants. It requires that only predefined subsets of participants can reconstruct the secret with their shares. The general model for secret sharing schemes is provided in different forms, in order to study the essential properties of secret sharing schemes. Considering that it is difficult to directly con- struct secret sharing schemes meeting the requirements of the general model, most of current theoretic researches always rely on other mathematical tools, such as matriod. However, these models can only handle with values in a finite field. In this paper, we firstly establish a one-to-one mapping relationship between Latin squares and 2-threshold secret sharing schemes. Afterwards, we utilize properties of Latin squares to further give an exact characterization for the general model of 2-threshold ideal secret sharing schemes. Furthermore, several interesting properties of 2-threshold ideal schemes are provided, which are not induced by any other means, especially nolinear schemes in an arbitrary integer domain.

Current cryptocurrencies provide a heavily limited transaction throughput that is clearly insufficient to cater to their growing adoption. Payment-channel networks (PCNs) have emerged as an interesting solution to the scalability issue and are currently deployed by popular cryptocurrencies such as Bitcoin and Ethereum. While PCNs do increase the transaction throughput by processing payments off-chain and using the blockchain only as a dispute arbitrator, they unfortunately require high collateral (i.e., they lock coins for a non-constant time along the payment path) and are restricted to payments in a path from sender to receiver. These issues have severe consequences in practice. The high collateral enables griefing attacks that hamper the throughput and utility of the PCN. Moreover, the limited functionality hinders the applicability of current PCNs in many important application scenarios. Unfortunately, current proposals do not solve either of these issues, or they require Turing-complete language support, which severely limits their applicability.

In this work, we present AMCU, the first protocol for atomic multi-channel updates and reduced collateral that is compatible with Bitcoin (and other cryptocurrencies with reduced scripting capabilities). We provide a formal model in the Universal Composability framework and show that AMCU realizes it, thus demonstrating that AMCU achieves atomicity and state privacy. Moreover, the reduced collateral mitigates the consequences of griefing attacks in PCNs while the (multi-payment) atomicity achieved by AMCU opens the door to new applications such as credit rebalancing and crowdfunding that are not possible otherwise. Moreover, our evaluation results demonstrate that AMCU has a performance in line with that of the Lightning Network (the most widely deployed PCN) and thus is ready to be deployed in practice.

We present a methodology for using the EasyCrypt proof assistant (originally designed for mechanizing the generation of proofs of game-based security of cryptographic schemes and protocols) to mechanize proofs of security of cryptographic protocols within the universally composable (UC) security framework. This allows, for the first time, the mechanization and formal verification of the entire sequence of steps needed for proving simulation-based security in a modular way:

* Specifying a protocol and the desired ideal functionality.

* Constructing a simulator and demonstrating its validity, via reduction to hard computational problems.

* Invoking the universal composition operation and demonstrating that it indeed preserves security.

We demonstrate our methodology on a simple example: stating and proving the security of secure message communication via a one-time pad, where the key comes from a Diffie-Hellman key-exchange, assuming ideally authenticated communication. We first put together EasyCrypt-verified proofs that: (a) the Diffie-Hellman protocol UC-realizes an ideal key-exchange functionality, assuming hardness of the Decisional Diffie-Hellman problem, and (b) one-time-pad encryption, with a key obtained using ideal key-exchange, UC-realizes an ideal secure-communication functionality. We then mechanically combine the two proofs into an EasyCrypt-verified proof that the composed protocol realizes the same ideal secure-communication functionality.

Although formulating a methodology that is both sound and workable has proven to be a complex task, we are hopeful that it will prove to be the basis for mechanized UC security analyses for significantly more complex protocols.

Information ratio of an access structure is an important measure for efficiency of the best secret sharing scheme realizing it. The most common notion of secret sharing security is that of total (perfect) realization. Two well-known relaxations are the notions of statistical and quasi-total secret sharing. In this paper, we study the relation between different security notions. The most non-trivial and technical result of this paper is that quasi-total and total information ratios coincide for linear schemes. The proof is non-intuitive and uses tools from linear algebra in companion with a new relaxed security notion, called partial realization. We provide some intuition that why proving coincidence/separation between total and quasi-total information ratios for the class of abelian schemes is probably much more challenging.

We also present some additional results which shed further light on our understanding of different security notions. In particular, one of our results, in combination with a recent result, shows that statistical and total security notions coincide for the class of group-homomorphic schemes, or maybe even a larger class.

Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set (known as a ring) of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. However, due to the complexity of RingCT they are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks.

As a solution to these problems, we present the first complete rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.