International Association
for Cryptologic Research

Threshold private set intersection enables Alice and Bob who hold sets $A$ and $B$ of size $n$ to compute the intersection $A \cap B$ if the sets do not differ by more than some threshold parameter $t$. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of $\Omega(t)$. We show that an almost matching upper bound of $\tilde{\mathcal{O}}(t)$ can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of $\tilde{\mathcal{O}}(t^2)$. For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings.

Prior to this work, all previous protocols had a communication complexity of $\Omega(n)$. Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter $t$ and only logarithmically on the set size $n$.

A secret sharing scheme allows a dealer to distribute shares of a secret among a set of $n$ parties $P=\{p_1,\dots,p_n\}$ such that any authorized subset of parties can reconstruct the secret, yet any unauthorized subset learns nothing about it. The family $\mathcal{A} \subseteq 2^P$ of all authorized subsets is called the access structure. Classic results show that if $\mathcal{A}$ contains precisely all subsets of cardinality at least $t$, then there exists a secret sharing scheme where the length of the shares is proportional to $\lg n$ bits plus the length of the secret. However, for general access structures, the best known upper bounds have shares of length exponential in $n$, whereas the strongest lower bound shows that the shares must have length at least $n/\log n$. Beimel conjectured that the exponential upper bound is tight, but proving it has so far resisted all attempts. In this paper, we almost prove Beimel's conjecture by showing that there exists an access structure $\mathcal{A}$, such that any secret sharing scheme for $\mathcal{A}$ must have either exponential share length, or the function used for reconstructing the secret by authorized parties must have an exponentially long description. As an example corollary, we conclude that if one insists that authorized parties can reconstruct the secret via a constant fan-in boolean circuit of size polynomial in the share length, then there exists an access structure that requires a share length that is exponential in $n$.

Despite recent advances in the area of pairing-friendly Non-Interactive Zero-Knowledge proofs, there have not been many efficiency improvements in constructing arguments of satisfiability of quadratic (and larger degree) equations since the publication of the Groth-Sahai proof system (JoC'12). In this work, we address the problem of aggregating such proofs using techniques derived from the interactive setting and recent constructions of SNARKs. For certain types of quadratic equations, this problem was investigated before by González et al. (ASIACRYPT'15). Compared to their result, we reduce the proof size by approximately 50% and the common reference string from quadratic to linear, at the price of using less standard computational assumptions. A theoretical motivation for our work is to investigate how efficient NIZK proofs based on falsifiable assumptions can be. On the practical side, quadratic equations appear naturally in several cryptographic schemes like shuffle and range arguments.

We show that the correlation of any quadratic Boolean function can be read out from its so-called disjoint quadratic form. We further propose a polynomial-time algorithm that can transform an arbitrary quadratic Boolean function into its disjoint quadratic form. With this algorithm, the exact correlation of quadratic Boolean functions can be computed efficiently.

We apply this method to analyze the linear trails of MORUS (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of MORUS-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of MORUS-like key-stream generators. As a result, a set of trails with correlation $2^{-38}$ is identified for all versions of full MORUS, while the correlations of previously published best trails for MORUS-640 and MORUS-1280 are $2^{-73}$ and $2^{-76}$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on MORUS-1280-256 from $2^{152}$ to $2^{76}$. These new trails also lead to the first distinguishing and message-recovery attacks on MORUS-640-128 and MORUS-1280-128 with surprisingly low complexities around $2^{76}$.

Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.

Event date: 16 December to 20 December 2019
Submission deadline: 12 July 2019
Notification: 25 September 2019

Event date: 25 October to 27 October 2019
Submission deadline: 6 May 2019
Notification: 8 July 2019

Applications are invited for a PhD fellowship/scholarship at the Department of Engineering, Aarhus University, Denmark. The position is available from 1 August 2019 or later.

Title: Verifiable cryptographic software

Zero-knowledge proofs are integral for deploying privacy-preserving cryptocurrencies and other blockchain applications, as they represent a fundamental building block for proving statements about confidential data. The most popular framework for such proofs is based on cryptographic pairings defined over elliptic curves, where pairing-based zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) underlie private transactions.

The PhD candidate will investigate techniques to develop a formally verified efficient software library for pairing-based cryptography, as means to support current blockchain projects relying on zero-knowledge proofs. The PhD candidate will also be involved in other educational activities, such as serving as teaching assistant in courses related to his/her expertise.

The project is a collaboration between researchers from the Departments of Engineering and Computer Science; the DIGIT Centre for Digitalisation, Big Data and Data Analytics; and the recently opened Concordium Blockchain Research Center.

Qualifications:

We are looking for dedicated and enthusiastic applicants, preferably with a Master’s degree in Computer Science/Engineering, Mathematics or related discipline. A theoretical background with cryptography or formal verification will be important for the project. Practical experience with software development and the Coq proof assistant will be seen as a plus. Analytical and critical thinking are naturally essential to pursuing a PhD degree. Further requirements are fluency in English, good reporting/organization skills and being able to work independently.

Closing date for applications: 1 May 2019

Contact: Diego F. Aranha, Assistant Professor, dfaranha (at) eng.au.dk; or Bas Spitters, Associate Professor, spitters (at) cs.au.dk

More information: https://phd.scitech.au.dk/for-applicants/apply-here/may-2019/verifiable-cryptographic-software/

Excellent candidates interested in pursuing a PhD in security/cryptography are invited to apply for this PhD studentship in the Department of Computer Science at the University of Warwick. This scholarship covers full UK/EU fees and a stipend payable at current UK Research Council rates for 3.5 years. Outstanding overseas students are also encouraged to apply, however a gap in the tuition fee will need to be filled. There is no formal closing date for this scholarship as it will be closed when it\'s filled. Therefore, candidates are advised to apply as early as possible.

For informal inquiries, please contact Professor Feng Hao, feng.hao (at) warwick.ac.uk, enclosing a CV and a short description of your relevant background and interests.

The Computer Science Department at Warwick is a leading department in the UK. In the 2014 Research Evaluation Framework (REF) which all UK universities participated in, Warwick computer science was ranked the 1st in terms of research output, 2nd in terms of impact and 2nd overall. It is also highly regarded for its research culture, informal environment, excellent students, and beautiful campus.

Closing date for applications: 1 August 2019

More information: https://warwick.ac.uk/fac/sci/dcs/admissions/postgraduateresearch/researchstudentships/?newsItem=8a1785d769003af00169015

The NTNU Applied Cryptology Lab at NTNU has an open PhD position (4 years) in statistical disclosure control. Of particular interest are development of differentially private response mechanisms for distributed data, longitudinal data, and theory around privacy as an only partially renewable resource.

Closing date for applications: 1 May 2019

Contact: Staal A. Vinterbo, Staal.Vinterbo (at) ntnu.no

More information: https://www.jobbnorge.no/en/available-jobs/job/163521/

We search a candidate who is internationally highly recognized for research on the foundations and methods of software engineering, specifically, the construction and analysis of large-scale software systems with a focus on security and privacy properties. This includes topics like static and dynamic program analysis for programming languages and their ecosystems, test-based quality assurance techniques to identify security vulnerabilities, e.g., test case generation, test optimization, fuzzing, program transformations, e.g., automatic program repair, constructive or interactive approaches to support developers in the engineering of secure systems.

For more details and application portal, see URL below

Closing date for applications: 14 March 2019

Contact: Prof. Dr. Frank Kargl, https://www.uni-ulm.de/in/vs/inst/team/frank-kargl/

More information: https://stellenangebote.uni-ulm.de/jobposting/95503659d66923316e3b202e35ce7405db5365d1

We are looking for highly-skilled, motivated, and driven students for multiple research internships at the HP Inc. Security Lab in Bristol, UK. As an intern you will help us advance the state-of-the-art in system security. We’re looking for people to work on a range of topics: from researching cyber-resilient hardware and software security architectures, designing security for next generation cyber-physical infrastructures, to security analytics, machine learning for security, and emerging 3D printing ecosystems.

Our industrial research lab is a unique environment at the intersection between academic research and real-world innovation in partnership with HP global business units. We provide interns with a unique opportunity to learn about the realities of both worlds, and to contribute research that may eventually impact the HP products and solutions used by millions of people across the globe.

Internships will start between February and July 2019, for a preferred duration of 5-6 months.

We welcome applications from full time students with the relevant skills and experience at Masters and PhD level.

Closing date for applications: 31 March 2019

Contact: Philippa Bayley

Security Lab Operations Manager

philippa.bayley (at) hp.com

More information: https://h30631.www3.hp.com/job/bristol/hp-security-lab-intern/3544/10307305

Advancements in deep learning enable cloud servers to provide inference-as-a-service for clients. In this scenario, clients send their raw data to the server to run the deep learning model and send back the results. One standing challenge in this setting is to ensure the privacy of the clients' sensitive data. Oblivious inference is the task of running the neural network on the client's input without disclosing the input or the result to the server. This paper introduces XONN, a novel end-to-end framework based on Yao's Garbled Circuits (GC) protocol, that provides a paradigm shift in the conceptual and practical realization of oblivious inference. In XONN, the costly matrix-multiplication operations of the deep learning model are replaced with XNOR operations that are essentially free in GC. We further provide a novel algorithm that customizes the neural network such that the runtime of the GC protocol is minimized without sacrificing the inference accuracy.

We design a user-friendly high-level API for XONN, allowing expression of the deep learning model architecture in an unprecedented level of abstraction. We further provide a compiler to translate the model description from high-level Python (i.e., Keras) to that of XONN. Extensive proof-of-concept evaluation on various neural network architectures demonstrates that XONN outperforms prior art such as Gazelle (USENIX Security'18) by up to 7×, MiniONN (ACM CCS'17) by 93×, and SecureML (IEEE S&P'17) by 37×. State-of-the-art frameworks require one round of interaction between the client and the server for each layer of the neural network, whereas, XONN requires a constant round of interactions for any number of layers in the model. XONN is first to perform oblivious inference on Fitnet architectures with up to 21 layers, suggesting a new level of scalability compared with state-of-the-art. Moreover, we evaluate XONN on four datasets to perform privacy-preserving medical diagnosis. The datasets include breast cancer, diabetes, liver disease, and Malaria.

The early registration deadline for FSE 2019 is approaching soon (February 26). After that date, registration prices will increase!

You can register online at https://secure.iacr.org/conferences/fse2019/register/.

FSE 2019 will take place in Paris, France during March 25-28, 2019. For more information on the conference please visit https://fse.iacr.org/2019.

Frit is a new lightweight 384-bit cryptographic permutation proposed by Simon et al., which is designed for resisting fault injection and performs competitively in both hardware and software. Dobraunig et al. first studied Frit in EM construction, and left an open problem to explore the security of Frit in a sponge or duplex modes. In this paper, by introducing a new key-dependent cube attack method, we partially answer the open question by Dobraunig et al. and give some key-recovery attacks on the rounded-reduced Frit used in duplex authenticated encryption mode (Frit-AE). Our results cover all the versions of Frit-AE and include some practical key-recovery attacks that could recover the key within several minutes.

In this paper, we introduce updatable anonymous credential systems (UACS) and use them to construct a new privacy-preserving incentive system. In a UACS, a user holding a credential certifying some attributes can interact with the corresponding issuer to update his attributes. During this, the issuer knows which update function is run, but does not learn the user's previous attributes. Hence the update process preserves anonymity of the user. One example for a class of update functions are additive updates of integer attributes, where the issuer increments an unknown integer attribute value $v$ by some known value $k$. This kind of update is motivated by an application of UACS to incentive systems. Users in an incentive system can anonymously accumulate points, e.g. in a shop at checkout, and spend them later, e.g. for a discount.

In this paper, we (1) formally define UACS and their security, (2) give a generic construction for UACS supporting arbitrary update functions, and (3) construct a practically efficient incentive system using UACS.

Profiling side-channel attacks represent the most powerful category of side-channel attacks. There, we assume that the attacker has access to a clone device in order to profile the device. Additionally, we assume the attacker to be unbounded in power in an effort to give the worst-case security analysis. In this paper, we start from a different premise and consider an attacker in a restricted setting where he is able to profile only a limited number of measurements. To that end, we propose a new framework for profiling side-channel analysis that we call the Restricted Attacker framework. With it, we enforce the attackers to really conduct the most powerful attack possible but also we provide a setting that inherently allows a more fair analysis among attacks. Next, we discuss the ramifications of having the attacker with unbounded power when considering neural network-based attacks. There, we are able to prove that the Universal Approximation Theorem can result in neural network-based attacks being able to break implementations with only a single measurement. Those considerations further strengthen the need for the Restricted Attacker framework.

Many secure cache designs have been proposed in literature with the aim of mitigating different types of cache timing-based side-channel attacks. However, there has so far been no systematic analysis of how these secure cache designs can, or cannot, protect against different types of the timing-based attacks. To provide a means of analyzing the caches, this paper first presents a novel three-step modeling approach to exhaustively enumerate all the possible cache timing-based side-channel vulnerabilities. The model covers not only attacks that leverage cache accesses or flushes from the local processor core, but also attacks that leverage changes in the cache state due to the cache coherence protocol actions from remote cores. Moreover, both conventional attacks and speculative execution attacks are considered. With the list of all possible cache timing side-channel vulnerabilities derived from the three-step model, this work further analyzes each of the existing secure cache designs to show which types of timing-based side-channel vulnerabilities each secure cache can mitigate. Based on the security analysis of the existing secure cache designs, this paper further summaries different techniques gleaned from the secure cache designs and the technique’s ability help mitigate different types of cache timing-based side-channel vulnerabilities.

We present two new Verifiable Delay Functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and some drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.

Boldyreva et al. (Eurocrypt 2012) defined a fine-grained security model capturing ciphertext fragmentation attacks against symmetric encryption schemes. The model was extended by Albrecht et al. (CCS 2016) to include an integrity notion. The extended security model encompasses important security goals of SSH that go beyond confidentiality and integrity to include length hiding and denial-of-service resistance properties. Boldyreva et al. also defined and analysed the InterMAC scheme, while Albrecht et al. showed that InterMAC satisfies stronger security notions than all currently available SSH encryption schemes. In this work, we take the InterMAC scheme and make it fully ready for use in practice. This involves several steps. First, we modify the InterMAC scheme to support encryption of arbitrary length plaintexts and we replace the use of Encrypt-then-MAC in InterMAC with modern nonce-based authenticated encryption. Second, we describe a reference implementation of the modified InterMAC scheme in the form of the library libInterMAC. We give a performance analysis of libInterMAC. Third, to test the practical performance of libInterMAC, we implement several InterMAC-based encryption schemes in OpenSSH and carry out a performance analysis for the use-case of file transfer using SCP. We measure the data throughput and the data overhead of using InterMAC-based schemes compared to existing schemes in OpenSSH. Our analysis shows that, for some network set-ups, using InterMAC-based schemes in OpenSSH only moderately affects performance whilst providing stronger security guarantees compared to existing schemes.

Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation. In recent years, a large effort has undergone into designing and implementing MPC protocols that can be used in practice. This paper focuses on the specific case of three-party computation with an honest majority, which is among the most popular models for real-world applications of MPC. Somewhat surprisingly, despite its significant popularity, there are currently no practical solutions for evaluating arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words, that are secure against active adversaries that may arbitrarily deviate from the protocol description. Existing solutions are either only passively secure or require the computations to be performed over prime fields, which do not match real-world system architectures. This is unfortunate, since it requires application developers to redesign their applications for the models of computation that are provided by existing MPC frameworks, rather than the MPC frameworks matching the needs of the developers.

In this paper we present the first fully-fledged implementation of an MPC framework that can evaluate arithmetic circuits with arbitrary word sizes. Our framework is based on a new protocol, which improves the communication overhead of the best known previous solutions by a factor of two. We provide extensive benchmarks of our framework in a LAN and in different WAN settings, showing that the online overhead for achieving active security is less than two, when compared to the best solutions for the same setting with passive security. Concretely, for the case of 32- and 64-bit words, we show that our framework can evaluate $10^6$ multiplication gates per second.