International Association
for Cryptologic Research

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth ``chunks''. This approach was however previously limited to circuits with a ``layered'' structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions:

1) Fractionally linear-communication MPC in the correlated randomness model: We provide an $N$-party protocol for computing an $n$-input, $m$-output $\mathsf{F}$-arithmetic circuit with $s$ internal gates (over any basis of binary gates) with communication complexity $(\frac{2}{3}s + n + m)\cdot N\cdot\log |\mathsf{F}|$, which can be improved to $((1+\epsilon)\cdot\frac{2}{5}s+n+m)\cdot N\cdot\log |\mathsf{F}|$ (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than $s\cdot N\cdot \log |\mathsf{F}|$ bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold.

2) Sublinear-Communication MPC: Assuming the existence of $N$-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure $N$-party computation for \emph{all} $\log^{1+o(1)}$-depth (resp.~$(\log\log)^{1+o(1)}$-depth) circuits. Previously, this result was limited to $(\mathcal{O}(\log))$-depth (resp.~$(\mathcal{O}(\log\log))$-depth) circuits, or to circuits with a specific structure (e.g. layered).

3) The 1-out-of-M-OT complexity of MPC: We introduce the `` 1-out-of-M-OT complexity of MPC'' of a function $f$, denoted $C_M(f)$, as the number of oracle calls required to securely compute $f$ in the 1-out-of-M-OT hybrid model. We establish the following upper bound: for every $M\geq 2$, $C_N(f) \leq (1+g(M))\cdot \frac{2 |f|}{5}$, where $g(M)$ is an explicit vanishing function.

We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.

This article presents an in-depth study of isogeny-based cryptographic methods for the development of secure and scalable electronic voting systems. We address critical challenges such as voter privacy, vote integrity, and resistance to quantum attacks. Our work introduces novel cryptographic protocols leveraging isogenies, establishing a robust framework for post-quantum secure electronic voting. We provide detailed mathematical foundations, protocol designs, and security proofs, demonstrating the efficacy and scalability of our proposed system in large-scale elections.

Distributed training that enables multiple parties to jointly train a model on their respective datasets is a promising approach to address the challenges of large volumes of diverse data for training modern machine learning models. However, this approach immedi- ately raises security and privacy concerns; both about each party wishing to protect its data from other parties during training and preventing leakage of private information from the model after training through various inference attacks. In this paper, we ad- dress both these concerns simultaneously by designing efficient Differentially Private, secure Multiparty Computation (DP-MPC) protocols for jointly training a model on data distributed among multiple parties. Our DP-MPC protocol in the two-party setting is 56-794× more communication-efficient and 16-182× faster than previous such protocols. Conceptually, our work simplifies and improves on previous attempts to combine techniques from secure multiparty computation and differential privacy, especially in the context of ML training.

Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial state.

In this work, we propose and construct quantum Pseudorandom State Scramblers (PRSSs), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an ɛ-net of the state space. This significantly strengthens what standard PRSGs can induce, as they may only concentrate on a small region of the state space as long as the average output state approximates a Haar random state in total variation distance.

Our PRSS construction develops a parallel extension of the famous Kac's walk, and we show that it mixes exponentially faster than the standard Kac's walk. This constitutes the core of our proof. We also describe a few applications of PRSSs. While our PRSS construction assumes a post-quantum one-way function, PRSSs are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSGs.

We witness an increase in applications like cryptocurrency wallets, which involve users issuing signatures using private keys. To protect these keys from loss or compromise, users commonly outsource them to a custodial server. This creates a new point of failure, because compromise of such a server leaks the user’s key, and if user authentication is implemented with a password then this password becomes open to an offline dictionary attack (ODA). A better solution is to secret-share the key among a set of servers, possibly including user’s own device(s), and implement password authentication and signature computation using threshold cryptography.

We propose a notion of augmented password protected threshold signature scheme (aptSIG) which captures the best possible security level for this setting. Using standard threshold cryptography techniques, i.e. threshold password authentication and threshold signatures, one can guarantee that compromising up to t out of n servers reveals no information on either the key or the password. However, we extend this with a novel property, namely that compromising even all n servers also does not leak any information, except via an unavoidable ODA attack, which reveals the key (and the password) only if the attacker guesses the password.

We define aptSIG in the Universally Composable (UC) framework and show that it can be constructed very efficiently, using a black-box composition of any UC threshold signature and a UC augmented Password-Protected Secret Sharing (aPPSS), which we define as an extension of prior notion of PPSS. As concrete instantiations we obtain secure aptSIG schemes for ECDSA and BLS signatures with very small overhead over the respective threshold signature.

The Lattice Isomorphism Problem (LIP) was recently introduced as a new hardness assumption for post-quantum cryptography. The strongest known efficiently computable invariant for LIP is the genus of a lattice. To instantiate LIP-based schemes one often requires the existence of a lattice that (1) lies in some fixed genus, and (2) has some good geometric properties such as a high packing density or small smoothness parameter.

In this work we show that such lattices exist. In particular, building upon classical results by Siegel (1935), we show that essentially any genus contains a lattice with a close to optimal packing density, smoothing parameter and covering radius. We present both how to efficiently compute concrete existence bounds for any genus, and asymptotically tight bounds under weak conditions on the genus.

Blockchain-enabled digital currency systems have typically operated in isolation, lacking necessary mechanisms for seamless interconnection. Consequently, transferring assets across distinct currency systems remains a complex challenge, with existing schemes often falling short in ensuring security, privacy, and practicality. This paper proposes P2C2T -- a privacy-preserving cross-chain transfer scheme. It is the first scheme to address atomicity, unlinkability, indistinguishability, non-collateralization, and required functionalities across diverse currency systems. P2C2T is based on \textit{threshold anonymous atomic locks} (TA$^2$L), also proposed by us, serving as the cornerstone for guaranteeing atomic cross-chain transfer while obscuring the payment relationships between users. By combining TA$^2$L with \textit{verifiable timed discrete logarithm} schemes, P2C2T renders cross-chain transactions indistinguishable from regular intra-chain ones. Notably, P2C2T eliminates the collateralization of senders and imposes minimal requirements on underlying blockchains, specifically on the ability to verify signatures. We substantiate the security of TA$^2$L based on a proposed cryptographic notion called \textit{threshold blind conditional signatures} and demonstrate the security of P2C2T through necessary proofs. Additionally, we compare the performance of P2C2T with an existing scheme that has properties closest to P2C2T. The comparison reveals that P2C2T reduces overhead by at least $85.488\%$ in terms of running time, communication cost, and storage cost when completing a cross-chain transfer. We further conduct cross-chain transfers and intra-chain payments using the Bitcoin testnet and Litecoin testnet to illustrate the privacy and practicality of P2C2T.

In this work, we study constant round multiparty computation (MPC) for Boolean circuits against a fully malicious adversary who may control up to $n-1$ out of $n$ parties. Without relying on fully homomorphic encryption (FHE), the best-known results in this setting are achieved by Wang et al. (CCS 2017) and Hazay et al. (ASIACRYPT 2017) based on garbled circuits, which require a quadratic communication in the number of parties $O(|C|\cdot n^2)$. In contrast, for non-constant round MPC, the recent result by Rachuri and Scholl (CRYPTO 2022) has achieved linear communication $O(|C|\cdot n)$.

In this work, we present the first concretely efficient constant round MPC protocol in this setting with linear communication in the number of parties $O(|C|\cdot n)$. Our construction can be based on any public-key encryption scheme that is linearly homomorphic for public keys. Our work gives a concrete instantiation from a variant of the El-Gamal Encryption Scheme assuming the DDH assumption. The analysis shows that when the computational security parameter $\lambda=128$ and statistical security parameter $\kappa=80$, our protocol achieves a smaller communication than Wang et al. (CCS 2017) when there are $16$ parties for AES circuit and $8$ parties for general Boolean circuits (where we assume that the numbers of AND gates and XOR gates are the same). When comparing with the recent work by Beck et al. (CCS 2023) that achieves constant communication complexity $O(|C|)$ in the strong honest majority setting ($t<(1/2-\epsilon)n$ where $\epsilon$ is a constant), our protocol is better as long as $n<3500$ (when $t=n/4$ for their work).

Using a purity theorem for exponential sums due to Rojas-Léon, we upper bound the absolute correlations of linear approximations of the Flystel construction used in Anemoi. This resolves open problem 7.1 in [Bouvier, 2023].

Local Differential Privacy (LDP) provides a formal guarantee of privacy that enables the collection and analysis of sensitive data without revealing any individual's data. While LDP methods have been extensively studied, there is a lack of a systematic and empirical comparison of LDP methods for descriptive statistics. In this paper, we first provide a systematization of LDP methods for descriptive statistics, comparing their properties and requirements. We demonstrate that several mean estimation methods based on sampling from a Bernoulli distribution are equivalent in the one-dimensional case and introduce methods for variance estimation. We then empirically compare methods for mean, variance, and frequency estimation. Finally, we provide recommendations for the use of LDP methods for descriptive statistics and discuss their limitations and open questions.

Distributed Key Generation (DKG) is a technique that enables the generation of threshold cryptography keys among a set of mutually untrusting nodes. DKG generates keys for a range of decentralized applications such as threshold signatures, multiparty computation, and Byzantine consensus. Over the past five years, research on DKG has focused on optimizing network communication protocols to improve overall system efficiency by reducing communication complexity. However, SOTA asynchronous distributed key generation (ADKG) schemes (e.g., Kokoris-Kogias ADKG, CCS 2020 and Das ADKG, S\&P 2022, and others) only support recovery thresholds of either $f$ or $2f$, where $f$ is the maximum number of malicious nodes. This paper proposes an asynchronous verifiable secret sharing protocol featuring an elastic threshold, where $t \in [f,n-f-1]$ and $n \ge 3f+1$ is the total number of parties. Our protocol enables a dealer to share up to $t+1$ secrets with a total communication cost of O($\lambda n^3$), where $\lambda$ is the security parameter, and the protocol relies on the hardness of the $q$-SDH problem. We further modified the Schnorr protocol to enable simultaneous commitments to multiple secrets, which we refer to $m$-Schnorr.

Private set intersection (PSI) allows Sender holding a set \(X\) and Receiver holding a set \(Y\) to compute only the intersection \(X\cap Y\) for Receiver. We focus on a variant of PSI, called fuzzy PSI (FPSI), where Receiver only gets points in \(X\) that are at a distance not greater than a threshold from some points in \(Y\).

Most current FPSI approaches first pick out pairs of points that are potentially close and then determine whether the distance of each selected pair is indeed small enough to yield FPSI result. Their complexity bottlenecks stem from the excessive number of point pairs selected by the first picking process. Regarding this process, we consider a more general notion, called fuzzy mapping (Fmap), which can map each point of two parties to a set of identifiers, with closely located points having a same identifier, which forms the selected point pairs.

We initiate the formal study on Fmap and show novel Fmap instances for Hamming and \(L_\infty\) distances to reduce the number of selected pairs. We demonstrate the powerful capability of Fmap with some superior properties in constructing FPSI variants and provide a generic construction from Fmap to FPSI.

Our new Fmap instances lead to the fastest semi-honest secure FPSI protocols in high-dimensional space to date, for both Hamming and general \(L_{\mathsf p\in [1, \infty]}\) distances. For Hamming distance, our protocol is the first one that achieves strict linear complexity with input sizes. For \(L_{\mathsf p\in [1, \infty]}\) distance, our protocol is the first one that achieves linear complexity with input sizes, dimension, and threshold.

We study error detection and error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial time adversarial channel. We consider codes where the encoding procedure uses random coins and define two distinct variants: (1) in randomized codes, fresh randomness is chosen during each encoding operation and is unknown a priori, while (2) in self-seeded codes, the randomness of the encoding procedure is fixed once upfront and is known to the adversary. In both cases, the randomness need not be known to the decoding procedure, and there is no trusted common setup between the encoder and decoder. The encoding and decoding algorithms are efficient and run in some fixed polynomial time, independent of the run time of the adversary.

The parameters of standard codes for worst-case (inefficient) errors are limited by the Singleton bound: for rate $R$ it is not possible to detect more than a $1-R$ fraction of errors, or uniquely correct more than a $(1-R)/2$ fraction of errors, and efficient codes matching this bound exist for sufficiently large alphabets. In the computationally bounded setting, we show that going beyond the Singleton bound implies one-way functions in the case of randomized codes and collision-resistant hash functions in the case of self-seeded codes. We construct randomized and self-seeded codes under these respective minimal assumptions with essentially optimal parameters over a constant-sized alphabet:

- Detection: the codes have a rate $R \approx 1$ while detecting a $\rho \approx 1$ fraction of errors. - Correction: for any $\rho < 1/2$, the codes uniquely correct a $\rho$ fraction of errors with rate $R \approx 1-\rho$.

Codes for computationally bounded errors were studied in several prior works starting with Lipton (STACS '94), but all such works either: (a) need some trusted common setup (e.g., public-key infrastructure, common reference string) between the encoder and decoder, or (b) only handle channels whose complexity is a prior bounded below that of the code.

Modern data analytics requires computing functions on streams of data points from many users that are challenging to calculate, due to both the high scale and nontrivial nature of the computation at hand. The need for data privacy complicates this matter further, as general-purpose privacy-enhancing technologies face limitations in at least scalability or utility. Existing work has attempted to improve this by designing purpose-built protocols for the use case of Private Stream Aggregation; however, prior work lacks the ability to compute more general aggregative functions without the assumption of trusted parties or hardware.

In this work, we present PPSA, a protocol that performs Private Polynomial Stream Aggregation, allowing the private computation of any polynomial function on user data streams even in the presence of an untrusted aggregator. Unlike previous state-of-the-art approaches, PPSA enables secure aggregation beyond simple summations without relying on trusted hardware; it utilizes only tools from cryptography and differential privacy. Our experiments show that PPSA has low latency during the encryption and aggregation processes with an encryption latency of 10.5 ms and aggregation latency of 21.6 ms for 1000 users, which are up to 138$\times$ faster than the state-of-the-art prior work.

We revisit the lattice-based verifiable oblivious PRF construction from PKC'21 and remove or mitigate its central three sources of inefficiency. First, applying Rényi divergence arguments, we eliminate one superpolynomial factor from the ciphertext modulus \(q\), allowing us to reduce the overall bandwidth consumed by RLWE samples by about a factor of four. This necessitates us introducing intermediate unpredictability notions to argue PRF security of the final output in the Random Oracle model. Second, we remove the reliance on the \(\mathsf{1D-SIS}\) assumption, which reduces another superpolynomial factor, albeit to a factor that is still superpolynomial. Third, by applying the state-of-the-art in zero-knowledge proofs for lattice statements, we achieve a reduction in bandwidth of several orders of magnitude for this material. Finally, we give a \(t\)-out-of-\(n\) threshold variant of the VOPRF for constant \(t\) and with trusted setup, based on a \(n\)-out-of-\(n\) distributed variant of the VOPRF (and without trusted setup).

Passive (leakage exploitation) and active (fault injection) physical attacks pose a significant threat to cryptographic schemes. Although leakage-resistant cryptography is well studied, there is little work on mode-level security in the presence of joint faults and leakage exploiting adversaries. In this paper, we focus on integrity for authenticated encryption (AE). First, we point out that there is an inherent attack in the fault-resilience model presented at ToSC 2023. This shows how fragile the freshness condition of a forgery is when faults are injected into either the tag-generation or the encryption algorithm. Therefore, we provide new integrity definitions for AE in the presence of leakage and faults, and we follow the atomic model, in which the scheme is divided into atoms (or components, e.g. a call to a block cipher) and allows the adversary to inject a fault only into the inputs of an atom. We envision this model as a first step for leveled implementations in the faults context, the granularity of atoms can be made finer or coarser (for example, instead of considering a call to a block cipher, we can consider atoms to be rounds of the block cipher). We hold the underlying belief that it would be easier to protect smaller blocks than a full scheme. The proposed model is very flexible and allows us to understand where to apply faults countermeasures (in some very interesting cases this model can reduce faults inside atoms to faults on their outputs, as we discuss). We then show that an AE-scheme using a single call to a highly leakage-protected (and thus very expensive) component, CONCRETE (presented at Africacrypt 2019), maintains integrity in the presence of leakage in both encryption and decryption, and faults only in decryption.On the other hand, a single fault in encryption is enough to forge. Therefore, we first introduce a weaker definition (which restricts the meaning of freshness), weak integrity, which CONCRETE achieves even if the adversary can introduce faults in the encryption queries (with some restrictions on the number and type of faults). Finally, we provide a variant, CONCRETE2, which is slightly more computationally expensive, but still uses a single call to a strongly protected component that provides integrity in the presence of leakage and faults.

True Random Number Generators (TRNGs) and Physically Unclonable Functions (PUFs) are critical hardware primitives for cryptographic systems, providing randomness and device-specific security. TRNGs require complete randomness, while PUFs rely on consistent, device-unique responses. In this work, both primitives are implemented on a System-on-Chip Field-Programmable Gate Array (SoC FPGA), leveraging the integrated Phase-Locked Loops (PLLs) for robust entropy generation in PLLbased TRNGs. A novel backtracking parameter selection algorithm for the TRNG implementation is employed, alongside a methodology to boost data generation rates without compromising entropy. The design is rigorously evaluated using the German BSI AIS-20/31 standards. For the PUF implementation, the Arbiter PUF, known for its lightweight design and key generation, is enhanced to resist machine learning attacks by implementing a 32-bit and a 64-bit component-differentially challenged XOR Arbiter PUF (CDC-XPUF). These designs are tested using standard PUF metrics, including uniformity, correctness, and uniqueness. Finally, a combined 4-PLL-TRNG and 64-bit CDC-XPUF design is introduced and evaluated for its suitability in Internet-of-Things (IoT) systems, demonstrating strong performance in both TRNG and PUF tests. The tests are conducted on the Xilinx Zynq 7020 SoC using a ZC702 evaluation board, confirming the effectiveness of this integrated approach for secure, low-resource applications like IoT.

Event date: 25 March to
Submission deadline: 23 November 2024
Notification: 24 January 2025

Event date: 28 October to 1 November 2024

We are looking for a bright and motivated PhD student for a 3-year fully funded PhD position starting January 1st, 2025 (negotiable). The project is financed by the Independent Research Fund Denmark, and it is a collaboration between DTU, the University of Cambridge (UK), the Royal Holloway University of London (UK), and Stony Brook University (USA). It is an excellent opportunity to be involved in advanced research on cyber-security and cyber-deception, with important practical applications.

The position is part of the project Loki: Situational aware collaborative bio-inspired cyber-deception. This project, inspired by Norse mythology, with Loki being a shape-shifter god and a master of trickery, aims at redefining and evolving the emerging field of cyber-deception. Here, we attempt to deceive attackers by creating fake vulnerable systems that are aware of their surroundings and are constantly shifting. The project takes inspiration from nature (e.g., from the mimicry phenomenon) to synthesize sophisticated deception.

Closing date for applications:

Contact: Emmanouil Vasilomanolakis

More information: https://efzu.fa.em2.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1/job/4075