International Association
for Cryptologic Research

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.

Event date: 2 September to 5 September 2019

Event date: 12 November to 15 November 2019
Submission deadline: 15 June 2019
Notification: 15 August 2019

Today server authentication is largely handled through Public Key Infrastructure (PKI) in both the private and the public sector. PKI is established as the defacto standard for Internet communication through the world wide web, and its usage in HTTPS, SSL/TLS (Web PKI). However, in its application to Internet of Things (IoT) devices, using Web PKI infrastructure for server authentication has several shortcomings, including issues with validity periods, identity, revocation practice, and governance. Recently, di erent approaches to decentralized PKI (DPKI) using Blockchain technology have been proposed, but so far have lacked practicality in their application to devices commonly used in IoT deployments. The approaches are too resource intensive for IoT devices to handle and even the “light client” protocols have not been resource e cient enough to be practical. We present BlockQuick, a novel protocol for a super-light client, which features reading blockchain data securely from a remote client. BlockQuick requires less data for validation than existing approaches, like PoPoW or FlyClient, while also providing e ective means to protect against eclipse and MITM attacks on the network. BlockQuick clients have low kilobyte RAM requirements, which are optimal for IoT devices and applications with embedded MCUs.

A recent line of research has investigated a new profiling technique based on deep learning as an alternative to the well-known template attack. The advantage of this new profiling approach is twofold: $(1)$ the approximation of the information leakage by a multivariate Gaussian distribution is relaxed (leading to a more generic approach) and $(2)$ the pre-processing phases such as the traces realignment or the selection of the Points of Interest (PoI) are no longer mandatory, in some cases, to succeed the key recovery (leading to a less complex security evaluation roadmap). The related published works have demonstrated that Deep Learning based Side-Channel Attacks (DL-SCA) are very efficient when targeting cryptographic implementations protected with the common side-channel countermeasures such as masking, jitter and random delays insertion. In this paper, we assess the efficiency of this new profiling attack under different realistic and practical scenarios. First, we study the impact of the intrinsic characteristics of the manipulated data-set (\emph{i.e.} distance in time samples between the PoI, the dimensionality of the area of interest and the pre-processing of the data) on the robustness of the attack. We demonstrate that the deep learning techniques are sensitive to these parameters and we suggest some practical recommendations that can be followed to enhance the profiling and the key recovery phases. Second, we discuss the tolerance of DL-SCA with respect to a deviation from the idealized leakage models and provide a comparison with the well-known stochastic attack. Our results show that DL-SCA are still efficient in such a context. Then, we target a more complex masking scheme based on Shamir's secret sharing and prove that this new profiling approach is still performing well. Finally, we conduct a security evaluation of a batch of several combinations of side-channel protections using simulations and real traces captured on the ChipWhisperer board. The experimental results obtained confirm that DL-SCA are very efficient even when a cryptographic implementation combines several side-channel countermeasures.

An important characteristic of recent MPC protocols is an input independent preprocessing phase in which most computations are offloaded, which greatly reduces the execution overhead of the online phase where parties provide their inputs. For a very efficient evaluation of arithmetic circuits in an information-theoretic online phase, the MPC protocols consume Beaver multiplication triples generated in the preprocessing phase. Triple generation is generally the most expensive part of the protocol, and improving its efficiency is the aim of our work. We specifically focus on the semi-honest model and the two-party setting, for which an Oblivious Transfer (OT)-based protocol is the currently best solution. To improve upon this method, we propose a Somewhat Homomorphic Encryption-based protocol. Our experiments show that our protocol is more scalable, and it outperforms the OT-based protocol in most cases, improving communication by up to 6.9x and runtime by up to 3.6x for 64-bit triple generation.

A group-characterizable random variable [Chan and Yeung 2002] is induced by a joint distribution on the (left) cosets of some subgroups of a main group. A homomorphic secret sharing scheme [Benaloh 1986] is called group-homomorphic if the secret and share spaces are groups. We study the connection between these two notions. It is easy to see that a group-characterizable secret sharing with \emph{normal} subgroups in the main group is group-homomorphic. In this paper, we show that the converse holds true as well. A non-trivial consequence of this result is that total and statistical secret sharing coincide for group-homomorphic schemes.

We present a necessary and sufficient condition for a joint distribution to be inherently group-characterizable (i.e., up to a relabeling of the elements of the support). Then, we show that group-homomorphic secret sharing schemes satisfy the sufficient condition and, consequently, they are inherently group-characterizable. We strengthen our result by showing that they indeed have a group characterization with normal subgroups in the main group.

Group-characterizable random variables are known to be quasi-uniform (namely, all marginal distributions are uniform). As an additional contribution, we present an example of a quasi-uniform random variable which is not inherently group-characterizable.

Unlike linear secret sharing, very little is known about abelian secret sharing. In this paper, we present two results on abelian secret sharing. First, we show that the information ratio of access structures (or more generally access functions) remain invariant for the class of abelian schemes with respect to duality. Then, we prove that abelian secret sharing schemes are superior to the linear ones.

New techniques and insight are used to achieve both results. Our result on abelian duality is proved using the notion of Pontryagin duality. The intuition behind the usefulness of this tool is to work with an equivalent definition of linear secret sharing, which is less prevalent in the literature, to make it possible to extend the result on linear duality to abelian duality.

We develop a new method for proving lower bound on the linear information ratio of access structures that can work not only for general linear secret sharing but also for linear schemes on finite fields with a specific characteristic. Unlike the common lower bound techniques, which are usually either based on rank/information inequalities or based on counting/combinatorial-algebraic arguments, our method is linear algebraic in essence. We apply our method to the Fano and non-Fano access structures for the characteristics on which they are not ideal.

We then show in a straightforward way that for their union---a well-known 12-participant access structure---the abelian schemes are superior to the linear ones.