Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Soft-Decision Decodierung langer Blockcodes mit Informationsmengen

Dulte José de Barros

Published Jul 26, 2000• 2 citations
OpenAlex

Abstract

In der vorliegenden Arbeit wird ein effizienter Soft-Decision Algorithmus vorgeschlagen, der fur die Decodierung langer linearen Blockcodes angewendet werden kann. Im Gegensatz zu Faltungscodes kann normalerweise die zusatzliche Zuverlassigkeitsinformation in die Decodierung von Blockcodes nicht auf einfache und effiziente Weise integrierte werden. Diese Arbeit ist ein Versuch, diese Lucke zu schliesen. Eine Moglichkeit der Hard-Decision Decodierung besteht in der Verwendung von sogenannten Informationsmengen. Eine Informationsmenge gestattet es, durch Kenntnis einiger Komponenten eines Codewortes die unbekannten Stellen exakt zu berechnen. In dieser Arbeit wird ein Decodieralgorithmus vorgestellt, der auf Informationsmengen basiert. Die Zuverlassigkeitsinformationen werden derart zur Auswahl der Informationsmengen verwendet, das fur sehr lange Blockcodes eine minimale Anzahl von Operationen notwendig ist. Zur weiteren Begrenzung der durchschnittlichen Komplexitat werden einige Kriterien hergeleitet, die einen Abbruch der Iteration gestatten, wenn der Algorithmus bereits eine Maximum-Likelihood Schatzung erreicht hat. Weiterhin werden ausfuhrliche Simulationen mit dem beschriebenen Algorithmus durchgefuhrt. Um auch sehr lange Blockcodes zu simulieren, wird zunachst eine Simulationsmethode vorgeschlagen, die die wahrscheinlichsten Fehlerereignisse stark berucksichtigt. Dadurch wird es moglich, sehr lange Codes auch fur grose Signal zu Rauschverhaltnis zu simulieren. Es wird eingehend untersucht, wie sich verschiedene Abbruchkriterien auf die Komplexitat des Decodieralgorithmus auswirken. Ferner wird dieser Algorithmus fur die BCH-Codes (128,64) und (255,123) angewendet. Es zeigt sich, das selbst mit wenigen Iterationen eine deutliche Steigerung gegenuber einer BMD-Decodierung erreicht werden kann. Durch Erhohung der Anzahl der Iterationen gestattet es der vorschlagene Algorithmus beliebig dicht an die Leistungsfahigkeit eines Maximum-Likelihood-Decodierers heranzukommen.

Related papers

Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Schmidt, Arthur

In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].

•Jan 1, 2008•1 citation

Cryptographic Protocols from Physical Assumptions

Alexander Koch

Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.

•Jan 1, 2019•16 citations

Rekursive Codes mit der Plotkin-Konstruktion und ihre Decodierung

N. Stolte

In dieser Arbeit werden Codes betrachtet, die allein durch rekursive Anwendung der |u|u+v|-Konstruktion, auch als PLOTKIN-Konstruktion bezeichnet, generiert werden. Der Schwerpunkt liegt hier sowohl auf der Konstruktion als auch auf der Decodierung von Codes dieser Klasse, die die Klasse der REED-MULLER (RM) Codes enthält. Bezüglich der auftretenden Störungen werden nur die beiden Sonderfälle des binären symmetrischen Kanals (BSC) und des additiven weißen gaußschen Rauschkanals (AWGN) betrachtet. Alle hier vorgestellten Codes sind Untercodes von RM-Codes und lassen sich als verallgemeinert verkettete Codes beschreiben. Für die zur Decodierung notwendige Zuverlässigkeitsübergabe an die Decoder der äußeren Codes wird neben der optimalen auch eine suboptimale Methode beschrieben und bewertet. Aufbauend auf diesen Methoden wird sowohl ein neues sequentielles als auch ein listengestütztes Decodierverfahren vorgeschlagen, die für alle Codes dieser Klasse geeignet sind. Es können damit beim AWGN-Kanal mit geringem Aufwand alle RM-Codes bis zu einer Länge von N = 128 Codesymbolen annähernd optimal decodiert werden. Speziell für RM-Codes wird darüber hinaus auch eine kombinierte Listen- und Permutationsdecodierung vorgeschlagen, womit beim AWGN-Kanal auch für alle Codes der Länge N = 256 und beim BSC bis zur Länge N = 512 nahezu optimale Wortfehlerwahrscheinlichkeiten erzielt werden. Um auch bei größeren Codelängen ebenfalls gute Decodierergebnisse zu erzielen, werden zwei verschiedene Methoden zur Anpassung des Codes an die verwendeten Decoder vorgestellt. Beide Methoden ermöglichen für Codelängen N = 2m die Konstruktion von Codes beliebiger Raten K/N, K ∈ {1, 2, ... , N}. Unter anderem die Berücksichtigung der bei Multilevel-Codes bekannten Ergebnisse führt so zu Codes, die zusammen mit dem hier vorgestellten Listendecodierverfahren auch bei deutlich über der Cutoff-Rate liegenden Coderaten kleine Fehlerwahrscheinlichkeiten ermöglichen.

•Jan 1, 2008•59 citations

Stochastische Analysen und Algorithmen zur Soft-Decodierung binärer linearer Blockcodes

Thomas F. Sturm

•Jan 1, 2003•0 citations

Decodierung und Fehlerkorrektur

Frank J. Furrer

Die Codierung eines Block-Codes kann verstanden werden als die Zuordnung der Elemente einer Menge (nämlich der 2k möglichen Kombinationen von k Informationsbit) zu ausgewählten Elementen einer grösseren Menge (nämlich der 2n möglichen Kombinationen von n Bit). Die ausgewählten n-stelligen Kombinationen werden die Codewörter des Codes genannt. Die Zuordnung der Codewörter zur Information lässt sich durch eine Tabelle (z.Bsp. Tabelle 2.1) oder durch ein Rechenverfahren (Abschnitte 4.6–4.10) definieren und wird Codiervorschrift genannt (Bild 2.5). Dadurch, dass wesentlich mehr Kombinationen von n Bit zur Auswahl zur Verfügung stehen als Informationsblöcke übertragen werden sollen, kann dem Satz von ausgewählten Codewörtern eine Fehlererkennungs- oder Fehlerkorrekturfahigkeit gegeben werden.

Birkhäuser Basel eBooks•Jan 1, 1981•0 citations

Femtosecond quantum control studies on vibrational quantum information processing

C. Gollub

Diese Dissertation befasst sich mit der Quantenkontrolle von Schwingungsprozessen im Hinblick auf molekulares Quantencomputing.Der Ansatz des Quantencomputing Konzepts basiert auf Schwingungsfreiheitsgraden von polyatomaren Molekülen.Die logischen Werte der Qubits 0 oder 1 werden jeweils durch einen bestimmten Anregungsgrad einer Normalmode kodiert und die logischen Quantenoperationen werden durch speziell geformte, ultrakurze Laserpulse implementiert.Diese Laserfelder lassen sich mit Hilfe der sogenannten Optimalen Kontrolltheorie ermitteln.Das Konzept des molekularen Quantencomputings, das ursprünglich auf Quantengattern basierte, die einen IR Anregungsprozess im Molekül bewirken, wird im ersten Teil der Dissertation auf Raman aktive Normalmoden übertragen.Daraus ergibt sich der Vorteil, dass nun auch andere Frequenzbereiche, z.B. der Bereich um 800 nm, für die Realisierung der Quantenoperationen im Experiment zur Verfügung steht.Im nahen IR und UV/VIS Bereich existieren schon seit längerer Zeit ausgereifte Techniken des Pulsformens.Mittels verschiedener ab-initio Untersuchungen konnte das Molekül Butylamin und speziell dessen Raman aktive C-H Streckschwingungen, als ein geeignetes Qubit System zur ersten theoretischen Demonstration dieser Idee, ermittelt werden.Ein universeller Satz von Quantengatter, bestehend aus kurzen und einfach strukturierten Laserpulsen konnte mit sehr hohen Effizienzen optimiert werden.Zur Berechnung der nichtresonanten Laserfelder, die den Schwingungsprozess induzieren, der den logischen Operationen zu Grunde liegt, musste das bisher in der Optimalen Kontrolltheorie verwendete Kontrollfunktional modifiziert werden.Die Erweiterung um Frequenzfilteroperationen erlaubt nun zum ersten Mal die Kontrolle von nichtresonanten Zwei-Farben-Prozessen und die gleichzeitige Berechnung der beiden an dem Prozess beteiligten Laserfelder.Dieses neu entwickelte, kontrolltheoretische Verfahren stellt eine universelle Methode dar und lässt sich leicht auf verschiedene Prozesse v übertragen in denen entspechende Filteroperationen hilfreich oder sogar essentiell sind.Nachdem gegenwärtig die ersten erfolgreichen Demonstrationen von geformten, ultrakurzen Laserpulsen auch im mittleren IR Bereich vorgestellt werden, ist es interessant die Übereinstimmung der jeweilig gefundenen Ergebnisse von theoretischen und experimentellen Kontrollstudien zu vergleichen.Die experimentelle Herangehensweise basiert auf Optimierungen mit Rückkopplungsschleifen, deren zentrale Elemente ein evolutionärer Algorithmus, ein Pulsformer und ein Rückkopplungssignal, das auf die Effizienz des Prozesses schließen lässt, sind.Die experimentellen Ergebnisse für die optimalen Laserpulse können sehr komplex und auch ungünstigerweise sehr lang ausfallen.In der vorliegenden Arbeit wurden verschiedene Strategien entwickelt um dies zu umgehen.Untersucht wurden in diesem Zusammenhang zwei verschiedene Ansätze der Phasenmodulation, eine Einschränkung der Variationsbreite der Phase, sowie die spektrale Breite der Eingangspulse.Als Ergebnis konnte gezeigt werden, dass eine parametrisierte, sinusförmige Phasenmodulation, die oft im Experiment Verwendung findet um die Komplexität der Felder zu reduzieren, zu unflexibel ist für eine effiziente Implementierung von Quantengattern.Dagegen bieten sich gepixelte Maskenfunktionen in Kombination mit einer geeigneten Wahl der Eingangspuls-und Optimierungsparameter an.Alternativ zu dem bisher verwendeten evolutionären Algorithmus wurden neue Optimierungsmethoden vorgeschlagen, die auf einem "multi-objective" genetischen Algorithmus und einem natürlichen Algorithmus, dem sogenannten Ameisenalgorithmus, beruhen.Diese Methoden führen leicht zu den gewünschten Ergebnissen, ohne Verlust der hohen Quanteneffizienz und lassen sich direkt auf die experimentelle Herangehensweise übertragen.Diese Studien erlauben eine Optimierung direkt im Suchraum des Experiments und lassen von daher verlässliche Vorhersagen zu, bei denen alle experimentellen Rahmenbedingungen konsequent eingehalten werden können.Aussagen zur experimentell maximal erreichbaren Effizienz mit den zur Verfügung stehenden Eingangspulsen können getroffen werden, aber auch eine Benennung der geeignetsten Startbedingungen wird möglich.Zusätzlich wurden Quantenkontrollstudien von Schwingungsprozessen in offenen Systemen durchgeführt, d.h.dissipative Effekte wurden direkt in die theoretischen Untersuchungen miteinbezogen.Aus den Resultaten lässt sich ableiten, dass möglichst kurze Pulsdauern essentiell für hohe Quantenausbeuten vi sind und genau dies lässt sich mit den in der Dissertation entwickelten und vorgestellten Kontrollverfahren erreichen.Einen Schritt über einzelne Qubit Systeme hinaus, wurde durch die Konstruktion eines ersten, kleinen Quantennetzwerkes gemacht.Hierbei wurden zwei molekulare Qubit Einheiten durch eine lineare Molekülkette miteinander verknüpft.Diese Idee stellt ein erstes Konzept in Richtung der Skalierbarkeit des Quantencomputing Ansatzes dar.Ein Modellsystem wurde aufgesetzt und ein Laser-getriebener Schwingungsenergietransfer über das Kettenmolekül von der einen Qubit Seite auf die andere Seite optimiert.Dies lässt sich als eine Kommunikation zwischen benachbarten Qubit Einheiten verstehen und könnte so zur Konstruktion von Quantenregistern oder einer entsprechenden Wechselwirkung mit molekularen Speichereinheiten führen.

•Jan 1, 2009•2 citations
In der vorliegenden Arbeit wird ein effizienter Soft-Decision Algorithmus vorgeschlagen, der fur die Decodierung langer linearen Blockcodes angewendet werden kann. Im Gegensatz zu Faltungscodes kann normalerweise die zusatzliche Zuverlassigkeitsinformation in die Decodierung von Blockcodes nicht auf einfache und effiziente Weise integrierte werden. Diese Arbeit ist ein Versuch, diese Lucke zu schliesen. Eine Moglichkeit der Hard-Decision Decodierung besteht in der Verwendung von sogenannten Informationsmengen. Eine Informationsmenge gestattet es, durch Kenntnis einiger Komponenten eines Codewortes die unbekannten Stellen exakt zu berechnen. In dieser Arbeit wird ein Decodieralgorithmus vorgestellt, der auf Informationsmengen basiert. Die Zuverlassigkeitsinformationen werden derart zur Auswahl der Informationsmengen verwendet, das fur sehr lange Blockcodes eine minimale Anzahl von Operationen notwendig ist. Zur weiteren Begrenzung der durchschnittlichen Komplexitat werden einige Kriterien hergeleitet, die einen Abbruch der Iteration gestatten, wenn der Algorithmus bereits eine Maximum-Likelihood Schatzung erreicht hat. Weiterhin werden ausfuhrliche Simulationen mit dem beschriebenen Algorithmus durchgefuhrt. Um auch sehr lange Blockcodes zu simulieren, wird zunachst eine Simulationsmethode vorgeschlagen, die die wahrscheinlichsten Fehlerereignisse stark berucksichtigt. Dadurch wird es moglich, sehr lange Codes auch fur grose Signal zu Rauschverhaltnis zu simulieren. Es wird eingehend untersucht, wie sich verschiedene Abbruchkriterien auf die Komplexitat des Decodieralgorithmus auswirken. Ferner wird dieser Algorithmus fur die BCH-Codes (128,64) und (255,123) angewendet. Es zeigt sich, das selbst mit wenigen Iterationen eine deutliche Steigerung gegenuber einer BMD-Decodierung erreicht werden kann. Durch Erhohung der Anzahl der Iterationen gestattet es der vorschlagene Algorithmus beliebig dicht an die Leistungsfahigkeit eines Maximum-Likelihood-Decodierers heranzukommen.
In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].
Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.
In dieser Arbeit werden Codes betrachtet, die allein durch rekursive Anwendung der |u|u+v|-Konstruktion, auch als PLOTKIN-Konstruktion bezeichnet, generiert werden. Der Schwerpunkt liegt hier sowohl auf der Konstruktion als auch auf der Decodierung von Codes dieser Klasse, die die Klasse der REED-MULLER (RM) Codes enthält. Bezüglich der auftretenden Störungen werden nur die beiden Sonderfälle des binären symmetrischen Kanals (BSC) und des additiven weißen gaußschen Rauschkanals (AWGN) betrachtet. Alle hier vorgestellten Codes sind Untercodes von RM-Codes und lassen sich als verallgemeinert verkettete Codes beschreiben. Für die zur Decodierung notwendige Zuverlässigkeitsübergabe an die Decoder der äußeren Codes wird neben der optimalen auch eine suboptimale Methode beschrieben und bewertet. Aufbauend auf diesen Methoden wird sowohl ein neues sequentielles als auch ein listengestütztes Decodierverfahren vorgeschlagen, die für alle Codes dieser Klasse geeignet sind. Es können damit beim AWGN-Kanal mit geringem Aufwand alle RM-Codes bis zu einer Länge von N = 128 Codesymbolen annähernd optimal decodiert werden. Speziell für RM-Codes wird darüber hinaus auch eine kombinierte Listen- und Permutationsdecodierung vorgeschlagen, womit beim AWGN-Kanal auch für alle Codes der Länge N = 256 und beim BSC bis zur Länge N = 512 nahezu optimale Wortfehlerwahrscheinlichkeiten erzielt werden. Um auch bei größeren Codelängen ebenfalls gute Decodierergebnisse zu erzielen, werden zwei verschiedene Methoden zur Anpassung des Codes an die verwendeten Decoder vorgestellt. Beide Methoden ermöglichen für Codelängen N = 2m die Konstruktion von Codes beliebiger Raten K/N, K ∈ {1, 2, ... , N}. Unter anderem die Berücksichtigung der bei Multilevel-Codes bekannten Ergebnisse führt so zu Codes, die zusammen mit dem hier vorgestellten Listendecodierverfahren auch bei deutlich über der Cutoff-Rate liegenden Coderaten kleine Fehlerwahrscheinlichkeiten ermöglichen.
Die Codierung eines Block-Codes kann verstanden werden als die Zuordnung der Elemente einer Menge (nämlich der 2k möglichen Kombinationen von k Informationsbit) zu ausgewählten Elementen einer grösseren Menge (nämlich der 2n möglichen Kombinationen von n Bit). Die ausgewählten n-stelligen Kombinationen werden die Codewörter des Codes genannt. Die Zuordnung der Codewörter zur Information lässt sich durch eine Tabelle (z.Bsp. Tabelle 2.1) oder durch ein Rechenverfahren (Abschnitte 4.6–4.10) definieren und wird Codiervorschrift genannt (Bild 2.5). Dadurch, dass wesentlich mehr Kombinationen von n Bit zur Auswahl zur Verfügung stehen als Informationsblöcke übertragen werden sollen, kann dem Satz von ausgewählten Codewörtern eine Fehlererkennungs- oder Fehlerkorrekturfahigkeit gegeben werden.
Diese Dissertation befasst sich mit der Quantenkontrolle von Schwingungsprozessen im Hinblick auf molekulares Quantencomputing.Der Ansatz des Quantencomputing Konzepts basiert auf Schwingungsfreiheitsgraden von polyatomaren Molekülen.Die logischen Werte der Qubits 0 oder 1 werden jeweils durch einen bestimmten Anregungsgrad einer Normalmode kodiert und die logischen Quantenoperationen werden durch speziell geformte, ultrakurze Laserpulse implementiert.Diese Laserfelder lassen sich mit Hilfe der sogenannten Optimalen Kontrolltheorie ermitteln.Das Konzept des molekularen Quantencomputings, das ursprünglich auf Quantengattern basierte, die einen IR Anregungsprozess im Molekül bewirken, wird im ersten Teil der Dissertation auf Raman aktive Normalmoden übertragen.Daraus ergibt sich der Vorteil, dass nun auch andere Frequenzbereiche, z.B. der Bereich um 800 nm, für die Realisierung der Quantenoperationen im Experiment zur Verfügung steht.Im nahen IR und UV/VIS Bereich existieren schon seit längerer Zeit ausgereifte Techniken des Pulsformens.Mittels verschiedener ab-initio Untersuchungen konnte das Molekül Butylamin und speziell dessen Raman aktive C-H Streckschwingungen, als ein geeignetes Qubit System zur ersten theoretischen Demonstration dieser Idee, ermittelt werden.Ein universeller Satz von Quantengatter, bestehend aus kurzen und einfach strukturierten Laserpulsen konnte mit sehr hohen Effizienzen optimiert werden.Zur Berechnung der nichtresonanten Laserfelder, die den Schwingungsprozess induzieren, der den logischen Operationen zu Grunde liegt, musste das bisher in der Optimalen Kontrolltheorie verwendete Kontrollfunktional modifiziert werden.Die Erweiterung um Frequenzfilteroperationen erlaubt nun zum ersten Mal die Kontrolle von nichtresonanten Zwei-Farben-Prozessen und die gleichzeitige Berechnung der beiden an dem Prozess beteiligten Laserfelder.Dieses neu entwickelte, kontrolltheoretische Verfahren stellt eine universelle Methode dar und lässt sich leicht auf verschiedene Prozesse v übertragen in denen entspechende Filteroperationen hilfreich oder sogar essentiell sind.Nachdem gegenwärtig die ersten erfolgreichen Demonstrationen von geformten, ultrakurzen Laserpulsen auch im mittleren IR Bereich vorgestellt werden, ist es interessant die Übereinstimmung der jeweilig gefundenen Ergebnisse von theoretischen und experimentellen Kontrollstudien zu vergleichen.Die experimentelle Herangehensweise basiert auf Optimierungen mit Rückkopplungsschleifen, deren zentrale Elemente ein evolutionärer Algorithmus, ein Pulsformer und ein Rückkopplungssignal, das auf die Effizienz des Prozesses schließen lässt, sind.Die experimentellen Ergebnisse für die optimalen Laserpulse können sehr komplex und auch ungünstigerweise sehr lang ausfallen.In der vorliegenden Arbeit wurden verschiedene Strategien entwickelt um dies zu umgehen.Untersucht wurden in diesem Zusammenhang zwei verschiedene Ansätze der Phasenmodulation, eine Einschränkung der Variationsbreite der Phase, sowie die spektrale Breite der Eingangspulse.Als Ergebnis konnte gezeigt werden, dass eine parametrisierte, sinusförmige Phasenmodulation, die oft im Experiment Verwendung findet um die Komplexität der Felder zu reduzieren, zu unflexibel ist für eine effiziente Implementierung von Quantengattern.Dagegen bieten sich gepixelte Maskenfunktionen in Kombination mit einer geeigneten Wahl der Eingangspuls-und Optimierungsparameter an.Alternativ zu dem bisher verwendeten evolutionären Algorithmus wurden neue Optimierungsmethoden vorgeschlagen, die auf einem "multi-objective" genetischen Algorithmus und einem natürlichen Algorithmus, dem sogenannten Ameisenalgorithmus, beruhen.Diese Methoden führen leicht zu den gewünschten Ergebnissen, ohne Verlust der hohen Quanteneffizienz und lassen sich direkt auf die experimentelle Herangehensweise übertragen.Diese Studien erlauben eine Optimierung direkt im Suchraum des Experiments und lassen von daher verlässliche Vorhersagen zu, bei denen alle experimentellen Rahmenbedingungen konsequent eingehalten werden können.Aussagen zur experimentell maximal erreichbaren Effizienz mit den zur Verfügung stehenden Eingangspulsen können getroffen werden, aber auch eine Benennung der geeignetsten Startbedingungen wird möglich.Zusätzlich wurden Quantenkontrollstudien von Schwingungsprozessen in offenen Systemen durchgeführt, d.h.dissipative Effekte wurden direkt in die theoretischen Untersuchungen miteinbezogen.Aus den Resultaten lässt sich ableiten, dass möglichst kurze Pulsdauern essentiell für hohe Quantenausbeuten vi sind und genau dies lässt sich mit den in der Dissertation entwickelten und vorgestellten Kontrollverfahren erreichen.Einen Schritt über einzelne Qubit Systeme hinaus, wurde durch die Konstruktion eines ersten, kleinen Quantennetzwerkes gemacht.Hierbei wurden zwei molekulare Qubit Einheiten durch eine lineare Molekülkette miteinander verknüpft.Diese Idee stellt ein erstes Konzept in Richtung der Skalierbarkeit des Quantencomputing Ansatzes dar.Ein Modellsystem wurde aufgesetzt und ein Laser-getriebener Schwingungsenergietransfer über das Kettenmolekül von der einen Qubit Seite auf die andere Seite optimiert.Dies lässt sich als eine Kommunikation zwischen benachbarten Qubit Einheiten verstehen und könnte so zur Konstruktion von Quantenregistern oder einer entsprechenden Wechselwirkung mit molekularen Speichereinheiten führen.