*19:17* [Pub][ePrint]
How Fair is Your Protocol? A Utility-based Approach to Protocol Optimality, by Juan Garay and Jonathan Katz and Bjoern Tackmann and Vassilis Zikas
In his seminal result, Cleve [STOC\'86] established that secure distributed computation--- guaranteeing fairness---is impossible in the presence of dishonest majorities. A generous number of proposals for relaxed notions of fairness ensued this seminal result, by weakening in various ways the desired security guarantees. While these works also suggest completeness results (i.e., the ability to design protocols which achieve their fairness notion), their assessment is typically of an all-or-nothing nature. That is, when presented with a protocol which is not designed to be fair according to their respective notion, they most likely would render it unfair and make no further statement about it.In this work we put forth a comparative approach to fairness. We present new intuitive notions that when presented with two arbitrary protocols, provide the means to answer the question \"Which of the protocols is fairer?\" The basic idea is that we can use an appropriate utility function to express the preferences of an adversary who wants to break fairness. Thus, we can compare protocols with respect to how fair they are, placing them in a partial order according to this relative-fairness relation.

After formulating such utility-based fairness notions, we turn to the question of finding optimal protocols---i.e., maximal elements in the above partial order. We investigate---and answer---this question for secure function evaluation, both in the two-party and multi-party settings.

To our knowledge, the only other fairness notion providing some sort of comparative state- ment is that of 1/p-security (aka \"partial fairness\") by Gordon and Katz [Eurocrypt\'10]. We also show in this paper that for a special class of utilities our notion strictly implies 1/p-security. In addition, we fix a shortcoming of the definition which is exposed by our comparison, thus strengthening that result.

*19:17* [Pub][ePrint]
New Techniques for SPHFs and Efficient One-Round PAKE Protocols, by Fabrice Benhamouda and Olivier Blazy and Céline Chevalier and David Pointcheval and Damien Vergnaud
Password-authenticated key exchange (PAKE) protocols allow two players to agree on a shared high entropy secret key, that depends on their own passwords only. Following the Gennaro and Lindell\'s approach, with a new kind of smooth-projective hash functions (SPHFs), Katz and Vaikuntanathan recently came up with the first concrete one-round PAKE protocols, where the two players just have to send simultaneous flows to each other. The first one is secure in the Bellare-Pointcheval-Rogaway (BPR) model and the second one in the Canetti\'s UC framework, but at the cost of simulation-sound non-interactive zero-knowledge (SSNIZK) proofs (one for the BPR-secure protocol and two for the UC-secure one), which make the overall constructions not really efficient.This paper follows their path with, first, a new efficient instantiation of SPHF on Cramer-Shoup ciphertexts, which allows to get rid of the SSNIZK proof and leads to the design of the most efficient one-round PAKE known so far, in the BPR model, and in addition without pairings.

In the UC framework, the security proof required the simulator to be able to extract the hashing key of the SPHF, hence the additional SSNIZK proof. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash functions (TSPHFs). Our concrete instantiation leads to the most efficient one-round PAKE UC-secure against static corruptions to date.

We additionally show how these SPHFs and TSPHFs can be used for blind signatures and zero-knowledge proofs with straight-line extractability.

*19:17* [Pub][ePrint]
Multi-Client Non-Interactive Verifiable Computation, by Seung Geol Choi and Jonathan Katz and Ranjit Kumaresan and Carlos Cid
Gennaro et al.\\ (Crypto 2010) introduced the notion of \\emph{non-interactive verifiable computation}, which allows a computationally weak client to outsource the computation of a function $f$ on a series of inputs $x^{(1)}, \\ldots$ to a morepowerful but untrusted server. Following a pre-processing phase (that is carried out only once), the client sends some representation of its current input $x^{(i)}$ to the server; the server returns an answer that allows the client to recover the correct result $f(x^{(i)})$, accompanied by a proof of correctness that ensures the client does not accept an incorrect result. The crucial property is that the work done by the client in preparing its input and verifying the server\'s proof is less than the time required for the client to compute~$f$ on its own.

We extend this notion to the \\emph{multi-client} setting, where $n$ computationally weak clients wish to outsource to an untrusted server the computation of a function $f$ over a series of {\\em joint} inputs $(x_1^{(1)}, \\ldots, x_{\\clients}^{(1)}), \\ldots$ without interacting with each other. We present a construction for this setting by combining the scheme of Gennaro et al.\\ with a primitive called proxy oblivious transfer.

*19:17* [Pub][ePrint]
Memory-saving computation of the pairing final exponentiation on BN curves, by Sylvain DUQUESNE and Loubna GHAMMAM
In this paper, we describe and improve efficient methods for computingthe hard part of the final exponentiation of pairings on Barreto-Naehrig

curves.

Thanks to the variants of pairings which decrease the length of the Miller

loop, the final exponentiation has become a significant component of the

overall calculation. Here we exploit the structure of BN curves to improve

this computation.

We will first present the most famous methods in the literature that en-

sure the computing of the hard part of the final exponentiation. We are

particularly interested in the memory resources necessary for the implementation of these methods. Indeed, this is an important constraint in

restricted environments.

More precisely, we are studying Devegili et al. method, Scott et al. addition chain method and Fuentes et al. method. After recalling these methods and their complexities, we determine the number of required registers

to compute the final result, because this is not always given in the literature. Then, we will present new versions of these methods which require

less memory resources (up to 37%). Moreover, some of these variants are

providing algorithms which are also more efficient than the original ones.