International Association
for Cryptologic Research

In state-of-the-art design paradigm, time, space and power efficiency are considered the primary design constraints. Quite often, this approach adversely impacts the security of the overall system, especially when security is adopted as a countermeasure after some vulnerability is identified. In this position paper, we motivate the idea that security should also be considered as an architectural design constraint in addition to time, space and power. We show that security and efficiency objectives along the three design axes of time, space and power are in fact tightly coupled while identifying that security stands in direct contrast with them across all layers of architectural design. We attempt to prove our case utilizing a proof-by-evidence approach wherein we refer to various works across literature that explicitly imply the eternal conflict between security and efficiency. Thus, security has to be treated as a design constraint from the very beginning. Additionally, we advocate a security-aware design flow starting from the choice of cryptographic primitives, protocols and system design.

Threshold secret sharing allows a dealer to split a secret into $n$ shares such that any authorized subset of cardinality at least $t$ of those shares efficiently reveals the secret, while at the same time any unauthorized subset of cardinality less than $t$ contains no information about the secret. Leakage-resilience requires that the secret remains hidden even if the unauthorized subset is given a bounded amount of additional leakage from every share.

In this work, we study leakage-resilient secret sharing schemes with information-theoretic security and prove a lower bound on the share size and the required amount randomness of any such scheme. We prove that for any leakage-resilient secret sharing scheme either the amount of randomness across all shares or the share size has to be linear in $n$. More concretely, for a secret sharing scheme with $p$-bit long shares, $\ell$-bit leakage per share, where $\widehat{t}$ shares uniquely define the remaining $n - \widehat{t}$ shares, it has to hold that $$ p \ge \frac{\ell (n - t)}{\widehat{t}}\ . $$

We use our lower bound to gain further insights into a question that was recently posed by Benhamouda et al. (CRYPTO'18), who ask to what extend existing regular secret sharing schemes already provide protection against leakage. The authors proved that Shamir's secret sharing is leakage-resilient for very large thresholds $t = n - \mathcal{O}(\log n)$ and conjectured that it is also $1$-bit leakage-resilient for any threshold that is a constant fraction of the total number of shares. We do not disprove their conjecture, but show that two mild and natural strengthenings thereof are false, thus concluding that their conjecture is essentially the best one could hope for.

The results described above only apply to secret sharing schemes with information-theoretic security, since the lower bound proof relies on an adversary that can enumerate all possible secret sharings and thus runs in time exponential in at least the share size $p$ and the full reconstruction threshold $\widehat{t}$. In addition, we present a conceptually simple and highly efficient attack for the specific case of $2$-out-of-$n$ Shamir secret sharing that only requires $1$ bit of leakage, has a running time of $\bigO{n}$ field operations, and could easily be run in practice by a computationally bounded adversary.

At Real World Crypto 2017, Joan Daemen won the Levchin Prize and announced that he believed permutation-based crypto was the future of symmetric cryptography. At the same conference Mike Hamburg introduced Strobe, a symmetric protocol framework capable of protecting sessions as well as building symmetric cryptographic primitives for the single cost of Joan Daemen’s permutation Keccak. The next year, at Real World Crypto 2018 Trevor Perrin came to talk about the Noise protocol framework, a modern TLS-like protocol with similar traits but with a focus on flexibility, offering many handshake patterns to choose from in order to authenticate peers of a connection in different ways. Disco is the natural merge of the two projects, creating a new protocol based solely on two unique primitives: Curve25519 and the Keccak permutation (or more correctly its wrapper Strobe). Experimental results show that a library based on Disco can be implemented on top of these two cryptographic primitives with only a thousand lines of code. This, while offering both a flexible way to encryption sessions and a complete cryptographic library for all of an application’s needs.

Murphy, Murky, Mopey, Moody, and Morose decide to write a paper together over the Internet and submit it to the prestigious CRYPTO’19 conference that has the most amazing PC. They encounter a few problems. First, not everyone is online every day: some are lazy and go skiing on Mondays; others cannot use git correctly and they are completely unaware that they are losing messages. Second, a small subset of the co-authors may be secretly plotting to disrupt the project (e.g., because they are writing a competing paper in stealth). Suppose that each day, sufficiently many honest co-authors are online (and use git correctly); moreover, suppose that messages checked into git on Monday can be correctly received by honest and online co-authors on Tuesday or any future day. Can the honest co-authors successfully finish the paper in a small number of days such that they make the CRYPTO deadline; and perhaps importantly, can all the honest co-authors, including even those who are lazy and those who sometimes use git incorrectly, agree on the final theorem?

In light of widespread misuse of personal data, we enable users to control the sharing and use of their data, even when offline, by binding that data to policies. A policy specifies the allowed function, conditions guarding the execution (based on the history of all prior computations on that data), and identities of the input providers and output recipients. For this level of control, we aim for a compute system that ensures policy compliance to the input providers, and fairness (i.e., either all or no party gets the output) to the output recipients, without requiring these parties to trust each other or the compute host.

Recently, trusted execution environments (TEEs), such as Intel SGX and Sanctum enclaves, are finding applications in outsourced computing on sensitive data. However, since TEEs are at the mercy of an untrusted host for storage and network communication, they are incapable of enforcing history-dependent policies or fairness. For instance, against a user's wish that only an aggregate function over her entire data is revealed, an adversarial host can repeatedly evaluate that aggregate function on different subsets of her dataset, and learn the individual records. The adversary may also collude and deliver the output only to a subset of the output recipients, thus violating fairness.

This paper presents LucidiTEE, the first system to enable multiple parties to jointly compute on large-scale private data, while guaranteeing that the aforementioned policies are enforced even when the input providers are offline, and guaranteeing fairness to all output recipients. To that end, LucidiTEE develops a set of novel protocols between a network of TEEs and a distributed, shared, append-only ledger. LucidiTEE uses the ledger only to enforce policies; it does not store inputs, outputs, or state on the ledger, nor does it duplicate execution amongst the participants, which allows it to scale to large data and large number of parties.

We demonstrate several policy-based applications including personal finance, federated machine learning, fair $n$-party information exchange, and private set intersection for medical records.

We study $(\ell,\ell)$-isogeny graphs of principally polarised supersingular abelian surfaces (PPSSAS). The $(\ell,\ell)$-isogeny graph has cycles of small length that can be used to break the collision resistance assumption of the genus two isogeny hash function suggested by Takashima. Algorithms for computing $(2,2)$-isogenies on the level of Jacobians and $(3,3)$-isogenies on the level of Kummers are used to develop a genus two version of the supersingular isogeny Diffie--Hellman protocol of Jao and de~Feo. The genus two isogeny Diffie--Hellman protocol achieves the same level of security as SIDH but uses a prime with a third of the bit length.

We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme to LWE, instead we reduce it to a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

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.