Unausgewogenes Öl-und-Essig-Schema

In der Kryptographie ist das Unbalanced Oil and Vinegar (UOV)-Verfahren eine modifizierte Version des von J. Patarin entwickelten Oil-and-Vesicer-Verfahrens. Beide sind digitale Signaturprotokolle und gehören zur multivariaten Kryptographie . Die Sicherheit dieses Signaturverfahrens basiert auf einem NP-schweren mathematischen Problem. Zur Erstellung und Validierung von Signaturen muss ein minimales quadratisches Gleichungssystem gelöst werden. Die Lösung von m Gleichungen mit n Variablen ist NP-schwer. Während das Problem leicht ist, wenn m entweder viel größer oder viel kleiner als n ist [ ^{1 ]} – was für kryptographische Zwecke von Bedeutung ist –, gilt es im Durchschnitt, wenn m und n nahezu gleich sind, als schwierig, selbst mit einem Quantencomputer . Es wurden mehrere Signaturverfahren auf Basis multivariater Gleichungen entwickelt ^, um Quantenresistenz zu erreichen .

Ein wesentlicher Nachteil von UOV ist die potenziell große Schlüssellänge . Typischerweise wird die Anzahl der Variablen n auf das Doppelte der Anzahl der Gleichungen m gewählt. Die Kodierung der Koeffizienten all dieser Gleichungen im Schlüssel erfordert erheblichen Speicherplatz, mindestens 200 Kilobyte für ein System, das eine mit dem Digital Signature Algorithm (DSA) oder dem Elliptic Curve Digital Signature Algorithm (ECDA) vergleichbare Sicherheit bieten soll .

Ein Signaturverfahren verwendet einen Signaturschlüssel, der geheim gehalten wird, und einen Verifizierungsschlüssel, der öffentlich bekanntgegeben wird. Beispielsweise sind bei RSA- basierten Signaturverfahren beide Schlüssel Exponenten. Beim UOV-Verfahren und allen anderen multivariaten Signaturverfahren sind die Schlüssel komplexer.

Das mathematische Problem besteht darin, Gleichungen mit Variablen zu lösen. Das gesamte Gleichungssystem ist der öffentliche Schlüssel. ${\displaystyle m}$${\displaystyle n}$

Um ein mathematisches Problem für die Kryptographie zu nutzen, muss es modifiziert werden. Die Berechnung der Variablen wäre sehr ressourcenintensiv. Ein Standardcomputer kann dies nicht in akzeptabler Zeit bewerkstelligen. Daher wird eine spezielle „Trapdoor“ in das Gleichungssystem eingefügt. Diese Trapdoor ist der Signaturschlüssel. Er besteht aus drei Teilen: zwei affinen Transformationen und einem Polynomvektor . Beide Transformationen dienen dazu, Elemente in bestimmten Gruppen zu transformieren. Die erste Transformation transformiert zu . Die zweite Transformation transformiert den Variablenvektor in die gültige Signatur. ${\displaystyle n}$${\displaystyle T}$${\displaystyle S}$${\displaystyle {\acute {P}}}$${\displaystyle T}$${\displaystyle y}$${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle S}$

Das dritte geheime Element stellt bestimmte Werkzeuge zur Erstellung der Gleichungen bereit. Die Gleichungen werden mithilfe von Regeln erstellt, die nur dem Besitzer des Signaturschlüssels bekannt sind. ${\displaystyle {\acute {P}}}$

Um eine gültige Signatur zu erstellen, muss das folgende Gleichungssystem gelöst werden.

$${\displaystyle {\begin{aligned}y_{1}&=f_{1}(x_{1},\ldots ,x_{n})\\y_{2}&=f_{2}(x_{1},\ldots ,x_{n})\\&~\vdots \\y_{m}&=f_{m}(x_{1},\ldots ,x_{n})\\\end{aligned}}}$$

Hier ist eine gegebene Nachricht, die signiert werden soll. Die gültige Signatur lautet : ${\displaystyle y=(y_{1},y_{2},\ldots ,y_{m})}$${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$

Um ein gegebenes Signal zu signieren , muss die Nachricht zunächst so transformiert werden, dass sie in das Gleichungssystem passt. wird verwendet, um die Nachricht in akzeptable Teile zu zerlegen . Anschließend müssen die Gleichungen aufgestellt werden. Jede einzelne Gleichung hat die gleiche Form: ${\displaystyle y}$${\displaystyle T}$${\displaystyle y_{1},y_{2},\ldots ,y_{m}}$

$${\displaystyle y_{i}=\sum {\gamma _{ijk}a_{j}{\acute {a}}_{k}}+\sum {\lambda _{ijk}{\acute {a}}_{j}{\acute {a}}_{k}}+\sum {\xi _{ij}a_{j}}+\sum {{\acute {\xi }}_{ij}{\acute {a}}_{j}}+\delta _{i}}$$

Die nächsten Schritte signieren eine gegebene Nachricht , und das Ergebnis ist eine gültige Signatur . ${\displaystyle y}$${\displaystyle x}$

1. Die Koeffizienten , müssen geheim gewählt werden.${\displaystyle \gamma _{ijk},\lambda _{ijk},\xi _{ij},{\acute {\xi }}_{ij},\delta _{i}}$
2. Die Essigvariablen ( ) werden zufällig ausgewählt.${\displaystyle {\acute {a}}_{j}}$
3. Das resultierende lineare Gleichungssystem wird nach den Ölvariablen ( ) aufgelöst.${\displaystyle a_{i}}$

Die Variablen für Essig und Öl bilden die Vorsignatur . Diese wird schließlich durch die private Transformation in die gültige Signatur umgewandelt . ${\displaystyle A=(a_{1},\ldots ,a_{n},{\acute {a}}_{1},\ldots ,{\acute {a}}_{v})}$${\displaystyle A}$${\displaystyle S}$${\displaystyle x=S^{-1}(A)}$

Das Gleichungssystem wird linear , wenn die Essigvariablen fixiert sind – keine Ölvariable wird in der Gleichung mit einer anderen Ölvariable multipliziert. Daher lassen sich die Ölvariablen beispielsweise mithilfe eines Gaußschen Reduktionsalgorithmus leicht berechnen . Die Signaturerzeugung selbst ist schnell und rechentechnisch einfach.

Die Signatur wird an den Kommunikationspartner übermittelt. Die Validierung der Signatur erfolgt mithilfe des öffentlichen Schlüssels, der ein Gleichungssystem darstellt.

$${\displaystyle {\begin{aligned}y_{1}&={f_{1}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\y_{2}&={f_{2}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\&~\vdots \\y_{m}&={f_{m}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\\end{aligned}}}$$

Dieses Gleichungssystem ist eine leicht modifizierte Version des Systems zur Signaturerstellung. Es wurde so modifiziert, dass ein Angreifer keine Informationen über die geheimen Koeffizienten und die spezielle Formatierung der Öl- und Essigvariablen erlangen kann. Jede Gleichung des öffentlichen Schlüssels muss gelöst werden, um die Signatur zu validieren. Die Eingabe ist die Signatur selbst. Stimmen alle Ergebnisse mit dem entsprechenden Teil der Originalnachricht überein, ist die Verifizierung erfolgreich. ${\displaystyle y_{i}}$

Ein wesentlicher Vorteil besteht darin, dass das im Algorithmus zu lösende mathematische Problem als quantenresistent gilt. Sollte jemals ein Quantencomputer entwickelt werden, der große zusammengesetzte Zahlen mithilfe des Shors-Algorithmus faktorisieren kann , würde dies kommerzielle Signaturverfahren wie RSA oder ElGamal außer Kraft setzen , die auf der Unlösbarkeit des diskreten Logarithmusproblems beruhen . UOV bleibt möglicherweise sicher, da kein Algorithmus bekannt ist, der Quantencomputern einen signifikanten Vorteil bei der Lösung mehrdimensionaler Gleichungssysteme verschafft.

Der zweite Vorteil besteht darin, dass die in den Gleichungen verwendeten Operationen relativ einfach sind. Signaturen werden nur durch Addition und Multiplikation von „kleinen“ Werten erstellt und validiert, wodurch diese Signatur auch für ressourcenarme Hardware wie Smartcards geeignet ist .

Ein Nachteil von UOV besteht darin, dass es sehr lange Schlüssellängen verwendet, wobei der öffentliche Schlüssel das gesamte Gleichungssystem umfasst , was mehrere hundert Kilobytes beanspruchen kann . UOV ist bisher nicht weit verbreitet. Obwohl bereits einige Angriffsmethoden bekannt sind, könnten bei einer breiteren Anwendung von UOV weitere auftreten. UOV ist noch nicht für den kommerziellen Einsatz geeignet, da seine Sicherheit weiterer Untersuchungen bedarf. ${\displaystyle m}$

Das Rainbow-Kryptosystem basiert auf UOV und ist einer der drei Finalisten im NIST-Wettbewerb für einen Post-Quanten-Standard für digitale Signaturen. Allerdings wurden kürzlich erhebliche Bedenken hinsichtlich seiner Sicherheit in der im NIST-Wettbewerb vorgeschlagenen Form geäußert. Ein neuer MinRank- Angriff auf Rainbow wurde entdeckt, der die Sicherheit der vorgeschlagenen Rainbow-Implementierung unter die von NIST festgelegten Anforderungen senkt. ^{[ 2 ]} Beullens entdeckte 2022 einen weiteren Angriff, der den privaten Schlüssel für den Rainbow-L1-Parametersatz innerhalb eines Wochenendes wiederherstellt. ^{[ 3 ]} UOV selbst ist von diesem Angriff nicht betroffen.

• Buchmann, Johannes; Coronado, Carlos; Doring, Martin; Engelbert, Daniela; Ludwig, Christoph; Overbeck, Raphael; Schmidt, Arthur; Vollmer, Ulrich; Weinmann, Ralf-Philipp: Post-Quantum Signatures, –, 29. Oktober 2004
• Wolf, Christopher: Multivariate quadratische Polynome in der Public-Key-Kryptographie, DIAMANT/EIDMA-Symposium 2005
• Braeken, An; Wolf, Christopher; Preneel, Bart: Eine Studie zur Sicherheit von unausgewogenen Öl- und Essigsignaturverfahren, ESAT-COSIC, 2. September 2004
• Coron, Jean-Sebastien; de Weger, Benne: Schwierigkeit der wichtigsten Rechenprobleme in der Kryptographie, ECRYPT D.AZTEC.6, 14. März 2007 (archiviert am 5. Juli 2017 im Internet Archive).
• Kipnis, Aviad: Unausgewogene Öl- und Essig-Signaturschemata – erweiterte Fassung, EURO-CRYPT, 1999
• Faugère, Jean-Charles und Perret, Ludovic. Zur Sicherheit von UOV. Cryptology eprint archive. Bericht 2009/483. 2009