Zugl.: Bochum, Univ., Diss., 2008

Techn. Universiẗat, Diss., 2004--Darmstadt.

This thesis aims at providing efficient and side-channel protected implementations of isogeny-based primitives, and at their application in threshold protocols. It is based on a sequence of academic papers. Chapter 3 reviews the original variable-time implementation of CSIDH and introduces several optimizations, e.g. a significant improvement of isogeny computations by using both Montgomery and Edwards curves. In total, our improvements yield a speedup of 25% compared to the original implementation. Chapter 4 presents the first practical constant-time implementation of CSIDH. We describe how variable-time implementations of CSIDH leak information on private keys, and describe ways to mitigate this. Further, we present several techniques to speed up the implementation. In total, our constant-time implementation achieves a rather small slowdown by a factor of 3.03. Chapter 5 reviews practical fault injection attacks on CSIDH and presents countermeasures. We evaluate different attack models theoretically and practically, using low-budget equipment. Moreover, we present countermeasures that mitigate the proposed fault injection attacks, only leading to a small performance overhead of 7%. Chapter 6 initiates the study of threshold schemes based on the Hard Homogeneous Spaces (HHS) framework of Couveignes. Using the HHS equivalent of Shamir’s secret sharing in the exponents, we adapt isogeny based schemes to the threshold setting. In particular, we present threshold versions of the CSIDH public key encryption and the CSI-FiSh signature scheme. Chapter 7 gives a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Recent compact isogeny-based protocols, namely B-SIDH and SQISign, both require large primes that lie between two smooth integers. Finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime. / Die vorliegende Dissertation stellt effiziente und Seitenkanal-geschützte Implementierungen Isogenie-basierter Verfahren bereit, und behandelt deren Verwendung in Threshold-Protokollen. Sie basiert auf einer Reihe von Veröffentlichungen. Kapitel 3 untersucht die originale variable-time Implementierung von CSIDH und beschreibt einige Optimierungen, wie etwa die effizientere Berechnung von Isogenien durch die Verwendung von Montgomery- und Edwards-Kurven. Insgesamt erreichen die Optimierungen eine Beschleuningung von 25% gegenüber der Referenzimplementierung. Kapitel 4 enthält die erste effiziente constant-time Implementierung von CSIDH. Es beschreibt inwiefern variable-time Implementierungen Informationen über private Schlüssel liefern, und entsprechende Gegenmaßnahmen. Des Weiteren werden einige Techniken zur Optimierung der Implementierung beschrieben. Insgesamt ist die constant-time Implementierung nur etwa 3x langsamer. Kapitel 5 untersucht praktische Fault-injection Attacken auf CSIDH und beschreibt Gegenmaßnahmen. Es betrachtet verschiedene Angriffsmodelle theoretisch und praktisch unter der Verwendung von low-budget Equipment. Die Gegenmaßnahmen führen zu einer sehr kleinen Performance-Verschlechterung von 7%. Kapitel 6 initiiert die Untersuchung von Threshold-Verfahren basierend auf Hard Homogeneous Spaces (HHS). Unter Verwendung der HHS-Version von Shamir Secret Sharing im Exponenten, werden Threshold-Varianten der CSIDH Verschlüsselung und des CSI-FiSh Signaturschemas definiert. Kapitel 7 enthält einen Sieb-Algorithmus zur Suche nach Paaren von aufeinanderfolgenden glatten Zahlen, unter Verwendung von Lösungen des Prouhet-Tarry-Escott-Problems. Die kürzlich veröffentlichten Isogenie-Verfahren B-SIDH und SQISign benötigen große Primzahlen, die zwischen zwei glatten ganzen Zahlen liegen. Die Suche nach solchen Primzahlen ist ein Spezialfall der Suche nach glatten benachbarten Zahlen, unter der zusätzlichen Bedingung dass deren Summe prim ist.

Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

Techn. University, Diss., 2006--Darmstadt.

Zugl.: Aachen, Techn. Hochsch. und Metz, Univ., Diss., 2006 u.d.T.: Salin, Sophie: Verflechtung nietzscheanischfreudianischer Motive mit dem Werk Gilles Deleuzes und Salin, Sophie: Cryptologie de l'inconscient

Techn. University, Diss., 2002--Darmstadt.

Techn. Universiẗat, Diss., 2002--Darmstadt.

Zugl.: Aachen, Techn. Hochsch. und Metz, Univ., Diss., 2006 u.d.T.: Salin, Sophie: Verflechtung nietzscheanischfreudianischer Motive mit dem Werk Gilles Deleuzes und Salin, Sophie: Cryptologie de l'inconscient

Gegenstand der Arbeit sind Maschinen zum Chiffrieren und dem korrespondierenden Entziffern, besonders im 2. Weltkrieg ("ULTRA"). Es werden die Gründe analysiert, warum die deutschen Chiffriermaschinen "geknackt" wurden und mit welchen maschinellen Methoden das erfolgte. Dazu wird gezeigt, dass ohne systematische deutsche Chiffrierfehler diese Methoden nicht anwendbar gewesen wären. Ferner zeigt eine Analyse der historischen Digitaltechnik, dass diese kryptanalytischen Maschinen Wegbereiter der Digitaltechnik mit Elektronenröhren waren und dass die ersten speicherprogrammierbaren Rechner Fortentwicklungen davon waren. Der Einfluss dieser Entwicklungen auf die Genese der Disziplin Informatik wird diskutiert.