International Association
for Cryptologic Research

We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument:

* A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee,

* A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zaj\k{a}c,

* A (simplified) consistency argument of Groth and Lu.

We prove the knowledge-soundness of the first two subarguments in the generic bilinear group model, and the culpable soundness of the third subargument under a KerMDH assumption. This proves the soundness of the shuffle argument. We also discuss our partially optimized implementation that allows one to prove a shuffle of $100\,000$ ciphertexts in less than a minute and verify it in less than $1.5$ minutes.

Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don't give meaningful security guarantees due to existing time-memory trade-offs.

In particular, Hellman showed that any permutation over a domain of size $N$ can be inverted in time $T$ by an algorithm that is given $S$ bits of auxiliary information whenever $S\cdot T \approx N$ (e.g. $S=T\approx N^{1/2}$). For functions Hellman gives a weaker attack with $S^2\cdot T\approx N^2$ (e.g., $S=T \approx N^{2/3}$). To prove lower bounds, one considers an adversary who has access to an oracle $f:[N]\rightarrow [N]$ and can make $T$ oracle queries. The best known lower bound is $S\cdot T\in \Omega(N)$ and holds for random functions and permutations.

We construct functions that provably require more time and/or space to invert. Specifically, for any constant $k$ we construct a function $[N]\rightarrow [N]$ that cannot be inverted unless $S^k\cdot T \in \Omega(N^k)$ (in particular, $S=T\approx N^{k/(k+1)}$). Our construction does not contradict Hellman's time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in $N$, which is sufficient for the PoS application.

Our simplest construction is built from a random function oracle $g:[N]\times[N]\rightarrow [N]$ and a random permutation oracle $f:[N]\rightarrow [N]$ and is defined as $h(x)=g(x,x')$ where $f(x)=\pi(f(x'))$ with $\pi$ being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets $S$ bits of auxiliary information, makes at most $T$ oracle queries, and inverts $h$ on an $\epsilon$ fraction of outputs must satisfy $S^2\cdot T\in \Omega(\epsilon^2N^2)$.

At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by $O(q^2r(\log r)^3/N)$, where $N$ is the size of the domain. In previous work, the best known bound was $O(q^2r^2/N)$, obtained as a direct result of interpreting the iterated random function problem as a special case of CBC-MAC based on a random function. For the iterated random function problem, the best known attack has an advantage of $\Omega(q^2r/N)$, showing that our security bound is tight up to a factor of $(\log r)^3$.

Developing an approach to test cryptographic hash function implementations can be particularly difficult, and bugs can remain unnoticed for a very long time. We revisit the NIST SHA-3 hash function competition, and apply a new testing strategy to all available reference implementations. Motivated by the cryptographic properties that a hash function should satisfy, we develop four types of tests. The Bit-Contribution Test checks if changes in the message affect the hash value, and the Bit-Exclusion Test checks that changes beyond the last bit of the message leave the hash value unchanged. We develop the Metamorphic Update Test to verify that messages are processed correctly in chunks, and then use combinatorial testing methods to reduce the test set size by several orders of magnitude while retaining the same fault detection capability. Our tests detect bugs in 41 of the 86 reference implementations submitted to the SHA-3 competition, including the rediscovery of a bug in all submitted implementations of the SHA-3 finalist BLAKE. This bug remained undiscovered for seven years, and is particularly serious because it provides a simple strategy to modify the message without changing the hash value that is returned by the implementation. We will explain how to detect this type of bug, using a simple and fully-automated testing approach.

The American signature standards DSA and ECDSA, as well as their Russian and Chinese counterparts GOST 34.10 and SM2, are of utmost importance in the current security landscape. The mentioned schemes are all rooted in the Elgamal signature scheme and use a hash function and a cyclic group as building blocks. Unfortunately, authoritative security guarantees for the schemes are still due: All existing positive results on their security use aggressive idealization approaches, like the generic group model, leading to debatable overall results.

In this work we conduct security analyses for a set of classic signature schemes, including the ones mentioned above, providing positive results in the following sense: If the hash function is modeled as a random oracle, and the signer issues at most one signature per message, then the schemes are unforgeable if and only if they are key-only unforgeable, where the latter security notion captures that the adversary has access to the verification key but not to sample signatures. Put differently, for the named signature schemes, in the one-signature-per-message setting the signature oracle is redundant.

In this paper we present a number of algorithms and optimization techniques to speedup computations in binary extension fields over GF(2). Particularly, we consider multiplication and modular reduction solutions. Additionally, we provide the table of optimal binary primitive polynomials over GF(2) of degree $2\le d<2048$, and the class of functions for optimal modular reduction algorithms for each of the listed polynomials. We give implementation examples targeting Intel CPU architectures, but generic results can be applied on other platforms as well.

The client-server architecture is one of the most widely used in Internet for its simplicity and flexibility. In practice the server is assigned a public address so that its services can be consumed.This makes the server vulnerable to a number of attacks such as Distributed Denial of Service (DDoS), censorship from authoritarian governments or exploitation of software vulnerabilities.

In this work we propose an asynchronous protocol for allowing a client to issue requests to a server without leaking any information about the location of the server. In addition, our solution reveals limited information about the network topology, leaking the distance from the client to the corrupted participants.

We also provide a simulation-based security definition capturing the requirement described above. Our protocol is secure in the semi-honest model against any number of colluding participants. Moreover our solution is efficient as it requires $O(N \cdot |M|)$ bits per client-server interaction where $N$ is the number of participants and $|M|$ is the number of bits of the message.

To the best of our knowledge our solution is the first asynchronous protocol that provides strong security guarantees.

It is tempting to think that if we encrypt a sequence of messages {xi} using a semantically secure encryption scheme, such that each xi is encrypted with its own independently generated public key pki, then even if the scheme is malleable (or homomorphic) then malleability is limited to acting on each xi independently. However, it is known that this is not the case, and in fact even non-local malleability might be possible. This phenomenon is known as spooky interactions.

We formally define the notion of spooky free compilers that has been implicit in the delegation of computation literature. A spooky free compiler allows to encode a sequence of queries to a multi-prover interactive proof system (MIP) in a way that allows to apply the MIP prover algorithm on the encoded values on one hand, and prevents spooky interactions on the other. In our definition, the compiler is allowed to be tailored to a specific MIP and does not need to support any other operation.

We show that (under a plausible complexity assumption) spooky free compilers that are sufficiently succinct to imply delegation schemes for NP with communication $n^{\alpha}$ (for any constant $\alpha < 1$) cannot be proven secure via black-box reduction to a falsifiable assumption. On the other hand, we show that it is possible to construct non-succinct spooky free fully homomorphic encryption, the strongest conceivable flavor of spooky free compiler, in a straightforward way from any fully homomorphic encryption scheme.

Our impossibility result relies on adapting the techniques of Gentry and Wichs (2011) which rule out succinct adaptively sound delegation protocols. We note that spooky free compilers are only known to imply non-adaptive delegation, so the aforementioned result cannot be applied directly. Interestingly, we are still unable to show that spooky free compilers imply adaptive delegation, nor can we apply our techniques directly to rule out arbitrary non-adaptive NP-delegation.

We propose two optimal representations for the elements of trace zero subgroups of twisted Edwards curves. For both representations, we provide efficient compression and decompression algorithms. The efficiency of the algorithm is compared with the efficiency of similar algorithms on elliptic curves in Weierstrass form.

Privacy preserving computation is gaining importance. Along with secure computation guarantees, it is essential to hide information leakage through access patterns. Input-oblivious execution is a security property that is crucial to guarantee complete privacy preserving computation. In this work, we present an algorithm-specific approach to achieve input-oblivious execution. We call this class of algorithms PermuteRam. PermuteRam algorithms satisfy a specific patterns in their execution profile called Perpat— patterns that can be realized using permutation as a primitive. Next, we claim that algorithms having Perpat pattern execute in an input-oblivious manner. Further, we show that PermuteRam is expressive and includes various categories of algorithms like sorting, clustering, operating on tree data structures and so on. PermuteRam algorithms incur only an additive overhead of O(N) and a private storage of O(sqrt(N)). Hence, PermuteRam algorithms demonstrate optimal performance for linear or super-linear complexities.

We consider trace-zero subgroups of elliptic curves over a degree three field extension. The elements of these groups can be represented in compressed coordinates, i.e. via the two coefficients of the line that passes through the point and its two Frobenius conjugates. In this paper we give the first algorithm to compute scalar multiplication in the degree three trace-zero subgroup using these coordinates.

Database management systems operating over encrypted data are gaining significant commercial interest. CryptDB is one such notable system supporting a variety SQL queries over encrypted data (Popa et al., SOSP '11). It is a practical system obtained by utilizing a number of encryption schemes, together with a new cryptographic primitive for supporting SQL's join operator.

This new primitive, an adjustable join scheme, is an encoding scheme that enables to generate tokens corresponding to any two database columns for computing their join given only their encodings. Popa et al. presented a framework for modeling the security of adjustable join schemes, but it is not completely clear what types of potential adversarial behavior it captures. Most notably, CryptDB's join operator is transitive, and this may reveal a significant amount of sensitive information.

In this work we put forward a strong and intuitive notion of security for adjustable join schemes, and argue that it indeed captures the security of such schemes: We introduce, in addition, natural simulation-based and indistinguishability-based notions (capturing the ``minimal leakage'' of such schemes), and prove that our notion is positioned between their adaptive and non-adaptive variants.

Then, we construct an adjustable join scheme that satisfies our notion of security based on the linear assumption (or on the seemingly stronger matrix-DDH assumption for improved efficiency) in bilinear groups. Instantiating CryptDB with our scheme strengthens its security by providing a non-transitive join operator, while increasing the size of CryptDB's encodings from one group element to four group elements based on the linear assumption (or two group elements based on the matrix-DDH assumption), and increasing the running time of the adjustment operation from that of computing one group exponentiation to that of computing four bilinear maps based on the linear assumption (or two bilinear maps based on the matrix-DDH assumption). Most importantly, however, the most critical and frequent operation underlying our scheme is comparison of single group elements as in CryptDB's join scheme.

Differential privacy, and close other notions such as $d_\chi$-privacy, is at the heart of the privacy framework when considering the use of randomization to ensure data privacy. Such a guarantee is always submitted to some trade-off between the privacy level and the accuracy of the result. While a privacy parameter of the differentially private algorithms leverages this trade-off, it is often a hard task to choose a meaningful value for this numerical parameter. Only a few works have tackled this issue, and the present paper's goal is to continue this effort in two ways. First, we propose a generic framework to decide whether a privacy parameter value is sufficient to prevent from some pre-determined and well-understood risks for privacy. Second, we instantiate our framework on mobility data from real-life datasets, and show some insightful features necessary for practical applications of randomized sanitization mechanisms. In our framework, we model scenarii where an attacker's goal is to de-sanitize some data previously sanitized in the sense of $d_{\chi}$-privacy, a privacy guarantee close to that of differential privacy. To each attack is associated a meaningful risk of data disclosure, and the level of success for the attack suggests a relevant value for the corresponding privacy parameter.

Cryptocurrencies allow users to securely transfer money without relying on a trusted intermediary, and the transparency of their underlying ledgers also enables public verifiability. This openness, however, comes at a cost to privacy, as even though the pseudonyms users go by are not linked to their real-world identities, all movement of money among these pseudonyms is traceable. In this paper, we present Moebius, an Ethereum-based tumbler or mixing service. Moebius achieves strong notions of anonymity, as even malicious senders cannot identify which pseudonyms belong to the recipients to whom they sent money, and is able to resist denial-of-service attacks. It also achieves a much lower off-chain communication complexity than all existing tumblers, with senders and recipients needing to send only two initial messages in order to engage in an arbitrary number of transactions.

The electronic chip of the Estonian ID card is widely used in Estonia to identify the cardholder to a machine. For example, the electronic ID card can be used to obtain benefits in customer loyalty programs, authenticate to public printers and self-checkout machines in libraries, and even unlock doors and gain access to restricted areas.

This paper studies the security aspects of using the Estonian ID card for this purpose. The paper shows that the current use of the ID card provides little or no assurance to the terminal about the identity of the cardholder. To demonstrate this, an ID card emulator is built, which, to the extent possible, emulates the electronic chip of the Estonian ID card and is able to successfully impersonate the real ID card to the terminals deployed in practice. The exact mechanisms used by the terminals to authenticate the ID card are studied and possible security improvements for the Estonian ID card are discussed.

The PKC 2018 submission server is now open. The submission deadline is October 7. PKC will be held March 25-28 in Rio De Janeiro.

We describe a technique to formally verify the security of masked implementations against side-channel attacks, based on elementary circuit transformations. We describe two complementary approaches: a generic approach for the formal verification of any circuit, but for small attack orders only, and a specialized approach for the verification of specific circuits, but at any order. We describe the implementation of CheckMasks, a formal verification tool for side-channel countermeasures, using the Common Lisp programming language. Using this tool, we show how to formally verify the security of the Rivain-Prouff countermeasure for AES.

Raziel combines secure multi-party computation and proof-carrying code to provide privacy, correctness and verifiability guarantees for smart contracts on blockchains. Effectively solving DAO and Gyges attacks, this paper describes an implementation and presents examples to demonstrate its practical viability (e.g., private and verifiable crowdfundings and investment funds). Additionally, we show how to use Zero-Knowledge Proofs of Proofs (i.e., Proof-Carrying Code certificates) to prove the validity of smart contracts to third parties before their execution without revealing anything else. Finally, we show how miners could get rewarded for generating pre-processing data for secure multi-party computation.

We introduce identity-based format-preserving encryption (IB-FPE) as a way to localize and limit the damage to format-preserving encryption (FPE) from key exposure. We give definitions, relations between them, generic attacks and two transforms of FPE schemes to IB-FPE schemes. As a special case, we introduce and cover identity-based tweakable blockciphers. We apply all this to analyze DFF, an FPE scheme proposed to NIST for standardization.

Selective opening (SO) security refers to adversaries that receive a number of ciphertexts and, after having corrupted a subset of the senders (thus obtaining the plaintexts and the senders' random coins), aim at breaking the security of remaining ciphertexts. So far, very few public-key encryption schemes are known to provide simulation-based selective opening (SIM-SO-CCA2) security under chosen-ciphertext attacks and most of them encrypt messages bit-wise. The only exceptions to date rely on all-but-many lossy trapdoor functions (as introduced by Hofheinz; Eurocrypt'12) and the Composite Residuosity assumption. In this paper, we describe the first all-but-many lossy trapdoor function with security relying on the presumed hardness of the Learning-With-Errors problem (LWE) with standard parameters. Our construction exploits homomorphic computations on lattice trapdoors for lossy LWE matrices. By carefully embedding a lattice trapdoor in lossy public keys, we are able to prove SIM-SO-CCA2 security under the LWE assumption. As a result of independent interest, we describe a variant of our scheme whose multi-challenge CCA2 security tightly relates to the hardness of LWE and the security of a pseudo-random function.