International Association
for Cryptologic Research

In this paper we analyse the algorithm Chaskey - a lightweight MAC algorithm for 32-bit micro controllers - with respect to rotational cryptanalysis. We perform a related-key attack over Chaskey and find a distinguisher by using rotational probabilities. Having a message $m$ we can forge and present a valid tag for some message under a related key with probability $2^{-57}$ for 8 rounds and $2^{-86}$ for all 12 rounds of the permutation for keys in a defined weak-key class. This attack can be extended to full key recovery with complexity $2^{120}$ for the full number of rounds. To our knowledge this is the first published attack targeting all 12 rounds of the algorithm. Additionally, we generalize the Markov theory with respect to a relation between two plaintexts and not their difference and apply it for rotational pairs.

This work introduces an extension of the UC framework with an abstract notion of time that allows for modeling relative delays in communication and sequential computation without requiring parties to keep track of a clock. The potential uses of this extension are demonstrated by: (1) formalizing a functionality for (semi-)synchronous secure message transmission; (2) formalizing the notion of time-lock puzzles in the UC setting and showing how to realize it in the restricted programmable and observable global random oracle model; (3) showing that UC time-lock puzzles yield UC-secure fair coin flips; (4) showing that UC-secure two-party computation realizing a new notion of output-independent abort can be obtained leveraging composable time-lock puzzles. Finally, we show that a programmable random oracle is necessary to obtain UC-secure fair coin flip, secure two-party computation with output-independent abort or time-lock puzzles, which yields a new separation between programmable and non-programmable random oracles.

Higher-order differential attacks are among the most powerful attacks against low-degree ciphers and hash functions. Predicting the evolution of the algebraic degree of the cipher (as a function of the number of rounds) is the main obstacle in assessing the feasibility of these attacks. For an SPN cipher over a finite field $\mathbb F$ of characteristic 2 with round function of algebraic degree $\delta$, it is a common belief that the degree of the cipher grows almost exponentially with $\delta$. However, for an iterated Even--Mansour cipher whose round function can be described as an invertible low-degree polynomial over $\mathbb F_{2^n}$ it has recently been shown that the algebraic degree grows linearly with the number of rounds, and not exponentially.

In this paper we generalise these results for SPN ciphers, showing that the growth of the algebraic degree is often linear for SPN ciphers with low-degree S-Boxes as well. We prove that the initial exponential growth of the degree turns into a linear growth after a certain number of rounds. Our analysis includes iterated Even--Mansour and MiMC-like ciphers as a special case, but most notably it also applies to SPN ciphers designed to be competitive for recent applications like MPC, FHE, SNARKs, and STARKs (e.g., HadesMiMC). Our findings have been practically verified on small-scale ciphers.

We provide two new constructions of non-interactive zero-knowledge arguments (NIZKs) for NP from discrete-logarithm-style assumptions over cyclic groups, without relying on pairings. A previous construction from (Canetti et al., Eurocrypt'18) achieves such NIZKs under the assumption that no efficient adversary can break the key-dependent message (KDM) security of (additive) ElGamal with respect to all (even inefficient) functions over groups of size $2^\lambda$, with probability better than $\mathsf{poly}(\lambda)/2^{\lambda}$. This is an extremely strong, non-falsifiable assumption. In particular, even mild (polynomial) improvements over the current best-known attacks on the discrete logarithm problem would already contradict this assumption. (Canetti et al. STOC'19) describe how to improve the assumption to rely only on KDM security with respect to efficient functions while additionally assuming public-key encryption schemes, therefore obtaining an assumption that is (in spirit) falsifiable.

Our first construction improves this state of affairs. We provide a construction of NIZKs for NP under the CDH assumption together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size $2^\lambda$, with probability better than $\mathsf{poly}(\lambda)/2^{c\lambda}$ (denoted $2^{-c\lambda}$-OWKDM), for a constant $c = 3/4$. Unlike the previous assumption, our assumption leaves an exponential gap between the best-known attack and the required security guarantee.

Our second construction is interested in the case where CDH does not hold. Namely, as a second contribution, we construct an infinitely often NIZK argument system for NP (where soundness and zero-knowledge are only guaranteed to hold for infinitely many security parameters), under the assumption that CDH is easy together with the $2^{-c\lambda}$-OWKDM security of ElGamal with $c = 28/29+o(1)$ and the existence of low-depth pseudorandom generators (PRG).

Combining our two results, we obtain a construction of (infinitely-often) NIZKs for NP under the $2^{-c\lambda}$-OWKDM security of ElGamal with $c = 28/29+o(1)$ and the existence of low-depth PRG, independently of whether CDH holds. To our knowledge, since neither OWKDM security of ElGamal nor low-depth PRGs are known to imply public key encryption, this provides the first construction of NIZKs from concrete and falsifiable Minicrypt-style assumptions.

We present KEMTLS, an alternative to the TLS 1.3 handshake that uses key-encapsulation mechanisms (KEMs) instead of signatures for server authentication. Among existing post-quantum candidates, signature schemes generally have larger public key/signature sizes compared to the public key/ciphertext sizes of KEMs: by using an IND-CCA-secure KEM for server authentication in post-quantum TLS, we obtain multiple benefits. A size-optimized post-quantum instantiation of KEMTLS requires less than half the bandwidth of a size-optimized post-quantum instantiation of TLS 1.3. In a speed-optimized instantiation, KEMTLS reduces the amount of server CPU cycles by almost 90% compared to TLS 1.3, while at the same time reducing communication size, reducing the time until the client can start sending encrypted application data, and eliminating code for signatures from the server's trusted code base.

When Proof-of-Stake (PoS) underlies a consensus protocol, parties who are eligible to participate in the protocol are selected via a public selection function that depends on the stake they own. Identity and stake of the selected parties must then be disclosed in order to allow verification of their eligibility, and this can raise privacy concerns. In this paper, we present a modular approach for addressing the identity leaks of selection functions, decoupling the problem of implementing an anonymous selection of the participants, from the problem of implementing others task, e.g. consensus. We present an ideal functionality for anonymous selection that can be more easily composed with other protocols. We then show an instantiation of our anonymous selection functionality based on the selection function of Algorand.

Collateral employed in cryptoeconomic protocols protects against the misbehavior of economically rational agents, compensating honest users for damages and punishing misbehaving parties. The introduction of collateral, however, carries three disadvantages: (i) requiring agents to lock up a substantial amount of collateral can be an entry barrier, limiting the set of candidates to wealthy agents; (ii) affected agents incur ongoing opportunity costs as the collateral cannot be utilized elsewhere; and (iii) users wishing to interact with an agent on a frequent basis (e.g., with a service provider to facilitate second-layer payments), have to ensure the correctness of each interaction individually instead of subscribing to a service period in which interactions are secured by the underlying collateral.

We present Promise, a subscription mechanism to decrease the initial capital requirements of economically rational service providers in cryptoeconomic protocols. The mechanism leverages future income (such as service fees) prepaid by users to reduce the collateral actively locked up by service providers, while sustaining secure operation of the protocol. Promise is applicable in the context of multiple service providers competing for users. We provide a model for evaluating its effectiveness and argue its security. Demonstrating Promise's applicability, we discuss how Promise can be integrated into a cross-chain interoperability protocol, XCLAIM, and a second-layer scaling protocol, NOCUST. Last, we present an implementation of the protocol on Ethereum showing that all functions of the protocol can be implemented in constant time complexity and Promise only adds USD 0.05 for a setup per user and service provider and USD 0.01 per service delivery during the subscription period.

The COVID-19 pandemic created a noticeable challenge to the cryptographic community with the development of contact tracing applications. The media reported a dispute between designers proposing a centralized or a decentralized solution (namely, the PEPP-PT and the DP3T projects). Perhaps, the time constraints to develop and deploy efficient solutions led to non-optimal (in terms of privacy) solutions. Moreover, arguments have been severely biased and the scientific debate did not really happen until recently. In this paper, we show the vulnerabilities and the advantages of both solutions systematically. We believe that none offers any sufficient level of privacy protection and the decision to use one or another is as hard as using automated contact tracing at the first place. A third way could be explored. We list here a few possible directions.

We present a constructive SAT-based algorithm to determine the multiplicative complexity of a Boolean function, i.e., the smallest number of AND gates in any logic network that consists of 2-input AND gates, 2-input XOR gates, and inverters. In order to speed-up solving time, we make use of several symmetry breaking constraints; these exploit properties of XAGs that may be useful beyond the proposed SAT-based algorithm. We further propose a heuristic post-optimization algorithm to reduce the number of XOR gates once the optimum number of AND gates has been obtained, which also makes use of SAT solvers. Our algorithm is capable to find all optimum XAGs for representatives of all 5-input affine-equivalent classes, and for a set of frequently occurring 6-input functions.

Password Authenticated Key Exchange (PAKE) protocols allow parties to establish a shared key based only on the knowledge of a password, without leaking any information about it. In this work, we propose a novel notion called ``Identity-based PAKE'' (iPAKE) that is resilient to the compromise of one or more parties. iPAKE protocols protect all parties in a symmetric setting, whereas in Asymmetric PAKE (aPAKE) only one party (a server) is protected. Binding each party to its identity prevents impersonation between devices with different roles and allows the revocation of compromised parties.

We further strengthen the notion by introducing ``Strong iPAKE'' (siPAKE), similar to ``Strong aPAKE'' (saPAKE), which is additionally immune to pre-computation. To mount an (inevitable) offline dictionary attack, an adversary must first compromise a device and only then start an exhaustive search over the entire password dictionary. Rather than storing its password in the clear, each party derives a password file using its identity and a secret random salt (``salted hash''). Although the random salts are independently selected, any pair of parties is able to establish a cryptographically secure shared key from these files.

We formalize iPAKE and siPAKE notions in the Universally Composable (UC) framework and propose a compiler from PAKE to iPAKE using Identity-Based Key-Agreement. We then present CRISP: a construction of siPAKE from any PAKE using bilinear groups with ``Hash2Curve''. We prove CRISP's UC-security in the Generic Group Model (GGM) and show that each offline password guess requires at least one pairing operation.

In this paper, we propose a privacy-preserving contact tracing app for COVID-19. The app allows users to be notified, if they have been a close contact with a confirmed patient. Our protocol is the most comprehensive and balanced privacy-preserving contact tracing solution to date.

Our protocol strikes a balance between security, privacy and scalability. In terms of privacy, it allows all users to hide his past location and contact history with respect to the Government. Yet, all users can check whether he had a close contact with a confirmed patient without learning the identity of the patient. We use a zero-knowledge protocol to ensure that user privacy is protected. In terms of security, no user can send fake message to the system to launch a false positive attack. We give a formal security model and give a security proof for our protocol. In terms of scalability, we have implemented our protocol into Android smartphone and our evaluation result shows its practicality.

An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs, give an efficient construction in prime-order groups from constant-sized polynomial commitments and use it to bootstrap a highly-efficient stateless cryptocurrency.

Our aSVC supports (1) computing all $n$ $O(1)$-sized proofs in $O(n\log{n})$ time, (2) updating a proof in $O(1)$ time and (3) aggregating $b$ proofs into an $O(1)$-sized subvector proof in $O(b\log^2{b})$ time. Importantly, our scheme has an $O(n)$-sized proving key, an $O(1)$-sized verification key and $O(1)$-sized update keys. In contrast, previous schemes with constant-sized proofs in prime-order groups either (1) require $O(n^2)$ time to compute all proofs, (2) require $O(n)$-sized update keys to update proofs in $O(1)$ time, or (3) do not support aggregating proofs. Furthermore, schemes based on hidden-order groups either (1) have larger concrete proof size and computation time, or (2) do not support proof updates.

We use our aSVC to obtain a stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block's proof overhead to just one group element, which is optimal. In contrast, previous work required $O(b\log{n})$ group elements, where $b$ is the number of transactions per block. Furthermore, our smaller proofs reduce the block verification time from $O(b\log{n})$ pairings to just two pairings and an $O(b)$-sized multi-exponentiation. Lastly, our aSVC's smaller update keys only take up $O(b)$ block space, compared to $O(b\log{n})$ in previous work. Also, their zverifiability reduces miner storage from $O(n)$ to $O(1)$. The end result is a stateless cryptocurrency that concretely and asymptotically outperforms the state of the art

Montgomery's formulas for doubling and differential addition in $x$-coordinates for elliptic curves $By^2 = x^3 + Ax^2 + x$ are among the most efficient formulas for point multiplication after compression. In general, if $E$ is an elliptic curve over a field $K$, then a degree 2 function $f:E\to K$ such that $f(P) = f(-P)$ for $P\in E$ can be used as a compression and there exist analogous formulas for doubling and differential addition of values $f$ which can be used in the Montgomery ladder algorithm to compute multiplication $[n]f(P) = f([n]P)$ for $n\in \mathbb N$. In this paper we give formulas for doubling and differential addition of the same or similar efficiency as Montgomery's for Huff's and general Huff's curves of odd characteristic and degree 2 compression, which seems to be new for these models of elliptic curves. Additionally, we give formulas for point recovery after compression. We also found efficient formulas for general odd-isogeny computation on Huff's curves and we showed how to apply obtained formulas, especially, to the isogeny based cryptography. Moreover, it was showed how to apply obtained by us formulas using compression to the ECM algorithm. In appendix, we present examples of convenient cryptographic Huff's curves, where presented compression techniques can be used.

Blockchain protocols based on Proof-of-Stake (PoS) depend — by nature — on the active participation of stakeholders. If users are offline and abstain from the PoS consensus mechanism, the system’s security is at risk, so it is imperative to explore ways to both maximize the level of participation and minimize the effects of non-participation. One such option is stake representation, such that users can delegate their participation rights and, in the process, form "stake pools". The core idea is that stake pool operators always participate on behalf of regular users, while the users retain the ownership of their assets. Our work provides a formal PoS wallet construction that enables delegation and stake pool formation. While investigating the construction of addresses in this setting, we distil and explore address malleability, a security property that captures the ability of an attacker to manipulate the delegation information associated with an address. Our analysis consists of identifying multiple levels of malleability, which are taken into account in our paper’s core result. We then introduce the first ideal functionality of a PoS wallet’s core which captures the PoS wallet’s capabilities and is realized as a secure protocol based on standard cryptographic primitives. Finally, we cover how to use the wallet core in conjunction with a PoS ledger, as well as investigate how delegation and stake pools affect a PoS system’s security.

Randomizable encryption lets anyone randomize a ciphertext so it is distributed like a fresh encryption of the same plaintext. Signatures on randomizable ciphertexts (SoRC), introduced by Blazy et al. (PKC'11), let one adapt a signature on a ciphertext to a randomization of the latter. Since signatures can only be adapted to ciphertexts that encrypt the same message as the signed ciphertext, signatures thus obliviously authenticate plaintexts. SoRC have been used as a building block in e-voting, blind signatures, and (delegatable) anonymous credentials.

We observe that SoRC can be seen as signatures on equivalence classes (JoC'19), another primitive with many applications to anonymous authentication, and that SoRC provide better anonymity guarantees. We first strengthen the unforgeability notion for SoRC and then give a scheme that provably achieves it in the generic group model. Signatures in our scheme consist of only 4 bilinear-group elements, which is considerably more efficient than prior schemes.

In this paper we introduce the strictly zero-correlation attack. We extend the work of Ashur and Posteuca in BalkanCryptSec 2018 and build a 0-correlation key-dependent linear trails covering the full DES. We show how this approximation can be used for a key recovery attack and empirically verify our claims through a series of experiments. To the best of our knowledge, this paper is the first to use this kind of property to leverage a meaningful attack against a symmetric-key algorithm.

With the outbreak of the coronavirus, governments rely more and more on location data shared by European mobile network operators to monitor the advancements of the disease. In order to comply with often strict privacy requirements, this location data, however, has to be anonymized, limiting its usefulness for making statements about a filtered part of the population, like already infected people. In this research, we aim to assist with the disease tracking efforts by designing a protocol to detect coronavirus hotspots from mobile data while still maintaining compliance with privacy expectations. We use various state-of-the-art privacy-preserving cryptographic primitives to design a protocol that can best be described as aggregated private information retrieval (APIR). Our protocol is based on homomorphic encryption, with additional measures to protect against malicious requests from clients. We have implemented our APIR protocol in the SEAL library and tested it for parameters suitable to create a coronavirus hotspot map for entire nationstates. This demonstrates that it is feasible to apply our APIR protocol to support nationwide disease analysis while still preserve the privacy of infected people.

MP-SPDZ is a fork of SPDZ-2 (Keller et al., CCS '13), an implementation of the multi-party computation (MPC) protocol called SPDZ (Damgård et al., Crypto '12). MP-SPDZ extends SPDZ-2 to more than twenty MPC protocols, all of which can be used with the same high-level programming interface based on Python. This considerably simplifies comparing the cost of different protocols and security models.

The protocols cover all commonly used security model (honest/dishonest majority and semi-honest/malicious corruption) as well as computation of binary and arithmetic circuits (the latter modulo primes and powers of two). The underlying primitives employed include secret sharing, oblivious transfer, homomorphic encryption, and garbled circuits.

The breadth of implemented protocols coupled with an accessible high-level interface makes it suitable to benchmark the cost of computation in various security models for researchers both with and without a background in secure computation

This paper aims the outline the variety of protocols implemented and the design choices made in the development of MP-SPDZ as well as the capabilities of the programming interface.

Event date: 13 September 2020
Submission deadline: 1 June 2020
Notification: 31 July 2020

Post-Quantum (PQ) signature schemes are known for large key and signature sizes, which may inhibit their deployment in real world applications. In this work, we construct a PQ signature scheme MMSAT that is the first such scheme capable of aggregating unrelated messages signed individually by different parties. Our proposal extends the notion of multisignatures, which are signatures that support aggregation of signatures on a single message signed by multiple parties. Multisignatures are especially useful in blockchain applications, where a transaction may be signed by multiple users. The proposed construction achieves significant gains in bandwidth and storage requirements by allowing aggregation of unrelated transactions. Our construction is derived by extending the PASS scheme, and thus the security of our scheme relies on the hardness of the Vandermonde-SIS problem. When aggregated, a signature consists of two parts. The first part is a post-quantum size signature that grows very slowly, scaling by on the order of~$\log{K}$ bits for~$K$ signatures. The second part scales linearly with~$K$, with a very short fixed cost, roughly twice the bit security. Thus even when aggregating a modest number of signatures, the per signature cost of MMSAT is in line with that of traditional pre-quantum signature schemes such as ECDSA. As an extension to MMSAT, we describe a variant called MMSATK in which it the public keys required to verify an aggregated signature are compressed by a factor of~$20$ to~$30$.