International Association
for Cryptologic Research

Multivariate cryptography studies applications of endomorphisms of K[x_1, x_2, …, x_n] where K is a finite commutative ring. The importance of this direction for the construction of multivariate digital signature systems is well known. We suggest modification of the known digital signature systems for which some of cryptanalytic instruments were found . This modification prevents possibility to use recently developed attacks on classical schemes such as rainbow oil and vinegar system, and LUOV. Modification does not change the size of hashed messages and size of signatures. Basic idea is the usage of multivariate messages of unbounded degree and polynomial density for the construction of public rules. Modified algorithms are presented for standardization and certification studies.

In recent years, deep neural networks (DNN) have become an important type of intellectual property due to their high performance on various classification tasks. As a result, DNN stealing attacks have emerged. Many attack surfaces have been exploited, among which cache timing side-channel attacks are hugely problematic because they do not need physical probing or direct interaction with the victim to estimate the DNN model. However, existing cache-side-channel-based DNN reverse engineering attacks rely on analyzing the binary code of the DNN library that must be shared between the attacker and the victim in the main memory. In reality, the DNN library code is often inaccessible because 1) the code is proprietary, or 2) memory sharing has been disabled by the operating system. In our work, we propose GANRED, an attack approach based on the generative adversarial nets (GAN) framework which utilizes cache timing side-channel information to accurately recover the structure of DNNs without memory sharing or code access. The benefit of GANRED is four-fold. 1) There is no need for DNN library code analysis. 2) No shared main memory segment between the victim and the attacker is needed. 3) Our attack locates the exact structure of the victim model, unlike existing attacks which only narrow down the structure search space. 4) Our attack efficiently scales to deeper DNNs, exhibiting only linear growth in the number of layers in the victim DNN.

Gated Recurrent Unit (GRU) has broad application fields, such as sentiment analysis, speech recognition, malware analysis, and other sequential data processing. For low-cost deployment and efficient machine learning services, a growing number of model owners choose to deploy the trained GRU models through Machine-learning-as-a-service (MLaaS). However, privacy has become a significant concern for both model owners and prediction clients, including model weights privacy, input data privacy, and output results privacy. The privacy leakage may be caused by either external intrusion or insider attacks. To address the above issues, this research designs a framework for privacy-preserving GRU models, which aims for privacy scenarios such as predicting on textual data, network packets, heart rate data, and so on. In consideration of accuracy and efficiency, this research uses additive secret sharing to design the basic operations and gating mechanisms of GRU. The protocols can meet the security requirements of privacy and correctness under the Universal Composability framework with the semi-honest adversary. Additionally, the framework and protocols are realized with a proof-of-concept implementation. The experiment results are presented with respect to time consumption and inference accuracy.

Oblivious transfer (OT) is an essential tool of cryptographic protocols. It can serve as a building block for realizing all multiparty functionalities. The strongest security notion against malicious adversaries is universal composibility (UC-secure). Due to the rigorous algebraic structures and operations, achieving the specific security notion with isogenies is believed to be difficult. Hence, it is an open problem to have an efficient UC-secure OT oblivious transfer scheme based on isogenies.

In this work, we propose the first isogeny-based UC-secure oblivious transfer protocol in the presence of malicious adversaries without analogues in the Diffie-Hellman setting. The simple and compact CSIDH-based scheme consists of a constant number of isogeny computations. The underlying relaxed problem is called the computational reciprocal CSIDH problem which we can prove equivalent to the computational CSIDH problem with a quantum reduction.

The private join and compute (PJC) functionality enables secure computation over data distributed across different databases, which is a functionality with a wide range of applications, many of which address settings where the input databases are of significantly different sizes.

We introduce the notion of private information retrieval (PIR) with default, which enables two-party PJC functionalities in a way that hides the size of the intersection of the two databases and incurs sublinear communication cost in the size of the bigger database. We provide two constructions for this functionality, one of which requires offline linear communication, which can be amortized across queries, and one that provides sublinear cost for each query but relies on more computationally expensive tools. We construct inner-product PJC, which has applications to ads conversion measurement and contact tracing, relying on an extension of PIR with default. We evaluate the efficiency of our constructions, which can enable $\mathbf{2^{12}}$ PIR with default lookups on a database of size $\mathbf{2^{30}}$ (or inner-product PJC on databases with such sizes) with the communication of $\mathbf{945}$MB, which costs less than $\mathbf{\$0.04}$ for the client and $\mathbf{\$5.22}$ for the server.

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: - the Learning with Error (LWE) assumption (with subexponential modulus-to-noise ratio); - the Decisional Composite Residuosity (DCR) assumption; and, - a circular security conjecture regarding the Gentry-Sahai-Water’s (GSW) and the Damgard-Jurik (DJ) encryption schemes.

More precisely, the circular security conjecture states that a notion of leakage-resilient security (which we refer to as “shielded randomness leakage security”) satisfied by GSW (assuming LWE) is retained in the presence of a key-cycle w.r.t. GSW and DJ.

Our work thus places iO on qualitatively similar assumptions as (unlevelled) FHE, for which known constructions also rely on a circular security conjecture.

We construct a VBB and perfect circuit-hiding obfuscator for evasive deterministic finite automata using a matrix encoding scheme with a limited zero-testing algorithm. We construct the matrix encoding scheme by extending an existing matrix FHE scheme. Using obfuscated DFAs we can for example evaluate secret regular expressions or disjunctive normal forms on public inputs. In particular, the possibility of evaluating regular expressions solves the open problem of obfuscated substring matching.

Side-channel attacks exploit information that is leaked from hardware. The differential power analysis (DPA) attack aims at extracting sensitive information that is processed by the operations in a cryptographic primitive. Power traces are collected and subsequently processed using statistical methods. The ChipWhisperer Nano is a low-cost, open-source device that can be used to implement and study side-channel attacks. This paper describes how the DPA attack with the difference of means method can be used to extract the secret key from both an 8-bit and a 32-bit implementation of AES using the ChipWhisperer Nano. The results show that although it is possible to carry out the attack on both implementations, the attack on the 32-bit implementation requires more traces than the 8-bit implementation.

In 2019, Gu Chunsheng introduced Integer-RLWE, a variant of RLWE devoid of some of its efficiency flaws. Most notably, he proposes a setting where $n$ can be an arbitrary positive integer, contrarily to the typical construction $n = 2^k$. In this paper, we analyze the new problem and implement the classical meet-in-the-middle and lattice-based attacks. We then use the peculiarity of the construction of $n$ to build an improved lattice-based attack in cases where $n$ is composite with an odd divisor. For example, for parameters $n = 2000$ and $q = 2^{33}$, we reduce the estimated complexity of the attack from $2^{288}$ to $2^{164}$. We also present reproducible experiments confirming our theoretical results.

CSIDH is an isogeny-based post-quantum key establishment protocol proposed in 2018. In this work, we analyze attacking implementations of CSIDH which use dummy isogeny operations using fault injections from a mathematical perspective. We detail an attack by which the private key can be learned by the attacker up to sign with absolute certainty using $\sum \lceil \log_2(b_i) + 1 \rceil$ fault attacks on pairwise distinct group action evaluations under the same private key under ideal conditions using a binary search approach, where $\vec{b}$ is the bound vector defining the keyspace. As a countermeasure to this attack, we propose randomly mixing the real degree $\ell_j$ isogenies together with the dummy ones by means of a binary decision vector. To evaluate the efficacy of this countermeasure, we formulate a probability-based attack on this randomized scheme using a maximum likelihood approach and simulate the attack using 6 bound vectors used in previous CSIDH implementations. We found that the number of attacks required under our model to reach just 1% certainty about the key increased by a factor between 8--12 over the standard approach in the setting of signed private keys and a factor between 28--45 using non-negative private keys, depending on $\vec{b}$. We derive theoretical upper bounds on the number of attacks required to reach a specified certainty threshold about the key under our model. Based on our data and the minimal additional overhead required, we recommend all future implementations of CSIDH to employ a randomized decision vector approach. Finally since our model assumes fault attacks provide no information on the sign of the key, we use a technique based on Gray codes to optimize the standard meet-in-the-middle attack for learning the sign of the key values once their magnitudes have been learned through fault attacks. We estimate that, on average, this optimized technique uses approximately 88% fewer field-multiplication-equivalent operations over the standard approach.

Event date: 3 May to 6 May 2021
Submission deadline: 4 December 2020
Notification: 19 February 2021

Event date: 5 November to 6 November 2020
Submission deadline: 10 September 2020
Notification: 26 October 2020

Event date: 3 September to 4 September 2020

DFINITY is reimagining the Internet as a public network that hosts secure software and services. The Internet Computer is a new technology stack that is unhackable, fast, scales to billions of users around the world, and supports a new kind of autonomous software that promises to reverse Big Tech’s monopolization of the internet.

DFINITY is looking for a full-time Cryptography Researcher, specialized in practical and provably secure cryptographic protocols for blockchains. The main task will be to design, develop, and prove secure, efficient cryptographic protocols for a distributed system and you will contribute in creating a high-performance blockchain computer. We offer a flexible work environment and an opportunity to collaborate with a dynamic and talented team of researchers and developers from around the world.

Requirements:

PhD in Cryptography, emphasis on efficient and provably secure protocols

Excellent record of peer-reviewed publications, in particular at IACR, ACM, and IEEE conferences

Experience in the implementation of cryptographic protocols in C or Rust

Good understanding of practical systems and their security

Responsibilities:

Identify functional and security requirements of cryptographic protocols for the DFINITY platform

Design provably secure, scalable and practical cryptographic protocols

Design security models, capturing requirements and adversarial models

Provide full implementation specification of cryptographic protocols

Collaborate with a team of Researchers and Developers across our global research centers

Participate in software architecture decisions, providing necessary information in a clear fashion

Collaborate with engineers to implement cryptographic protocols

Write high-quality research papers targeted at top conferences and journals

Represent the company in academic and industry conferences and share technical information with the public

Closing date for applications:

Contact: Jan Camenisch - please submit via https://dfinity.org/careers/

More information: https://dfinity.org/careers/

The isogeny-based scheme CSIDH is a promising candidate for quantum-resistant static-static key exchanges with very small public keys, but is inherently difficult to implement in constant time. In the current literature, there are two directions for constant-time implementations: algorithms containing dummy computations and dummy-free algorithms. While the dummy-free implementations come with a 2x slowdown, they offer by design more resistance against fault attacks. In this work, we evaluate how practical fault injection attacks are on the constant-time implementations containing dummy calculations. We present three different fault attacker models. We evaluate our fault models both in simulations and in practical attacks. We then present novel countermeasures to protect the dummy isogeny computations against fault injections. The implemented countermeasures result in an overhead of 7% on the Cortex-M4 target, falling well short of the 2x slowdown for dummy-less variants.

WebAuthn, forming part of FIDO2, is a W3C standard for strong authentication, which employs digital signatures to authenticate web users whilst preserving their privacy. Owned by users, WebAuthn authenticators generate attested and unlinkable public-key credentials for each web service to authenticate users. Since the loss of authenticators prevents users from accessing web services, usable recovery solutions preserving the original WebAuthn design choices and security objectives are urgently needed.

We examine Yubico's recent proposal for recovering from the loss of a WebAuthn authenticator by using a secondary backup authenticator. We analyse the cryptographic core of their proposal by modelling a new primitive, called Asynchronous Remote Key Generation (ARKG), which allows some primary authenticator to generate unlinkable public keys for which the backup authenticator may later recover corresponding private keys. Both processes occur asynchronously without the need for authenticators to export or share secrets, adhering to WebAuthn's attestation requirements. We prove that Yubico's proposal achieves our ARKG security properties under the discrete logarithm and PRF-ODH assumptions in the random oracle model. To prove that recovered private keys can be used securely by other cryptographic schemes, such as digital signatures or encryption schemes, we model compositional security of ARKG using composable games by Brzuska et al. (ACM CCS 2011), extended to the case of arbitrary public-key protocols.

As well as being more general, our results show that private keys generated by ARKG may be used securely to produce unforgeable signatures for challenge-response protocols, as used in WebAuthn. We conclude our analysis by discussing concrete instantiations behind Yubico's ARKG protocol, its integration with the WebAuthn standard, performance, and usability aspects.

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $\lambda$:

- The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^\lambda)$,

- The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^\epsilon}$, where $k$ is the dimension of the LWE secret,

- The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^\delta$, where $\ell$ is the dimension of the LPN secret,

- The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$,

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

We present CrypTFlow2, a cryptographic framework for secure inference over realistic Deep Neural Networks (DNNs) using secure 2-party computation. CrypTFlow2 protocols are both correct -- i.e., their outputs are bitwise equivalent to the cleartext execution -- and efficient -- they outperform the state-of-the-art protocols in both latency and scale. At the core of CrypTFlow2, we have new 2PC protocols for secure comparison and division, designed carefully to balance round and communication complexity for secure inference tasks. Using CrypTFlow2, we present the first secure inference over ImageNet-scale DNNs like ResNet50 and DenseNet121. These DNNs are at least an order of magnitude larger than those considered in the prior work of 2-party DNN inference. Even on the benchmarks considered by prior work, CrypTFlow2 requires an order of magnitude less communication and 20x-30x less time than the state-of-the-art.

In distributed symmetric-key encryption (DiSE), a set of n distributed servers share a key (or key set) and any t, t <= n, servers can collectively use the shared key (or key set) in a DiSE transaction to encrypt a message or decrypt a ciphertext without reconstructing the shared key (or key set). Each participating server contributes one or more partial results and one participating server called the initiator combines all partial results into a final result. An adversary who has compromised up to (t-1) servers will not be able to access the shared key (or key set).

Due to the distributed nature of DiSE, a DiSE server that has been compromised by an adversary may return wrong partial results to the initiator. Worse, multiple DiSE servers compromised by the same adversary may collude to send back wrong partial results. In this article we developed a robust DiSE that allows an honest initiator to detect wrong partial results by an adversary. The robustness of our DiSE is built through redundant computation. Our robust DiSE can detect wrong partial results by an adversary who has compromised up to min(t-1, n-t) servers. Next, the honest-initiator assumption is removed by rotating the initiator role among active servers across multiple DiSE transactions. A scalable, industry-level implementation for the robust DiSE has been developed and two cases, (t=3, n=5) and (t=16, n=24), have been tested to show the feasibility of robust DiSE. Our robust DiSE can be used to build intrusion-tolerant applications, such as intrusion-tolerant database encryption.

Distance-bounding protocols provide a means for a verifier (e.g., an RFID reader) to estimate his relative distance to a prover (e.g., a bankcard), in order to counteract relay attacks. We propose FlexiDB, a new cryptographic model for DB, parameterised over fine-grained corruptions. It allows to consider trivial cases, classical cases but also new, generalised scenarios in which we show manipulating differently-corrupt provers at once leads to new attacks. We propose a proof-of-concept mechanisation of FlexiDB in the interactive cryptographic prover EasyCrypt, and use it to prove a flavour of man-in-the-middle security on a variant of MasterCard's contactless-payment protocol.