The subfield bilinear collision problem and its application to post-quantum signatures

Abstract

In this dissertation, we introduce the Subfield Bilinear Collision (SBC) problem as a new cryptographic hardness assumption and explore its application to post-quantum signature schemes. First, we construct an MPC-in-the-Head (MPCitH) based identification protocol and digital signature scheme from SBC. The resulting signature scheme is more compact compared to previous post-quantum MPCitH proposals, while retaining efficient signing and verification algorithms. Building on this, we design a VOLE-in-the-Head (VOLEitH) signature scheme from SBC, further reducing communication costs and signature size. In order to achieve these improvements, we develop new generic techniques, including a faster hypercube folding algorithm, the correlated GGM forest, and MinMax commitments for GGM trees. These optimizations are not tied to the SBC problem and can therefore be applied more broadly to improve the efficiency of schemes based on MPCitH and VOLEitH. Finally, we extend the methodology of MPCitH beyond digital signatures to Fully Homomorphic Encryption (FHE). We propose Fherret, a novel proof system that leverages MPCitH techniques to provide correctness and honest evaluation guarantees for FHE while preserving circuit privacy. This approach protects against reaction-based attacks without requiring the heavy overhead of zk-SNARK-based methods.

In dieser Dissertation stellen wir das Subfield Bilinear Collision (SBC) Problem als neue kryptografische Annahme vor und untersuchen dessen Anwendung auf quantenresistente digitale Signaturen. Zunächst konstruieren wir ein Identifikationsprotokoll, basierend auf MPC-in-the-Head (MPCitH) sowie ein darauf aufbauendes digitales Signaturschema aus dem SBC Problem. Die resultierende Signatur ist kompakter als bisherige quantenresistente MPCitH Schemata und ermöglicht effiziente Algorithmen zum Signieren und Verifizieren. Darauf aufbauend entwickeln wir zusätzlich ein VOLE-in-the-Head (VOLEitH) Signaturschema, basierend auf dem SBC Problem, welches die Kommunikationskosten und Signaturgröße nochmals reduziert. Um diese Verbesserungen zu erreichen, entwickeln wir neue generische Techniken. Darunter einen schnelleren Algorithmus zum Berechnen des Hypercube-Foldings, den korrelierten GGM Forest sowie das MinMax Commitment-Verfahren für GGM Binärbäume. Diese Optimierungen sind nicht an das SBC Problem gebunden und können daher zur Effizienzsteigerung von Signaturverfahren, basierend auf MPCitH und VOLEitH genutzt werden. Abschließend erweitern wir die MPCitH Techniken über digitale Signaturen hinaus auf vollständig homomorphe Verschlüsselungsverfahren (FHE). Mit Fherret präsentieren wir ein neuartiges Beweissystem, welches ebenfalls Techniken aus MPCitH benutzt, um die Korrektheit und ehrliche Auswertung von FHE Verfahren zu gewährleisten und gleichzeitig die Circuit Privacy erhält.