International Association
for Cryptologic Research

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$.

Collective coin-tossing allows $n$ processors with private randomness sources to agree on a common public coin. Without loss of generality, one can assume that the output is in the set $\{0,1\}$, and the expected output of a coin-tossing protocol is $X$. The objective of a coin-tossing protocol is to be robust to adversarial interventions. In this paper, we study Byzantine adversaries who can arbitrarily set the messages of the corrupted processors.

Historically, the study of coin-tossing protocols, with the introduction of even the mildest of variations in its setting, tends to yield surprising and exciting outcomes. We know several optimal or asymptotically optimal protocols like tribes, baton passing, and threshold protocols. Incidentally, there are several variants of coin-tossing where the majority protocol (or, more generally, the threshold protocols) turn out to be asymptotically optimal. In this work, we consider coin-tossing protocols in two security models and study the susceptibility of the optimal coin-tossing protocols in those settings to adversarial attacks.

In the first model, there are $n$ processors and processor $i$ broadcasts her uniformly and independently random message $x_i\in\{0,1\}$. The processors apply a function $f_n\colon\{0,1\}^n\to\{0,1\}$ to the broadcast messages and agree on their common output $f_n(x_1,\dotsc,x_n)$. After all the processors broadcast their messages, the adversary may corrupt at most $t$ processors and change their messages arbitrarily. The optimal protocol minimizes the change in the expected output that this adversary causes. We reduce this problem to an isoperimetric inequality over the boolean hypercube and demonstrate that the threshold protocols are the optimal protocols.

In the second model, at time $i$, processor $i$ broadcasts her message $x_i$, and her message distribution possibly depends on the previously broadcast messages. We consider an adversary who can take control of one processor and change her message arbitrarily. In this case, we prove that the threshold protocols are asymptotically optimal.

We propose a lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution $\vec{s} \in \{-1,0,1\}^n$ to a linear equation $A\vec{s}=\vec{u}$ over $\mathbb{Z}_q$, which produces proofs that are $7.5\times$ shorter than the state-of-the-art result by Bootle, Lyubashevsky and Seiler (CRYPTO 2019).

At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring $\mathbb{Z}_q[X]/(X^d + 1)$ to prove scalar products with the NTT vector of a secret polynomial.

We construct a practical lattice-based zero-knowledge argument for proving multiplicative relations between committed values. The underlying commitment scheme that we use is the currently most efficient one of Baum et al. (SCN 2018), and the size of our multiplicative proof ($8$KB) is only slightly larger than the $7$KB required for just proving knowledge of the committed values. We additionally expand on the work of Lyubashevsky and Seiler (Eurocrypt 2018) by showing that the above-mentioned result can also apply when working over rings $\mathbb{Z}_q[X]/(X^d+1)$ where $X^d+1$ splits into low-degree factors, which is a desirable property for many applications (e.g. range proofs, multiplications over $\mathbb{Z}_q$) that take advantage of packing multiple integers into the NTT coefficients of the committed polynomial.

It is known that attackers can exfiltrate data from air-gapped computers through their speakers via sonic and ultrasonic waves. To eliminate the threat of such acoustic covert channels in sensitive systems, audio hardware can be disabled and the use of loudspeakers can be strictly forbidden. Such audio-less systems are considered to be \textit{audio-gapped}, and hence immune to acoustic covert channels.

In this paper, we introduce a technique that enable attackers leak data acoustically from air-gapped and audio-gapped systems.

Our developed malware can exploit the computer power supply unit (PSU) to play sounds and use it as an out-of-band, secondary speaker with limited capabilities. The malicious code manipulates the internal \textit{switching frequency} of the power supply and hence controls the sound waveforms generated from its capacitors and transformers. Our technique enables producing audio tones in a frequency band of 0-24khz and playing audio streams (e.g., WAV) from a computer power supply without the need for audio hardware or speakers. Binary data (files, keylogging, encryption keys, etc.) can be modulated over the acoustic signals and sent to a nearby receiver (e.g., smartphone). We show that our technique works with various types of systems: PC workstations and servers, as well as embedded systems and IoT devices that have no audio hardware at all. We provide technical background and discuss implementation details such as signal generation and data modulation. We show that the POWER-SUPPLaY code can operate from an ordinary user-mode process and doesn't need any hardware access or special privileges. Our evaluation shows that using POWER-SUPPLaY, sensitive data can be exfiltrated from air-gapped and audio-gapped systems from a distance of five meters away at a maximal bit rates of 50 bit/sec.