International Association
for Cryptologic Research

Event date: 10 September to 12 September 2018
Submission deadline: 20 June 2018
Notification: 27 July 2018

Event date: 10 December to 13 December 2018
Submission deadline: 26 May 2018
Notification: 14 August 2018

Event date: 4 March to 8 March 2019
Submission deadline: 14 September 2018
Notification: 19 November 2018

We propose a detailed construction of Collision Resistance Preimage Sampleable Functions $($CRPSF$)$ over any cyclotomic field based on NTRU, hence give a provably secure NTRU Signature scheme $($NTRUSign$)$, which is strongly existentially unforgeable under adaptive chosen-message attacks in the random oracle module. The security of CRPSF $($NTRUSign$)$ is reduced to the corresponding small integer solution problem over rings $($Ring-SIS$)$. More precisely, the security of our scheme is based on the worst-case approximate shortest independent vectors problem $($SIVP$_\gamma$$)$ over ideal lattices. For any fixed cyclotomic field, we give a probabilistic polynomial time $($PPT$)$ key generation algorithm which shows how to extend the secret key of NTRUEncrypt to the secret key of NTRUSign. This conversion is important for constructions of many cryptographic primitives based on NTRU, for example, CRPSF, NTRUSign, identity-based encryption and identity-based signature. We also delve back into former construction of NTRUEncrypt and enrich the choices of the module $q$. Some useful results about $q$-ary lattices, regularity and uniformity of distribution of the public key of NTRUEncrypt are also generalized to more general algebraic field $K$, as long as $K$ is Galois over $\mathbb{Q}$.

Oblivious transfer (OT) is a fundamental primitive in cryptography. Halevi-Kalai OT (Halevi, S. and Y. Kalai (2012), Journal of Cryptology 25(1)), which is based on smooth projective hash(SPH), is a famous and the most efficient framework for $1$-out-of-$2$ oblivious transfer ($\mbox{OT}^{2}_{1}$) against malicious adversaries in plain model. However, it does not provide simulation-based security. Thus, it is harder to use it as a building block in secure multiparty computation (SMPC) protocols. A natural question however, which so far has not been answered, is whether it can be can be made fully-simulatable. In this paper, we give a positive answer. Further, we present a fully-simulatable framework for general $\mbox{OT}^{n}_{t}$ ($n,t\in \mathbb{N}$ and $n>t$). Our framework can be interpreted as a constant-round blackbox reduction of $\mbox{OT}^{n}_{t}$ (or $\mbox{OT}^{2}_{1}$) to SPH. To our knowledge, this is the first such reduction. Combining Kilian's famous completeness result, we immediately obtain a black-box reduction of SMPC to SPH.

Fully homomorphic encryption (FHE) is a powerful notion of encryption which allows data to be encrypted in such a way that anyone can perform arbitrary computations over the encrypted data without decryption or knowledge of the secret key. Traditionally, FHE only allows for computations over data encrypted under a single public key. Lopez-Alt et al. (STOC 2012) introduced a new notion of FHE, called multi-key FHE (MFHE), which permits joint computations over data encrypted under multiple independently-generated (unrelated) keys such that any evaluated ciphertext could be (jointly) decrypted by the parties involved in the computation. Such MFHE schemes could be readily used to delegate computation to cloud securely.

Recently a number of works have studied the problem of constructing quantum homomorphic encryption (QHE) which is to perform quantum computations over encrypted quantum data. In this work we initiate the study of quantum multi-key homomorphic encryption (QMHE) and obtain the following results:

1) We formally define the notion of quantum multi-key homomorphic encryption and construct such schemes from their classical counterpart. Building on the framework of Broadbent and Jeffery (Crypto 2015) and Dulek et al. (Crypto 2016), we show that any classical multi-key leveled homomorphic encryption can be used to build a quantum multi-key leveled homomorphic encryption if we also have certain suitable error-correcting quantum gadgets. The length of the evaluation key grows linearly with the number of $T$-gates in the quantum circuit, thereby giving us a quantum multi-key leveled homomorphic encryption for circuits with polynomial but bounded number of $T$-gates.

2) To enable a generic transformation from any classical multi-key scheme, we introduce and construct a new cryptographic primitive which we call conditional oblivious quantum transform (COQT). A COQT is a distributed non-interactive encoding scheme that captures the essence of error-correcting gadgets required for quantum homomorphic encryption in the multi-key setting. We then build COQTs themselves from any classical multi-key leveled homomorphic encryption with $\boldsymbol{\mathrm{NC}}^1$ decryption. We believe that COQTs might be an object of independent interest.

3) We also show that our quantum multi-key homomorphic encryption schemes support distributed decryption of multi-key ciphertexts as well as allows ciphertext re-randomizability (thereby achieves quantum circuit privacy) if the underlying classical scheme also supports distributed decryption and satisfies classical circuit privacy. We show usefulness of distributed decryption and ciphertext re-randomizability for QMHE by providing efficient templates for building multi-party delegated/server-assisted quantum computation protocols from QMHE.

Additionally, due to our generic transformation, our quantum multi-key HE scheme inherits various features of the underlying classical scheme such as: identity/attribute-based, multi-hop, etc.

Neural Networks (NN) provide a powerful method for machine learning training and prediction. For effective training, it is often desirable for multiple parties to combine their data -- however, doing so conflicts with data privacy. In this work, we provide novel three-party and four-party secure computation protocols for various NN building blocks such as matrix multiplication, Rectified Linear Units, MaxPool, normalization etc. This enables us to construct three-party and four-party information-theoretically secure protocols for training and prediction of CNNs, DNNs and a number of other NN architectures such that no single party learns any information about the data.

Experimentally, we build a system and train a (A) 3-layer DNN (B) 4-layer CNN from MiniONN, and (C) 4-layer LeNet network. Compared to the state-of-the-art prior work SecureML (Mohassel and Zhang, IEEE S&P 2017) that provided (computationally-secure) protocols for only the network A in the 2 and 3-party setting, we obtain 93X and 8X improvements, respectively. In the WAN setting, these improvements are more drastic - for example, we obtain an improvement of 407X. Our efficiency gains come from a >8X improvement in communication, coupled with the complete elimination of expensive oblivious transfer protocols. In fact, our results show that the overhead of executing secure training protocols is only between 17-33X of the cleartext implementation even for networks that achieve >99% accuracy.

In a $k$-party CDS protocol, each party sends one message to a referee (without seeing the other messages) such that the referee will learn a secret held by the parties if and only if the inputs of the parties satisfy some condition (e.g., if the inputs are all equal). This simple primitive is used to construct attribute based encryption, symmetrically-private information retrieval, priced oblivious transfer, and secret-sharing schemes for any access structure. Motivated by these applications, CDS protocols have been recently studied in many papers. In this work, we study linear CDS protocols, where each of the messages of the parties is a linear function of the secret and random elements taken from some finite field. Linearity is an important property of CDS protocols as many applications of CDS protocols required it.

Our main result is a construction of linear $k$-party CDS protocols for an arbitrary function $f:[N]^{k}\rightarrow \{0,1\}$ with messages of size $O(N^{(k-1)/2})$. By a lower bound of Beimel et al. [TCC 2017], this message size is optimal. We also consider functions with few inputs that return one, and design more efficient CDS protocols for them.

CDS protocols can be used to construct secret-sharing schemes for uniform access structures, where for some $k$ all sets of size less than $k$ are unauthorized, all sets of size greater than $k$ are authorized, and each set of size $k$ can be either authorized or unauthorized. We show that our results imply that every $k$-uniform access structure with $n$ parties can be realized by a linear secret-sharing scheme with share size $\min\{ (O(n/k))^{(k-1)/2},O(n \cdot 2^{n/2})\}$. Furthermore, the linear $k$-party CDS protocol with messages of size $O(N^{(k-1)/2})$ was recently used by Liu and Vaikuntanathan [STOC 2018] to construct a linear secret-sharing scheme with share size $O(2^{0.999n})$ for any $n$-party access structure.

A distance bounding (DB) protocol is a two-party authentication protocol between a prover and a verifier which is based on the distance between the prover and the verifier. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. All these threats are covered in several security definitions and it is not possible to have a single definition covering all. In this paper, we describe a new DB model with three parties where the new party is named hardware. In this model, called secure hardware model (SHM), the hardware is held by the prover without being able to tamper with. We define an all-in-one security model which covers all the threats of DB and an appropriate privacy notion for SHM. In the end, we construct the most efficient (in terms of computation by the prover-hardware and number of rounds) and secure DB protocols achieving the optimal security bounds as well as privacy.

Masking is a common countermeasure to secure implementations against side-channel attacks. In 2003, Ishai, Sahai, and Wagner introduced a formal security model, named t-probing model, which is now widely used to theoretically reason on the security of masked implementations. While many works have provided security proofs for small masked components, called gadgets, within this model, no formal method allowed to securely compose gadgets with a tight number of shares (namely, t+1) until recently. In 2016, Barthe et al. filled this gap with maskComp, a tool checking the security of masking schemes composed of several gadgets. This tool can achieve provable security with tight number of shares by inserting mask-refreshing gadgets at carefully selected locations. However the method is not tight in the sense that there exists some compositions of gadgets for which it cannot exhibit a flaw nor prove the security. As a result, it is overconservative and might insert more refresh gadgets than actually needed to ensure t-probing security. In this paper, we exhibit the first method able to clearly state whether a shared circuit composed of standard gadgets (addition, multiplication and refresh) is t-probing secure or not. Given such a composition, our method either produces a probing-security proof (valid at any order) or exhibits a security flaw that directly imply a probing attack at a given order. Compared to maskComp, our method can drastically reduce the number of required refresh gadgets to get a probing security proof, and thus the randomness requirement for some secure shared circuits. We apply our method to a recent AES implementation secured with higher-order masking in bitslice and we show that we can save all the refresh gadgets involved in the s-box layer, which results in an significant performance gain.

We revisit the security analysis of bitslice masking which is currently the most efficient way to protect block ciphers against higher-order side-channel analysis. First, we put forward that the existing definition of Strong Non-Interference (SNI) used to reason about composability in masked implementations requires minor adaptations to capture the multiple-input multiple-output functions that bitslice implementations contain. We argue that the latter adaptations are instrumental in the analysis of a compositional strategy used in the masked AES implementations of Goudarzi and Rivain from EUROCRYPT 2017, where all multiplications are SNI with one input "refreshed" in a SNI manner. Second, we show that this strategy can be improved thanks to integer programming and report on an optimized masked AES S-box with significantly less SNI gadgets than previously required. Eventually we propose a new definition of Probe-Isolating Non-Interference (PINI) which captures a weaker yet sufficient requirement for composability in masked implementations. The latter definition allows major simplifications of the probing security analyzes of complex circuits. We show that it leads to improved performances for masked AES implementations (of order up to 20) by proposing and proving a first PINI multiplication.

We consider natural ways to extend the notion of Zero-Knowledge (ZK) Proofs beyond decision problems. Specifically, we consider search problems, and define zero-knowledge proofs in this context as interactive protocols in which the prover can establish the correctness of a solution to a given instance without the verifier learning anything beyond the intended solution, even if it deviates from the protocol.

The goal of this work is to initiate a study of Search Zero-Knowledge (search-ZK), the class of search problems for which such systems exist. This class trivially contains search problems where the validity of a solution can be efficiently verified (using a single message proof containing only the solution). A slightly less obvious, but still straightforward, way to obtain zero-knowledge proofs for search problems is to let the prover send a solution and prove in zero-knowledge that the instance-solution pair is valid. However, there may be other ways to obtain such zero-knowledge proofs, and they may be more advantageous.

In fact, we prove that there are search problems for which the aforementioned approach fails, but still search zero-knowledge protocols exist. On the other hand, we show sufficient conditions for search problems under which some form of zero-knowledge can be obtained using the straightforward way.

Fault-tolerant distributed consensus is a fundamental problem in secure distributed computing. In this work, we consider the problem of distributed consensus in directed graphs tolerating crash failures. Tseng and Vaidya (PODC'15) presented necessary and sufficient condition for the existence of consensus protocols in directed graphs. We improve the round and communication complexity of their protocol. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a restricted class of crash-tolerant consensus protocols in directed graphs.

A treasury system is a community controlled and decentralized collaborative decision-making mechanism for sustainable funding of the blockchain development and maintenance. During each treasury period, project proposals are submitted, discussed, and voted for; top-ranked projects are funded from the treasury. The Dash governance system is a real-world example of such kind of systems. In this work, we, for the first time, provide a rigorous study of the treasury system. We modeled, designed, and implemented a provably secure treasury system that is compatible with most existing blockchain infrastructures, such as Bitcoin, Ethereum, etc. More specifically, the proposed treasury system supports liquid democracy/delegative voting for better collaborative intelligence. Namely, the stake holders can either vote directly on the proposed projects or delegate their votes to experts. Its core component is a distributed universally composable secure end-to-end verifiable voting protocol. The integrity of the treasury voting decisions is guaranteed even when all the voting committee members are corrupted. To further improve efficiency, we proposed the world’s first honest verifier zero-knowledge proof for unit vector encryption with logarithmic size communication. This partial result may be of independent interest to other cryptographic protocols. A pilot system is implemented in Scala over the Scorex 2.0 framework, and its benchmark results indicate that the proposed system can support tens of thousands of treasury participants with high efficiency.

The Cascaded LRW2 tweakable block cipher was introduced by Landecker et al. at CRYPTO 2012, and proven secure up to $2^{2n/3}$ queries. There has not been any attack on the construction faster than the generic attack in $2^n$ queries. In this work we initiate the quest towards a tight bound. We first present a distinguishing attack in $2n^{1/2}2^{3n/4}$ queries against a generalized version of the scheme. The attack is supported with an experimental verification and a formal success probability analysis. We subsequently discuss non-trivial bottlenecks in proving tight security, most importantly the distinguisher's freedom in choosing the tweak values. Finally, we prove that if every tweak value occurs at most $2^{n/4}$ times, Cascaded LRW2 is secure up to $2^{3n/4}$ queries.

With the advancement of Cloud computing, people now store their data on remote Cloud servers for larger compu- tation and storage resources. However, users’ data may contain sensitive information of users and should not be disclosed to the Cloud servers. If users encrypt their data and store the encrypted data in the servers, the search capability supported by the servers will be significantly reduced because the server has no access to the data content. In this paper, we propose a Fine-grained Multi-keyword Ranked Search (FMRS) scheme over encrypted Cloud data. Specifically, we leverage novel techniques to real- ize multi-keyword ranked search, which supports both mixed “AND”, “OR” and “NO” operations of keywords and ranking according to the preference factor and relevance score. Security analysis indicates that the FMRS scheme can achieve the data confidentiality, the privacy protection of index and trapdoor, and the unlinkability of trapdoor. Extensive experiments using the real-world dataset demonstrate that the FMRS achieves better performance than the existing schemes in terms of functionality and efficiency.

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition, with other operations, as a modular addition. The starting point of our paper is afollow up of these previous results:

First, we have developped new algorithms that improve and generalize Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions.

Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005,largely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.

We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes. We also propose a generic algorithm to solve the hidden shift problem in non-abelian groups.

In order to verify the theoretical analysis we performed, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.

Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak, concluding that it does not seem to be efficient.

Event date: 19 November to 21 November 2018

Event date: 13 August to 14 August 2018

The Department of Computer, Control and Management Engineering Antonio Ruberti (DIAG) of Sapienza University of Rome invites outstanding candidates to express their interests for 1 full-time RTD-B Assistant Professor position (Tenure-track) in Cyber Security (in the context of Computer Science Engineering). The RTD-B Assistant Professor position can be converted after three years into an Associate Professor position if the national qualification (ASN) at the Associate Professor level is obtained in the Academic Discipline \"Information Processing Systems\" (ING-INF/05) of the Italian University System.

Profile

Candidates will hold a PhD from a leading research university, three years of research experience after PhD, and an appropriate record of publications in highly ranked international conferences and journals. Teaching experience is also positively considered.

Position

Successful candidates will be engaged in first-class research in the area of Cyber Security, will supervise Master Thesis and PhD students in their fields, will teach in the Master degree in Cyber Security at Sapienza University of Rome and in the degree of Computer Science Engineering, will be involved in collaborations with industry and public bodies, and will take an important role at the Inter-Departmental Research Center of Cyber Intelligence and Information Security (CIS) at Sapienza University of Rome. Appointments are full-time. The salary is competitive. We especially welcome expression of interests from female scholars.

Expression of Interest

People who are interested in this position should send the following to recruitment (at) diag.uniroma1.it:

1. Curriculum vitae

2. 3-page (max) research statement including the research program that the candidate intends to pursue while at Sapienza.

Expressions of interest should preferably be sent before the end of May 2018. For further information, please consult recruitment (at) diag.uniroma1.it

Closing date for applications: 31 May 2018