International Association
for Cryptologic Research

Homomorphic encryption provides the ability to compute on encrypted data without ever decrypting them. Potential applications include aggregating sensitive encrypted data on a cloud environment and computing on the data in the cloud without compromising data privacy. There have been several recent advances resulting in new homomorphic encryption schemes and optimized variants of existing schemes. Two efficient Residue-Number-System variants of the Brakerski-Fan-Vercauteren homomorphic encryption scheme were recently proposed: the Bajard-Eynard-Hasan-Zucca (BEHZ) variant based on integer arithmetic with auxiliary moduli, and the Halevi-Polyakov-Shoup (HPS) variant based on a combination of integer and floating-point arithmetic techniques. We implement and evaluate the performance of both variants in CPU (both single- and multi-threaded settings) and GPU. The most interesting (and also unexpected) result of our performance evaluation is that the HPS variant in practice scales significantly better (typically by 15%-30%) with increase in multiplicative depth of the computation circuit than BEHZ. This implies that the runtime performance and supported circuit depth for HPS will always be better for most practical applications. The comparison of the homomorphic multiplication runtimes for CPU and GPU demonstrates that our best GPU performance results are 3x-33x faster than our best multi-threaded results for a modern server CPU environment. For the multiplicative depth of 98, our fastest GPU implementation performs decryption in 0.5 ms and homomorphic multiplication in 51 ms for 128-bit security settings, which is already practical for cloud environments supporting GPU computations. Our best runtime results are at least two orders of magnitude faster than all previously reported results for any variant of the Brakerski-Fan-Vercauteren scheme.

The prevalence and availability of cloud infrastructures has made them the de facto solution for storing and archiving data, both for organizations and individual users. Nonetheless, the cloud's wide spread adoption is still hindered by data privacy and security concerns, particularly in applications with large data collections where efficient search and retrieval services are also major requirements. This leads to increased tension between security, efficiency, and search expressiveness, which current state of art solutions try to balance through complex cryptographic protocols that sacrifice efficiency and expressiveness for near optimal security.

In this paper we tackle this tension by proposing BISEN, a new provably-secure boolean searchable symmetric encryption scheme that improves these three complementary dimensions by exploring the design space of isolation guarantees offered by novel commodity hardware such as Intel SGX, abstracted as Isolated Execution Environments (IEEs). BISEN is the first scheme to enable highly expressive and arbitrarily complex boolean queries, with minimal leakage of information regarding performed queries and accessed data. Furthermore, by exploiting trusted hardware and the IEE abstraction, BISEN reduces communication costs between the client and the cloud, boosting query execution performance. Experimental validation and comparison with the state of art shows that BISEN provides better performance with enriched search semantics and security

Witness pseudorandom functions (witness PRFs), introduced by Zhandry [Zha16], was defined for an NP language L and generate a pseudorandom value for any instance x. The same pseudorandom value can be obtained efficiently using a valid witness w for x belongs to L. Zhandry built a subset-sum encoding scheme from multilinear maps and then converted a relation circuit corresponding to an NP language L to a subset-sum instance to achieve a witness PRF for L. The main goal in developing witness PRF in [Zha16] is to avoid obfuscation from various constructions of cryptographic primitives. Reliance on cryptographic tools built from multilinear maps may be perilous as existing multilinear maps are still heavy tools to use and suffering from many non-trivial attacks.

In this work, we give constructions of the following cryptographic primitives without using multilinear maps and instantiating obfuscation from randomized encoding: – We construct witness PRFs using a puncturable pseudorandom function and sub-exponentially secure randomized encoding scheme in common reference string (CRS) model. A sub-exponentially secure randomized encoding scheme in CRS model can be achieved from a sub-exponentially secure public key functional encryption scheme and learning with error assumptions with sub-exponential hardness. – We turn our witness PRF into a multi-relation witness PRF where one can use the scheme with a class of relations related to an NP language. – Furthermore, we construct an offline witness encryption scheme using our proposed witness PRF. The offline witness encryption scheme of Abusalah et al. [AFP16] was built from a plain public-key encryption, a statistical simulation-sound non-interactive zero knowledge (SSS-NIZK) proof system and obfuscation. In their scheme, a(n) SSS-NIZK proof is needed for the encryption whose efficiency depends on the underlying public key encryption. We replace SSS-NIZK by our witness PRF and construct an offline witness encryption scheme. More precisely, our scheme is based on a public-key encryption, a witness PRF and employs a sub-exponentially secure randomized encoding scheme in CRS model instantiating obfuscation. Our offline witness encryption can be turned into an offline functional witness encryption scheme where decryption releases a function of a message and witness as output.

At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.

In this paper, we suggest a new selective secure functional encryption scheme for degree $d$ polynomial. The number of ciphertexts for a message with length $\ell$ in our scheme is $O(\ell)$ regardless of $d$, while it is at least $\ell^{d/2}$ in the previous works.

Our main idea is to generically combine two abstract encryption schemes that satisfies some special properties. We also gives an instantiation of our scheme by combining ElGamal scheme and Ring-LWE based homomorphic encryption scheme, whose ciphertext length is exactly $2\ell+1,$ for any degree $d.$

We present a new method that produces bounded FHE schemes (see Definition 3), starting with encryption schemes that support one algebraic operation. We use this technique to construct examples of encryption schemes that, theoretically can handle any algebraic function on encrypted data.

We analyze the structure of commutative ring homomorphic encryption schemes and show that they are not quantum IND-CCA secure.

PQShield Ltd. is a spin-out company of the University of Oxford, specialised in Post-Quantum Cryptography.

We invite experts in PQ cryptography to join our team as (Senior) Cryptographic Researchers. Candidates are expected to have a PhD degree in any PQ cryptography field or the equivalent in industrial experience with a solid publication record.

The company is offering competitive packages in addition to the chance to be affiliated with the Mathematical Institute at the University of Oxford.

Closing date for applications: 15 August 2018

Contact: Interested candidates, please send your CVs to Ali El Kaafarani on elkaafarani (at) pqshield.com or elkaafarani (at) maths.ox.ac.uk

(For NUS SoC CS Dept)

Research Fellow

National University of Singapore

Description:

“NUS-Singtel Cyber Security R&D Lab” (http://nus-singtel.nus.edu.sg/) is a 5 years joint project with about SGD 43 mil (approximately USD 31 mil) of funds contributed by Singapore Telecommunications Limited (SingTel), National University of Singapore (NUS), and National Research Foundation (NRF) of Singapore. The R&D Lab will conduct research in four broad areas of cyber security having strategic relevance to Singtel’s business: (1) Predictive Security Analytics; (2) Network, Data and Cloud Security; (3) Internet-of-Things and Industrial Control Systems; (4) Future-Ready Cyber Security Systems.

NUS-SingTel Lab currently has one research fellow position with competitive pay. It is available to (fresh) PhD graduates in computer science/engineering from Singapore or overseas.

The Research Fellow will be responsible for working closely with the Principal Investigator and lab members on a new 3-year research project which just starts in June 2018. He/she should possess experience or interest in at least some of the following research areas:

• Key management, Authentication, Authorization and Access control

• Trusted computing (e.g. TPM, Intel SGX)

• Post-quantum cryptography

Job requirements:

• A PhD degree in a relevant area (Computer Science/Engineer, mathematics, etc);

• Good publication record in cyber security and crypto area

o Publication in Rank 1 Cyber Security or Crypto Conference, or AsiaCrypt, ESORICS, ACSAC, TCC, Euro S&P, etc;

• Good communication skills (English), self-motivated and good team players;

• Some experience in programming is a plus;

• Willing to perform practical research which may eventually lead to products

To apply for the above position, please send a copy of your recent CV to comxj (at) nus.edu.sg with an email subject “Application for RF”.

Closing date for applications: 31 December 2018

Contact: Dr Xu (comxj (at) nus.edu.sg)

More information: https://www.nus-singtel.nus.edu.sg/

The Centre for Cyber Security and Privacy at the University of Birmingham has 4 open vacancies for PhD students to start Sept/Oct 2018. This is an opportunity to join a successful and growing research group with a healthy cohort of PhD students (currently 15). Full stipends are available (including UK/EU tuition fees).

Candidates should have a background including cyber security (e.g. good grades in cyber security modules, a strong cyber security final project, or being on a dedicated cyber security course). Given the focus of all three studentships on hardware and attacks, candidates should additionally have a demonstrable interest in and familiarity with hardware security, pentesting, embedded systems and/or side-channel attacks.

The available projects (with supervisors and stipends) are:

• Cyber Security for the Vehicles of Tomorrow (Flavio Garcia) £14,553 for 3 years
• User-controlled Hardware Security Anchors: Evaluation and Design (Mark Ryan, Flavio Garcia, David Oswald) £14,553 for 3 years
• BioLeak: Side-Channel Analysis of Fingerprint Matching Algorithms (David Oswald, Flavio Garcia) £22,000 for 3 years
• FaultFinder: from Faulty Output to Fault Model – an Automated Approach (David Oswald, Flavio Garcia) £22,000 for 3 years

For more information please contact the relevant supervisors or our centre administrator. Please note that for BioLeak and FaultFinder candidates must be UK citizens.

Closing date for applications: 25 June 2018

Contact: Garfield Benjamin (administrator) g.r.benjamin (at) cs.bham.ac.uk

Mark Ryan (Professor) m.d.ryan (at) cs.bham.ac.uk

Flavio Garcia (Professor) f.garcia (at) cs.bham.ac.uk

David Oswald (Lecturer) d.f.oswald (at) cs.bham.ac.uk

More information: https://sec.cs.bham.ac.uk/

The chair MAIS at TU Darmstadt, led by Prof. Dr. Heiko Mantel, is offering multiple positions. We are looking for researchers who are interested in addressing foundational problems that will be of practical relevance or in addressing practical problems based on solid foundations. The research focus shall be on software security (information-flow security or side-channel analysis) using formal methods or systematic experiments.

We are offering three positions for Ph.D. candidates and Postdocs in the following areas:

1. information-flow analysis techniques for object-oriented programs at the level of source code and bytecode based on compositional and precise verification techniques
2. experimental analysis of side-channel vulnerabilities in cryptographic implementations and generation of attacks exploiting such vulnerabilities
3. program analysis techniques for detecting side-channel vulnerabilities in cryptographic implementations and for assessing the seriousness of such vulnerabilities

The overall goal of our research at MAIS is to make software-based systems more trustworthy (i.e. secure, safe, and correct) than they are today. As software engineering is a complex and error-prone task,

we employ formal methods in combination with experiments for reasoning about software and critical system properties. We investigate software systems on the level of source code, bytecode, and machine code as well as on the level of more abstract system specifications. This allows us to provide support for security at different stages of software

development. At MAIS we are offering a productive and collaborative research environment in which you can discuss ideas with other team members working on related topics.

The positions are available immediately and applications will be considered until the positions are taken. These are positions with regular salary and social benefits based on TV-TUD. For more information and how to apply, see http://www.mais.informatik.tu-darmstadt.de/Positions.html.

Closing date for applications:

Event date: 22 October to 26 October 2018
Submission deadline: 3 July 2018
Notification: 2 August 2018

State channels are a leading approach for improving the scalability of blockchains and cryptocurrencies. They allow a group of distrustful parties to optimistically execute an application-defined program amongst themselves, while the blockchain serves as a backstop in case of a dispute or abort. This effectively bypasses the congestion, fees and performance constraints of the underlying blockchain in the typical case. However, state channels introduce a new and undesirable assumption that a party must remain on-line and synchronised with the blockchain at all times to defend against execution fork attacks. An execution fork can revert a state channel’s history, potentially causing financial damage to a party that is innocent except for having crashed. To provide security even to parties that may go off-line for an extended period of time, we present Pisa, a protocol enables such parties to delegate to a third party, called the custodian, to cancel execution forks on their behalf. To evaluate Pisa, we provide a proof-of-concept implementation for a simplified Sprites and we demonstrate that it is cost-efficient to deploy on the Ethereum network.

We present three smart contracts that allow a briber to fairly exchange bribes to miners who pursue a mining strategy benefiting the briber. The first contract, CensorshipCon, highlights that Ethereum’s uncle block reward policy can directly subsidise the cost of bribing miners. The second contract, HistoryRevisionCon, rewards miners via an in-band payment for reversing transactions or enforcing a new state of another contract. The third contract, GoldfingerCon, rewards miners in one cryptocurrency for reducing the utility of another cryptocurrency. This work is motivated by the need to understand the extent to which smart contracts can impact the incentive mechanisms involved in Nakamoto-style consensus protocols.

Secure multi-party computation (MPC) is a problem of fundamental interest in cryptography. Traditional MPC protocols treat a "lazy" party (one that behaves honestly but aborts in the middle of the protocol execution) as a corrupt party that is colluding with the other corrupt parties. However, this outlook is unrealistic as there are various cases where an honest party may abort and turn "lazy" during the execution of a protocol without colluding with other parties. To address this gap, we initiate the study of what we call secure lazy multi-party computation with a formal definition that achieves meaningful correctness and security guarantees. We then construct a three-round lazy MPC protocol from standard cryptographic assumptions. Our protocol is malicious secure in the presence of a CRS and semi-malicious secure in the plain model without a CRS.

Using the techniques from above, we also achieve independently interesting consequences in the traditional MPC model. We construct the first round-optimal (three rounds) MPC protocol in the plain model (without a CRS) that achieves guaranteed output delivery (GOD) and is malicious-secure in the presence of an honest majority of parties. Previously, Gordon et al. [CRYPTO' 15] constructed a three-round protocol that achieves GOD in the honest majority setting, but required a CRS. They also showed that it is impossible to construct two-round protocols for the same even in the presence of a CRS. Thus, our result is the first 3-round GOD protocol that does not require any trusted setup, and it is optimal in terms of round complexity.

Furthermore, all our above protocols have communication complexity proportional only to the depth of the circuit being evaluated.

The key technical tool in our above protocols is a primitive called threshold multi-key fully homomorphic encryption which we define and construct assuming just learning with errors (LWE). We believe this primitive may be of independent interest.

An important initialization step in many social-networking applications is contact discovery, which allows a user of the service to identify which of its existing social contacts also use the service. Naive approaches to contact discovery reveal a user's entire set of social/professional contacts to the service, presenting a significant tension between functionality and privacy.

In this work, we present a system for private contact discovery, in which the client learns only the intersection of its own contact list and a server's user database, and the server learns only the (approximate) size of the client's list. The protocol is specifically tailored to the case of a small client set and large user database. Our protocol has provable security guarantees and combines new ideas with state-of-the-art techniques from private information retrieval and private set intersection.

We report on a highly optimized prototype implementation of our system, which is practical on real-world set sizes. For example, contact discovery between a client with 1024 contacts and a server with 67 million user entries takes 1.36 sec (when using server multi-threading) and uses only 4.28 MiB of communication.

Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the- art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically:

- We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6x improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation.

- We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5x improvement in the communication and a 2x improvement in the computation for that step.

We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security).

For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a ``strong'' semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack. Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security.

We revisit constructions of asymmetric primitives from obfuscation and give simpler alternatives. We consider public-key encryption, (hierarchical) identity-based encryption ((H)IBE), and predicate encryption. Obfuscation has already been shown to imply PKE by Sahai and Waters (STOC'14) and full-fledged functional encryption by Garg et al. (FOCS'13). We simplify all these constructions and reduce the necessary assumptions on the class of circuits that the obfuscator needs to support. Our PKE scheme relies on just a PRG and does not need any puncturing. Our IBE and bounded HIBE schemes convert natural key-delegation mechanisms from (recursive) applications of puncturable PRFs to IBE and HIBE schemes. Our most technical contribution is an unbounded HIBE, which uses (public-coin) differing-inputs obfuscation for circuits and whose proof relies on a recent pebbling-based hybrid argument by Fuchsbauer et al. (ASIACRYPT'14). All our constructions are anonymous, support arbitrary inputs, and have compact keys and ciphertexts.

The generalized birthday problem (GBP) was introduced by Wagner in 2002 and has shown to have many applications in cryptanalysis. In its typical variant, we are given access to a function $H:\{0,1\}^{\ell} \rightarrow \{0,1\}^n$ (whose specification depends on the underlying problem) and an integer $K>0$. The goal is to find $K$ distinct inputs to $H$ (denoted by $\{x_i\}_{i=1}^{K}$) such that $\sum_{i=1}^{K}H(x_i) = 0$. Wagner's K-tree algorithm solves the problem in time and memory complexities of about $N^{1/(\lfloor \log K \rfloor + 1)}$ (where $N= 2^n$). Two important open problems raised by Wagner were (1) devise efficient time-memory tradeoffs for GBP, and (2) reduce the complexity of the K-tree algorithm for $K$ which is not a power of 2.

In this paper, we make progress in both directions. First, we improve the best know GBP time-memory tradeoff curve (published by independently by Nikoli\'{c} and Sasaki and also by Biryukov and Khovratovich) for all $K \geq 8$ from $T^2M^{\lfloor \log K \rfloor -1} = N$ to $T^{\lceil (\log K)/2 \rceil + 1 }M^{\lfloor (\log K)/2 \rfloor} = N$, applicable for a large range of parameters. For example, for $K = 8$ we improve the best previous tradeoff from $T^2M^2 = N$ to $T^3M = N$ and for $K = 32$ the improvement is from $T^2M^4 = N$ to $T^4M^2 = N$.

Next, we consider values of $K$ which are not powers of 2 and show that in many cases even more efficient time-memory tradeoff curves can be obtained. Most interestingly, for $K \in \{6,7,14,15\}$ we present algorithms with the same time complexities as the K-tree algorithm, but with significantly reduced memory complexities. In particular, for $K=6$ the K-tree algorithm achieves $T=M=N^{1/3}$, whereas we obtain $T=N^{1/3}$ and $M=N^{1/6}$. For $K=14$, Wagner's algorithm achieves $T=M=N^{1/4}$, while we obtain $T=N^{1/4}$ and $M=N^{1/8}$. This gives the first significant improvement over the K-tree algorithm for small $K$.

Finally, we optimize our techniques for several concrete GBP instances and show how to solve some of them with improved time and memory complexities compared to the state-of-the-art.

Our results are obtained using a framework that combines several algorithmic techniques such as variants of the Schroeppel-Shamir algorithm for solving knapsack problems (devised in works by Howgrave-Graham and Joux and by Becker, Coron and Joux) and dissection algorithms (published by Dinur, Dunkelman, Keller and Shamir). It then builds on these techniques to develop new GBP algorithms.