*00:17* [Pub][ePrint]
On the Communication Complexity of Secure Function Evaluation with Long Output, by Pavel Hubacek and Daniel Wichs
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input $x_A$, Bob has an input $x_B$ and we want Bob to learn some function $y = f(x_A, x_B)$ with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice\'s key. In a trivial insecure protocol, Alice can just send her short input $x_A$ to Bob. However, all known SFE protocols have communication complexity that scales with size of the output $y$, which can potentially be much larger. Is such ``output-size dependence\'\' inherent in SFE?Surprisingly, we show that output-size dependence can be avoided in the \\emph{honest-but-curious} setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a ``somewhere statistically binding (SSB) hash\'\', and which may be of independent interest.

On the negative side, we show that output-size dependence is inherent in the \\emph{fully malicious} setting, or even already in an \\emph{honest-but-deterministic} setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.

*00:17* [Pub][ePrint]
DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity, by Dhananjay S. Phatak, Qiang Tang, Alan T. Sherman, Warren D. Smith, Peter Ryan, Kostas Kalpakis
An encryption relation $f \\subseteq {\\mathbb Z} \\times {\\mathbb Z}$ with decryption function $f^{-1}$ is {\\it ``group-homomorphic\'\'} if, for any suitable plaintexts $x_1$ and $x_2$, $\\, x_1+x_2 = f^{-1} ( f(x_1) + f(x_2) )$. It is {\\it ``ring-homomorphic\'\'} if furthermore $x_1 x_2 = f^{-1} ( f(x_1) f(x_2) )$; it is {\\it ``field-homomorphic\'\'} if furthermore $1/x_1 = f^{-1} ( f(1/x_1) )$. Such relations would support oblivious processing of encrypted data. We propose a simple randomized encryption relation~$f$ over the integers, called\\linebreak {\\it \\mbox{DoubleMod}}, which is ``bounded ring-homomorphic\'\' or what some call \"somewhat homomorphic.\" Here, ``bounded\'\' means that the number of additions and multiplications that can be performed, while not allowing the encrypted values to go out of range, is limited~(any pre-specified bound on the operation-count can be accommodated). Let $R$ be any large integer. For any plaintext $x \\in {\\mathbb Z}_R$, DoubleMod encrypts $x$ as $f(x) = x + au + bv$, where $a$ and $b$ are randomly chosen integers in some appropriate interval, while $(u,v)$ is the secret key. Here $u>R^2$ is a large prime and the smallest prime factor of $v$ exceeds $u$. With knowledge of the key, but not of $a$ and $b$, the receiver decrypts the ciphertext by computing $f^{-1}(y) =(y \\bmod v) \\bmod u$.

DoubleMod generalizes an independent idea of van Dijk {\\it et al.} 2010. We present and refine a new CCA1 chosen-ciphertext attack that finds the secret key of both systems (ours and van Dijk {\\it et al.}\'s) in linear time in the bit length of the security parameter. Under a known-plaintext attack, breaking DoubleMod is at most as hard as solving the {\\it Approximate GCD (AGCD)} problem. The complexity of AGCD is not known.

We also introduce the \\mbox{{\\it SingleMod}} {field}-homomorphic cryptosystems. The simplest\\linebreak \\mbox{SingleMod} system based on the integers can be broken trivially. We had hoped, that if SingleMod is implemented inside non-Euclidean quadratic or higher-order fields with large discriminants, where GCD computations appear difficult, it may be feasible to achieve a desired level of security. We show, however, that a variation of our chosen-ciphertext attack works against SingleMod even in non-Euclidean fields.

*20:13* [Job][New]
Cryptography Engineer, *CloudFlare Inc.*
CloudFlare is looking for a talented cryptography engineer to join our team. We are working on a number of ambitious projects to secure the web and protect our customers from threats of all sorts. At CloudFlare we deal with cryptography at scale, and tackle projects that shape the future of the Web.

The role of cryptography engineer at CloudFlare is more that of a builder than a breaker. You will have to approach problems with creativity and flexibility and be able to identify and use the best tools for the job or build better ones from scratch. At CloudFlare, we are serious about protecting our customers and advancing the state of the art in computer security.

**Requirements:**

Expertise in theory and implementation of white-box cryptographyExperience building code obfuscation toolsExperience writing cryptographic libraries and APIsExperience implementing production-grade cryptographic algorithmsExpert in C/C++/Go and performance analysisFamiliarity with compilers or code generation tools**Bonus Points:**

Contributions to the open source communityExperience with cryptographic hardware (TPM, HSM, etc.)Healthy sense of paranoia

*15:02* [Job][New]
Post-Doc, *LORIA-CNRS, University of Lorraine, Nancy, France*
**Provably secure e-voting**We are looking for one postdoctoral researcher to join the ProSecure project at Loria, Nancy, in the Cassis team, for 1 or 2 years.

**Context**

One important family of protocols is e-voting. Electronic voting protocols should offer the same guarantees than more traditional voting systems. In particular, they should offer both vote privacy and verifiability : anyone should be able to check that the result corresponds to the votes. Surprisingly, even defining a crucial property such as vote privacy has not yet reached a consensus in the scientific community. Moreover, existing voting systems should still be improved in terms of verifiability, coercion-resistance, or usability. To achieve a high level of trust, these systems should be proved secure rigorously.

**Objectives**

One objective is to propose well-founded definitions of crucial properties in e- voting such as privacy, receipt-freeness, coercion-resistance, and verifiability and apply them on various e-voting protocols including well-known schemes such as Helios or Civitas. In particular, our team is developing a variant of Helios named Belenios. This scheme has been proved to be ballot private and fully verifiable. More security properties are yet to be proved and several enhancement of the protocol are planned. Belenios benefits from the support of an engineer that develops and maintains it.

The post-doc researcher is expected to contribute autonomously to the development of new results for defining and proving cryptographic security properties and for designing a both practical and secure voting scheme. The postdoc researcher should have a good publication record and a strong expertise in cryptography.

*14:33* [Job][Update]
Doctoral Researcher in the collaborative research center CROSSING, *Technische Universität Darmstadt, Germany*
Collaborative Research Centers are institutions funded by the German Research Foundation (DFG) and are established at universities to pursue a scientifically ambitious, complex, long?term research program. The goal of the center CROSSING is to provide cryptography-based security solutions enabling trust in new and next generation computing environments. In the center researchers from different areas such as Cryptography, IT-Security, Quantum Physics, and Software Engineering will collaborate. The available doctoral positions are distributed over the aforementioned areas, and will be affiliated with the research training school of the center.

As part of its research program CROSSING will develop an open-source software called OpenCCE which will allow users to deploy the developed solutions in a secure and easy way.

Applicants should upload their applications on www.crossing.tu-darmstadt.de/de/crossing/jobs/application/ including the usual documents and indicating the applicant’s area of interest. Applications will be considered until the positions are filled.

For more information about CROSSING and the application process please visit www.crossing.tu-darmstadt.de.

TU Darmstadt has a large interest in increasing the number of female researchers, and hence particularly encourages female candidates to apply. Applicants with a degree of disability of 50% or more will be preferred in case they are otherwise equally qualified to the other candidates. It is generally possible to work part time.

*09:17* [Pub][ePrint]
Revocation in Publicly Verifiable Outsourced Computation, by James Alderman and Carlos Cid and Jason Crampton and Christian Janson
The combination of software-as-a-service and the increasing use of mobile devices gives rise to a considerable difference in computational power between servers and clients. Thus, there is a desire for clients to outsource the evaluation of complex functions to an external server. Servers providing such a service may be rewarded per computation, and as such have an incentive to cheat by returning garbage rather than devoting resources and time to compute a valid result.In this work, we introduce the notion of Revocable Publicly Verifiable Computation (RPVC), where a cheating server is revoked and may not perform future computations (thus incurring a financial penalty). We introduce a Key Distribution Center (KDC) to efficiently handle the generation and distribution of the keys required to support RPVC. The KDC is an authority over entities in the system and enables revocation. We also introduce a notion of blind verification such that results are verifiable (and hence servers can be rewarded or punished) without learning the value.

We present a rigorous definitional framework, define a number of new security models and present a construction of such a scheme built upon Key-Policy Attribute-based Encryption.

*09:17* [Pub][ePrint]
The Multiple Number Field Sieve with Conjugation Method, by Cécile Pierrot
In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields.We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \\sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \\sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

*09:17* [Pub][ePrint]
Balanced permutations Even-Mansour ciphers, by Shoni Gilboa and Shay Gueron
The $r$-rounds Even-Mansour block cipher uses $r$ public permutations of $\\{0, 1\\}^n$ and $r+1$ secret keys. An attack on this construction was described in \\cite{DDKS}, for $r = 2, 3$. Although this attack is only marginally better than brute force, it is based on an interesting observation (due to \\cite{NWW}): for a \"typical\" permutation $P$, the distribution of $P(x) \\oplus x$ is not uniform. To address this, and other potential threats that might stem from this observation in this (or other) context, we introduce the notion of a ``balanced permutation\'\' for which the distribution of $P(x) \\oplus x$ is uniform, and show how to generate families of balanced permutations from the Feistel construction.

This allows us to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. The cipher uses public balanced permutations of $\\{0, 1\\}^{2n}$, which are based on two public permutations of $\\{0, 1\\}^{n}$.

By construction, this cipher is immune against attacks that rely on the non-uniform behavior of $P(x) \\oplus x$. We prove that this cipher is indistinguishable from a random permutation of $\\{0, 1\\}^{2n}$,

for any adversary who has oracle access to the public permutations and to an encryption/decryption oracle, as long as the number of queries is $o (2^{n/2})$. As a practical example, we discuss the properties and the performance of a $256$-bit block cipher that is based on AES.