# Changeset 7282

Ignore:
Timestamp:
Feb 5, 2018, 7:35:48 PM (4 years ago)
Message:

LatticeCrypto documentation:

• replaced special characters with their HTML symbol entities
• </br> tag replaced with <br>
Location:
trunk/CrypPlugins/LatticeCrypto/OnlineHelp
Files:
2 edited

Unmodified
Removed
• ## trunk/CrypPlugins/LatticeCrypto/OnlineHelp/Start.en.htm

 r6122

Lattices
Lattices
A lattice consists of linearly independent vectors that are linearly combined with each other and thereby generate lattice points. The difference between lattices and a "normal" vector space is the fact that the vectors are multiplied with integer factors instead of real factors.
vectors are multiplied with integer factors instead of real factors.
All the vectors form a so called basis for the lattice. This basis can be written in the form of a matrix. The vectors can be written down in column notation, this is the most common way in papers. The vectors define so-called parallelepipeds, in the two-dimensional case these are parallelograms. The volume of this parallelepiped is equal to the absolute value of the determinant.

The volume of this parallelepiped is equal to the absolute value of the determinant.

Please note that in this crypto tutorial all values are integers,

Lattice problems
Lattice problems
An important characteristic of lattices is the fact that they have the same value. Regarding lattices, vectors with minimum length are interesting. The problem to find these vectors is called the Shortest Vector Problem (SVP) and relates to the search for "successive minima".
Problem (SVP) and relates to the search for "successive minima".
The first minimum is the shortest vector. All other vectors are linearly independent to this and to each other, they are Lattice point being as large as possible without overlapping each other (both the Hermite circuit and the package circuits can be enabled in the settings). It can be easily observed that after reduction the vectors are very much orthogonal to each other, ideally they even have the angle of 90 °.
It can be easily observed that after reduction the vectors are very much orthogonal to each other, ideally they even have the angle of 90°.
Another interesting problem is the Closest Vector Problem (CVP).

Lattice reduction
Lattice reduction
There are two important methods that implement the search for shortest vectors. One of these is the Gaussian algorithm for dimension 2 and secondly the LLL algorithm, named after Arjen Lenstra, Hendrik Lenstra and László Lovász, for an arbitrary lattice dimension. Arjen Lenstra, Hendrik Lenstra and László Lovász, for an arbitrary lattice dimension. The Gaussian algorithm works similar to the Euclidean algorithm for searching the greatest common divisor (gcd) of two integers. By combining and subtracting of two vectors the basis improves after each iteration with a shorter vector.

Cryptanalysis
Cryptanalysis
After the publication of the LLL algorithm in 1982, many possible applications were found for it, cryptanalysis being one of them. The Merkle-Hellman knapsack cryptosystem, designed in 1978 and named after its two inventors Ralph C. Merkle and Martin E. Hellman, could impressively be broken with the help of lattices. This cryptosystem is based on the knapsack problem, for which a general solution is difficult to find. But it could be demonstrated, that the problem of decrypting a ciphertext can be reformulated as a search for a shortest vector.
But it could be demonstrated, that the problem of decrypting a ciphertext can be reformulated as a search for a shortest vector.
The well-known asymmetric encryption scheme RSA (named after its inventors Ronald L. Rivest, Adi Shamir and Leonard Adleman) was developed at about the same time as the Merkle-Hellman cryptosystem. The messages in this case are so called "stereotypical messages", for example "Your new PIN is: ****". The first part of the messages, which is always the same, must be known to the attacker. A prerequisite for this attack is that the public exponent e is very small, for example 3.
A prerequisite for this attack is that the public exponent e is very small, for example 3.
Another attack scenario that uses lattices involves a partially known private key.

Lattice-based cryptosystems
Lattice-based cryptosystems
Cryptosystems that are based on lattices exploit the hardness of certain lattice problems, in particular the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). As in the case of RSA, these cryptosystems are asymmetric public-key cryptosystems.
As in the case of RSA, these cryptosystems are asymmetric public-key cryptosystems.
The foundations for lattice-based cryptography were laid by Miklos Ajtai in 1986, when he demonstrated how lattices could be used for cryptography. The security of GGH is based on the hardness of CVP. GGH can also be used to generate electronic signatures. Both cryptosystems, Ajtai-Dwork and GGH, were successfully attacked and broken.
Both cryptosystems, Ajtai-Dwork and GGH, were successfully attacked and broken.
The cryptosystem NTRU (Number Theory Research Unit) was presented by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman in 1998. It can encrypt (NTRUEncrypt) as well as create electronic signatures (NTRUSign). The security of NTRU relies on the hardness of SVP. The advantages of NTRU are the fast encryption and decryption speed and the fact that, unlike in the case of RSA, no quantum algorithm for attacking it in polynomial time is as yet known.
The advantages of NTRU are the fast encryption and decryption speed and the fact that, unlike in the case of RSA, no quantum algorithm for attacking it in polynomial time is as yet known.
The latest lattice-based cryptosystem is Learning With Errors (LWE), which was published by Oded Regev in 2005. It too is based on hard lattice problems, like SVP.
It too is based on hard lattice problems, like SVP.
Compared to established public-key cryptosystems like RSA, lattice-based cryptosystems have to handle larger key sizes and also larger ciphertexts.

• ## trunk/CrypPlugins/LatticeCrypto/OnlineHelp/Start.htm

 r6045

Gitter
Ein Gitter besteht aus linear unabhängigen Vektoren, die miteinander linear kombiniert werden, Gitter
Ein Gitter besteht aus linear unabhängigen Vektoren, die miteinander linear kombiniert werden, und dadurch Gitterpunkte erzeugen. Der Unterschied zwischen Gittern und einem "normalen" Vektorraum besteht darin, dass die Vektoren ganzzahlig kombiniert werden.
darin, dass die Vektoren ganzzahlig kombiniert werden.
Nimmt man alle Vektoren zusammen, bezeichnet man diese als Basis für das Gitter. Diese Basis kann auch in Form einer Matrix aufgeschrieben werden. Die Vektoren können z.B. in Spaltenschreibweise aufgeschrieben werden. Die Vektoren spannen so genannte Parallelepipede auf, im zwei-dimensionalen Fall sind dies Parallelogramme. Das Volumen dieses Parallelepipeds ist gleich dem Absolutbetrag der Determinante.

Beachten Sie bitte, dass in diesem Kryptotutorial alle Werte ganzzahlig sind. Dies ist keine Voraussetzung für Gitter. Da aber in der Kryptographie häufig mit großen Ganzzahlen gerechnet wird, werden auch hier

Gitterprobleme
Eine wichtige Eigenschaft von Gittern ist, dass sie Gitterprobleme
Eine wichtige Eigenschaft von Gittern ist, dass sie verschiedene Basen haben können, die alle das gleiche  Gitter erzeugen. Diese Basen haben dann auch alle die gleiche Gitterdeterminante. Im Zusammenhang mit Gittern sind aber vor allem solche Vektoren interessant, die eine minimale Länge besitzen. Dieses Problem wird Shortest Vector Problem (SVP) genannt. Gesucht werden dabei die so genannten "Sukzessiven Minima".
Gesucht werden dabei die so genannten "Sukzessiven Minima".
Das erste Minimum ist dabei der kürzeste Vektor. Alle weiteren sind dazu linear unabhängig und wiederum so kurz wie möglich. Eine obere Schranke für den kürzesten Vektor wird durch die Hermite-Konstante. Der (sowohl der Hermite-Kreis als auch die Packungskreise können in den Einstellungen freigeschaltet werden). Es lässt sich gut beobachten, dass die Vektoren nach einer Reduktion sehr viel orthogonaler zueinander sind, im Idealfall haben sie sogar den Winkel 90°.
im Idealfall haben sie sogar den Winkel 90°.
Ein weiteres interessantes Problem ist das Closest Vector Problem (CVP). Hier wird ein beliebiger Punkt vorgegeben und es soll ein Gitterpunkt gesucht werden, der diesem Punkt am nächsten ist.

Gitterreduktion
Es gibt zwei wichtige Verfahren, welche die Suche nach Gitterreduktion
Es gibt zwei wichtige Verfahren, welche die Suche nach kürzesten Vektoren realisieren. Zum einen ist dies der Gauß-Algorithmus für die Dimension 2 und zum anderen der LLL-Algorithmus, benannt nach Arjen Lenstra, Hendrik Lenstra und László Lovász, für eine beliebige Gitterdimension.
zum anderen der LLL-Algorithmus, benannt nach Arjen Lenstra, Hendrik Lenstra und László Lovász, für eine beliebige Gitterdimension.
Der Gauß-Algorithmus arbeitet ähnlich dem euklidischen Algorithmus zur Suche des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen. Durch Kombination und Subtraktion der beiden Vektoren aber nur noch eine Approximation (Annäherung) an den kürzesten Vektor. Ein wichtiger Bestandteil des Algorithmus ist die Gram-Schmidt-Orthogonalisierung.
Algorithmus ist die Gram-Schmidt-Orthogonalisierung.

Kryptoanalyse
Nachdem der LLL-Algorithmus 1982 veröffentlicht wurde, Kryptoanalyse
Nachdem der LLL-Algorithmus 1982 veröffentlicht wurde, fanden sich zahlreiche Einsatzmöglichkeiten, unter anderem in der Kryptoanalyse. So wurde das von Ralph C. Merkle und Martin E. Hellman 1978 entwickelte und nach ihnen benannte Kryptosystem dem Rucksackproblem, welches im Allgemeinen sehr schwer zu lösen ist. Im Konkreten zeigte sich jedoch, dass das Entschlüsseln einer Chiffre in Kombination mit dem öffentlichen Schlüssel als Suche nach einem kürzesten Vektor umformuliert werden konnte.
umformuliert werden konnte.
Das bekannteste, asymmetrische Verschlüsselungsverfahren RSA, benannt nach Ronald L. Rivest, Adi Shamir und Leonard Adleman, wurde etwa zur gleichen Zeit wie das von Merkle und Hellman entwickelt. Es basiert auf dem Problem der Primfaktorzerlegung von großen Zahlen. der Nachricht bekannt ist, entschlüsselt werden können. Diese Nachrichten sind so genannte "stereotype Nachrichten", wie z.B. "Ihre neue PIN lautet: ****". Der erste Teil der Nachricht kann immer gleich sein und daher dem Angreifer bekannt. Voraussetzung für den Angriff ist, dass der öffentliche Exponent e sehr klein ist, z.B. 3.
Voraussetzung für den Angriff ist, dass der öffentliche Exponent e sehr klein ist, z.B. 3.
Eine weitere Angriffsmöglichkeit ist ein teilweise bekannter privater Schlüssel. Auch hier kann mithilfe von Gittern ein Angriff gestartet werden. Im Gegensatz zum Merkle-Hellman-Kryptosystem konnte das RSA-Verfahren nicht gebrochen werden und gilt daher (mit einigen

Gitterbasierte Kryptosysteme
Kryptosysteme, die auf Basis von Gittern arbeiten, machen sich die Gitterprobleme, im Besonderen, Shortest Vector Problem (SVP) und Closest Vector Problem (CVP), zunutze. Es handelt sich hierbei, wie bei RSA, um asymmetrische Public-Key-Kryptosysteme.
Gitterbasierte Kryptosysteme
Kryptosysteme, die auf Basis von Gittern arbeiten, machen sich die Gitterprobleme, im Besonderen, Shortest Vector Problem (SVP) und Closest Vector Problem (CVP), zunutze. Es handelt sich hierbei, wie bei RSA, um asymmetrische Public-Key-Kryptosysteme.
Die Grundlagen für die gitterbasierte Kryptographie wurden 1996 von Miklos Ajtai geschaffen, indem er aufzeigte, wie Gitter für die Kryptographie genutzt werden Schwierigkeit das CVP zu lösen. Es war außerdem möglich, Nachrichten mithilfe des GGH-Signaturverfahren zu signieren. Beide Kryptosysteme, sowohl Ajtai-Dwork als auch GGH, wurden erfolgreich angegriffen und gebrochen.
Das Kryptosystem NTRU (als Abkürzung von "Number Theory Research Unit") wurde 1998 von Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman vorgestellt. Es sind sowohl Verschlüsselungen (NTRUEncrypt) als auch elektronische Signaturen (NTRUSign) möglich. Die Sicherheit von NTRU liegt im Lösen des SVP. Als Besonderheit gilt zum einen die schnelle Ver- und Entschlüsselung und zum anderen der Umstand, dass (im Gegensatz zu RSA) bisher noch kein Quantenalgorithmus bekannt ist, der NTRU in Polynomialzeit bricht.
Das neueste, gitterbasierte Kryptosystem ist Learning with Errors (kurz LWE), welches von Oded Regev in 2005 veröffentlicht wurde. Es basiert ebenfalls auf schwer zu lösenden Gitterproblemen, wie dem SVP.
als auch GGH, wurden erfolgreich angegriffen und gebrochen.
Das Kryptosystem NTRU (als Abkürzung von "Number Theory Research Unit") wurde 1998 von Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman vorgestellt. Es sind sowohl Verschlüsselungen (NTRUEncrypt) als auch elektronische Signaturen (NTRUSign) möglich. Die Sicherheit von NTRU liegt im Lösen des SVP. Als Besonderheit gilt zum einen die schnelle Ver- und Entschlüsselung und zum anderen der Umstand, dass (im Gegensatz zu RSA) bisher noch kein Quantenalgorithmus bekannt ist, der NTRU in Polynomialzeit bricht.
Das neueste, gitterbasierte Kryptosystem ist Learning with Errors (kurz LWE), welches von Oded Regev in 2005 veröffentlicht wurde. Es basiert ebenfalls auf schwer zu lösenden Gitterproblemen, wie dem SVP.
Im Vergleich zu etablierten Public-Key-Verfahren wie RSA haben gitterbasierte Kryptosysteme häufig mit längeren Schlüssellängen und auch größeren Chiffren zu kämpfen. Dagegen haben sie oft den Vorteil, dass sie schneller sind und im Gegensatz zu RSA (noch) nicht durch den Einsatz von Quantencomputern angreifbar sind.

Note: See TracChangeset for help on using the changeset viewer.