International Association
for Cryptologic Research

Event date: 30 October 2017
Submission deadline: 4 August 2017
Notification: 8 September 2017

Machine learning models hosted in a cloud service are increasingly popular but risk privacy: clients sending prediction requests to the service need to disclose potentially sensitive information. In this paper, we explore the problem of privacy-preserving predictions: after each prediction, the server learns nothing about clients' input and clients learn nothing about the model.

We present MiniONN, the first approach for transforming an existing neural network to an oblivious neural network supporting privacy-preserving predictions with reasonable efficiency. Unlike prior work, MiniONN requires no change to how models are trained. To this end, we design oblivious protocols for commonly used operations in neural network prediction models. We show that MiniONN outperforms existing work in terms of response latency and message sizes. We demonstrate the wide applicability of MiniONN by transforming several typical neural network models trained from standard datasets.

The goal of leakage-resilient cryptography is to construct cryptographic algorithms that are secure even if the adversary obtains side-channel information from the real world implementation of these algorithms. Most of the prior works on leakage-resilient cryptography consider leakage models where the adversary has access to the leakage oracle before the challenge-ciphertext is generated (before-the-fact leakage). In this model, there are generic compilers that transform any leakage-resilient CPA-secure public key encryption (PKE) scheme to its CCA-2 variant using Naor-Yung type of transformations. In this work, we give an efficient generic compiler for transforming a leakage-resilient CPA-secure PKE to leakage-resilient CCA-2 secure PKE in presence of after-the-fact split-state (bounded) memory leakage model, where the adversary has access to the leakage oracle even after the challenge phase. The salient feature of our transformation is that the leakage rate (defined as the ratio of the amount of leakage to the size of secret key) of the transformed after-the-fact CCA-2 secure PKE is same as the leakage rate of the underlying after-the-fact CPA-secure PKE, which is $1-o(1)$. We then present another generic compiler for transforming an after-the-fact leakage-resilient CCA-2 secure PKE to a leakage-resilient authenticated key exchange (AKE) protocol in the bounded after-the-fact leakage-resilient eCK (BAFL-eCK) model proposed by Alawatugoda et al. (ASIACCS'14). To the best of our knowledge, this gives the first compiler that transform any leakage-resilient CCA-2 secure PKE to an AKE protocol in the leakage variant of the eCK model.

An emerging direction for authenticating people is the adoption of biometric authentication systems. Biometric credentials are becoming increasingly popular as a mean of authenticating people due to the wide rage of advantages that they provide with respect to classical authentication methods (e.g., password-based authentication). The most characteristic feature of this authentication method is the naturally strong bond between a user and her biometric credentials. This very same advantageous property, however, raises serious security and privacy concerns in case the biometric trait gets compromised. In this article, we present the most challenging issues that need to be taken into consideration when designing secure and privacy- preserving biometric authentication protocols. More precisely, we describe the main threats against privacy-preserving biometric authentication systems and give directions on possible countermeasures in order to design secure and privacy-preserving biometric authentication protocols.

Many block ciphers use permutations defined over the finite field $\mathbb{F}_{2^{2k}}$ with low differential uniformity, high nonlinearity, and high algebraic degree to provide confusion. Due to the lack of knowledge about the existence of almost perfect nonlinear (APN) permutations over $\mathbb{F}_{2^{2k}}$, which have lowest possible differential uniformity, when $k>3$, constructions of differentially 4-uniform permutations are usually considered. However, it is also very difficult to construct such permutations together with high nonlinearity; there are very few known families of such functions, which can have the best known nonlinearity and a high algebraic degree. At Crypto'16, Perrin et al. introduced a structure named butterfly, which leads to permutations over $\mathbb{F}_{2^{2k}}$ with differential uniformity at most 4 and very high algebraic degree when $k$ is odd. It is posed as an open problem in Perrin et al.'s paper and solved by Canteaut et al. that the nonlinearity is equal to $2^{2k-1}-2^k$. In this paper, we extend Perrin et al.'s work and study the functions constructed from butterflies with exponent $e=2^i+1$. It turns out that these functions over $\mathbb{F}_{2^{2k}}$ with odd $k$ have differential uniformity at most 4 and algebraic degree $k+1$. Moreover, we prove that for any integer $i$ and odd $k$ such that $\gcd(i,k)=1$, the nonlinearity equality holds, which also gives another solution to the open problem proposed by Perrin et al. This greatly expands the list of differentially 4-uniform permutations with good nonlinearity and hence provides more candidates for the design of block ciphers.

We devise a virtual black-box (VBB) obfuscator for querying whether set elements are stored within Bloom filters, with security based on the Ring Learning With Errors (RLWE) problem and strongly universal hash functions. Our construction uses an abstracted encoding scheme that we instantiate using the Gentry, Gorbunov and Halevi (GGH15) multilinear map, with an explicit security reduction to RLWE. This represents an improvement on the functionality and security guarantees compared with the conjunction obfuscator introduced by Brakerski et al. (ITCS 2016), where security follows from a non-standard RLWE variant. Immediate applications of our work arise from any common usage of Bloom filters, such as efficient set intersection testing. Our obfuscated program allows this functionality to be executed in a non-interactive manner whilst preventing the natural leakage that occurs when providing offline access to a Bloom filter. Compared to more general obfuscators for evasive functions, we demonstrate a significant asymptotic reduction in size and required computation for obfuscating set intersection queries. The obfuscator of Wichs and Zirdelis (EPRINT 2017) requires \(O(4^{n \log n})\) encodings for obfuscating circuits computing the intersection of sets of size \(n\), requiring the usage of additional primitives such as FHE to allow sets of polynomial size. Our construction requires only \(O(kn)\) total encodings and operations for evaluation, where \(k << n\). Moreover, the size of our obfuscator is independent of the size of the elements that are contained in the set. Our results, alongside recent and concurrent work, can be seen as another step forward in obfuscating wider classes of evasive functions using standard assumptions and models.

The mechanism for traditional Searchable Symmetric Encryption is pay-then-use. That is to say, if a user wants to search some documents that contain special keywords, he needs to pay to the server firstly, then he can enjoy search service. Under this situation, these kinds of things will happen: After the user paying the service fees, the server may either disappear because of the poor management or returning nothing. As a result, the money that the user paid cannot be brought back quickly. Another case is that the server may return incorrect document sets to the user in order to save his own cost. Once such events happen, it needs the arbitration institution to mediate which will cost a long time. Besides, to settle the disputes the user has to pay to the arbitration institution. Ideally, we deeply hope that when the user realizes the server has a tendency to cheat in the task of searching, he can immediately and automatically withdraw his money to safeguard his right. However, the existing SSE protocols cannot satisfy this demand.

To solve this dilemma, we find a compromised method by introducing the block chain into SSE. Our scheme achieves three goals stated below. Firstly, when the server does not return any thing to user after he gets the search token, the user can get some compensation from the server, because the server can infer some important information from the Index and this token. Besides, the user also doesn't pay the service charge. Secondly, if the documents that the server returns are false, the server cannot receive service fees, meanwhile, he will be punished. Lastly, when the user receives some bitcoin from server at the beginning, he may terminate the protocol. Under this situation, the server is a victim. In order to prevent such thing from happening, the server will broadcast a transaction to redeem his pledge after an appointed time.

Contract signing protocols have been proposed and analyzed for more than three decades now. One of the main problems that appeared while studying such schemes is the impossibility of achieving both fairness and guaranteed output delivery. As workarounds, cryptographers have put forth three main categories of contract signing schemes: gradual release, optimistic and concurrent or legally fair schemes. Concurrent signature schemes or legally fair protocols do not rely on trusted arbitrators and, thus, may seem more attractive for users. Boosting user trust in such manner, an attacker may cleverly come up with specific applications. Thus, our work focuses on embedding trapdoors into contract signing protocols. In particular, we describe and analyze various SETUP (Secretly Embedded Trapdoor with Universal Protection) mechanisms which can be injected in concurrent signature schemes and legally fair protocols without keystones.

Sanitizable signatures are a variant of digital signatures where a designated party (the sanitizer) can update admissible parts of a signed message. At PKC’17, Camenisch et al. introduced the notion of invisible sanitizable signatures that hides from an outsider which parts of a message are admissible. Their security definition of invisibility, however, does not consider dishonest signers. Along the same lines, their signer-accountability definition does not prevent the signer from falsely accusing the sanitizer of having issued a signature on a sanitized message by exploiting the malleability of the signature itself. Both issues may limit the usefulness of their scheme in certain applications. We revise their definitional framework, and present a new construction eliminating these shortcomings. In contrast to Camenisch et al.’s construction, ours requires only standard building blocks instead of chameleon hashes with ephemeral trapdoors. This makes this, now even stronger, primitive more attractive for practical use. We underpin the practical efficiency of our scheme by concrete benchmarks of a prototype implementation.

Crowdsourcing systems have gained considerable interest and adoption in recent years. They coordinate the human intelligence of individual and businesses together from all over the world to solve complex tasks. However, these central systems are subject to the weaknesses of the trust based model like traditional financial institutions, such as single point of failure, high services fee and privacy disclosure. In this paper, we conceptualize a blockchain-based decentralized framework for crowdsourcing, in which a requester’s task can be solved by a crowd of workers without relying on central crowdsourcing systems or requiring users to access services with registering true identities. In particular, we present the architecture of our proposed framework and separate CrowdBC into three layer: application layer, blockchain layer and storage layer. Users can register, post or receive a task securely under this structure. We enhance the scalability of crowdsourcing by depicting complex crowdsourcing logic with smart contract. Moreover, we give a detailed scheme for the whole process of crowdsourcing and also discuss the security of decentralized crowdsourcing framework. Finally, we implement a software prototype on Ethereum to show the validity and effectiveness of our proposed framework design for crowdsourcing.

A memory-hard function (MHF) $f_n$ with parameter $n$ can be computed in sequential time and space $n$. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.

Essentially all iMHFs can be viewed as some mode of operation (making $n$ calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called ``depth-robustness'') which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.

In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:

- Prove that their depth-robustness is asymptotically maximal.

- Prove bounds of at least $3$ orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.

-Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.

Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, for the best performing of the new DAGs we implement an iMHF using the Argon2i round function and code base and show that on a standard off-the-shelf CPU the new iMHF can actually be evaluated slightly faster than Argon2i (despite seemingly enjoying significantly higher aAT).

Argon2i is a data-independent memory hard function that won the password hashing competition. The password hashing algorithm has already been incorporated into several open source crypto libraries such as libsodium. In this paper we analyze the cumulative memory cost of computing Argon2i. On the positive side we provide a lower bound for Argon2i. On the negative side we exhibit an improved attack against Argon2i which demonstrates that our lower bound is nearly tight. In particular, we show that

- An Argon2i DAG is $\left(e,O\left(n^3/e^3\right)\right))$-reducible.

- The cumulative pebbling cost for Argon2i is at most $O\left(n^{1.768}\right)$. This improves upon the previous best upper bound of $O\left(n^{1.8}\right)$ [Alwen and Blocki, EURO S&P 2017].

- Argon2i DAG is $\left(e,\tilde{\Omega}\left(n^3/e^3\right)\right))$-depth robust. By contrast, analysis of [Alwen et al., EUROCRYPT 2017] only established that Argon2i was $\left(e,\tilde{\Omega}\left(n^3/e^2\right)\right))$-depth robust.

- The cumulative pebbling complexity of Argon2i is at least $\tilde{\Omega}\left( n^{1.75}\right)$. This improves on the previous best bound of $\Omega\left( n^{1.66}\right)$ [Alwen et al. EUROCRYPT 2017] and demonstrates that Argon2i has higher cumulative memory cost than competing proposals such as Catena or Balloon Hashing.

We also show that Argon2i has high fractional depth-robustness which strongly suggests that data-dependent modes of Argon2 are resistant to space-time tradeoff attacks.

The main objective of the research in the Embedded System Security Group is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. Currently, the central theme of this research consists in designing architectures for secure embedded systems implemented in logic devices such as FPGAs and ASICs.

More information on https://laboratoirehubertcurien.univ-st-etienne.fr/en/teams/secure-embedded-systems-hardware-architectures.html.

For a new project which addresses the problem of secure and privacy in MPSoC architectures, we proposes a Post Doc position to work on security evaluation of heterogeneous MPSoC. We are looking for candidates with an outstanding Ph.D in hardware security and a strong publication record in this field. Strong knowledge in side channel attacks and countermeasures, digital system (VHDL, FPGA) design would be appreciated. Knowledge of French is not mandatory.

The Post-Doc position will start in September or October 2017 (flexible starting date), it is funded for 13 month.

To apply please send your detailed CV (with publication list), motivation for applying (1 page) and names of at least two people who can provide reference letters (e-mail).

Closing date for applications: 30 June 2017

Contact: Prof. Lilian BOSSUET lilian.bossuet(at)univ-st-etienne.fr

The main objective of the research in the Embedded System Security Group is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. Currently, the central theme of this research consists in designing architectures for secure embedded systems implemented in logic devices such as FPGAs and ASICs.

More information on https://laboratoirehubertcurien.univ-st-etienne.fr/en/teams/secure-embedded-systems-hardware-architectures.html.

For a new project which addresses the problem of the security of TRNG against fault injection attack. We are looking for candidates with an outstanding Ph.D in hardware security and a strong publication record in this field. Strong knowledge in fault injection attacks with laser, and VLSI design would be appreciated. Knowledge of French is not mandatory.

The Post-Doc position will start in September or October 2017, it is funded for 34 month.

To apply please send your detailed CV (with publication list), motivation for applying (1 page) and names of at least two people who can provide reference letters (e-mail).

Closing date for applications: 30 June 2017

Contact: Prof. Lilian BOSSUET lilian.bossuet(at)univ-st-etienne.fr

We present a new approach to construct several leakage-resilient cryptographic primitives, including public-key encryption (PKE) schemes, authenticated key exchange (AKE) protocols and low-latency key exchange (LLKE) protocols. To this end, we develop a new primitive called leakage-resilient non-interactive key exchange (LR-NIKE). We introduce a new generic security model for LR-NIKE protocols, which can be instantiated in both bounded-and-continuous-memory leakage setting. We then show a secure construction of LR-NIKE protocol in the bounded-memory leakage setting, that achieves an optimal leakage rate, i.e., $1- o(1)$. We then show how to construct the aforementioned leakage-resilient primitives from such a LR-NIKE. In particular,

We show how to construct a leakage-resilient IND-CCA-2-secure PKE scheme in the bounded- memory leakage setting, from LR-NIKE protocol. Our construction differs from the state-of-the- art constructions of leakage-resilient IND-CCA-2-secure PKE, which use hash proof techniques to achieve leakage resiliency. Moreover, our transformation preserves the leakage-rate of the underlying LR-NIKE and admits more efficient construction than the previous such PKE constructions.

We introduce a new leakage model for AKE protocols, in the bounded-memory leakage setting. We show how to construct a leakage-resilient AKE protocol starting from LR-NIKE protocol.

We introduce the first-ever leakage model for LLKE protocols, in the bounded-memory leakage setting, and the first construction of such a leakage-resilient LLKE from LR-NIKE protocol.

T-310 is an important Cold War cipher. It was the principal encryption algorithm used to protect various state communication lines in Eastern Germany throughout the 1980s. The cipher seems to be quite robust, and until now, no cryptography researcher has proposed an attack on T-310. In this paper we provide a detailed analysis of T-310 in the context of modern cryptography research and other important or similar ciphers developed in the same period. We introduce new notations which show the peculiar internal structure of this cipher in a new light. We point out a number of significant strong and weak properties of this cipher. Finally we propose several new attacks on T-310.

We study the problem of securely building single-commodity multi-markets auction mechanisms. We introduce a novel greedy algorithm and its corresponding privacy preserving implementation using secure multi-party computation. More specifically, we determine the quantity of supply and demand bids maximizing welfare. Each bid is attached to a specific market, but exchanges between different markets are allowed up to some upper limit. The general goal is for the players to bid their intended valuations without concerns about what the other players can learn. This problem is inspired by day-ahead electricity markets where there are substantial transmission capacity between the different markets, but applies to other commodity markets like gas. Furthermore, we provide computational results with a specific C++ implementation of our algorithm and the necessary MPC primitives. We can solve problems of 1945 bids and 4 markets in 1280 seconds when online/offline phases are considered. Finally, we report on possible set-ups, workload distributions and possible trade-offs for real-life applications of our results based on this experimentation and prototyping.

Lattice-based cryptography is one of the most promising areas within post-quantum cryptography, and offers versatile, efficient, and high performance security services. The aim of this paper is to verify the correctness of the discrete Gaussian sampling component, one of the most important modules within lattice-based cryptography. In this paper, the GLITCH software test suite is proposed, which performs statistical tests on discrete Gaussian sampler outputs. An incorrectly operating sampler, for example due to hardware or software errors, has the potential to leak secret-key information and could thus be a potential attack vector for an adversary. Moreover, statistical test suites are already common for use in pseudo-random number generators (PRNGs), and as lattice-based cryptography becomes more prevalent, it is important to develop a method to test the correctness and randomness for discrete Gaussian sampler designs. Additionally, due to the theoretical requirements for the discrete Gaussian distribution within lattice-based cryptography, certain statistical tests for distribution correctness become unsuitable, therefore a number of tests are surveyed. The final GLITCH test suite provides 11 adaptable statistical analysis tests that assess the exactness of a discrete Gaussian sampler, and which can be used to verify any software or hardware sampler design.

In the implementation of many public key schemes, there is a need to implement modular arithmetic. Typically this consists of addition, subtraction, multiplication and (occasionally) division with respect to a prime modulus. To resist certain side-channel attacks it helps if implementations are ``constant time''. As the calculations proceed there is potentially a need to reduce the result of an operation to its remainder modulo the prime modulus. However often this reduction can be delayed, a process known as ``lazy reduction''. The idea is that results do not have to be fully reduced at each step, that full reduction takes place only occasionally, hence providing a performance benefit. Here we extend the idea to determine the circumstances under which reduction can be delayed to the very end of a particular public key operation.

In this paper we investigate weak keys of universal hash functions (UHFs) from their combinatorial properties. We find that any UHF has a general class of keys, which makes the combinatorial properties totally disappear, and even compromises the security of the UHF-based schemes, such as the Wegman-Carter scheme, the UHF-then-PRF scheme, etc. By this class of keys, we actually get a general method to search weak-key classes of UHFs, which is able to derive all previous weak-key classes of UHFs found by intuition or experience. Moreover we give a weak-key class of the BRW polynomial function which was once believed to have no weak-key issue, and exploit such weak keys to implement a distinguish attack and a forgery attack against DTC - a BRW-based authentication encryption scheme. Furthermore in Grain-128a, with the linear structure revealed by weak-key classes of its UHF, we can recover any first $(32+b)$ bits of the UHF key, spending no more than $1$ encryption and $(2^{32} + b)$ decryption queries.