The Fiat-Shamir with Aborts technique and its application to lattice-based signatures

Abstract

When developing secure signature schemes, a common approach is constructing a secure identification scheme and then transforming it into a non-interactive signature scheme using the Fiat-Shamir Transformation. Therefore, one can use a newly introduced technique, the Aborting Technique. With the use of the Aborting Technique, the resulting signature scheme is more efficient than without the use of the Aborting Technique. This work introduces the Fiat-Shamir Transformation, specifically in a factoring-based cryptographic setting. We comprehensively describe the Fiat-Shamir Transformation, including identification schemes and signature schemes. Additionally, we examine the cryptographic primitives used in the Fiat-Shamir Transformation and those employed in the identification and signature scheme. An essential aspect of the Fiat-Shamir Transformation with Aborts is the probability that one can expect to abort the protocol, which is crucial for evaluating the efficiency and security of the protocol. A short introduction to the Rejection Sampling Technique used in the Fiat-Shamir Transformation with Aborts is given, and we consider the mathematics behind that technique. After that, we will apply the Fiat-Shamir Transformation in the lattice-based cryptographic setting, where we give a short introduction to lattice-based mathematics. Bei der Entwicklung sicherer Signaturverfahren besteht ein gängiger Ansatz darin, zunächst ein sicheres Identifikationsverfahren zu konstruieren und dieses dann mit Hilfe der Fiat-Shamir Transformation in ein nicht-interaktives Signaturverfahren umzuwandeln. Dazu kann man eine neu eingeführte Technik, die Aborting (Abbruch)-Technik anwenden. Durch den Einsatz der Aborting-Technik ist das resultierende Signaturverfahren effizienter als ohne den Einsatz der Aborting-Technik. Die vorliegende Arbeit befasst sich mit der Einführung der Fiat-Shamir Transformation, insbesondere im Zusammenhang mit der faktorbasierten kryptographischen Umgebung. Konkret wird die Fiat-Shamir Transformation beschrieben, aber auch Identifikations- und Signaturverfahren werden behandelt. Darüber hinaus schauen wir die kryptographischen Primitive, die in der Fiat-Shamir Transformation verwendet werden sowie diejenigen, die im Identifikations- und Signaturverfahren eingesetzt werden an. Ein wichtiger Aspekt der Fiat-Shamir Transformation mit Abbrüchen ist die Wahrscheinlichkeit, mit der man erwarten kann, das Protokoll abzubrechen. Dies spielt eine wichtige Rolle in der Bewertung der Effizienz und Sicherheit des Protokolls. Es wird eine kurze Einführung über die Rejection Sampling Technik gegeben, die in der Fiat-Shamir Transformation mit Abbrüchen verwendet wird. Dabei wird auch die Mathematik dieser Technik angeschaut. Danach wenden wir die Fiat-Shamir Transformation in der gitterbasierten kryptographischen Umgebung an, wobei wir auch eine kurze Einführung in die gitterbasierte Mathematik geben.