International Association
for Cryptologic Research

A commitment scheme allows a committer to create a commitment to a secret value, and later may open and reveal the secret value in a verifiable manner. In the common reference string model, commitment schemes require a setup phase which is supposed to be done by a third trusted party or distributed authority. During last few years, various news are reported about subversion of $\textit{trusted}$ setup phase in mass-surveillance activities; strictly speaking about commitment schemes, recently it was discovered that the SwissPost-Scytl mix-net uses a trapdoor commitment scheme, that allows undetectably altering the votes once you know the trapdoor [Hae19, LPT19]. Motivated by such news and recent studies on subversion-resistance of various cryptographic primitives, this research studies security of commitment schemes in the presence of a maliciously chosen public commitment key. To attain a clear understanding of achievable security, we present a variation of current definitions called subversion hiding, subversion equivocality and subversion binding. Then we provide both negative and positive results on constructing subversion-resistant commitment schemes, by showing that some combinations of notions are not compatible, while presenting subversion-resistant constructions that can achieve other combinations.

Password-Authenticated Key Exchange (PAKE) is a method to establish cryptographic keys between two users sharing a low-entropy password. In its asymmetric version, one of the users acts as a server and only stores some function of the password, e.g., a hash. Upon server compromise, the adversary learns H(pw). Depending on the strength of the password, the attacker now has to invest more or less work to reconstruct pw from H(pw). Intuitively, asymmetric PAKE seems more challenging than standard (symmetric) PAKE since the latter is not supposed to protect the password upon compromise. In this paper, we provide three contributions: * Separating standard and asymmetric PAKE. We prove that a strong assumption like a programmable random oracle is necessary to achieve security of asymmetric PAKE in the Universal Composability (UC) framework. For standard PAKE, programmability is not required. Our results thus give the first formal evidence that, in the UC model, asymmetric PAKE is indeed harder to achieve than standard PAKE. * Revising the security definition. We identify and close a gap in the UC security definition of 2-party asymmetric PAKE given by Gentry, MacKenzie and Ramzan (Crypto 2006). For this, we specify a natural corruption model for server compromise attacks. We further remove an undesirable weakness that lets parties wrongly believe in security of compromised session keys. We demonstrate usefulness by proving that the $\Omega$-protocol proposed by Gentry et al. satisfies our new security notion for aPAKE. * Composable multi-party aPAKE. We demonstrate that reliance on a programmable random oracle hinders construction of multi-party aPAKE protocols from 2-party protocols via UC composition. Namely, the resulting protocols offer such strong security guarantees that they become impractical in any application. We provide guidance on how to relax composable security notions for multi-party asymmetric aPAKE to obtain useful protocols.

Hash proof systems or smooth projective hash functions (SPHFs) have been proposed by Cramer and Shoup (Eurocrypt'02) and can be seen as special type of zero-knowledge proof system for a language. While initially used to build efficient chosen-ciphertext secure public-key encryption, they found numerous applications in several other contexts. In this paper, we revisit the notion of SPHFs and introduce a new feature (a third mode of hashing) that allows to compute the hash value of an SPHF without having access to neither the witness nor the hashing key, but some additional auxiliary information. We call this new type publicly computable SPHFs (PC-SPHFs) and present a formal framework along with concrete instantiations from a large class of SPHFs. We then show that this new tool generically leads to commitment schemes that are secure against adaptive adversaries, assuming erasures in the Universal Composability (UC) framework, yielding the first UC secure commitments build from a single SPHF instance. Instantiating our PC-SPHF with an SPHF for labeled Cramer-Shoup encryption gives the currently most efficient non-interactive UC-secure commitment. Finally, we also discuss additional applications to information retrieval based on anonymous credentials being UC secure against adaptive adversaries.

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP).

In this work we construct, for a large class of NP relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any NP relation for which membership can be decided in polynomial-time and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, Vertex-Cover, etc.) and for any constant $\gamma>0$, we construct an IOP with communication complexity $(1+\gamma) \cdot n$, where $n$ is the original witness length. The number of rounds as well as the number of queries made by the IOP verifier are constant.

This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity.

In particular, as a special case, we also obtain an IOP for Circuit-SAT with rate approaching 1: the communication complexity is $(1+\gamma) \cdot t$, for circuits of size $t$ and any constant $\gamma>0$. This improves upon the prior state-of-the-art work of Ben Sasson et-al (ICALP, 2017) who construct an IOP for Circuit-SAT with rate that is a small (unspecified) constant bounded away from 0.

Our proof leverages recent constructions of high-rate locally testable tensor codes. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a core component in all known short PCP/IOP constructions.

In an attribute-based credential (ABC) system, users obtain a digital certificate on their personal attributes, and can later prove possession of such a certificate in an unlinkable way, thereby selectively disclosing chosen attributes to the service provider. Recently, the concept of encrypted ABCs (EABCs) was introduced by Krenn et al. at CANS 2017, where virtually all computation is outsourced to a semi-trusted cloud-provider called wallet, thereby overcoming existing efficiency limitations on the user’s side, and for the first time enabling “privacy-preserving identity management as a service”. While their approach is highly relevant for bringing ABCs into the real world, we present a simple attack fully breaking privacy of their construction if the wallet colludes with other users – a scenario which is not excluded in their analysis and needs to be considered in any realistic modeling. We then revise the construction of Krenn et al. in various ways, such that the above attack is no longer possible. Furthermore, we also remove existing non-collusion assumptions between wallet and service provider or issuer from their construction. Our protocols are still highly efficient in the sense that the computational effort on the end user side consists of a single exponentiation only, and otherwise efficiency is comparable to the original work of Krenn et al.

Event date: 10 June to 12 June 2020
Submission deadline: 10 February 2020
Notification: 10 April 2020

The 2019 TCC Test-of-Time Award goes to Paul Valiant, for his TCC 2008 paper "Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency". 

The award committee recognizes this paper “for demonstrating the power of recursive composition of proofs of knowledge and enabling the development of efficiently verifiable proofs of correctness for complex computations" 

The TCC Test of Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other area of cryptography, theory, and beyond. The inaugural TCC Test of Time Award was given in TCC 2015 for papers published no later than TCC 2007.

We examine all of the signature submissions to Round-2 of the NIST PQC ``competition'' in the context of whether one can transform them into threshold signature schemes in a relatively straight forward manner. We conclude that all schemes, except the ones in the MQ family, have significant issues when one wishes to convert them using relatively generic MPC techniques. The lattice based schemes are hampered by requiring a mix of operations which are suited to both linear secret shared schemes (LSSS)- and garbled circuits (GC)-based MPC techniques (thus requiring costly transfers between the two paradigms). The Picnic and SPHINCS+ algorithms are hampered by the need to compute a large number of hash function queries on secret data. Of the nine submissions the two which would appear to be most suitable for using in a threshold like manner are Rainbow and LUOV, with LUOV requiring less rounds and less data storage.

In this paper, we intend to study the geometric meaning of the discrete logarithm problem defined over an Elliptic Curve. The key idea is to reduce the Elliptic Curve Discrete Logarithm Problem (EC-DLP) into a system of equations. These equations arise from the interesection of quadric hypersurfaces in an affine space of lower dimension. In cryptography, this interpretation can be used to design attacks on EC-DLP. Presently, the best known attack algorithm having a sub-exponential time complexity is through the implementation of Summation Polynomials and Weil Descent. It is expected that the proposed geometric interpretation can result in faster reduction of the problem into a system of equations. These overdetermined system of equations are hard to solve. We have used F4 (Faugere) algorithms and got results for primes less than 500,000. Quantum Algorithms can expedite the process of solving these over-determined system of equations. In the absence of fast algorithms for computing summation polynomials, we expect that this could be an alternative. We do not claim that the proposed algorithm would be faster than Shor's algorithm for breaking EC-DLP but this interpretation could be a candidate as an alternative to the 'summation polynomial attack' in the post-quantum era.

Key Words: Elliptic Curve Discrete Logarithm Problem, Intersection of Curves, Grobner Basis, Vanishing Ideals.

Token management systems were the first application of blockchain technology and are still the most widely used one. Early implementations such as Bitcoin or Ethereum provide virtually no privacy beyond basic pseudonymity: all transactions are written in plain to the blockchain, which makes them perfectly linkable and traceable. Several more recent blockchain systems, such as Monero or Zerocash, implement improved levels of privacy. Most of these systems target the permissionless setting, just like Bitcoin. Many practical scenarios, in contrast, require token systems to be permissioned, binding the tokens to user identities instead of pseudonymous addresses, and also requiring auditing functionality in order to satisfy regulation such as AML/KYC. We present a privacy-preserving token management system that is designed for permissioned blockchain systems and supports fine-grained auditing. The scheme is secure under computational assumptions in bilinear groups, in the random-oracle model.

Persistent faults mark a new class of injections that perturb lookup tables within block ciphers with the overall goal of recovering the encryption key. Unlike earlier fault types persistent faults remain intact over many encryptions until the affected device is rebooted, thus allowing an adversary to collect a multitude of correct and faulty ciphertexts. It was shown to be an efficient and effective attack against substitution-permutation networks. In this paper, the scope of persistent faults is further broadened and explored. More specifically, we show how to construct a key-recovery attack on generic Feistel schemes in the presence of persistent faults. In a second step, we leverage these faults to reverse-engineer AES- and PRESENT-like ciphers in a chosen-key setting, in which some of the computational layers, like substitution tables, are kept secret. Finally, we propose a novel, dedicated, and low-overhead countermeasure that provides adequate protection for hardware implementations against persistent fault injections.

In this paper, we study isogeny graphs of supersingular elliptic curves. Supersingular isogeny graphs were introduced as a hard problem into cryptography by Charles, Goren, and Lauter for the construction of cryptographic hash functions. These are large expander graphs, and the hard problem is to find an efficient algorithm for routing, or path-finding, between two vertices of the graph. We consider four aspects of supersingular isogeny graphs, study each thoroughly and, where appropriate, discuss how they relate to one another. First, we consider two related graphs that help us understand the structure: the `spine' $\mathcal{S}$, which is the subgraph of $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ given by the $j$-invariants in $\mathbb{F}_p$, and the graph $\mathcal{G}_\ell(\mathbb{F}_p)$, in which both curves and isogenies must be defined over $\mathbb{F}_p$. We show how to pass from the latter to the former. The graph $\mathcal{S}$ is relevant for cryptanalysis because routing between vertices in $\mathbb{F}_p$ is easier than in the full isogeny graph. The $\mathbb{F}_p$-vertices are typically assumed to be randomly distributed in the graph, which is far from true. We provide an analysis of the distances of connected components of $\mathcal{S}$.

Next, we study the involution on $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ that is given by the Frobenius of $\mathbb{F}_p$ and give heuristics on how often shortest paths between two conjugate $j$-invariants are preserved by this involution (mirror paths). We also study the related question of what proportion of conjugate $j$-invariants are $\ell$-isogenous for $\ell = 2,3$. We conclude with experimental data on the diameters of supersingular isogeny graphs when $\ell = 2$ and compare this with previous results on diameters of LPS graphs and random Ramanujan graphs.

Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform updates and searches on encrypted data which makes it very useful in practice. To protect DSSE from the leakage of updates (leading to break query or data privacy), two new security notions, forward and backward privacy, have been proposed recently. Although extensive attention has been paid to forward privacy, this is not the case for backward privacy. Backward privacy, first formally introduced by Bost et al., is classified into three types from weak to strong, exactly Type-III to Type-I. To the best of our knowledge, however, no practical DSSE schemes without trusted hardware (e.g. SGX) have been proposed so far, in terms of the strong backward privacy and constant roundtrips between the client and the server.

In this work, we present a new DSSE scheme by leveraging simple symmetric encryption with homomorphic addition and bitmap index. The new scheme can achieve both forward and backward privacy with one roundtrip. In particular, the backward privacy we achieve in our scheme (denoted by Type-I$^-$) is somewhat stronger than Type-I. Moreover, our scheme is very practical as it involves only lightweight cryptographic operations. To make it scalable for supporting billions of files, we further extend it to a multi-block setting. Finally, we give the corresponding security proofs and experimental evaluation which demonstrate both security and practicality of our schemes, respectively.

The Holy Grail of a decentralised stablecoin is achieved on rigorous mathematical frameworks, obtaining multiple advantageous proofs: stability, convergence, truthfulness, faithfulness, and malicious-security. These properties could only be attained by the novel and interdisciplinary combination of previously unrelated fields: model predictive control, deep learning, alternating direction method of multipliers (consensus-ADMM), mechanism design, secure multi-party computation, and zero-knowledge proofs. For the first time, this paper proves:

- the feasibility of decentralising the central bank while securely preserving its independence in a decentralised computation setting

- the benefits for price stability of combining mechanism design, provable security, and control theory, unlike the heuristics of previous stablecoins

- the implementation of complex monetary policies on a stablecoin, equivalent to the ones used by central banks and beyond the current fixed rules of cryptocurrencies that hinder their price stability

- methods to circumvent the impossibilities of Guaranteed Output Delivery (G.O.D.) and fairness: standing on truthfulness and faithfulness, we reach G.O.D. and fairness under the assumption of rational parties

As a corollary, a decentralised artificial intelligence is able to conduct the monetary policy of a stablecoin, minimising human intervention.

Memory fault attacks, inducing errors in computations, have been an ever-evolving threat to cryptographic schemes since their discovery for cryptography by Boneh et al. (Eurocrypt 1997). Initially requiring physical tampering with hardware, the software-based rowhammer attack put forward by Kim et al. (ISCA 2014) enabled fault attacks also through malicious software running on the same host machine. This lead to concerning novel attack vectors, for example on deterministic signature schemes, whose approach to avoid dependency on (good) randomness renders them vulnerable to fault attacks. This has been demonstrated in realistic adversarial settings in a series of recent works. However, a unified formalism of different memory fault attacks, enabling also to argue the security of countermeasures, is missing yet.

In this work, we suggest a generic extension for existing security models that enables a game-based treatment of cryptographic fault resilience. Our modeling specifies exemplary memory fault attack types of different strength, ranging from random bit-flip faults to differential (rowhammer-style) faults to full adversarial control on indicated memory variables. We apply our model first to deterministic signatures to revisit known fault attacks as well as to establish provable guarantees of fault resilience for proposed fault-attack countermeasures. In a second application to nonce-misuse resistant authenticated encryption, we provide the first fault-attack treatment of the SIV mode of operation and give a provably secure fault-resilient variant.

This paper presents two new improved attacks on the KMOV cryptosystem. KMOV is an encryption algorithm based on elliptic curves over the ring ${\mathbb{Z}}_N$ where $N=pq$ is a product of two large primes of equal bit size. The first attack uses the properties of the convergents of the continued fraction expansion of a specific value derived from the KMOV public key. The second attack is based on Coppersmith's method for finding small solutions of a multivariate polynomial modular equation. Both attacks improve the existing attacks on the KMOV cryptosystem.

The elliptic curve cryptography plays a central role in various cryptographic schemes and protocols. For efficiency reasons, Edwards curves and twisted Edwards curves have been introduced. In this paper, we study the properties of twisted Edwards curves on the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=p^rq^s$ is a prime power RSA modulus and propose a new scheme and study its efficiency and security.

Let $N=pq$ be an RSA modulus and $e$ be a public exponent. Numerous attacks on RSA exploit the arithmetical properties of the key equation $ed-k(p-1)(q-1)=1$. In this paper, we study the more general equation $eu-(p-s)(q-r)v=w$. We show that when the unknown integers $u$, $v$, $w$, $r$ and $s$ are suitably small and $p-s$ or $q-r$ is factorable using the Elliptic Curve Method for factorization ECM, then one can break the RSA system. As an application, we propose an attack on Demytko's elliptic curve cryptosystem. Our method is based on Coppersmith's technique for solving multivariate polynomial modular equations.

We present CrypTFlow, a first of its kind system that converts TensorFlow inference code into Secure Multi-party Computation (MPC) protocols at the push of a button. To do this, we build three components. Our first component, Athos, is an end-to-end compiler from TensorFlow to a variety of semi-honest MPC protocols. The second component, Porthos, is an improved semi-honest 3-party protocol that provides significant speedups for Tensorflow like applications. Finally, to provide malicious secure MPC protocols, our third component, Aramis, is a novel technique that uses hardware with integrity guarantees to convert any semi-honest MPC protocol into an MPC protocol that provides malicious security. The security of the protocols output by Aramis relies on hardware for integrity and MPC for confidentiality. Moreover, our system, through the use of a new float-to-fixed compiler, matches the inference accuracy over the plaintext floating-point counterparts of these networks.

We experimentally demonstrate the power of our system by showing the secure inference of real-world neural networks such as ResNet50, DenseNet121, and SqueezeNet over the ImageNet dataset with running times of about 30 seconds for semi-honest security and under two minutes for malicious security. Prior work in the area of secure inference (SecureML, MiniONN, HyCC, ABY$^3$, CHET, EzPC, Gazelle, and SecureNN) has been limited to semi-honest security of toy networks with 3--4 layers over tiny datasets such as MNIST or CIFAR which have 10 classes. In contrast, our largest network has 200 layers, 65 million parameters and over 1000 ImageNet classes. Even on MNIST/CIFAR, CrypTFlow outperforms prior work.

In the article we propose a new compression method (to $2\log_2(p) + 3$ bits) for the $\mathbb{F}_{\!p^2}$-points of an elliptic curve $E_b\!: y^2 = x^3 + b$ (for $b \in \mathbb{F}_{\!p^2}^*$) of $j$-invariant $0$. It is based on $\mathbb{F}_{\!p}$-rationality of some generalized Kummer surface $GK_b$. This is the geometric quotient of the Weil restriction $R_b := \mathrm{R}_{\: \mathbb{F}_{\!p^2}/\mathbb{F}_{\!p}}(E_b)$ under the order $3$ automorphism restricted from $E_b$. More precisely, we apply the theory of conic bundles (i.e., conics over the function field $\mathbb{F}_{\!p}(t)$) to obtain explicit and quite simple formulas of a birational $\mathbb{F}_{\!p}$-isomorphism between $GK_b$ and $\mathbb{A}^{\!2}$. Our point compression method consists in computation of these formulas. To recover (in the decompression stage) the original point from $E_b(\mathbb{F}_{\!p^2}) = R_b(\mathbb{F}_{\!p})$ we find an inverse image of the natural map $R_b \to GK_b$ of degree $3$, i.e., we extract a cubic $\mathbb{F}_{\!p}$-root. For $p \not\equiv 1 \: (\mathrm{mod} \ 27)$ this is just a single exponentiation in $\mathbb{F}_{\!p}$, hence the new method seems to be much faster than the classical one with $x$ coordinate, which requires two exponentiations in $\mathbb{F}_{\!p}$. In particular, it is perfectly applicable to pairing-friendly elliptic curves from one IETF-draft and to those used in the cryptocurrencies Ethereum and Zcash.