TU Darmstadt / ULB / TUprints

Code-based Identification and Signature Schemes

EL Yousfi Alaoui, Sidi Mohamed (2013)
Code-based Identification and Signature Schemes.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Other (PDF)
Elyousfi_Dissertation.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (747kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Code-based Identification and Signature Schemes
Language: English
Referees: Buchmann, Prof. Johannes ; Otmani, Prof. Ayoub ; Cayrel, Asso.Prof. Pierre-Louis
Date: 24 June 2013
Place of Publication: Darmstadt
Date of oral examination: 3 June 2013
Corresponding Links:
Abstract:

In an age of explosive growth of digital communications and electronic data storage, cryptography plays an integral role in our society. Some examples of daily use of cryptography are software updates, e-banking, electronic commerce, ATM cards, etc. The security of most currently used cryptosystems relies on the hardness of the factorization and discrete logarithm problems. However, in 1994 Peter Shor discovered polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. Therefore, it is of extreme importance to develop cryptosystems that remain secure even when the adversary has access to a quantum computer; such systems are called post-quantum cryptosystems. One promising candidate is based on codes; in this thesis we focus more specifically on code-based identification and signature schemes. Public key identification schemes are typically applied in cryptography to reach the goal of entity authentication. Their applications include authentication and access control services such as remote login, credit card purchases and many others. One of the most well-known systems of this kind is the zero-knowledge identification scheme introduced in Crypto 1993 by Stern. It is very fast compared to schemes based on number-theoretic problems since it involves only simple and efficiently executable operations. However, its main drawbacks are the high communication complexity and the large public key size, that makes it impractical for many applications. Our first contribution addresses these drawbacks by taking a step towards reducing communication complexity and public key size simultaneously. To this end, we propose a novel zero-knowledge five-pass identification scheme which improves on Stern's scheme. It reduces the communication complexity by a factor of 25 % compared to Stern's one. Moreover, we obtain a public key of size of 4 KB, whereas Stern's scheme requires 15 KB for the same level of security. To the best of our knowledge, there is no code-based identification scheme with better performance than our proposal using random codes. Our second contribution consists of extending one of the most important paradigms in cryptography, namely the one by Fiat and Shamir. In doing so, we enlarge the class of identification schemes to which the Fiat-Shamir transform can be applied. Additionally, we put forward a generic methodology for proving the security of signature schemes derived from this class of identification schemes. We exemplify our extended paradigm and derive a provably secure signature scheme based on our proposed five-pass identification scheme. In order to contribute to the development of post-quantum schemes with additional features, we present an improved code-based threshold ring signature scheme using our two previous results. Our proposal has a shorter signature length and a smaller public-key size compared to Aguilar et al.'s scheme, which is the reference in this area.

Alternative Abstract:
Alternative AbstractLanguage

Gegenwärtig spielt die Kryptographie eine fundamentale Rolle bei der Absicherung einer Vielzahl von täglichen Anwendungen und Prozessen. Dazu gehören beispielsweise Software-Updates, E-Commerce und E-Banking Anwendungen. Die Sicherheit der am häufigsten in der Praxis eingesetzten kryptographischen Verfahren beruht auf der Schwierigkeit, große Zahlen in ihre Primfaktoren zu zerlegen oder diskrete Logarithmen zu berechnen. Im Jahr 1994 präsentierte Peter Shor Algorithmen, mit denen das Problem der Faktorisierung und des diskreten Logarithmus in polynomieller Laufzeit mittels Quantencomputern gelöst werden können. Daher ist es von äußerster Bedeutung nach Alternativen zu suchen, die langfristig als Ersatz fungieren. Als mögliche Kandidaten kommen Code-, gitter-, multivariate-, und hash-basierte Kryptosysteme in Betracht, die in den letzten Jahren große Erfolge verzeichnen konnten. Die Untersuchung und das Design von Code-basierten Identifikation- und Signaturverfahren stellen den Kerninhalt dieser Arbeit dar.

Im Jahr 1993 wurde von Jacques Stern das erste effiziente Identifikationsverfahren veröffentlicht, welches auf Codierungstheorie basiert. Es hat allerdings zwei Nachteile, welche die Größe des öffentlichen Schlüssels und die hohen Kommunikationskosten betreffen. Zu diesem Zweck schlagen wir ein neues 5-Pass Zero-Knowledge-Identifikationsverfahren vor, das unseres Wissens nach alle Code-basierten Verfahren übertrifft. Mittels unserer Konstruktion werden die Kommunikationskosten um bis zu 25\% und die Größe des öffentlichen Schlüssels von 15 KB auf 4 KB im Vergleich zum Verfahren von Stern reduziert. Als weiteres Ergebnis präsentieren wir eine Verallgemeinerung der Fiat-Shamir Heuristik, welches eines der wichtigsten Paradigmen in der Kryptographie darstellt. Diese wird dazu verwendet, um aus einem kanonischen (3-Pass) Identifikationsprotokoll ein Signaturverfahren zu konstruieren. Ebenfalls entwickeln wir einen Sicherheitsbeweis für diese Transformation für Protokolle, die nicht kanonischen sind. Mit dieser Verallgemeinerung kann man nun unsere Identifikationsverfahren als auch viele andere nicht kanonischen Identifikationsprotokolle zu sicheren Signaturverfahren transformieren. Im letzten Teil schlagen wir ein Threshold Ring Signaturverfahren vor, ein Signaturverfahren mit speziellen Eigenschaften, dem das vorgeschlagene Zero-Knowledge-Identifikations\-verfahren zugrunde liegt. Es stellt sich heraus, dass unsere Konstruktion in Bezug auf die Signaturlänge, die Größe des öffentlichen Schlüssels und die Signaturkosten effizienter ist als alle bekannten Code-basierten Threshold Ring Signaturverfahren.

German
URN: urn:nbn:de:tuda-tuprints-34852
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science
Date Deposited: 09 Jul 2013 15:33
Last Modified: 09 Jul 2020 00:29
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3485
PPN: 386820813
Export:
Actions (login required)
View Item View Item