International Association
for Cryptologic Research

We present eclipse attacks on Ethereum nodes that exploit the peer-to-peer network used for neighbor discovery. Our attacks can be launched using only two hosts, each with a single IP address. Our eclipse attacker monopolizes all of the victim's incoming and outgoing connections, thus isolating the victim from the rest of its peers in the network. The attacker can then filter the victim's view of the blockchain, or co-opt the victim's computing power as part of more sophisticated attacks. We argue that these eclipse-attack vulnerabilities result from Ethereum's adoption of the Kademlia peer-to-peer protocol, and present countermeasures that both harden the network against eclipse attacks and cause it to behave differently from the traditional Kademlia protocol. Several of our countermeasures have been incorporated in the Ethereum geth 1.8 client released on February 14, 2018.

In the problem of byzantine agreement (BA), a set of n parties wishes to agree on a value v by jointly running a distributed protocol. The protocol is deemed secure if it achieves this goal in spite of a malicious adversary that corrupts a certain fraction of the parties and can make them behave in arbitrarily malicious ways. Since its first formalization by Lamport et al. (TOPLAS `82), the problem of BA has been extensively studied in the literature under many different assumptions. One common way to classify protocols for BA is by their synchrony and network assumptions. For example, some protocols offer resilience against up to a one-half fraction of corrupted parties by assuming a synchronized, but possibly slow network, in which parties share a global clock and messages are guaranteed to arrive after a given time D. By comparison, other protocols achieve much higher efficiency and work without these assumptions, but can tolerate only a one-third fraction of corrupted parties. A natural question is whether it is possible to combine protocols from these two regimes to achieve the ``best of both worlds'': protocols that are both efficient and robust. In this work, we answer this question in the affirmative. Concretely, we make the following contributions:

* We give the first generic compilers that combine BA protocols under different network and synchrony assumptions and preserve both the efficiency and robustness of their building blocks. Our constructions are simple and rely solely on a secure signature scheme.

* We prove that our constructions achieve optimal corruption bounds.

* Finally, we give the first efficient protocol for (binary) asynchronous byzantine agreement (ABA) which tolerates adaptive corruptions and matches the communication complexity of the best protocols in the static case.

In this paper, we propose P2KMV, a novel privacy-preserving counting sketch, based on the k minimum values algorithm. With P2KMV, we offer a versatile privacy-enhanced technology for obtaining statistics, following the principle of data minimization, and aiming for the sweet spot between privacy, accuracy, and computational efficiency. As our main contribution, we develop methods to perform set operations, which facilitate cardinality estimates under strong privacy requirements. Most notably, we propose an efficient, privacy-preserving algorithm to estimate the set intersection cardinality. P2KMV provides plausible deniability for all data items contained in the sketch. We discuss the algorithm's privacy guarantees as well as the accuracy of the obtained estimates. An experimental evaluation confirms our analytical expectations and provides insights regarding parameter choices.

At the Faculty of Engineering and Science, Department of Mathematical Sciences, a number of positions as Assistant Professor in algebraic coding theory and code-based cryptography are open for appointment from 1st of August 2018. Later appointments will be considered. The positions are for a period of 3 years.

More information, at http://www.stillinger.aau.dk/vis-stilling/?vacancy=963578.

The applications are only to be submitted online at http://www.stillinger.aau.dk/vis-stilling/?vacancy=963578 by using the \"Apply online\" button at the end of the page.

Closing date for applications: 2 April 2018

Contact: You may obtain further information from Head of Department Søren Højsgaard, phone: +45 9940 8801, e-mail: sorenh (at) math.aau.dk.

More information: http://www.stillinger.aau.dk/vis-stilling/?vacancy=963578

Event date: 1 March to 15 June 2018
Submission deadline: 15 June 2018

Event date: 16 April to 20 April 2018
Submission deadline: 12 March 2018
Notification: 15 March 2018

Event date: 28 December to 30 December 2018
Submission deadline: 25 June 2018
Notification: 6 August 2018

Logistic regression is a popular technique used in machine learning to construct classification models. Since the construction of such models is based on computing with large datasets, it is an appealing idea to outsource this computation to a cloud service. The privacy-sensitive nature of the input data requires appropriate privacy preserving measures before outsourcing it. Homomorphic encryption enables one to compute on encrypted data directly, without decryption, and can be used to mitigate the privacy concerns raised by using a cloud service. In this paper, we propose an algorithm (and its implementation) to train a logistic regression model on a homomorphically encrypted dataset. The core of our algorithm consists of a new iterative method that can be seen as a simplified form of the fixed Hessian method, but with a much lower multiplicative complexity. We test the new method on two interesting real life applications: the first application is in medicine and constructs a model to predict the probability for a patient to have cancer, given genomic data as input; the second application is in finance and the model predicts the probability of a credit card transaction to be fraudulent. The method produces accurate results for both applications, comparable to running standard algorithms on plaintext data. This article introduces a new simple iterative algorithm to train a logistic regression model that is tailored to be applied on a homomorphically encrypted dataset. This algorithm can be used as a privacy-preserving technique to build a binary classification model and can be applied in a wide range of problems that can be modelled with logistic regression. Our implementation results show that our method can handle the large datasets used in logistic regression training.

A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) is known as fully homomorphic encryption (FHE) and is very powerful. Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on ciphertexts of their inputs to produce a ciphertext of their output. Since such a program never decrypts its input, it can be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In previous work I proposed the fully homomorphic public-key encryption scheme with the size of ciphertext which is not small enough. In this paper the size of ciphertext is one-eighth of the size in the previously proposed scheme. Because proposed scheme adopts the medium text with zero norm, it is immune from the the “p and -p attack”. As the proposed scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree, it is immune from the Gröbner basis attack, the differential attack, rank attack and so on.

Quantum entanglement is of great importance to quantum cryptography and computation. So far, all experimental demonstrations of entanglement are designed to check Bell's inequality which is based on Bell's formulation for EPR paradox. In this note, we specify the assumptions needed in Bell's mathematical argument. We then show the contradictions among these assumptions. As a result, it becomes very easy to see that Bell's inequality is trivial.

In this paper, we introduce Saber, a package of cryptographic primitives whose security relies on the hardness of the Module Learning With Rounding problem (Mod-LWR). We first describe a secure Diffie-Hellman type key exchange protocol, which is then transformed into an IND-CPA encryption scheme and finally into an IND-CCA secure key encapsulation mechanism using a post-quantum version of the Fujisaki-Okamoto transform. The design goals of this package were simplicity, efficiency and flexibility resulting in the following choices: all integer moduli are powers of $2$ avoiding modular reduction and rejection sampling entirely; the use of LWR halves the amount of randomness required compared to LWE-based schemes and reduces bandwidth; the module structure provides flexibility by reusing one core component for multiple security levels. A constant-time AVX2 optimized software implementation of the KEM with parameters providing more than 128 bits of post-quantum security, requires only 101K, 125K and 129K cycles for key generation, encapsulation and decapsulation respectively on a Dell laptop with an Intel i7-Haswell processor.

NTRUEncrypt is one of the most promising candidates for quantum-safe cryptography. In this paper, we focus on the NTRU743 paramter set. We give a report on all known attacks against this parameter set and show that it delivers 256 bits of security against classical attackers and 128 bits of security against quantum attackers. We then present a parameter-dependent optimization using a tailored hierarchy of multipli- cation algorithms as well as the Intel AVX2 instructions, and show that this optimization is constant-time. Our implementation is two to three times faster than the reference implementation of NTRUEncrypt.

While non-interactive zero-knowledge (NIZK) proofs require trusted parameters, Groth, Ostrovsky and Sahai constructed non-interactive witness-indistinguishable (NIWI) proofs without any setup; they called their scheme a non-interactive zap. More recently, Bellare, Fuchsbauer and Scafuro investigated the security of NIZK in the face of parameter subversion and observe that NI zaps provide subversion-resistant soundness and WI. Arguments of knowledge prove that not only the statement is true, but also that the prover knows a witness for it, which is essential for anonymous identification. We present the first NIWI argument of knowledge without parameters, i.e., a NI zap of knowledge. Consequently, our scheme is also the first subversion-resistant knowledge-sound proof system, a notion recently proposed by Fuchsbauer.

It is well-known that non-comparison-based techniques can allow us to sort $n$ elements in $o(n \log n)$ time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort $n$ elements from the domain $[1..2^k]$ with $o(k n \log n)$ boolean gates. We consider weakened forms of this question: first, we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length; and second, we explore Oblivious RAMs and probabilistic circuit families, i.e., computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort $o(\log n)$-bit keys in $o(n \log n)$ time or $o(k n \log n)$ circuit complexity where $n$ is the input length. We also show that in the balls-and-bins model of sorting where each key may carry an opaque ball that can only be moved around atomically but cannot be computed upon, our result achieves optimality, in that any oblivious algorithm or probabilistic circuit family that sorts $n$ balls each with a $\Omega(\log n)$-bit key must incur at least $\Omega(n \log n)$ atomic movement operations on balls. We extend our result to support the case when the keys are chosen from a large space but the number of distinct keys is small.

Finally, we optimize the IO efficiency of our oblivious algorithms for RAMs --- we show that even the $1$-bit special case of our algorithm can solve open questions regarding whether there exist oblivious algorithms for tight compaction and selection in linear IO.

The random-permutation model (RPM) and the ideal-cipher model (ICM) are idealized models that offer a simple and intuitive way to assess the conjectured standard-model security of many important symmetric-key and hash-function constructions. Similarly, the generic-group model (GGM) captures generic algorithms against assumptions in cyclic groups by modeling encodings of group elements as random injections and allows to derive simple bounds on the advantage of such algorithms.

Unfortunately, both well-known attacks, e.g., based on rainbow tables (Hellman, IEEE Transactions on Information Theory '80), and more recent ones, e.g., against the discrete-logarithm problem (Corrigan-Gibbs and Kogan, EUROCRYPT '18), suggest that the concrete security bounds one obtains from such idealized proofs are often completely inaccurate if one considers non-uniform or preprocessing attacks in the standard model. To remedy this situation, this work

1) defines the auxiliary-input (AI) RPM/ICM/GGM, which capture both non-uniform and preprocessing attacks by allowing an attacker to leak an arbitrary (bounded-output) function of the oracle's function table;

2) derives the first non-uniform bounds for a number of important practical applications in the AI-RPM/ICM, including constructions based on the Merkle-Damgard and sponge paradigms, which underly the SHA hashing standards, and for AI-RPM/ICM applications with computational security; and

3) using simpler proofs, recovers the AI-GGM security bounds obtained by Corrigan-Gibbs and Kogan against preprocessing attackers, for a number of assumptions related to cyclic groups, such as discrete logarithms and Diffie-Hellman problems, and provides new bounds for two assumptions.

An important step in obtaining these results is to port the tools used in recent work by Coretti et al. (EUROCRYPT '18) from the ROM to the RPM/ICM/GGM, resulting in very powerful and easy-to-use tools for proving security bounds against non-uniform and preprocessing attacks.

Many voting systems rely on art, rather than science, to ensure that votes are freely made, with equal influence. Such systems build upon creativity and skill, rather than scientific foundations. These systems are routinely broken in ways that compromise free-choice or permit undue influence. Breaks can be avoided by proving that voting systems satisfy formal notions of voters voting freely and of detecting undue influence. This manuscript provides a detailed technical introduction to a definition of ballot secrecy by Smyth that formalises the former notion and a definition of verifiability by Smyth, Frink & Clarkson that formalises the latter. The definitions are presented in the computational model of cryptography: Ballot secrecy is expressed as the inability to distinguish between an instance of the voting system in which voters cast some votes, from another instance in which the voters cast a permutation of those votes. Verifiability decomposes into individual verifiability, which is expressed as the inability to cause a collision between ballots, and universal verifiability, which is expressed as the inability to cause an incorrect election outcome to be accepted. The definitions are complimented with simple examples that demonstrate the essence of these properties and detailed proofs are constructed to show how secrecy and verifiability can be formally proved. Finally, the Helios and Helios Mixnet voting systems are presented as case studies to provide an understanding of state-of-the-art systems that are being used for binding elections.

We present a semantically secure somewhat homomorphic public-key cryptosystem working in sub-groups of $\mathbb{Z}_{n}^{*}$ of prime power order. Our scheme introduces a novel threshold homomorphic property, which we use to build a two-party protocol for secure integer comparison. In contrast to related work which encrypts and acts on each bit of the input separately, our protocol compares multiple input bits simultaneously within a single ciphertext. Compared to the related protocol of Damg\r{a}rd et al.~we present results showing this approach to be both several times faster in computation and lower in communication complexity.

Password-authenticated key exchange (PAKE) protocols allow users sharing a password to agree upon a high entropy secret. In this paper, a provably secure password-authenticated pro- tocol for group key establishment in the common reference string (CRS) model is presented. Our protocol is quite ecient, as regardless of the number of involved participants it can be imple- mented with only three communication rounds. We use a (by now classical) trick of Burmester and Desmedt for deriving group key exchange protocols using a two-party construction as main building block. In our case, the two party PAKE used as a base is a one-round protocol by Katz and Vaikuntanatan, which in turn builds upon a special kind of smooth projective hash functions (KV-SPHFs). As evidenced by Benhamouda et al., KV-SPHFs can be instantiated on Cramer-Shoup ciphertexts, thus yielding very ecient (and pairing free) constructions.

Event date: 24 September to 26 September 2018
Submission deadline: 30 April 2018
Notification: 18 June 2018

Event date: 19 August 2018
Submission deadline: 1 June 2018