International Association
for Cryptologic Research

Ability to query and update over encrypted data is an essential feature to enable breach-resilient cyber-infrastructures. Statistical attacks on searchable encryption (SE) have demonstrated the importance of sealing information leakages in access patterns. In response to such attacks, Oblivious Random Access Machine (ORAM) has been proposed. However, the composition of ORAM and SE is extremely costly in client-server model, and this poses a critical barrier towards its practical adaptations. In this paper, we create a new hardware-supported privacy-enhancing platform called as Practical Oblivious Search and Update Platform (POSUP), which enables oblivious keyword search/update operations on very large datasets with a high efficiency. We harness Intel SGX to realize highly optimized oblivious data structures for oblivious search/update purposes. We implemented POSUP and evaluated its performance with Wikipedia dataset containing $\ge 2^{29}$ keyword-file pairs. Our implementation is highly efficient, where it takes 1ms to access a 3 KB block with Circuit-ORAM. Our experiments have shown that POSUP offers up to $70\times$ less end-to-end delay and $100\times$ reduced bandwidth consumption, compared with the traditional ORAM-SE composition without secure hardware. POSUP is also at least $10\times$ faster for up to 99.5% fraction of keywords to be searched, compared with existing Intel SGX-assisted search platforms.

We present a very simple universally verifiable MPC protocol. The first component is a threshold somewhat homomorphic cryptosystem that permits an arbitrary number of additions (in the source group), followed by a single multiplication, followed by an arbitrary number of additions in the target group. The second component is a black-box construction of universally verifiable distributed encryption switching between any public key encryption schemes supporting shared setup and key generation phases, as long as the schemes satisfy some natural additive-homomorphic properties. This allows us to switch back from the target group to the source group, and hence perform an arbitrary number of multiplications. The key generation algorithm of our prototypical cryptosystem, which is based upon concurrent verifiable secret sharing, permits robust re-construction of powers of a shared secret. We demonstrate the scalability of distribution switching as a viable approach to secure vote tallying by implementing a private verifiable form of Instant Runoff Voting on real Australian election data comprising 40,000 votes.

Secure search is the problem of securely retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL ``SELECT...WHERE...'' queries, but where the database and the query are encrypted. Secure search has been the leading example for practical applications of Fully Homomorphic Encryption (FHE) since Gentry's seminal work in 2009, attaining the desired properties of a single-round low-communication protocol with semantic security for database and query (even during search). Nevertheless, the wide belief was that the high computational overhead of current FHE candidates is too prohibitive in practice for secure search solutions (except for the restricted case of searching for a uniquely identified record as in SQL UNIQUE constrain and Private Information Retrieval). This is due to the high degree in existing solutions that is proportional at least to the number of database records m.

We present the first algorithm for secure search that is realized by a polynomial of logarithmic degree (log m)^c for a small constant c>0. We implemented our algorithm in an open source library based on HElib, and ran experiments on Amazon's EC2 cloud with up to 100 processors. Our experiments show that we can securely search to retrieve database records in a rate of searching in millions of database records in less than an hour on a single machine.

We achieve our result by: (1) Designing a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative real numbers; this sketch may be of independent interest. (2) Suggesting a multi-ring evaluation of FHE -- instead of a single ring as in prior works -- and leveraging this to achieve an exponential reduction in the degree.

At the Quantum Cryptography Group, University of Tartu, we have two open postdoc positions on Verification of Quantum Cryptography.

We are starting a project in which we will develop methods for the verification of proofs in quantum cryptography. Similar to what the EasyCrypt tool does in classical cryptography. The scope of the project covers everything from the logical foundations, through the development of tools, to the verification of real quantum protocols.

The ideal candidate would have experience in:

• Semantics

• Theorem proving

• Verification of classical cryptography

• Quantum cryptography

• Quantum computation / communication

Of course, expertise in all those areas is very rare, so candidates who are strong in some of those areas and are interested in the others are encouraged to apply!

Please contact Dominique Unruh if you have more questions about the project, the required background, Estonia, the position itself, or the application process.

The salary range is 30000-36000 Euro per year (depending on experience), which is highly competitive in Estonia due to low costs of living and low income tax rate (20%), pension contributions and health insurance are covered by the employer.

The position is for three years, as soon as possible till August 31, 2020. The starting date and duration can be negotiated (in both directions).

To apply, please send the following documents to unruh (at) ut.ee:

• Curriculum vitae (please explain your scientific background)

• List of publications

• Research plan (i.e., how do you think you could contribute to the topic)

• At least two letters of reference (please ask for the letters to be sent directly to us)

• Phd degree

Closing date for applications: 31 March 2018

Contact: Dominique Unruh (unruh (at) ut.ee)

More information: https://crypto.cs.ut.ee/index.php/Main/PostdocInVerificationOfQuantumCryptography

NTNU Applied Cryptology Lab (https://www.ntnu.edu/iik/nacl-lab)

seek to host new ERCIM postdoctoral researchers that can contribute to our research activities. In particular, we are seeking candidates working within the area of real-world cryptographic protocol problems applied to wireless and mobile technologies, including interests for experimental open-source software-defined radio.

We refer you to the general Call for ERCIM Post-Doc Fellowship, with deadline 30 April 2018. You apply at the web site https://fellowship.ercim.eu/ and indicate NTNU as your preferred host institution. Contract extension opportunities with NTNU may be sought.

Closing date for applications: 30 April 2018

Contact: Professor Stig F. Mjølsnes, Dep.Information Security and Communications, for further inquiries. sfm(at)ntnu.no

More information: https://fellowship.ercim.eu/

Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. Accepted applicants will receive competitive scholarships including tuition waiver, housing, monthly stipend, computer, travel support, etc.

• For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit

  https://gsse.ku.edu.tr/en/admissions/application-requirements/

  All applications must be completed online. Deadline is 1 June 2018.

• For summer research opportunities (at both undergraduate and graduate level), visit

  http://kusrp.ku.edu.tr

  All applications must be completed online. Deadline is 30 March 2018.

• For postdoctoral researcher positions, contact Asst. Prof. Alptekin Küpçü directly, including full CV, sample publications, a research proposal, and 2-3 reference letters sent directly by the referees.

  http://home.ku.edu.tr/~akupcu

  Dates are flexible.

Applications with missing documents will not be considered.

Closing date for applications: 1 June 2018

Contact: gsse (at) ku.edu.tr

More information: https://crypto.ku.edu.tr/join

Event date: 2 December to 6 December 2018
Submission deadline: 11 May 2018
Notification: 3 August 2018

HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of "packed" ciphertexts. An important operation (which is used in bootstrapping, as well as in other applications) is applying a known linear map to a vector of encrypted data. In this paper, we describe several algorithmic improvements that significantly speed up this operation: in our experiments, our new algorithms were 30-75 times faster than those currently implemented in HElib for typical parameters.

Our techniques also reduce the size of the large public evaluation key, often using 33%-50% less space than the previous HElib implementation. We also implemented a new tradeoff that enables a drastic reduction in size, maybe a 25x factor or more for some parameters, paying only a 2-4x factor in runtime (and giving up some parallelization opportunities).

Mounting deanonymization attacks on the unreachable Bitcoin nodes -- these nodes do not accept incoming connections -- residing behind the NAT is a challenging task. Such an attack was first given by Biryukov, Khovratovich and Pustogarov based on their observation that a node can be uniquely identified in a single session by their directly-connected neighbouring nodes (ACM CCS'15). However, the BKP15 attack is less effective across multiple sessions. To address this issue, Biryukov and Pustogarov later on devised a new strategy exploiting certain properties of address-cookies (IEEE S&P'15). Unfortunately, the BP15 attack is also rendered ineffective by the present modification to the Bitcoin client.

In this paper, we devise an efficient method to link the sessions of unreachable nodes, even if they connect to the Bitcoin network over the Tor. We achieve this using a new approach based on organizing the block-requests made by the nodes in a Bitcoin session graph. This attack also works against the modified Bitcoin client. We performed experiments on the Bitcoin main network, and were able to link consecutive sessions with a precision of 0.90 and a recall of 0.71. We also provide counter-measures to mitigate the attacks.

Accountable ring signature (ARS), introduced by Xu and Yung (CARDIS 2004), combines many useful properties of ring and group signatures. In particular, the signer in an ARS scheme has the flexibility of choosing an ad hoc group of users, and signing on their behalf (like a ring signature). Furthermore, the signer can designate an opener who may later reveal his identity, if required (like a group signature). In 2015, Bootle et al. (ESORICS 2015) formalized the notion and gave an efficient construction for ARS with signature-size logarithmic in the size of the ring. Their scheme is proven to be secure in the random oracle model. Recently, Russell et al. (ESORICS 2016) gave a construction with constant signature-size that is secure in the standard model. Their scheme is based on $q$-type assumptions ($q$-SDH).

In this paper, we give a new construction for ARS having the following properties: signature is constant-sized, secure in the standard model, and based on indistinguishability obfuscation iO and one-way functions. To the best of our knowledge, this is the first iO-based ARS scheme. Independent of this, our work can be viewed as a new application of puncturable programming and hidden sparse trigger techniques introduced by Sahai and Waters (STOC 2014) to design iO-based deniable encryption.

Distributed ledgers (e.g. blockchains) enable financial institutions to efficiently reconcile cross-organization transactions. For example, banks might use a distributed ledger as a settlement log for digital assets. Unfortunately, these ledgers are either entirely public to all participants, revealing sensitive strategy and trading information, or are private but do not support third-party auditing without revealing the contents of transactions to the auditor. Auditing and financial oversight are critical to proving institutions are complying with regulation.

This paper presents zkLedger, the first system to protect ledger participants' privacy and provide fast, provably correct auditing. Banks create digital asset transactions that are visible only to the organizations party to the transaction, but are publicly verifiable. An auditor sends queries to banks, for example "What is the outstanding amount of a certain digital asset on your balance sheet?" and gets a response and cryptographic assurance that the response is correct.

zkLedger has two important benefits over previous work. First, zkLedger provides fast, rich auditing with a new proof scheme using Schnorr-type non-interactive zero-knowledge proofs. Unlike zkSNARKs, our techniques do not require trusted setup and only rely on widely-used cryptographic assumptions. Second, zkLedger provides *completeness*; it uses a columnar ledger construction so that banks cannot hide transactions from the auditor, and participants can use rolling caches to produce and verify answers quickly.

We implement a distributed version of zkLedger that can produce provably-correct answers to auditor queries on a ledger with a hundred thousand transactions in less than 10 milliseconds.

Non-interactive zero-knowledge (NIZK) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Despite this, general purpose constructions of NIZK proof systems are only known under a rather limited set of assumptions that are either number-theoretic (and can be broken by a quantum computer) or are not sufficiently well understood, such as obfuscation. Thus, a basic question that has drawn much attention is whether it is possible to construct general-purpose NIZK proof systems based on the learning with errors (LWE) assumption.

Our main result is a reduction from constructing NIZK proof systems for all of NP based on LWE, to constructing a NIZK proof system for a particular computational problem on lattices, namely a decisional variant of the Bounded Distance Decoding (BDD) problem. That is, we show that assuming LWE, every language L in NP has a NIZK proof system if (and only if) the decisional BDD problem has a NIZK proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008).

To construct our NIZK proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling (POCS), which we believe to be of independent interest. This notion extends the idea of oblivious ciphertext sampling, which allows one to sample ciphertexts without knowing the underlying plaintext. Specifically, we augment the oblivious ciphertext sampler with access to an (untrusted) prover to help it accomplish this task. We show that the existence of encryption schemes with a POCS procedure, as well as some additional natural requirements, suffices for obtaining NIZK proofs for NP. We further show that such encryption schemes can be instantiated based on LWE, assuming the existence of a NIZK proof system for the decisional BDD problem.

Existing proof-of-work (PoW) cryptocurrencies cannot tolerate attackers controlling more than 50% of the network's computing power at any time, but assume that such a condition happening is "unlikely". However, recent attack sophistication, e.g., where attackers can rent mining capacity to obtain a majority of computing power temporarily (flash attacks), render this assumption unrealistic.

This paper proposes RepuCoin, the first system to provide guarantees even when more than 50% of the system's computing power is temporarily dominated by an attacker. RepuCoin defines a miner's power by its reputation as a function integrated over the entire blockchain, rather than through its sheer computing power which can be obtained relatively quickly and temporarily. As an example, after a single year of operation, RepuCoin can tolerate attacks compromising 51% of the network's computing resources, even if such power stays maliciously seized for almost a whole year.

Moreover, RepuCoin provides better resilience to known attacks, compared to existing PoW systems, while achieving a high throughput of 10000 transactions per second.

This work presents an improved hashing-based algorithm for Private Set Intersection (PSI) in the honest-but-curious setting. The protocol is generic, modular and provides both asymptotic and concrete efficiency improvements over eisting PSI protocols.

If each player has $m$ elements, our scheme requires only $O(m \lambda)$ communication between the parties, where $\lambda$ is a security parameter. This is the first protocol that to achieve PSI using only asymptotically linear communication under standard cryptographic assumptions and without Random Oracles. Our protocol also provides 10-15\% reduction in communication costs under real-world parameter choices.

Our protocol builds on the hashing-based PSI protocol of Pinkas et al. (USENIX 2014, USENIX 2015), but we replace one of the sub-protocols (handling the cuckoo ``stash'') with a special-purpose PSI protocol that is optimized for comparing sets of unbalanced size. This brings the asymptotic communication complexity of the overall protocol down from $\omega(\lambda m)$ to $O(m\lambda)$, and provides concrete performance improvements over the most efficient existing PSI protocols.

Our protocol is simple, generic and benefits from the permutation-hashing optimizations of Pinkas et al. (USENIX 2015) and the Batched, Relaxed Oblivious Pseudo Random Functions of Kolesnikov (CCS 2016).

We consider the reduction loss of security reductions for non-interactive key exchange (NIKE) schemes. Currently, no tightly secure NIKE schemes exist, and in fact Bader et al. (EUROCRYPT 2016) provide a lower bound (of O(n^2), where n is the number of parties an adversary interacts with) on the reduction loss for a large class of NIKE schemes.

We offer two results: the first ``somewhat tight'' NIKE scheme (with a reduction loss of n/2) that circumvents the lower bound of Bader et al., but is of course still far from tightly secure. Second, we provide a generalization of Bader et al.'s lower bound to a larger class of NIKE schemes (that also covers our NIKE scheme), with an adapted lower bound of n/2 on the reduction loss. Hence, in that sense, the reduction for our NIKE scheme is optimal.

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