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

25
May
2017

ePrint Report
Fully Homomorphic Encryption Using Multivariate Polynomials
Matthew Tamayo-Rios, Jean-Charles Faugère, Ludovic Perret, Peng Hui How, Robin Zhang

Efficient and secure third party computation has many practical applications in cloud computing. We develop new approach for building fully homomorphic encryption (FHE) schemes, by starting with the intuition of using algebraic descriptions of the encryption and decryption functions to construct a functionally complete set of homomorphic boolean operators. We use this approach to design a compact efficient asymmetric cryptosystem that supports secure third party evaluation of arbitrary boolean functions. In the process, we introduce a new hard problem that is a more difficult variant of of the classical Isomorphism of Polynomials (IP) that we call the Obfuscated-IP.

ePrint Report
Universal Construction of Cheater-Identifiable Secret Sharing Against Rushing Cheaters without Honest Majority
Masahito Hayashi, Takeshi Koshiba

For conventional secret sharing, if cheaters can submit possibly forged shares after observing shares of the honest users in the reconstruction phase, they can disturb the protocol and reconstruct the true secret. To overcome the problem, secret sharing scheme with properties of cheater-identification have been proposed. Existing protocols for cheater-identifiable secret sharing assumed non-rushing cheaters or honest majority. In this paper, we remove both conditions simultaneously, and give its universal construction from any secret sharing scheme. To resolve this end, we propose the concepts of "individual identification" and "agreed identification".

Proxy re-encryption (PRE) and Proxy re-signature (PRS) were introduced by Blaze, Bleumer and Strauss [Eurocrypt '98]. Basically, PRE allows a semi-trusted proxy to transform a ciphertext encrypted under one key into an encryption of the same plaintext under another key, without revealing the underlying plaintext. Since then, many interesting applications have been explored, and many constructions in various settings have been proposed, while PRS allows a semi-trusted proxy to transform Alice's signature on a message into Bob's signature on the same message, but the proxy cannot produce new valid signature on new messages for either Alice or Bob.

Recently, for PRE related progress, Cannetti and Honhenberger [CCS '07] defined a stronger notion -- CCA-security and construct a bi-directional PRE scheme. Later on, several work considered CCA-secure PRE based on bilinear group assumptions. Very recently, Kirshanova [PKC '14] proposed the first single-hop CCA1-secure PRE scheme based on learning with errors (LWE) assumption. For PRS related progress, Ateniese and Hohenberger [CCS'05] formalized this primitive and provided efficient constructions in the random oracle model. At CCS 2008, Libert and Vergnaud presented the first multi-hop uni-directional proxy re-signature scheme in the standard model, using assumptions in bilinear groups.

In this work, we first point out a subtle but serious mistake in the security proof of the work by Kirshanova. This reopens the direction of lattice-based CCA1-secure constructions, even in the single-hop setting. Then we construct a single-hop PRE scheme that is proven secure in our new tag-based CCA-PRE model. Next, we construct the first multi-hop PRE construction. Lastly, we also construct the first PRS scheme from lattices that is proved secure in our proposed unified security model

Recently, for PRE related progress, Cannetti and Honhenberger [CCS '07] defined a stronger notion -- CCA-security and construct a bi-directional PRE scheme. Later on, several work considered CCA-secure PRE based on bilinear group assumptions. Very recently, Kirshanova [PKC '14] proposed the first single-hop CCA1-secure PRE scheme based on learning with errors (LWE) assumption. For PRS related progress, Ateniese and Hohenberger [CCS'05] formalized this primitive and provided efficient constructions in the random oracle model. At CCS 2008, Libert and Vergnaud presented the first multi-hop uni-directional proxy re-signature scheme in the standard model, using assumptions in bilinear groups.

In this work, we first point out a subtle but serious mistake in the security proof of the work by Kirshanova. This reopens the direction of lattice-based CCA1-secure constructions, even in the single-hop setting. Then we construct a single-hop PRE scheme that is proven secure in our new tag-based CCA-PRE model. Next, we construct the first multi-hop PRE construction. Lastly, we also construct the first PRS scheme from lattices that is proved secure in our proposed unified security model

ePrint Report
Vector Encoding over Lattices and Its Applications
Daniel Apon, Xiong Fan, Feng-Hao Liu

In this work, we design a new lattice encoding structure for vectors. Our encoding can be used to achieve a packed FHE scheme that allows some SIMD operations and can be used to improve all the prior IBE schemes and signatures in the series. In particular, with respect to FHE setting, our method improves over the prior packed GSW structure of Hiromasa et al. (PKC '15), as we do not rely on a circular assumption as required in their work. Moreover, we can use the packing and unpacking method to extract each single element, so that the homomorphic operation supports element-wise and cross-element-wise computation as well. In the IBE scenario, we improves over previous constructions supporting $O(\lambda)$-bit length identity from lattices substantially, such as Yamada (Eurocrypt '16), Katsumata, Yamada (Asiacrypt '16) and Yamada (Eprint '17), by shrinking the master public key to three matrices from standard Learning With Errors assumption. Additionally, our techniques from IBE can be adapted to construct a compact digital signature scheme, which achieves existential unforgeability under the standard Short Integer Solution (SIS) assumption with small polynomial parameters.

ePrint Report
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich

Algorand is a new cryptocurrency system that can confirm transactions
with latency on the order of a minute while scaling to many users.
Algorand ensures that users never have divergent views of confirmed
transactions, even if some of the users are malicious and the network is
partitioned. In contrast, existing cryptocurrencies allow for temporary
forks and therefore require a long time, on the order of an hour, to confirm transactions with
high confidence.

Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand's BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed.

We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 30$\times$ Bitcoin's throughput, and incurs almost no penalty for scaling to more users.

Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand's BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed.

We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 30$\times$ Bitcoin's throughput, and incurs almost no penalty for scaling to more users.

ePrint Report
Subtleties in Security Definitions for Predicate Encryption with Public Index
Johannes Bl\"{o}mer, Gennadij Liske

We take a critical look at established security definitions for predicate encryption (PE) with public index under chosen-plaintext attack (CPA) and under chosen-ciphertext attack (CCA). In contrast to conventional public-key encryption (PKE), security definitions for PE have to deal with user collusion which is modeled by an additional key generation oracle. We identify three different formalizations of key handling in the literature implicitly assumed to lead to the same security notion. Contrary to this assumption we prove that the corresponding models result in two different security notions under CPA and three different security notions under CCA. Similarly to the recent results for PKE and conventional key-encapsulation mechanism (KEM) (Journal of Cryptology, 2015) we also analyze subtleties in security definitions for PE and predicate key-encapsulation mechanism (P-KEM) regarding the so-called "no-challenge-decryption" condition. While the results for PE and PKE are similar, the results for P-KEM significantly differ from the corresponding results for conventional KEM. Our analysis is based on appropriate definitions of semantic security and indistinguishability of encryptions for PE under different attacks scenarios. These definitions complement related security definitions for identity-based encryption and functional encryption. As a result of our work we suggest security definitions for PE and P-KEM under different attack scenarios.

23
May
2017

Event Calendar
IV TIBETS: IV Taller Iberoamericano de EnseÃ±anza e InnovaciÃ³n Educativa en Seguridad
Buenos Aires, Argentina, 1 November - 3 November 2017

Event date: 1 November to 3 November 2017

Submission deadline: 15 July 2017

Notification: 31 August 2017

Submission deadline: 15 July 2017

Notification: 31 August 2017

Event Calendar
IX CIBSI: IX Congreso Iberoamericano de Seguridad InformÃ¡tica
Buenos Aires, Argentina, 1 November - 3 November 2017

Event date: 1 November to 3 November 2017

Submission deadline: 15 June 2017

Notification: 31 July 2017

Submission deadline: 15 June 2017

Notification: 31 July 2017

Event Calendar
CANS 2017: 16th International Conference on Cryptology and Network Security
Hong Kong, Hong Kong, 30 November - 2 December 2017

Event date: 30 November to 2 December 2017

Submission deadline: 25 July 2017

Notification: 12 September 2017

Submission deadline: 25 July 2017

Notification: 12 September 2017

Event Calendar
WPES '17: Workshop on Privacy in the Electronic Society
Dallas, Texas, United States, 30 October 2017

Event date: 30 October 2017

Submission deadline: 4 August 2017

Notification: 8 September 2017

Submission deadline: 4 August 2017

Notification: 8 September 2017

ePrint Report
Oblivious Neural Network Predictions via MiniONN transformations
Jian Liu, Mika Juuti, Yao Lu, N. Asokan

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.

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.

ePrint Report
Efficient Compilers for After-the-Fact Leakage: from CPA to CCA-2 secure PKE to AKE
Suvradip Chakraborty, Goutam Paul, C. Pandu Rangan

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.

ePrint Report
Privacy-preserving biometric authentication: challenges and directions
Elena Pagnin, Aikaterini Mitrokotsa

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.

ePrint Report
Differentially 4-Uniform Permutations with the Best Known Nonlinearity from Butterflies
Shihui Fu, Xiutao Feng, Baofeng Wu

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.

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.

ePrint Report
Secretly Embedding Trapdoors into Contract Signing Protocols
Diana Maimut, George Teseleanu

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.

ePrint Report
Practical Strongly Invisible and Strongly Accountable Sanitizable Signatures
Michael Till Beck, Jan Camenisch, David Derler, Stephan Krenn, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig

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.

ePrint Report
CrowdBC: A Blockchain-based Decentralized Framework for Crowdsourcing
Ming Li, Jian Weng, Anjia Yang, Wei Lu

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.

ePrint Report
Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions
Joel Alwen, Jeremiah Blocki, Ben Harsha

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).

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).

ePrint Report
On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i
Jeremiah Blocki, Samson Zhou

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.

- 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.

Job Posting
Post Doc in Embedded System Security
Laboratoire Hubert Curien, University of Lyon, Saint-Etienne, France

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

Job Posting
Post Doc in Hardware Security
Laboratoire Hubert Curien, University of Lyon, Saint-Etienne, France

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

22
May
2017

ePrint Report
New Approach to Practical Leakage-Resilient Public-Key Cryptography
Suvradip Chakraborty, Janaka Alawatugoda, C. Pandu Rangan

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.

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.

ePrint Report
Cryptographic Security Analysis of T-310
Nicolas T. Courtois, Klaus Schmeh, Jörg Drobick, Jacques Patarin, Maria-Bristena Oprisanu, Matteo Scarlata, Om Bhallamudi

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.

ePrint Report
Practically Efficient Secure Single-Commodity Multi-Market Auctions
Abdelrahaman Aly, Mathieu Van Vyve

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.

ePrint Report
GLITCH: A Discrete Gaussian Testing Suite For Lattice-Based Cryptography
James Howe, M\'aire O'Neill

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.

ePrint Report
Analyzing Multi-Key Security Degradation
Atul Luykx, Bart Mennink, Kenneth G. Paterson

The multi-key, or multi-user, setting challenges cryptographic algorithms to maintain high levels of security when used with many different keys, by many different users. Its significance lies in the fact that in the real world, cryptography is rarely used with a single key in isolation. A folklore result, proved by Bellare, Boldyreva, and Micali for public-key encryption in EUROCRYPT 2000, states that the success probability in attacking any one of many independently keyed algorithms can be bounded by the success probability of attacking a single instance of the algorithm, multiplied by the number of keys present. Although sufficient for settings in which not many keys are used, once cryptographic algorithms are used on an internet-wide scale, as is the case with TLS, the effect of multiplying by the number of keys can drastically erode security claims. We establish a sufficient condition on cryptographic schemes and security games under which multi-key degradation is avoided. As illustrative examples, we discuss how AES and GCM behave in the multi-key setting, and prove that GCM, as a mode, does not have multi-key degradation. Our analysis allows limits on the amount of data that can be processed per key by GCM to be significantly increased. This leads directly to improved security for GCM as deployed in TLS on the Internet today.