Miyaji Laboratory

The potential development of large-scale quantum computers has raised serious concerns about the security of classical cryptographic systems. In response, the field of post-quantum cryptography has emerged to design cryptographic schemes that remain secure even against quantum adversaries. Isogeny-based cryptography is the most recent addition to post-quantum cryptography and started garnering attention in the 2010s. Digital signature schemes are a fundamental part of public key cryptography, providing authenticity, integrity, and non-repudiation for digital messages. They are essential for secure communication, software updates, electronic transactions, and virtually all systems requiring trust and verification. Although the traditional digital signature scheme consists only of a single prover and verifier, numerous variants have been developed over the years to address specific needs, such as multi-signatures, ring signatures, group signatures, and proxy signatures. These variants extend the functionality of traditional signatures to support more complex security models in real-world applications, such as contact tracing. As isogeny-based cryptography is a relatively young research field, many commonly used cryptographic primitives, such as variants of signature schemes, have not yet been fully developed or widely implemented. This leaves room for exploration and optimization in designing secure and efficient isogeny-based alternatives, while taking advantage of its strength with its small keys and signature compared to other post-quantum based constructions such as lattice.

Multi-signature schemes have been extensively studied for decades and form a well-established area of research in cryptography. These schemes enable a group of users to collaboratively generate a single, compact signature on a shared message, ensuring that all designated parties have approved the content. Their efficiency and security properties make them particularly valuable in applications such as blockchain transactions and distributed systems. Active security in multi-signature schemes requires the signature to be unforgeable even in the worst-case scenario, where malicious signers would collude to generate a multi-signature in a group with a single honest signer. Our first contribution is to propose an actively secure isogeny-based multi-signature scheme.

Proxy signature schemes have been the subject of extensive research over the years, offering cryptographic solutions for secure delegation of signing authority. These schemes allows an original signer to designate a proxy signer to generate signatures on their behalf, within the limitations imposed by the original signer. Such mechanisms are particularly useful in settings like secure communications, delegated access control, and corporate approval systems where it is essential for operations to continue even in the absence of the designated signer. Proxy signatures are required to be unforgeable even if either the original or the proxy signer is malicious, which is commonly referred to as the existential unforgeability under chosen message attack and chosen warrant attack. Some security models with more stringent requirements, such as existential unforgeability under chosen message attack with proxy key exposition (EUFCMA-PKE), require the proxy signature to be unforgeable even if the proxy signing key are leaked. Our second contribution is to propose two proxy signatures satisfying both models using isogeny-based cryptography.

Contact tracing applications have become a crucial tool in managing public health during pandemics, relying on digital protocols to identify and notify individuals exposed to infectious diseases. These systems must balance effective tracking with strong privacy guarantees, ensuring that users' identities remain confidential. At the same time, it is essential that they reflect accurately the situation on the ground. To achieve this, advanced cryptographic techniques, such as ring signatures and multi-signatures, can be employed, making contact tracing a promising real-world application for these variant signature schemes. Our third contribution is to propose a contact tracing application which correctly reflects the interactions between patients and their close contacts while preserving the privacy of its users.

The work of this dissertation is divided into studies about isogeny-based multi-signatures, isogeny-based proxy signatures, and efficient multi-party contact tracing protocols.

• A proposal of an actively secure isogeny-based multi-signature that uses zero-knowledge proofs and commitments to guarantee the existential unforgeability of the signature.

• A proposal of two isogeny-based proxy signature protocols guaranteeing existential unforgeability in the case of a corrupted original or proxy signer, one designed to remain secure even in the event of proxy key leakage, and another constructed under the assumption that the proxy key remains secret.

• A proposal of a contact tracing protocol using ID-based ring signatures and multi-signatures to accurately reflect the interactions between users in an efficient way while preserving their privacy.

The first study is composed of the first isogeny-based multi-signature scheme by extending the isogeny-based signature scheme CSI-SharK [ABCP22] to the multi-party setting. Our scheme is proven unforgeable in the random oracle model under the MT-GAIP and Ck−1-VPwAI assumptions. To achieve security, a new proof system based on zero-knowledge proof and commitments is proposed by modifying the piecewise verifiable proof system proposed in the Distributed Key Generation protocol CSI-RASHI [BDPV21].

The second study is composed of two isogeny-based proxy signature protocols, PKE and CWA, based on CSI-SharK. Both are proven unforgeable under the MT-GAIP and Ck−1-VPwAI assumptions in the quantum random oracle model and considers chosen message attacks (corrupted original signer) and chosen warrant attacks (corrupted proxy signer), but only the former considers the risk of proxy key leakage.

The third study is composed of a privacy-preserving contact tracing application that accurately represents the interaction of its users, such as the number of participants. It is achieved by using the contact tracing protocol proposed by Liu et al. [LAY+20] and adapt it to the multi-party setting by incorporating a multi-signature [DGNW20, MM00] as a proof of the meeting and a ring signature [CYH05] as a way to alert the close contacts while preserving the patient's privacy.

To summarize, the first two studies adapt a variant signature scheme, i.e., a multi-signature and a proxy signature, to the isogeny-based setting, while the third study proposes a potential application of such variant schemes. The multi-signature scheme from the first study can be integrated into the third study's contact tracing protocol by replacing it, although the protocol would need to be adjusted to compensate for the lack of ID-based ring signatures in isogeny-based cryptography.