International Association
for Cryptologic Research

Multi-authority/input attribute-based encryption (MA-/MI-ABE) are multi-party extensions of ABE which enable flavours of decentralised cryptographic access control. This work aims to advance research on multi-party ABE and their lattice-based constructions in several directions:

- We introduce the notion of multi-client (MC-)ABE. This can be seen as an augmentation of MI-ABE with the addition of a ciphertext identity (CID) in the syntax, or a specialisation of multi-client functional encryption (MC-FE) to the ABE setting.

- We adapt the 2-input (2I-)ABE of Agrawal et al. (CRYPTO'22), which is heuristically secure yet without a security proof, into a 2-client (2C-)ABE, and prove it satisfies a variant of very-selective security under the learning with errors (LWE) assumption.

- We extend Wee's ciphertext-policy (CP-)ABE (EUROCRYPT'22) to the MA setting, yielding an MA-ABE. Furthermore, combining techniques in Boneh et al.'s key-policy ABE (EUROCRYPT'14) and our MA-ABE, we construct an MC-ABE. We prove that they satisfy variants of very-selective security under the evasive LWE, tensor LWE, and LWE assumptions.

All our constructions support policies expressed as arbitrary polynomial-size circuits, feature distributed key generation (for MA) and encryption (for 2C/MC), and are proven secure in the random oracle model. Although our constructions only achieve limited security against corrupt authorities/clients, the fully distributed key generation/encryption feature makes them nevertheless non-trivial and meaningful.

Prior to this work, existing MA-ABEs only support up to NC1 policies regardless of their security against corrupt authorities; existing MI-ABEs only support up to constant-many encryptors/clients and do not achieve any security against corrupt encryptors/clients; and MC-ABEs only existed in the form of MC-FEs for linear and quadratic functions.

In LWE based cryptosystems, using small (polynomially large) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs simulation security: the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Renyi divergence based analyses that are sufficient for game-based but not simulation security.

In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially large modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.

Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require confidentiality. ACSS permits a dealer to distribute a secret to a collection of N servers so that everyone holds shares of a polynomial containing the dealer's secret.

This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for large secrets. Haven++ allows the dealer to pack multiple secrets in a single sharing phase, and to reconstruct either one or all of them later. For even larger secrets, we contribute a batching technique to amortize the cost of proof generation and verification across multiple invocations of our protocol.

The result is an asymptotic improvement in the worst-case amortized communication and computation complexity, both for ACSS itself and for its application to asynchronous distributed key generation. Our ADKG based on Haven++ achieves, for the first time, an optimal worst case amortized communication complexity of κN without a trusted setup. To show the practicality of Haven++, we implement it and find that it outperforms the work of Yurek et al. (NDSS 2022) by more than an order of magnitude when there are malicious, faulty parties.

We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing the limitations of existing isogeny-based ring signatures.

First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas.

Second, we propose a variant of SQIsign (Asiacrypt'20) that is resistant to the distinguisher attack with only a x1.4 increase in size and we render it to a ring signature, that we refer to as Erebor. This variant introduces a new zero-knowledge assumption that ensures full anonymity. The efficiency of Erebor remains comparable to that of SQIsign, with only a proportional increase due to the ring size. This results in a signature size of 0.71 KB for 4 users and 1.41 KB for 8 users, making it the most compact post-quantum ring signature for up to 29 users.

Third, we revisit the GPS signature scheme (Asiacrypt'17), developing efficient subroutines to make the scheme more efficient and significantly reduce the resulting signature size. By integrating our scheme with the paradigm by Beullens, Katsumata, and Pintore (Asiacrypt’20), we achieve an efficient logarithmic ring signature, that we call Durian, resulting in a signature size of 9.87 KB for a ring of size 1024.

The server-aided model for multiparty computation (MPC) was introduced to capture a real-world scenario where clients wish to off-load the heavy computation of MPC protocols to dedicated servers. A rich body of work has studied various trade-offs between security guarantees (e.g., semi-honest vs malicious), trust assumptions (e.g., the threshold on corrupted servers), and efficiency.

However, all existing works make the assumption that all clients must agree on employing the same servers, and accept the same corruption threshold. In this paper, we challenge this assumption and introduce a new paradigm for server-aided MPC, where each client can choose their own set of servers and their own threshold of corrupted servers. In this new model, the privacy of each client is guaranteed as long as their own threshold is satisfied, regardless of the other servers/clients. We call this paradigm per-party private server-aided MPC to highlight both a security and efficiency guarantee: (1) per-party privacy, which means that each party gets their own privacy guarantees that depend on their own choice of the servers; (2) per-party complexity, which means that each party only needs to communicate with their chosen servers. Our primary contribution is a new theoretical framework for server-aided MPC. We provide two protocols to show feasibility, but leave it as a future work to investigate protocols that focus on concrete efficiency.

Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker.

In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices).

We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).

Dynamic Searchable Symmetric Encryption (DSSE) allows users to securely outsource their data to cloud servers while enabling efficient searches and updates. The verifiability property of a DSSE construction ensures that users do not accept incorrect search results from a malicious server while the fault-tolerance property guarantees the construction functions correctly even with faulty queries from the client (e.g., adding a keyword to a document multiple times, deleting a keyword from a document that was never added). There have been very few studies on fault-tolerant verifiable DSSE schemes that achieve forward privacy, and none of the existing constructions achieve backward privacy. In this paper, we aim to design an efficient fault-tolerant verifiable DSSE scheme that provides both forward and backward privacy. First, we propose a basic fault-tolerant verifiable DSSE scheme, dubbed $\textsf{FVS1}$, which achieves forward privacy and stronger backward privacy with the update pattern (BPUP). However, the communication complexity for the search operation of this scheme is $O(u)$, where $u$ is the total number of updates for the search keyword. To address this issue, we propose an efficient variant of the previous DSSE scheme, called $\textsf{FVS2}$, which achieves the same functionality with an optimized communication complexity of $O(m+u')$ for search queries. Here $m$ is the size of the result set and $u'$ is the number of update operations made on the queried keyword after the previous search made on the keyword. This improvement comes at the cost of some additional information leakage, but it ensures the construction achieves backward privacy with the link pattern (BPLP).

A linear error-correcting code exhibits proximity gaps if each affine line of words either consists entirely of words which are close to the code or else contains almost no such words. In this short note, we prove that for each linear code which exhibits proximity gaps within the unique decoding radius, that code's interleaved code also does. Combining our result with a recent argument of Angeris, Evans and Roh ('24), we extend those authors' sharpening of the tensor-based proximity gap of Diamond and Posen (Commun. Cryptol. '24) up to the unique decoding radius, at least in the Reed–Solomon setting.

FALCON is a signature selected for standardisation of the new Post-Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers, which is unusual in the cryptography field. Although recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most noticeably, how to protect the floor function. In this work, we propose to complete the first existing tests of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proofs in the probing model by ensuring Multiple Input Multiple Output Strong Non-Interference (MIMO-SNI) security. We provide performances on a laptop computer of our gadgets as well as of a complete masked FALCON. We notice significant overhead in doing so and discuss the deployability of our method in a real-world context.

In recent years, there has been much focus on developing core cryptographic primitives based on lattice assumptions, driven by the NIST call for post-quantum key encapsulation and digital signature algorithms. However, more work must be conducted on efficient privacy-preserving protocols based on quantum-safe assumptions. Electronic voting is one such privacy-preserving protocol whose adoption is increasing across the democratic world. E-voting offers both a fast and convenient alternative to postal voting whilst further ensuring cryptographic privacy of votes and offering full verifiability of the process. Owing to the sensitivity of voting and its infrastructure challenges, it is crucial to ensure security against quantum computers is baked into e-voting solutions. We present an e-voting scheme from quantum-safe assumptions based on the hardness of the RLWE and NTRU lattice problems, providing concrete parameters and an efficient implementation. Our design achieves a factor $5.3 \times$ reduction in ciphertext size, $2.5 \times$ reduction in total communication cost, and $2 \times$ reduction in total computation time compared to the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). We argue that the efficiency of this scheme makes it suitable for real-world elections. Our scheme makes use of non-ternary NTRU secrets to achieve optimal parameters. In order to compute the security of our design, we extend the ternary-NTRU work of Ducas and van Woerden (ASIACRYPT 2021) by determining the concrete fatigue point (for general secrets) of NTRU to be $q = 0.0058 \cdot \sigma^2 \cdot d^{2.484}$ (above which parameters become overstretched) for modulus $q$, ring dimension $d$, and secrets drawn from a Gaussian of parameter $\sigma$. We consider this relation to be of independent interest and demonstrate its significance by improving the efficiency of the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022).

Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves – known as "BGJ1" and "BDGL" in the literature - that scales across multiple servers (with varying success). This class of algorithms requires exponential memory which had put into question their ability to scale across sieving nodes. We discuss our architecture and optimisations and report experimental evidence of the efficiency of our approach.