Keitaro Hashimoto (𣘺本 啓太郎)

WireGuard is a VPN based on the Noise protocol, known for its high performance, small code base, and unique security features. Recently, Hülsing et al. (IEEE S&P’21) presented post-quantum (PQ) WireGuard, replacing the Diffie-Hellman (DH) key exchange underlying the Noise protocol with key-encapsulation mechanisms (KEMs). Since WireGuard requires the handshake message to fit in one UDP packet of size roughly 1200 B, they combined Classic McEliece and a modified variant of Saber. However, as Classic McEliece public keys are notoriously large, this comes at the cost of severely increasing the server’s memory requirement. This hinders deployment, especially in environments with constraints on memory (allocation), such as a kernel-level implementations. In this work, we revisit PQ WireGuard and improve it on three fronts: design, (computational) security, and efficiency. As KEMs are semantically, but not syntactically, the same as DH key exchange, there are many (in hindsight) ad-hoc design choices being made, further amplified by the recent finding on the binding issues with PQ KEMs (Cremers et al., CCS’24). We redesign PQ WireGuard addressing these issues, and prove it secure in a new computational model by fixing and capturing new security features that were not modeled by Hülsing et al. We further propose ’reinforced KEM’ (RKEM) as a natural building block for key exchange protocols, enabling a PQ WireGuard construction where the server no longer needs to store Classical McEliece keys, reducing public key memory by 190 to 390×. In essence, we construct a RKEM named ’Rebar’ to compress two ML-KEM-like ciphertexts which may be of an independent interest.

Registered Attribute-Based Encryption (RABE) enhances traditional attribute-based encryption by allowing users to register their own public keys, while a key curator transparently aggregates these keys into a compact master public key, addressing key escrow issues. In long-term applications, the compromise of users’ secret keys becomes a significant risk, making key revocation a critical functionality. In this paper, we initiate a formal study of key revocation mechanisms for RABE and introduce two types: Deletable Registered Attribute-Based Encryption (DRABE) and Directly Revocable Registered Attribute-Based Encryption (RRABE). The key distinction between these two approaches lies in how the revocation process is managed. In DRABE, the key curator handles revocation by deleting previously registered keys and updating the master public key. In contrast, RRABE bypasses the need for such updates, allowing the encryptor to directly specify a set of revoked users during encryption. Our primary contribution is the construction of DRABE, where we propose a generic framework based on Slotted Registered Attribute-Based Encryption (sRABE), a primitive introduced by Hohenberger et al. at EUROCRYPT 2023. This generic construction inherits the predicate structure of the underlying sRABE scheme, enabling DRABE to support a wide range of predicates. By instantiating our construction with existing sRABE schemes, we obtain efficient pairing-based DRABE schemes for a bounded number of users, as well as schemes for an unbounded number of users, though the latter relies on non-black-box cryptographic techniques. For RRABE, we propose a semi-generic construction for Boolean formulae, leveraging RABE schemes that support these predicates. This yields RRABE schemes (supporting Boolean formulae) under assumptions similar to those used in the DRABE case. At the core of our generic construction (of DRABE) lies an unexplored interplay between Hohenberger et al.’s “power-of-two” construction and the complete binary tree structure, which may be of independent interest.

A multi-designated verifier signature (MDVS) is a digital signature that empowers a signer to designate specific verifiers capable of verifying signatures. Notably, designated verifiers are allowed to not only verify signatures but also simulate "fake" signatures indistinguishable from real ones produced by the original signer. Since this property is useful for realizing off-the-record (i.e., deniable) communication in group settings, MDVS is attracting attention in secure messaging. Recently, Damgård et al. (TCC’20) and Chakraborty et al. (EUROCRYPT’23) have introduced new MDVS schemes, allowing a subset of designated verifiers to simulate signatures in contrast to the conventional one, which requires all designated verifiers for signature simulation. They also define a stronger notion of security for them. This work delves into this new MDVS and offers a comprehensive formalization. We identify all possible security levels of MDVS schemes in subset simulations and prove that some of them are not feasible. Furthermore, we demonstrate that MDVS schemes meeting the security notion defined by Chakraborty et al. imply IND-CCA secure public-key encryption schemes. Beyond formalization, we present new constructions of MDVS schemes in subset simulation. Notably, we introduce a new construction of strongly secure MDVS schemes based on ring signatures and public-key encryption, accompanied by a generic conversion for achieving consistency through non-interactive zero-knowledge arguments. Finally, we evaluate the efficiency of our MDVS schemes in classical and post-quantum settings, showing their practicality.

The Signal protocol relies on a special handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. Prior analysis of these protocols (or proposals for post-quantum alternatives) has all used highly tailored models to the individual protocols and generally made ad-hoc adaptations to “standard” AKE definitions, making the concrete security attained unclear and hard to compare between similar protocols. Indeed, we observe that some natural Signal handshake protocols cannot be handled by these tailored models. In this work, we introduce Bundled Authenticated Key Exchange (BAKE), a concrete treatment of the Signal handshake protocol. We formally model prekey bundles and states, enabling us to define various levels of security in a unified model. We analyse Signal’s classically secure X3DH and harvest- now-decrypt-later-secure PQXDH, and show that they do not achieve what we call optimal security (as is documented). Next, we introduce RingXKEM, a fully post-quantum Signal handshake protocol achieving optimal security; as RingXKEM shares states among many prekey bundles, it could not have been captured by prior models. Lastly, we provide a security and efficiency comparison of X3DH, PQXDH, and RingXKEM.

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype,Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong(or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available