International Association
for Cryptologic Research

Recent rapid progress in fully homomorphic encryption (FHE) and somewhat homomorphic encryption (SHE) has catalyzed renewed efforts to develop efficient privacy preserving protocols. Several works have already appeared in the literature that provide solutions to these problems by employing FHE or SHE techniques. In this work, we focus on a natural application where privacy is a major concern: web search. An estimated 5 billion web queries are processed by the world's leading search engines each day. It is no surprise, then, that privacy-preserving web search was proposed as the paragon FHE application in Gentry's seminal FHE paper. Indeed, numerous proposals have emerged in the intervening years that attack various privatized search problems over encrypted user data, e.g. private information retrieval (PIR). Yet, there is no known work that focuses on implementing a completely blind web search engine using an FHE/SHE construction. In this work, we focus first on single keyword queries with exact matches, aiming toward real-world viability. We then discuss multiple-keyword searches and tackle a number of issues currently hindering practical implementation, such as communication and computational efficiency.

An $\alpha$-fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than $\alpha$. Cleve [STOC 1986] has shown that if half of the parties can be corrupted, then, no $r$-round coin-tossing protocol is $o(1/r)$-fair. For over two decades the best known $m$-party protocols, tolerating up to $t\geq m/2$ corrupted parties, were only $O(t/\sqrt{r})$-fair. In a surprising result, Moran, Naor, and Segev [TCC 2009] constructed an $r$-round two-party $O(1/r)$-fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel, Omri, and Orlov [Crypto 2010] extended the results of Moran et al.~to the {\em multiparty setting} where strictly fewer than 2/3 of the parties are corrupted. They constructed a $2^{2^k}/r$-fair $r$-round $m$-party protocol, tolerating up to $t=\frac{m+k}{2}$ corrupted parties.

Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $O(\log^3(r)/r)$-fair (almost optimal) three-party coin-tossing protocol. Their work brings forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $t=2m/3$, where $m>3$) were $\theta(1/\sqrt{r})$-fair. We construct an $O(\log^3(r)/r)$-fair $m$-party coin-tossing protocol, tolerating up to $t$ corrupted parties, whenever $m$ is constant and $t<3m/4$.

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semi-honest adversaries. In an OPRF protocol a receiver has an input $r$; the sender gets output $s$ and the receiver gets output $F(s,r)$, where $F$ is a pseudorandom function and $s$ is a random seed. Our protocol uses a novel adaptation of 1-out-of-2 OT-extension protocols, and is particularly efficient when used to generate a large batch of OPRF instances. The cost to realize $m$ OPRF instances is roughly the cost to realize $3.5 m$ instances of standard 1-out-of-2 OTs (using state-of-the-art OT extension).

We explore in detail our protocol's application to semi-honest secure private set intersection (PSI). The fastest state-of-the-art PSI protocol (Pinkas et al., Usenix 2015) is based on efficient OT extension. We observe that our OPRF can be used to remove their PSI protocol's dependence on the bit-length of the parties' items. We implemented both PSI protocol variants and found ours to be 3.1--3.6$\times$ faster than Pinkas et al.\ for PSI of 128-bit strings and sufficiently large sets. Concretely, ours requires only 3.8 seconds to securely compute the intersection of $2^{20}$-size sets, regardless of the bitlength of the items. For very large sets, our protocol is only $4.3\times$ slower than the {\em insecure} na\"{\i}ve hashing approach for PSI.

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around $2^{32}$ blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet.

In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

This paper proposes a decentralised and privacy-preserving local electricity trading market. The proposed market employs a bidding protocol based upon secure multiparty computations and allows users to trade their excess electricity among themselves. The bid selection and calculation of the clearance price at which the electricity is traded are performed by the market in a decentralised and privacy-preserving manner. We implemented the market in C++ and tested its performance with realistic data sets. Our simulation results show that the market tasks can be performed for 2500 bids in less than five minutes in the online phase, showing its feasibility for a typical electricity trading period of, for example, 30 minutes.

Greetings from the IACR! It is now a few days since Crypto 2016 wrapped up. For those of you who weren't able to make it to the membership meeting, here are some of the important things you missed. You can see IACR President Christian Cachin's complete slides from the membership meeting at https://www.iacr.org/docs/minutes/minutes.html.

2016 IACR Election

The 2016 IACR election is being held to fill all four IACR Officer positions (president, vice president, treasurer, secretary) and three of nine IACR Director positions. Nominations are due by September 24, 2016. Information about the vacant positions and a nomination form can be found at https://www.iacr.org/elections/2016/.

2018 IACR Distinguished Lecture

The board has selected Mitsuru Matsui to give the 2018 IACR Distinguished Lecture. The lecture will be delivered at Asiacrypt 2018 (December) in Brisbane, Australia. Information about the IACR Distinguished Lectures can be found at https://www.iacr.org/publications/dl/.

New Cryptology ePrint Archive editor

Nigel Smart has stepped down as co-editor of ePrint. We thank him for his dedicated service to the community. He is replaced by Tancrède Lepoint, who joins Alexandra Boldyreva as the current ePrint co-editors.

Future Events

Two upcoming IACR events have been recently approved by the board:

• CHES 2017 will be in Taipei, Taiwan (September 26-28). Bo-Yin Yang & Chen-Mou Cheng will be general chairs, while Naofumi Homma & Wieland Fischer will be program co-chairs.
• TCC 2017 will be at Johns Hopkins University in Baltimore, USA (November 13-15). Abhishek Jain will be general chair, while Yael Kalai & Leonid Reyzin will be program co-chairs.

Upcoming deadlines:

• August 31 (extended!): Propose an IACR Cryptology School for the next cycle. See http://iacr.org/schools/propose.php.
• September 1: Submit to FSE 2017 / issue 2 of Transactions on Symmetric Cryptology. See http://www.nuee.nagoya-u.ac.jp/labs/tiwata/fse2017/.
• September 2 (extended!): Propose an event to be affiliated with Eurocrypt and EuroS&P in Paris. See https://eurocrypt2017.di.ens.fr/cfw.html.
• September 24: Nominate for the IACR election. See https://www.iacr.org/elections/2016/.
• October 1: Eurocrypt submission deadline. See https://eurocrypt2017.di.ens.fr/cfp.html.
• October 6: PKC submission deadline. See http://www.iacr.org/workshops/pkc2017/cfp.html.

The Faculty for Computer Science and Mathematics seeks applications for a Junior Professor position in Hardware-Oriented Security. The professor is expected to work on scientific problems at the interface of IT security and Computer Engineering. Possible research foci include hardware-supported authentication, security properties, and physical cryptography. We are looking for an internationally visible candidate with a strong publication record, interest in joint research within the Faculty, and potential to attract third-party funding. The candidate is expected to strengthen the University-wide focus on IT security and to be open for interdisciplinary research within the Institute for IT Security and Security Law.

The advertised position does not include a tenure track option. The first appointment is for a 3-years period, with an option of an extension for another 3 years upon successful evaluation.

The position is associated with a teaching load of 5 hours per week before evaluation (within the first 3 years) and 7 hours per week after evaluation. Teaching programs in Passau are offered in English and German languages. German language skills sufficient for teaching are desired, but exceptional candidates with a credible commitment to achieve proficiency within the duration of the appointment will be considered.

Please consult the official (German-language) announcement for more details on the position and how to apply. Note that only the official announcement on the University web page is legally binding.

http://www.uni-passau.de/fileadmin/dokumente/beschaeftigte/Stellenangebote/2016-W_1-Juniorprofessur_Hardware_Oriented_Security.pdf

Closing date for applications: 15 September 2016

Contact: Prof. Ilia Polian

More information: http://www.uni-passau.de/universitaet/stellenangebote/

We are a fast-growing cyber-security consulting company based in UAE. With a team of 250+ experts from around the world, we provide services and solutions that are changing the cyber security landscape. Working with us means collaborating with enthusiastic professionals who are passionate about technology and creating next-gen cyber security solutions.

We are looking for an expert who has good familiarity with standards (SPs, CAVP, FIPS 140-2, CMVP, etc.). The incumbent must have expertise in design of end-to-end secure protocols with PFS and validation using mathematical proofs and test vectors. Expertise in existing network protocols (e.g., TLS, OpenSSL) and knowledge of inherent vulnerabilities, cryptographic security analysis and security proofs covering: Symmetric crypto and Modes of Operation (state of art block ciphers , Rijndael variants, stream ciphers, etc.), Public Key Crypto / PKI (RSA, ECC, ECDSA, ECDH, etc.), Hashing Algorithms, Random Number Generation Algorithms, etc. Must have expertise in theoretical cryptanalysis techniques: Based on underlying mathematics of asymmetric ciphers (IF, DL, EC schemes)

We offer a tax-free package and an opportunity to live in an advanced city with easy access to the rest of the world.

For more information on the role and the organisation, please send your resume to itjobsuae16 (at) gmail (dot) com

Closing date for applications: 31 December 2016

Event date: 2 April to 6 April 2017
Submission deadline: 1 November 2016
Notification: 10 January 2017

We invite applications for a PhD position in cryptocurrencies and their applications. The successful candidate will join Dr. Yuliang Zheng and Dr. Jason Teutsch\'s research group in the Department of Computer and Information Sciences at the University of Alabama, Birmingham (UAB).

We seek a student interested in advancing the security of Bitcoin and related distributed peer-to-peer systems, understanding the theoretical foundations of decentralized networks, and developing disruptive technologies. Work may include big data management, incentive structures and consensus protocols, smart contracts, financial services, Internet of Things, quantum algorithms, decentralized governance, certification, and other forms of distributed trust.

The successful candidate will receive a Graduate Assistanship package with a starting annual stipend of $19,500 plus health insurance benefits and tuition waiver. Birmingham and its surrounding area offers natural beauty and modest cost-of-living. Applicants should hold an undergraduate degree in computer science, mathematics, or a related field prior to commencement of study. Coding and analytic skills will be viewed favorably. Please see the website below for additional information, requirements, and application instructions.

https://cis.uab.edu/academics/graduates/doctoral-degree-program/graduate-program-prerequisites/

Indicate in your application materials your interest in this position.

Closing date for applications: 31 December 2016

Contact: Informal inquiries may be sent to either Dr. Zheng (http://cis.uab.edu/yzheng/) or Dr. Teutsch (http://people.cs.uchicago.edu/~teutsch/).

Event date: 18 September to 22 September 2017

The Department of Computer Science at the University of California invites applications for an Assistant Project Scientist to be part of the research team of Dr. Cetin Koc in the areas of analog electronics as applied to random number generators; chaotic circuits analysis and design techniques; design, analysis, and random number generators, cryptographic hardware design; reconfigurable hardware design.

Apply via the UCSB Recruit. The URL is given below.

Closing date for applications: 5 September 2016

Contact: Dr. Çetin Kaya Koç

koc (at) cs.ucsb.edu

http://koclab.cs.ucsb.edu

More information: https://recruit.ap.ucsb.edu/apply/JPF00802

Many practical lattice-based schemes are built upon the Ring-SIS or Ring-LWE problems, which are problems that are based on the presumed difficulty of finding low-weight solutions to linear equations over polynomial rings $Z_q[x]/\langle f(x) \rangle$. Our belief in the asymptotic computational hardness of these problems rests in part on the fact that there are reduction showing that solving them is as hard as finding short vectors in all lattices that correspond to ideals of the polynomial ring $Z[x]/\langle f(x) \rangle$. These reductions, however, do not give us an indication as to the effect that the polynomial $f(x)$, which defines the ring, has on the average-case or worst-case problems. \\

As of today, there haven't been any weaknesses found in Ring-SIS or Ring-LWE problems when one uses an $f(x)$ which leads to a meaningful worst-case to average-case reduction, but there have been some recent algorithms for related problems that heavily use the algebraic structures of the underlying rings. It is thus conceivable that some rings could give rise to more difficult instances of Ring-SIS and Ring-LWE than other rings. A more ideal scenario would therefore be if there would be an average-case problem, allowing for efficient cryptographic constructions, that is based on the hardness of finding short vectors in ideals of $Z[x]/\langle f(x)\rangle$ for \emph{every} $f(x)$.\\

In this work, we show that the above may actually be possible. We construct a digital signature scheme based (in the random oracle model) on a simple adaptation of the Ring-SIS problem which is as hard to break as worst-case problems in every $f(x)$ whose degree is bounded by the parameters of the scheme. Up to constant factors, our scheme is as efficient as the highly practical schemes that work over the ring $Z[x]/\langle x^n+1\rangle$.

All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014 and Lin, EUROCRYPT 2016), or polynomial families of assumptions on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014).

We present a new construction of IO, with a security reduction based on two assumptions: (a) a DDH-like assumption — called the joint-SXDH assumption — on constant degree graded en- codings, and (b) the existence of polynomial-stretch pseudorandom generators (PRG) in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose indistinguishability obfuscation.

We give attacks on Feistel-based format-preserving encryption (FPE) schemes that succeed in message recovery (not merely distinguishing scheme outputs from random) when the message space is small. For $4$-bit messages, the attacks fully recover the target message using $2^{21}$ examples for the FF3 NIST standard and $2^{25}$ examples for the FF1 NIST standard. The examples include only three messages per tweak, which is what makes the attacks non-trivial even though the total number of examples exceeds the size of the domain. The attacks are rigorously analyzed in a new definitional framework of message-recovery security. The attacks are easily put out of reach by increasing the number of Feistel rounds in the standards.

Keymill is a side-channel resilient key generator, also known as re-keying function. Re-keying functions are a crucial building block of fresh re-keying schemes. To ensure the security against side-channel analysis of re-keying schemes, the used re-keying function has to withstand both simple power analysis and differential power analysis. We present a DPA attack on Keymill, which relies on the assumption that the dynamic power consumption of a digital circuit is tied to the $0\rightarrow 1$ and $1\rightarrow 0$ switches of its logical gates. Hence, the power consumption of the shift-registers used in Keymill depend on the $0\rightarrow 1$ and $1\rightarrow 0$ switches of its internal state. This information is enough to obtain the internal differential pattern (up to a small number of bits, which have to be brute-forced) of the 4 registers of Keymill after the nonce (or IV) is absorbed.

Key-homomorphic properties of cryptographic objects have proven to be useful, both from a theoretical as well as a practical perspective. Important cryptographic objects such as pseudorandom functions or (public key) encryption have been studied previously with respect to key-homomorphisms. Interestingly, however, signature schemes have not been explicitly investigated in this context so far.

We close this gap and initiate the study of key-homomorphic signatures, which turns out to be an interesting and versatile concept. In doing so, we firstly propose a definitional framework for key-homomorphic signatures distilling various natural flavours of key-homomorphic properties. Those properties aim to generalize larger classes of existing signature schemes, which makes it possible to infer general statements about signature schemes from those classes by simply making black-box usage of the respective properties. We then employ our definitional framework to show elegant and simple compilers from classes of schemes satisfying different types of key-homomorphisms to a number of other interesting primitives such as ring signature schemes, (universal) designated verifier signature schemes and multisignature schemes.

Moreover, we introduce the notion of multikey-homomorphic signatures. Such schemes provide homomorphic properties on the message space of signatures under different keys. We discuss key-homomorphisms in this context and present some first constructive results from key-homomorphic schemes. Finally, we discuss some interesting open problems and an application of multikey-homomorphic schemes to verifiable delegation of computations.

Most cryptographic schemes are designed in a model where perfect secrecy of the secret key is assumed. In most physical implementations, however, some form of information leakage is inherent and unavoidable. To deal with this, a flurry of works showed how to construct basic cryptographic primitives that are resilient to various forms of leakage.

Dodis et al. (FOCS '10) formalized and constructed leakage resilient one-way functions. These are one-way functions $f$ such that given a random image $f(x)$ and leakage $g(x)$ it is still hard to invert $f(x)$. Based on any one-way function, Dodis et al. constructed such a one-way function that is leakage resilient assuming that an attacker can leak any lossy function g of the input.

In this work we consider the problem of constructing leakage resilient one-way functions that are secure with respect to arbitrary computationally hiding leakage (a.k.a auxiliary-input). We consider both types of leakage --- selective and adaptive --- and prove various possibility and impossibility results. On the negative side, we show that if the leakage is an adaptively-chosen arbitrary one-way function, then it is impossible to construct leakage resilient one-way functions. The latter is proved both in the random oracle model (without any further assumptions) and in the standard model based on a strong vector-variant of DDH. On the positive side, we observe that when the leakage is chosen ahead of time, there are leakage resilient one-way functions based on a variety of assumption.

Since Keccak was selected as SHA-3 hash function by NIST, it has attracted considerable attention from cryptographic researchers. Keccak sponge function [1] has also been used to design message authentication codes (MAC) and authenticated encryption (AE) scheme Keyak. Till now, the most ecient key recovery attacks on Keccak-MAC and Keyak are cube attacks and cube-attack-like cryptanalysis proposed at EUROCRYPT'15. In this paper, we provide a new type of cube distinguisher named conditional cube tester for Keccak sponge function, where we append some bit conditions for some cube variables to reduce the dimension of the original cube tester. We apply the conditional cube tester to recover the key for reduced-round Keccak-MAC and Keyak. Compared to the previous key recovery attacks for Keccak-MAC and Keyak, our attacks are the best attacks according to the number of rounds or the complexity. Moreover, by constructing an MILP (mixed integer linear programming) model, we provide a searching algorithm to produce the most ecient conditional cube tester, which can be utilized as a distinguisher for Keccak sponge function. As a result, we improve the previous distinguishing attacks on Keccak sponge function. Although the attacks in this paper are the best ones compared with previous results, they cannot threat the security margin of Keccak sponge function.

The 2016 election is being held to fill all IACR Officer positions and three of nine IACR Director positions. Nominations are due by September 24, 2016. Information about the vacant positions and a nomination form can be found at https://www.iacr.org/elections/2016/.