International Association
for Cryptologic Research

Blockchains have become a buzzword and many blockchain proponents believe that smart contract is a panacea to redefine the digital economy. The community has a misconception that any kind of contracts could be implemented as a blockchain smart contract. There is no doubt that Turing-complete scripting languages in blockchain techniques such as Ethereum can be used to draft many important smart contracts. However, digital economy is much more than Turing-complete smart contracts. Many protocols/contracts in our daily life could not be implemented using Turing- complete smart contracts. As an example, we formulate an Obama-Trump contract and show that this kind of contract could not be implemented using blockchain smart contract techniques. It is straightforward to observe that many contracts in our daily life could be described in terms of an Obama-Trump contract. As a background discussion, we also give a comprehensive review of historical cryptographic currency techniques, bitcoin smart contract techniques, and Turing-complete smart contract techniques in modern blockchains.

While businesses shift their databases to the cloud, they continue to depend on them to operate correctly. Alarmingly, cloud services constantly face threats from exploits in the privileged computing layers (e.g. OS, Hypervisor) and attacks from rogue datacenter administrators, which tamper with the database's storage and cause it to produce incorrect results. Although integrity verification of outsourced storage and file systems is a well-studied problem, prior techniques impose prohibitive overheads (up to 30x in throughput) and place additional responsibility on clients.

We present VeritasDB, a key-value store that guarantees data integrity to the client in the presence of exploits or implementation bugs in the database server. VeritasDB is implemented as a network proxy that mediates communication between the unmodified client(s) and the unmodified database server, which can be any off-the-shelf database engine (e.g., Redis, RocksDB, Apache Cassandra). The proxy transforms each client request before forwarding it to the server and checks the correctness of the server's response before forwarding it to the client.

To ensure the proxy is trusted, we use the protections of modern trusted hardware platforms, such as Intel SGX, to host the proxy's code and trusted state, thus completely eliminating trust on the cloud provider. To maintain high performance in VeritasDB while scaling to large databases, we design an authenticated Merkle B+-tree that leverages features of SGX (modest amount of protected RAM, direct access to large unprotected RAM, and CPU parallelism) to implement several novel optimizations based on caching, concurrency, and compression. On standard YCSB and Visa transaction workloads, we observe an average overhead of 2.8x in throughput and 2.5x in latency, compared to the (insecure) system with no integrity checks --- using CPU parallelism, we bring the throughput overhead down to 1.05x.

We put forth a new notion of distributed public key functional encryption. In such a functional encryption scheme, the secret key for a function $f$ will be split into shares $sk_i^f$. Given a ciphertext $ct$ that encrypts a message $x$, a secret key share $sk_i^f$, one can evaluate and obtain a shared value $y_i$. Adding all the shares up can recover the actual value of $f(x)$, while partial shares reveal nothing about the plaintext. More importantly, this new model allows us to establish {\em function privacy} which was not possible in the setting of regular public key functional encryption. We formalize such notion and construct such a scheme from any public key functional encryption scheme together with learning with error assumption.

We then consider the problem of hosting services in the untrusted cloud. Boneh, Gupta, Mironov, and Sahai (Eurocrypt 2014) first studied such application and gave a construction based on indistinguishability obfuscation. Their construction had the restriction that the number of corrupted clients has to be bounded and known. They left an open problem how to remove such restriction. We resolve this problem by applying our function private (distributed) public key functional encryption to the setting of hosting service in multiple clouds. Furthermore, our construction provides a much simpler and more flexible paradigm which is of both conceptual and practical interests. Along the way, we strengthen and simplify the security notions of the underlying primitives, including function secret sharing.

Deutsch-Jozsa quantum algorithm is of great importance to quantum computation. It directly inspired Shor's factoring algorithm. In this note, we remark that Deutsch-Jozsa algorithm has confused two unitary transformations: one is performed on a pure state, the other is performed on a superposition. In the past decades, no constructive specification on the essential unitary operator performed on a superposition has been found. Thus, we think the algorithm needs more specifications so as to facilitate the construction of the wanted quantum oracle.

We describe a general attack on proof-of-stake (PoS) blockchains without checkpointing. Our attack leverages transaction fees, the ability to treat transactions "out of context," and the standard longest chain rule to completely dominate a blockchain. The attack grows in power with the number of honest transactions and the stake held by the adversary, and can be launched by an adversary controlling any constant fraction of the stake.

With the present statistical profile of blockchain protocols, the attack can be launched given a few years of prior blockchain operation; hence it is within the realm of feasibility for PoS protocols. Most importantly, it demonstrates how closely transaction fees and rewards are coupled with the security properties of PoS protocols. More broadly, our attack must be reflected and countered in any future PoS design that avoids checkpointing, as well as any effort to remove checkpointing from existing protocols. We describe several mechanisms for protecting against the attack that include context-sensitivity of transactions and chain density statistics.

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.