Here you can see all recent updates to the IACR webpage. These updates are also available:

13
January
2017

ePrint Report
Inference and Record-Injection Attacks on Searchable Encrypted Relational Databases
{Mohamed Ahmed Abdelraheem, Tobias Andersson, Christian Gehrmann

We point out the risks of providing security to relational databases via searchable encryption schemes by mounting a novel inference attack
exploiting the structure of relational databases together with the leakage of searchable encryption schemes.
We discuss some techniques to reduce the effectiveness of inference attacks against searchable encryption schemes. Moreover, we show that record-injection attacks mounted on relational databases have worse consequences than their file-injection counterparts on unstructured databases which have been recently proposed at USENIX 2016.We point out the risks of providing security to relational databases via searchable encryption schemes by mounting a novel inference attack
exploiting the structure of relational databases together with the leakage of searchable encryption schemes.
We discuss some techniques to reduce the effectiveness of inference attacks against searchable encryption schemes. Moreover, we show that record-injection attacks mounted on relational databases have worse consequences than their file-injection counterparts on unstructured databases which have been recently proposed at USENIX 2016.

ePrint Report
Dual System Framework in Multilinear Settings and Applications to Fully Secure (Compact) ABE for Unbounded-Size Circuits
Nuttapong Attrapadung

We propose a new generic framework for constructing fully secure attribute based encryption (ABE) in multilinear settings. It is applicable in a generic manner to any predicates. Previous generic frameworks of this kind are given only in bilinear group settings, where applicable predicate classes are limited. Our framework provides an abstraction of dual system paradigms over composite-order graded multilinear encoding schemes in a black-box manner.

As applications, we propose new fully secure ABE systems for general predicates, namely, ABE for circuits. We obtain two schemes for each of key-policy (KP) and ciphertext-policy (CP) variants of ABE. All of our four fully secure schemes can deal with unbounded-size circuits, while enjoy succinctness, meaning that the key and ciphertext sizes are (less than or) proportional to corresponding circuit sizes. In the CP-ABE case, no scheme ever achieves such properties, even when considering selectively secure systems. Furthermore, our second KP-ABE achieves constant-size ciphertexts, whereas our second CP-ABE achieves constant-size keys. Previous ABE systems for circuits are either selectively secure (Gorbunov et al. STOC'13, Garg et al. Crypto'13, and subsequent works), or semi-adaptively secure (Brakerski and Vaikuntanathan Crypto'16), or fully-secure but not succinct and restricted to bounded-size circuits (Garg et al. ePrint 2014/622, and Garg et al. TCC'16-A).

As applications, we propose new fully secure ABE systems for general predicates, namely, ABE for circuits. We obtain two schemes for each of key-policy (KP) and ciphertext-policy (CP) variants of ABE. All of our four fully secure schemes can deal with unbounded-size circuits, while enjoy succinctness, meaning that the key and ciphertext sizes are (less than or) proportional to corresponding circuit sizes. In the CP-ABE case, no scheme ever achieves such properties, even when considering selectively secure systems. Furthermore, our second KP-ABE achieves constant-size ciphertexts, whereas our second CP-ABE achieves constant-size keys. Previous ABE systems for circuits are either selectively secure (Gorbunov et al. STOC'13, Garg et al. Crypto'13, and subsequent works), or semi-adaptively secure (Brakerski and Vaikuntanathan Crypto'16), or fully-secure but not succinct and restricted to bounded-size circuits (Garg et al. ePrint 2014/622, and Garg et al. TCC'16-A).

ePrint Report
Privacy for Distributed Databases via (Un)linkable Pseudonyms
Jan Camenisch, Anja Lehmann

When data maintained in a decentralized fashion needs to be synchronized or exchanged between different databases, related data sets usually get associated with a unique identifier. While this approach facilitates cross-domain data exchange, it also comes with inherent drawbacks in terms of controllability. As data records can easily be linked, no central authority can limit or control the information flow. Worse, when records contain sensitive personal data, as is for instance the case in national social security systems, such linkability poses a massive security and privacy threat. An alternative approach is to use domain-specific pseudonyms, where only a central authority knows the cross-domain relation between the pseudonyms. However, current solutions require the central authority to be a fully trusted party, as otherwise it can provide false conversions and exploit the data it learns from the requests. We propose an (un)linkable pseudonym system that overcomes those limitations, and enables controlled yet privacy-friendly exchange of distributed data. We prove our protocol secure in the UC framework and provide an efficient instantiation based on discrete-logarithm related assumptions.

12
January
2017

Two, three-year PhD scholarships, covering international tuition fees and a stipend of NZ$27,500 per year.

Application deadline: March 12, 2017.

The project is to develop new theoretical foundations for practical obfuscation. The theoretical component will focus on designing and evaluating new security definitions for practical obfuscation solutions. The practical component will focus on creating practical obfuscation tools inspired by the results obtained in the theoretical component. The theoretical work will be led by Prof Steven Galbraith while Dr. Giovanni Russello will lead the practical aspects.

The ideal candidate will have an undergraduate degree in computer science, engineering or mathematics and have written a master thesis in some topic related to security, cryptography, or the underlying mathematics. Experience with obfuscation and programming preferable.

**Closing date for applications:** 12 March 2017

**Contact:** Professor Steven Galbraith

Mathematics Department

University of Auckland

*aucklandobfuscationphd (at) gmail.com*

**More information:** https://www.math.auckland.ac.nz/~sgal018/PhD-Marsden.pdf

11
January
2017

We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic
functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes.
(1) A mark-embedded function must be functionally equivalent to the original function.
(2) It must be difficult for adversaries to remove the embedded mark without damaging the original functionality.
In spite of its importance and usefulness,
there have only been a few theoretical works on watermarking for functions (or programs). Furthermore, we do not have rigorous definitions of watermarking for cryptographic functions and concrete constructions.

To solve the above problem, we introduce a notion of watermarking for cryptographic functions and define its security. Furthermore, we present a lossy trapdoor function (LTF) based on the decisional linear (DLIN) problem and a watermarking scheme for the LTF. Our watermarking scheme is secure under the DLIN assumption in the standard model. We use techniques of dual system encryption and dual pairing vector spaces (DPVS) to construct our watermarking scheme. This is a new application of DPVS. Our watermarking for cryptographic functions is a generalized notion of copyrighted functions introduced by Naccache, Shamir, and Stern (PKC 1999) and our scheme is based on an identity-based encryption scheme whose private keys for identities (i.e., decryption functions) are marked, so our technique can be used to construct black-box traitor tracing schemes.

To solve the above problem, we introduce a notion of watermarking for cryptographic functions and define its security. Furthermore, we present a lossy trapdoor function (LTF) based on the decisional linear (DLIN) problem and a watermarking scheme for the LTF. Our watermarking scheme is secure under the DLIN assumption in the standard model. We use techniques of dual system encryption and dual pairing vector spaces (DPVS) to construct our watermarking scheme. This is a new application of DPVS. Our watermarking for cryptographic functions is a generalized notion of copyrighted functions introduced by Naccache, Shamir, and Stern (PKC 1999) and our scheme is based on an identity-based encryption scheme whose private keys for identities (i.e., decryption functions) are marked, so our technique can be used to construct black-box traitor tracing schemes.

ePrint Report
A Generic Approach to Constructing and Proving Verifiable Random Functions
Rishab Goyal, Susan Hohenberger, Venkata Koppula, Brent Waters

Verifiable Random Functions (VRFs) as introduced by Micali, Rabin and
Vadhan are a special form of Pseudo Random Functions
(PRFs) wherein a secret key holder can also prove
validity of the function evaluation relative to a statistically
binding commitment.
Prior works have approached the problem of constructing VRFs by proposing a
candidate under specific number theoretic setting --- mostly in
bilinear groups --- and then grapple with the challenges of proving
security in the VRF environments. These constructions achieved
different results and tradeoffs in practical efficiency, tightness of
reductions and cryptographic assumptions.

In this work we take a different approach. Instead of tackling the VRF problem as a whole we demonstrate a simple and generic way of building Verifiable Random Functions from more basic and narrow cryptographic primitives. Then we can turn to exploring solutions to these primitives with a more focused mindset. In particular, we show that VRFs can be constructed generically from the ingredients of: (1) a 1-bounded constrained pseudo random function for a functionality that is ``admissible hash friendly" , (2) a non-interactive statistically binding commitment scheme (without trusted setup) and (3) a non-interactive witness indistinguishable proofs or NIWIs. The first primitive can be replaced with a more basic puncturable PRF constraint if one is willing to settle for selective security or assume sub-exponential hardness of assumptions.

In addition, we support our generic approach by giving new constructions of constrained PRFs under non bilinear groups and new constructions of perfectly binding commitments from the Learning with Errors (LWE) and Learning Parity with Noise (LPN) assumptions.

In this work we take a different approach. Instead of tackling the VRF problem as a whole we demonstrate a simple and generic way of building Verifiable Random Functions from more basic and narrow cryptographic primitives. Then we can turn to exploring solutions to these primitives with a more focused mindset. In particular, we show that VRFs can be constructed generically from the ingredients of: (1) a 1-bounded constrained pseudo random function for a functionality that is ``admissible hash friendly" , (2) a non-interactive statistically binding commitment scheme (without trusted setup) and (3) a non-interactive witness indistinguishable proofs or NIWIs. The first primitive can be replaced with a more basic puncturable PRF constraint if one is willing to settle for selective security or assume sub-exponential hardness of assumptions.

In addition, we support our generic approach by giving new constructions of constrained PRFs under non bilinear groups and new constructions of perfectly binding commitments from the Learning with Errors (LWE) and Learning Parity with Noise (LPN) assumptions.

ePrint Report
concerto: A Methodology Towards Reproducible Analyses of TLS Datasets
Olivier Levillain, Maxence Tury, Nicolas Vivet

Over the years, SSL/TLS has become an essential part of Internet security. As such, it should offer robust and state-of-the-art security, in particular for HTTPS, its first application. Theoretically, the protocol allows for a trade-off between secure algorithms and decent performance. Yet in practice, servers do not always support the latest version of the protocol, nor do they all enforce strong cryptographic algorithms. To assess the quality of HTTPS and other TLS deployment at large, several studies have been led to grasp the state of the ecosystem, and to characterize the quality of certificate chains in particular.

In this paper, we propose to analyse some of the existing data concerning TLS measures on the Internet. We studied several datasets, from the first public ones in 2010 to more recent scans. Even if the collection methodology and the used tools vary between campaigns, we propose a unified and reproducible way to analyse the TLS ecosystem through different datasets. Our approach is based on a set of open-source tools, concerto.

Our contribution is therefore threefold: an analysis of existing datasets to propose a unified methodology, the implementation of our approach with concerto, and the presentation of some results to validate our toolsets.

In this paper, we propose to analyse some of the existing data concerning TLS measures on the Internet. We studied several datasets, from the first public ones in 2010 to more recent scans. Even if the collection methodology and the used tools vary between campaigns, we propose a unified and reproducible way to analyse the TLS ecosystem through different datasets. Our approach is based on a set of open-source tools, concerto.

Our contribution is therefore threefold: an analysis of existing datasets to propose a unified methodology, the implementation of our approach with concerto, and the presentation of some results to validate our toolsets.

ePrint Report
SMART POOL : Practical Decentralized Pooled Mining
Loi Luu, Yaron Velner, Jason Teutsch, Prateek Saxena

Many blockchain-based cryptocurrencies such as Bitcoin and Ethereum use
Nakamoto consensus protocol to reach agreement on the blockchain state between
a network of participant nodes. The Nakamoto consensus protocol
probabilistically selects a leader via a mining process which rewards network
participants (or miners) to solve computational puzzles. Finding solutions for
such puzzles requires an enormous amount of computation. Thus, miners often
aggregate resources into {\em pools} and share rewards amongst all pool
members via {\em pooled mining} protocol. Pooled mining helps reduce the
variance of miners' payoffs significantly and is widely adopted in popular
cryptocurrencies. For example, as of this writing, more than $95\%$ of mining
power in Bitcoin emanates from $10$ mining pools.

Although pooled mining benefits miners, it severely degrades decentralization, since a centralized pool manager administers the pooling protocol. Furthermore, pooled mining increases the transaction censorship significantly since pool managers decide which transactions are included in blocks. Due to this widely recognized threat, the Bitcoin community has proposed an alternative called P2Pool which decentralizes the operations of the pool manager. However, P2Pool is inefficient, increases the variance of miners' rewards, requires much more computation and bandwidth from miners, and has not gained wide adoption.

In this work, we propose a new protocol design for a decentralized mining pool. Our protocol called SmartPool shows how one can leverage {\em smart contracts}, which are autonomous agents themselves running on decentralized blockchains, to decentralize cryptocurrency mining. SmartPool guarantees high security, low reward's variance for miners and is cost-efficient. We implemented a prototype of SmartPool as an Ethereum smart contract working as a decentralized mining pool for Bitcoin. We have deployed it on the Ethereum testnet and our experiments confirm that SmartPool is efficient and ready for practical use.

Although pooled mining benefits miners, it severely degrades decentralization, since a centralized pool manager administers the pooling protocol. Furthermore, pooled mining increases the transaction censorship significantly since pool managers decide which transactions are included in blocks. Due to this widely recognized threat, the Bitcoin community has proposed an alternative called P2Pool which decentralizes the operations of the pool manager. However, P2Pool is inefficient, increases the variance of miners' rewards, requires much more computation and bandwidth from miners, and has not gained wide adoption.

In this work, we propose a new protocol design for a decentralized mining pool. Our protocol called SmartPool shows how one can leverage {\em smart contracts}, which are autonomous agents themselves running on decentralized blockchains, to decentralize cryptocurrency mining. SmartPool guarantees high security, low reward's variance for miners and is cost-efficient. We implemented a prototype of SmartPool as an Ethereum smart contract working as a decentralized mining pool for Bitcoin. We have deployed it on the Ethereum testnet and our experiments confirm that SmartPool is efficient and ready for practical use.

ePrint Report
Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs
Nir Bitansky

{\em Verifiable random functions} (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with a wide range of applications, considerable efforts have been directed towards the construction of such VRFs. While these efforts have resulted in a variety of algebraic constructions (from bilinear maps or the RSA problem), the relation between VRFs and other general primitives is still not well understood.

We present new constructions of VRFs from general primitives, the main one being {\em non-interactive witness-indistinguishable proofs} (NIWIs). This includes: \begin{itemize} \item A selectively-secure VRF assuming NIWIs and non-interactive commitments. As usual, the VRF can be made adaptively-secure assuming subexponential hardness of the underlying primitives. \item An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and {\em (single-key) constrained pseudorandom functions} for a restricted class of constraints. \end{itemize}

The above primitives have known instantiations under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, {\em verifiable pseudorandom generators} (the construction can be made uniform under a standard derandomization assumption). This partially answers an open question by Dwork and Naor (FOCS '00).

The construction and its analysis are quite simple. Both draw from ideas commonly used in the context of {\em indistinguishability obfuscation}.

We present new constructions of VRFs from general primitives, the main one being {\em non-interactive witness-indistinguishable proofs} (NIWIs). This includes: \begin{itemize} \item A selectively-secure VRF assuming NIWIs and non-interactive commitments. As usual, the VRF can be made adaptively-secure assuming subexponential hardness of the underlying primitives. \item An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and {\em (single-key) constrained pseudorandom functions} for a restricted class of constraints. \end{itemize}

The above primitives have known instantiations under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, {\em verifiable pseudorandom generators} (the construction can be made uniform under a standard derandomization assumption). This partially answers an open question by Dwork and Naor (FOCS '00).

The construction and its analysis are quite simple. Both draw from ideas commonly used in the context of {\em indistinguishability obfuscation}.

ePrint Report
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Gottfried Herold, Elena Kirshanova

We present an algorithm for the approximate $k$-List problem for the Euclidean distance that improves upon the Bai-Laarhoven-Stehle (BLS) algorithm from ANTS'16. The improvement stems from the observation that almost all the solutions to the approximate $k$-List problem form a particular configuration in $n$-dimensional space. Due to special properties of configurations, it is much easier to verify whether a $k$-tuple forms a configuration rather than checking whether it gives a solution to the $k$-List problem. Thus, phrasing the $k$-List problem as a problem of finding such configurations immediately gives a better algorithm. Furthermore, the search for configurations can be sped up using techniques from Locality-Sensitive Hashing (LSH). Stated in terms of configuration-search, our LSH-like algorithm offers a broader picture on previous LSH algorithms.

For the Shortest Vector Problem, our configuration-search algorithm results in an exponential improvement for memory-efficient sieving algorithms. For $k=3$, it allows us to bring down the complexity of the BLS sieve algorithm on an $n$-dimensional lattice from $2^{0.4812n+o(n)}$ to $2^{0.3962n + o(n)}$ with the same space-requirement $2^{0.1887n + o(n)}$. Note that our algorithm beats the Gauss Sieve algorithm with time resp. space requirements of $2^{0.415n+o(n)}$ resp. $2^{0.208n + o(n)}$, while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to $2^{0.3717n + o(n)}$ while retaining a memory complexity of $2^{0.1887n+o(n)}$.

For the Shortest Vector Problem, our configuration-search algorithm results in an exponential improvement for memory-efficient sieving algorithms. For $k=3$, it allows us to bring down the complexity of the BLS sieve algorithm on an $n$-dimensional lattice from $2^{0.4812n+o(n)}$ to $2^{0.3962n + o(n)}$ with the same space-requirement $2^{0.1887n + o(n)}$. Note that our algorithm beats the Gauss Sieve algorithm with time resp. space requirements of $2^{0.415n+o(n)}$ resp. $2^{0.208n + o(n)}$, while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to $2^{0.3717n + o(n)}$ while retaining a memory complexity of $2^{0.1887n+o(n)}$.

ePrint Report
Provable Security of Substitution-Permutation Networks
Yevgeniy Dodis, Jonathan Katz, John Steinberger, Aishwarya Thiruvengadam, Zhe Zhang

Many modern block ciphers are constructed based on the paradigm of substitution-permutation networks (SPNs). But, somewhat surprisingly---especially in comparison with Feistel networks, which have been analyzed by dozens of papers going back to the seminal work of Luby and Rackoff---there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the security of SPNs as strong pseudorandom permutations when the underlying "S-box" is modeled as a public random permutation. We show that 3 rounds of S-boxes are necessary and sufficient for secure linear SPNs, but that even 1-round SPNs can be secure when non-linearity is allowed.

ePrint Report
Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-Malleable Codes
Dana Dachman-Soled, Mukul Kulkarni, Aria Shahverdi

In a recent result, Dachman-Soled et al.~(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was Omega(log n), meaning that if the original message size was n, then Omega(log n) positions of the codeword had to be accessed upon each decode and update instruction.

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack-wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back-we show that a locally decodable and updatable non-malleable code with block size Chi in poly(lambda) number of bits requires locality delta(n) in omega(1), where n = poly(lambda) is message length and lambda is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al.~(TCC '15)-which indeed allows the adversary to launch a rewind attack-and present a construction of a locally decodable and updatable non-malleable code with block size Chi in Omega(lambda^{1/mu}) number of bits (for constant 0 < mu < 1) with locality delta(n), for any delta(n) in omega(1), and n = poly(lambda).

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack-wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back-we show that a locally decodable and updatable non-malleable code with block size Chi in poly(lambda) number of bits requires locality delta(n) in omega(1), where n = poly(lambda) is message length and lambda is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al.~(TCC '15)-which indeed allows the adversary to launch a rewind attack-and present a construction of a locally decodable and updatable non-malleable code with block size Chi in Omega(lambda^{1/mu}) number of bits (for constant 0 < mu < 1) with locality delta(n), for any delta(n) in omega(1), and n = poly(lambda).

ePrint Report
ORAMs in a Quantum World
Tommaso Gagliardoni, Nikolaos P. Karvelas, Stefan Katzenbeisser

We study the security of {\em Oblivious Random Access Machines (ORAM)} in the
quantum world. First we introduce a new formal treatment of ORAMs, which is at the
same time elegant and simpler than the known formalization by Goldreich and
Ostrovsky. Then we define and analyze the notion of post-quantum security for ORAMs,
i.e., classical ORAMs resistant against quantum adversaries. We show that merely
switching %from classically secure
to post-quantum secure encryption in a
classically secure
ORAM
construction does not generally yield a post-quantum secure ORAM construction. On the
other hand, we provide a post-quantum secure construction based on a modification of
Path-ORAM, the most efficient general ORAM construction, introduced by Stefanov et al.

Furthermore, we initiate the study of {\em Quantum ORAMs (QORAMs)}, that is, ORAM constructions meant to be executed between quantum parties acting on arbitrary quantum data. We address many problems arising when formalizing Quantum ORAMs, and we provide a secure construction (based on Path-ORAM and a quantum encryption scheme introduced by Alagic et al.) which has the interesting property of making read and write operations {\em inherently equivalent}. In so doing, we develop a novel technique of quantum extractability which is of independent interest. We believe that QORAMs represent a natural and interesting step in the direction of achieving privacy in future scenarios where quantum computing is ubiquitous.

Furthermore, we initiate the study of {\em Quantum ORAMs (QORAMs)}, that is, ORAM constructions meant to be executed between quantum parties acting on arbitrary quantum data. We address many problems arising when formalizing Quantum ORAMs, and we provide a secure construction (based on Path-ORAM and a quantum encryption scheme introduced by Alagic et al.) which has the interesting property of making read and write operations {\em inherently equivalent}. In so doing, we develop a novel technique of quantum extractability which is of independent interest. We believe that QORAMs represent a natural and interesting step in the direction of achieving privacy in future scenarios where quantum computing is ubiquitous.

ePrint Report
Pinocchio-Based Adaptive zk-SNARKs and Secure/Correct Adaptive Function Evaluation
Meilof Veeningen <meilof.veeningen@philips.com>

Pinocchio is a practical zk-SNARK that allows a prover to perform cryptographically verifiable computations with verification effort sometimes less than performing the computation itself. A recent proposal showed how to make Pinocchio adaptive (or ``hash-and-prove''), i.e., to enable proofs with respect to computation-independent commitments. This enables computations to be chosen after the commitments have been produced, and for data to be shared in different computations in a flexible way. Unfortunately, this proposal is not zero-knowledge. In particular, it cannot be combined with Trinocchio, a system in which Pinocchio is outsourced to three workers that do not learn the inputs thanks to multi-party computation (MPC). In this paper, we show how to make Pinocchio adaptive in a zero-knowledge way; apply it to make Trinocchio work on computation-independent commitments; present tooling to easily program fleible verifiable computations (with or without MPC); and use it to build a prototype in a medical research case study.

ePrint Report
Universal Samplers with Fast Verification
Venkata Koppula, Andrew Poelstra, Brent Waters

Recently, Hofheinz, Jager, Khurana, Sahai, Waters and Zhandry~\cite{HJKSWZ14} proposed a new primitive called universal samplers that allows oblivious sampling from arbitrary distributions, and showed how to construct universal samplers using indistinguishability obfuscation ($\iO$) in the ROM.

One important limitation for applying universal samplers in practice is that the constructions are built upon indistinguishability obfuscation. The costs of using current $\iO$ constructions is prohibitively large. We ask is whether the cost of a (universal) sampling could be paid by one party and then shared (soundly) with all other users? We address this question by introducing the notion of universal samplers with verification. Our notion follows the general path of \cite{HJKSWZ14}, but has additional semantics that allows for validation of a sample.

In this work we define and give a construction for universal samplers with verification. Our verification procedure is simple and built upon one-time signatures, making verification of a sample much faster than computing it. Security is proved under the sub exponential hardness of indistinguishability obfuscation, puncturable pseudorandom functions, and one-time signatures.

One important limitation for applying universal samplers in practice is that the constructions are built upon indistinguishability obfuscation. The costs of using current $\iO$ constructions is prohibitively large. We ask is whether the cost of a (universal) sampling could be paid by one party and then shared (soundly) with all other users? We address this question by introducing the notion of universal samplers with verification. Our notion follows the general path of \cite{HJKSWZ14}, but has additional semantics that allows for validation of a sample.

In this work we define and give a construction for universal samplers with verification. Our verification procedure is simple and built upon one-time signatures, making verification of a sample much faster than computing it. Security is proved under the sub exponential hardness of indistinguishability obfuscation, puncturable pseudorandom functions, and one-time signatures.

ePrint Report
Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures
Jan Camenisch, David Derler, Stephan Krenn, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig

A chameleon-hash function is a hash function that involves a trapdoor the knowledge of which allows one to find arbitrary collisions in the domain of the function. In this paper, we introduce the notion of chameleon-hash functions with ephemeral trapdoors. Such hash functions feature additional, i.e., ephemeral, trapdoors which are chosen by the party computing a hash value. The holder of the main trapdoor is then unable to find a second pre-image of a hash value unless also provided with the ephemeral trapdoor used to compute the hash value. We present a formal security model for this new primitive as well as provably secure instantiations. The first instantiation is a generic black-box construction from any secure chameleon-hash function. We further provide three direct constructions based on standard assumptions. Our new primitive has some appealing use-cases, including a solution to the long-standing open problem of invisible sanitizable signatures, which we also present.

Multi-key fully homomorphic encryption (MFHE) schemes allow polynomially many users without trusted setup assumptions to send their data (encrypted under different FHE keys chosen by users independently of each other) to an honest-but-curious server that can compute the output of an arbitrary polynomial-time computable function on this joint data and issue it back to all participating users for decryption. One of the main open problems left in MFHE was dealing with malicious users without trusted setup assumptions. We show how this can be done, generalizing previous results of circuit-private FHE. Just like standard circuit-private FHE, our security model shows that even if both ciphertexts and public keys of individual users are not well-formed, no information is revealed regarding the server computation--- other than that gained from the output on some well-formed inputs of all users. MFHE schemes have direct applications to server-assisted multiparty computation (MPC), called on-the-fly MPC, introduced by López-Alt et al. (STOC '12), where the number of users is not known in advance. In this setting, a poly-time server wants to evaluate a circuit $C$ on data uploaded by multiple clients and encrypted under different keys. Circuit privacy requires that users' work is independent of $|C|$ held by the server, while each client learns nothing about $C$ other than its output. We present a framework for transforming MFHE schemes with no circuit privacy into maliciously circuit-private schemes. We then construct 3-round on-the-fly MPC with circuit privacy against malicious clients in the plain model.

ePrint Report
Access Control Encryption for Equality, Comparison, and More
Georg Fuchsbauer, Romain Gay, Lucas Kowalczyk, Claudio Orlandi

Access Control Encryption (ACE) is a novel paradigm for encryption which allows to control not only what users in the system are allowed to \emph{read} but also what they are allowed to \emph{write}.

The original work of Damg{\aa}rd et al.~\cite{cryptoeprint:2016:106} introducing this notion left several open questions, in particular whether it is possible to construct ACE schemes with polylogarithmic complexity (in the number of possible identities in the system) from standard cryptographic assumptions.

In this work we answer the question in the affirmative by giving (efficient) constructions of ACE for an interesting class of predicates which includes equality, comparison, interval membership, and more.

We instantiate our constructions based both on standard pairing assumptions (SXDH) or more efficiently in the generic group model.

The original work of Damg{\aa}rd et al.~\cite{cryptoeprint:2016:106} introducing this notion left several open questions, in particular whether it is possible to construct ACE schemes with polylogarithmic complexity (in the number of possible identities in the system) from standard cryptographic assumptions.

In this work we answer the question in the affirmative by giving (efficient) constructions of ACE for an interesting class of predicates which includes equality, comparison, interval membership, and more.

We instantiate our constructions based both on standard pairing assumptions (SXDH) or more efficiently in the generic group model.

We present the idea of externally verifiable oblivious RAM (ORAM). Our goal is to allow a client and server carrying out an ORAM protocol to have disputes adjudicated by a third party, allowing for the enforcement of penalties against an unreliable or malicious server. We give a security definition that guarantees protection not only against a malicious server but also against a client making false accusations. We then give modifications of the Path ORAM and Ring ORAM protocols that meet this security definition. These protocols both have the same asymptotic runtimes as the semi-honest original versions and require the external verifier to be involved only when the client or server deviates from the protocol. Finally, we implement externally verified ORAM, along with an automated cryptocurrency contract to use as the external verifier.

ePrint Report
Algebraic Attack Efficiency versus S-box Representation
Hossein Arabnezhad-Khanoki, Babak Sadeghiyan, Josef Pieprzyk

Algebraic analysis of block ciphers aims at finding the secret key by solving
a collection of polynomial equations that describe the internal structure of a cipher
for chosen observations of plaintext/ciphertext pairs.
Although algebraic attacks are already accepted as a standard test for block and
stream ciphers, there is a lack of understanding of the impact of algebraic
representation of the cipher on efficiency of solving the resulting collection of equations.
The work investigates different S-box representations and their effect on
complexity of algebraic attacks.
In particular, we observe that a S-box representation defined in the work as
\textit{Forward-Backward} (FWBW) leads to a collection of equations that can be solved efficiently.
We show that the $SR(10,2,1,4)$ cipher can be broken using
standard algebra software \textsc{Singular} and FGb.
This is the best result achieved so far.
The effect of description of S-boxes for some light-weight block ciphers is investigated.
Our study and experiments confirms a counter-intuitive conclusion
that algebraic attacks work best for the FWBW S-box representation.
This contradicts a common belief that algebraic attacks are more efficient
for quadratic S-box representation.

ePrint Report
Reduced Mumford divisors of a genus 2 curve through its jacobian function field
Eduardo Ruiz Duarte

We explore the function field of the jacobian JH of a hyperelliptic
curve H of genus 2 in order to find reduced coordinates to represent
points of JH and do arithmetic.
We show how this relates to the usual Mumford representation of points
of JH. Moreover we identify the open subsets of JH where our reduced coordinates are defined, characterizing the elements which can be reduced and we discuss the group operation with them.

ePrint Report
High-speed Hardware Implementations of Point Multiplication for Binary Edwards and Generalized Hessian Curves
Bahram Rashidi, Reza Rezaeian Farashahi, Sayed Masoud Sayedi

In this paper high-speed hardware architectures of point multiplication based on Montgomery ladder algorithm for binary Edwards and generalized Hessian curves in Gaussian normal basis are presented. Computations of the point addition and point doubling in the proposed architecture are concurrently performed by pipelined digit-serial finite field multipliers. The multipliers in parallel form are scheduled for lower number of clock cycles. The structure of proposed digit-serial Gaussian normal basis multiplier is constructed based on regular and low-cost modules of exponentiation by powers of two and multiplication by normal elements. Therefore, the structures are area efficient and have low critical path delay. Implementation results of the proposed architectures on Virtex-5 XC5VLX110 FPGA show that then execution time of the point multiplication for binary Edwards and generalized Hessian curves over GF(2163) and GF(2233) are 8.62µs and 11.03µs respectively. The proposed architectures have high-performance and high-speed compared to other works.

The department of research & development of Wordline, an Atos Group Company and the department of mathematics and information security of XLIM, University of Limoges - France are conjointly conducting a study on code-based cryptography. The successful applicant will be working on the code-based submissions for standardization of the NIST post-quantum project.

Applicants who have a Master degree in mathematics, computer science or related areas are encouraged to apply. Skills in error-correcting codes, complexity and software development will also be appreciated.

The position is fully funded for 3 years to work within our research teams. Additionally, the candidate may be proposed a six-month internship before the beginning of the Ph.D. Review of applications will start immediately until position is filled.

**Closing date for applications:** 1 September 2017

**Contact:** Applications should be directed to: slim.bettaieb [at] worldline.com, loic.bidoux [at] worldline.com and gaborit [at] unilim.fr

Job Posting
Principal Engineer, Blockchain Technologies
Hong Kong Applied Science and Technology Research Institute Company Limited

Job Responsibilities

•Design and build financial technology applications using Blockchain / Distributed Ledger Technologies

•Work closely with the banking industry to create high values Blockchain applications

•Conduct research on cryptographic schemes for Blockchain / Distributed Ledger Technologies

•Design and develop innovative yet high quality application software for cybersecurity and FinTech initiatives.

•Collaborate with the energetic team to develop impactful Blockchain Proof-of-Concept and production applications.

Requirements

•Bachelor’s degree in Computer Science or related disciplines with 6+ years’ experience or Master’s degree of equivalent education with 3+ years’ experience or Ph.D degree holder with less experience. Candidates with less experience will be considered as Engineer.

•Knowledge in Blockchain technology and good understanding of the cryptographic principles. Understanding of Blockchain platform such as Bitcoin, Ethereum, HyperLedger, etc. is a big plus.

•Understanding of distributed system and experience in implementing cryptographic protocols is a plus.

•Hands-on experience in one or more programming languages: Java, Scala, Python, JavaScript, C/C++, Go, etc.

•Good understanding of data structure, algorithm and design patterns.

•Must possess excellent interpersonal, verbal, and written communication skills.

•Must have collaborative mind set, be a team-player and be keen to share knowledge.

•Ability to work independently and thrive in learning new technologies.

**Closing date for applications:** 15 January 2017

**Contact:** *charlenechoo (at) astri.org*

**More information:** http://www.astri.org

NXP Semiconductors is looking for an excellent, motivated, self-driven doctoral student to work in the area of side-channel evaluation on embedded devices.

The PhD position is for three years and will be located in Hamburg (Germany) within the Innovation Center for Cryptography and Security of NXP and it will be supervised at the academic level by Pr. François-Xavier Standaert (Université Catholique de Louvain). It will be funded by the REASSURE European research project focusing on improving the efficiency of security evaluations with respect to side-channel analysis.

Education and Requirements

--------------------

- A Master degree in computer science, security or mathematics

- A proven interest in cryptography and side-channel analysis

- Excellent communication and presentation skills on tactical as well as executive level (internally and externally)

- Strong analytical skills

- Team player

- Fluent in spoken and written English

Background in cryptography and embedded security will be a plus. Knowledge of German is not required.

Applications will be considered on a rolling basis until the position is filled.

**Closing date for applications:**

**Contact:** Vincent Verneuil

**More information:** https://nxp.wd3.myworkdayjobs.com/careers/job/Hamburg/PhD-student-in-Side-Channel-Analysis--m-f-_R-10001468-1

The IMDEA Software Institute invites applications for a postdoctoral position in the area of Cryptography. The successful candidate will do research in the analysis and design of provably-secure cryptographic protocols, supported by a project within the area of verifiable computation and zero-knowledge proofs.

The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. Salaries are internationally competitive and include attractive conditions such as access to an excellent public healthcare system. The working language at the institute is English.

Applicants should have already completed, or be close to completing, a PhD in computer science, mathematics, or a related discipline. Applicants should have an excellent research track record demonstrated by publications at major cryptography/security venues, and should have significant experience in the design of cryptographic protocols and provable security. Solid programming skills and experience in implementing cryptographic protocols will be considered positively. The application requires, among other document, a CV, a research statement, and the names of 3 persons that can provide references about you and your work.

The postdoctoral position is for one year. The starting date is negotiable but expected to be mid 2017.

Applicants interested in the position should send an email to Dario Fiore and submit the application documents at https://careers.imdea.org/software/. Applications are accepted until the position is filled.

**Closing date for applications:** 31 May 2017

**Contact:** For enquiries about the position, please contact: Dario Fiore, dario.fiore (at) imdea.org

**More information:** https://software.imdea.org/open_positions.html

Job Posting
PhD student in Cryptography & Privacy (UK citizens only)
University of Surrey, Surrey Centre for Cyber Security

Surrey Centre for Cyber Security invites applications for a fully-funded PhD position (tax-free stipend of 22000 GBP per year for a total of 3,5 years) in Cryptography to work on a research project focusing on the design, analysis and development of cryptographic protocols for privacy-preserving authentication in vehicular communications.

Successful applicants are expected to hold Bachelor degree or Master degree in Information Security, Computer Science or Mathematics accomplished with at least 2:1 honours and have strong background knowledge and technical skills (incl. programming skills) in cryptography and/or information/cyber security. We particularly welcome applications from ongoing students who are projected to fulfil the above criteria and complete their degree in 2017.

This position is funded by HM Government and is available only to UK citizens. Applications are welcome from UK citizens who are prepared to undergo security vetting conducted by respective UK authorities. The initial stage of vetting may last up to 3 months and needs to be accomplished successfully before the applicant can commence with their PhD studies and become eligible for the stipend.

This is a rolling advert with the nominal closing date. Applications are accepted until the position is filled.

**Closing date for applications:** 31 March 2017

**Contact:** Dr Mark Manulis, *m.manulis (at) surrey.ac.uk*

**More information:** https://jobs.surrey.ac.uk/vacancy.aspx?ref=093316

Job Posting
Senior Software Engineer / Software Engineer, Applied Cryptography
The Hong Kong Applied Science and Technology Research Institute Company Limited

Job Responsibilities

•To design and develop cryptographic protocols and schemes

•To design, analyze and implement cryptographic systems and related systems such as blockchain

•To study the latest cryptographic algorithms and protocols

Requirements

•Master degree in computer science, electronic engineering or other relevant disciplines with 3+ years experience; less experience for PhD holders.

•Experience on cryptographic system design and cryptanalysis

•Deep knowledge on number theory and security proofs

•Hands-on experience with C/C++ and Java

•Preferably having experiences on using cryptographic libraries such as OpenSSL, MIRACL, PBC, etc.

•Experience on developing cloud computing systems an advantage, but not a must

•Strong interpersonal and communications skills

•Good command of both written and spoken English

**Closing date for applications:** 15 January 2017

**Contact:** *charlenechoo (at) astri.org*

**More information:** http://www.astri.org

A one year postdoc/research fellow in the Coding and Crypto Research Group at Nanyang Technological University, Singapore is available immediately. The suitable candidate is to work on code and/or lattice based crypto.

**Closing date for applications:** 29 January 2017

**Contact:** Huaxiong wang

email: *hxwang (at) ntu.edu.sg*

5
January
2017

Event Calendar
DBSec'17: 31st IFIP WG 11.3 Conference on Data and Applications Security and Privacy
Philadelphia, USA, 17 July - 19 July 2017

Event date: 17 July to 19 July 2017

Submission deadline: 6 March 2017

Notification: 26 April 2017

Submission deadline: 6 March 2017

Notification: 26 April 2017