Changeset 5963


Ignore:
Timestamp:
Apr 27, 2014, 1:27:45 PM (8 years ago)
Author:
schmeck
Message:
  • OnlineHelp for LWE
Location:
trunk/CrypPlugins/LatticeCrypto
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/LatticeCrypto/LatticeCrypto.csproj

    r5921 r5963  
    497497    <Content Include="OnlineHelp\Resources\ImgBabai.PNG" />
    498498    <Content Include="OnlineHelp\Resources\ImgGauss.png" />
     499    <Content Include="OnlineHelp\Resources\ImgLWE1.PNG" />
     500    <Content Include="OnlineHelp\Resources\ImgLWE2.png" />
    499501    <Content Include="OnlineHelp\Resources\ImgMerkleHellman.PNG" />
    500502    <Content Include="OnlineHelp\Start.htm">
  • trunk/CrypPlugins/LatticeCrypto/OnlineHelp/HelpFiles/de/LWE.html

    r5802 r5963  
    11<h2>LWE-Kryptosystem</h2>
    22<p>
    3     Todo</p>
     3    Learning with errors (kurz LWE) ist ein Problem, welches im Jahr 2005 von Oded
     4    Regev eingeführt wurde, siehe [Reg05]. Es kann folgendermaßen definiert werden:</p>
     5<p>
     6   
     7    Seien m, n und q ganze Zahlen und sei X auf Zq eine (normale)
     8    Wahrscheinlichkeitsverteilung. Gegeben sei nun das Paar (A, b), wobei die
     9    quadratisch Matrix A aus Zq^(m x n) zufällig gewählt sei, und der Vektor b = As
     10    + e, mit einem ebenfalls zufällig gewählten Vektor s aus Zq^n und einem
     11    Störvektor e aus Zq^m , welcher gemäß X^m gewählt sei. Das Problem ist, den
     12    Vektor s zu finden.</p>
     13   
     14<p>
     15    Anders formuliert soll auf Basis einer Anzahl von ‚approximierten‘ linearen Gleichungen
     16    der Vektor s aus Zq^n ermittelt werden, siehe nachfolgendes Beispiel. Falls kein Störvektor
     17    e verwendet würde, könnten die linearen Gleichungen etwa mithilfe des Gaußschen Eliminationsverfahrens
     18    gelöst werden. Die Approximation macht dieses Problem nun jedoch
     19    ungleich schwerer.
     20</p>
     21
     22<img src="ImgLWE1" />
     23
     24<p>Die Gleichungen sind korrekt bis auf einen kleinen Störwert, z.B. 1, welcher dazuaddiert
     25wurde. In diesem Beispiel ist der Vektor s = [5 7 11].</p>
     26
     27<p>Die Fehlerverteilung ist eine Normalverteilung, welche auf die nächste ganze Zahl gerundet
     28    und modulo q gerechnet wird. Die Standardabweichung ist sigma = alpha * q, mit alpha > 0. Als
     29    Beispiel für eine solche Fehlerverteilung siehe Abbildung 2 aus [Reg10]</p>
     30   
     31<img src="ImgLWE2" />
     32
     33<p>Die Fehlerverteilung ist angegeben mit q = 113 und alpha
     34= 0,05</p>
     35
     36<p>Der private Schlüssel ist s, der öffentliche Schlüssel ist b = As + e, wobei A zufällig und e anhand X generiert werden.
     37    Für die Verschlüsselung wird ein Zufallsvektor r aus {0,1}^m generiert. Dieser
     38    dient dazu, eine Teilmenge von A zu bestimmen, da für den
     39    Verschlüsselungsprozess nicht die gesamte Matrix verwendet werden muss. Im
     40    nächsten Schritt kann dann u = r^T*A berechnet werden. Nun wird der Geheimtext
     41    erzeugt: c = r^T * b + Bit * [q /2] (untere Gaussklammer). Die Verschlüsselung
     42    verläuft für jedes Bit einzeln. Je nachdem welchen Wert das zu verschlüsselnde
     43    Bit hat, wird [q /2] entweder hinzu addiert oder nicht. Der Sender verschickt
     44    (u, c) an den Besitzer des privaten Schlüssels. Dieser überprüft nun, ob das
     45    Ergebnis aus c - u*s näher an 0 oder näher an [q /2] liegt. Im ersten Fall wäre
     46    eine 0 verschlüsselt worden, im zweiten eine 1.</p>
     47   
     48    <p>Das LWE-Kryptosystem ist als Einzel-Bit-Verschlüsselung konzipiert. Das heißt, dass der
     49Vorgang der Verschlüsselung für alle Bits eines Klartextvektors einzeln durchgeführt werden
     50muss. Eine Multi-Bit-Variante wurde 2010 von Tore Kasper Frederiksen in [Fre10]
     51vorgestellt. Insgesamt werden darin drei neue Parameter t, r und l eingeführt. Im
     52        Nachfolgenden sei für eine binäre Verschlüsselung t = 2 gewählt und für den
     53        Optimierungsvektor gelte r = 1. Der dritte Parameter l gibt die Größe des
     54        Klartextvektors vor. Falls die Klartextnachricht also größer als l sein sollte,
     55        wäre hier eine Aufteilung in Blöcke nötig. In der Multi-Bit-Variante sei nun der
     56        private Schlüssel kein Vektor s aus Zq^n mehr, sondern eine Matrix S aus Zq^(n x
     57        l) . Der Störvektor e wird ebenfalls zur Matrix, es gelte E aus Zq^(m x l) . Der
     58        öffentliche Schlüssel sei B = AS+E mod q. Für die Verschlüsselung wird wie
     59        gewohnt ein Zufallsvektor r generiert. Es sei r aus {-1,0,1}^m. Der Rest der
     60        Verschlüsselung und die Entschlüsselung verlaufen analog der von Regev
     61        eingeführten Einzel-Bit-Verschlüsselung.</p>
     62<br/>
     63<p>Quellenangaben:</p>
     64<p>[Fre10] Frederiksen, T. K.: A Multi-bit Threshold Variant of Regev’s LWE-based Cryptosystem.
     652010. – Working Paper, Aarhus University</p>
     66<p>[Reg05] Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and
     67    Cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory
     68    of Computing, ACM, 2005 (STOC ’05), S. 84–93</p>
     69    <p>[Reg10] Regev, O.: The Learning with Errors Problem (Invited Survey). In: Proceedings
     70of the 2010 IEEE 25th Annual Conference on Computational Complexity, IEEE
     71Computer Society, 2010 (CCC ’10), S. 191–204</p>
  • trunk/CrypPlugins/LatticeCrypto/Properties/HelpLanguages.Designer.cs

    r5921 r5963  
    202202        ///   Sucht eine lokalisierte Zeichenfolge, die &lt;h2&gt;GGH-Kryptosystem&lt;/h2&gt;
    203203        ///&lt;p&gt;
    204         ///    Todo&lt;/p&gt;
    205         /// ähnelt.
     204        ///    Das GGH-Kryptosystem basiert auf der Annahme, dass es sehr leicht ist, mittels
     205        ///    einer Basis B und einem kleinen Störvektor e einen Vektor zu konstruieren, der
     206        ///    ebenfalls im Vektorraum V und sehr nahe an einem Gitterpunkt im Gitter L liegt.
     207        ///    Auf der anderen Seite ist es schwer, aus diesem Vektor den ursprünglichen
     208        ///    Gitterpunkt zu rekonstruieren, der in der Nähe dieses Vektors liegt.
     209        ///    Andererseits könnte auch das Finden einer sehr kleinen Basis die  [Rest der Zeichenfolge wurde abgeschnitten]&quot;; ähnelt.
    206210        /// </summary>
    207211        public static string GGH {
     
    277281            get {
    278282                object obj = ResourceManager.GetObject("ImgLengthVector", resourceCulture);
     283                return ((System.Drawing.Bitmap)(obj));
     284            }
     285        }
     286       
     287        /// <summary>
     288        ///   Sucht eine lokalisierte Ressource vom Typ System.Drawing.Bitmap.
     289        /// </summary>
     290        public static System.Drawing.Bitmap ImgLWE1 {
     291            get {
     292                object obj = ResourceManager.GetObject("ImgLWE1", resourceCulture);
     293                return ((System.Drawing.Bitmap)(obj));
     294            }
     295        }
     296       
     297        /// <summary>
     298        ///   Sucht eine lokalisierte Ressource vom Typ System.Drawing.Bitmap.
     299        /// </summary>
     300        public static System.Drawing.Bitmap ImgLWE2 {
     301            get {
     302                object obj = ResourceManager.GetObject("ImgLWE2", resourceCulture);
    279303                return ((System.Drawing.Bitmap)(obj));
    280304            }
     
    376400        ///   Sucht eine lokalisierte Zeichenfolge, die &lt;h2&gt;RSA-Kryptosystem&lt;/h2&gt;
    377401        ///&lt;p&gt;
    378         ///    Todo&lt;/p&gt;
    379         /// ähnelt.
     402        ///    Das RSA-Verfahren, siehe
     403        ///    [RSA78], basiert auf dem Problem der Primfaktorzerlegung. Auf der einen
     404        ///    Seite ist es leicht, zwei große Primzahlen miteinander zu multiplizieren, um
     405        ///    dadurch ein RSA-Modul zu erhalten. Auf der anderen Seite ist es schwer, eine
     406        ///    beliebige, große biprime Zahl in ihre beiden unbekannten, großen Primfaktoren zu
     407        ///    zerlegen. Es wird daher angenommen, dass es sich um eine Falltürfunktion
     408        ///    handelt. Das RSA-Verfahren macht si [Rest der Zeichenfolge wurde abgeschnitten]&quot;; ähnelt.
    380409        /// </summary>
    381410        public static string RSA {
     
    400429        ///&lt;body&gt;
    401430        ///    &lt;h2&gt;
    402         ///        fGitterbasierte Kryptographie&lt;/h2&gt;
     431        ///        Gitterbasierte Kryptographie&lt;/h2&gt;
    403432        ///    &lt;p align=&quot;justify&quot;&gt;
    404433        ///        In diesem Kryptotutorial lernen Sie Gitter kennen und erfahren über ihren Einsatz in der Kryptographie,
    405         ///        insbesondere der Kryptoanalyse. [Rest der Zeichenfolge wurde abgeschnitten]&quot;; ähnelt.
     434        ///        insbesondere der Kryptoanalyse. D [Rest der Zeichenfolge wurde abgeschnitten]&quot;; ähnelt.
    406435        /// </summary>
    407436        public static string Start {
  • trunk/CrypPlugins/LatticeCrypto/Properties/HelpLanguages.resx

    r5921 r5963  
    221221    <value>..\OnlineHelp\resources\ImgBabai.png;System.Drawing.Bitmap, System.Drawing, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a</value>
    222222  </data>
     223  <data name="ImgLWE1" type="System.Resources.ResXFileRef, System.Windows.Forms">
     224    <value>..\OnlineHelp\resources\ImgLWE1.png;System.Drawing.Bitmap, System.Drawing, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a</value>
     225  </data>
     226  <data name="ImgLWE2" type="System.Resources.ResXFileRef, System.Windows.Forms">
     227    <value>..\OnlineHelp\resources\ImgLWE2.png;System.Drawing.Bitmap, System.Drawing, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a</value>
     228  </data>
    223229</root>
  • trunk/CrypPlugins/LatticeCrypto/ViewModels/SvpGaussViewModel.cs

    r5883 r5963  
    154154                paragraph.Inlines.Add(" " + Util.FormatDoubleToPercentageLog(Lattice.Density) + " / " + Util.FormatDoubleToPercentageLog(Lattice.DensityRelToOptimum) + "\r\n");
    155155            }
    156 
    157             paragraph.Inlines.Add(new Bold(new Run("   " + Languages.labelSuccessiveMinima)));
    158             paragraph.Inlines.Add(" " + Lattice.VectorReducedLengthToString() + "\r\n");
    159 
     156           
    160157            paragraph.Inlines.Add(new Bold(new Run("   " + Languages.labelMinimalVector)));
    161158            paragraph.Inlines.Add(" " + Lattice.GetMinimalReducedVector() + "\r\n");
Note: See TracChangeset for help on using the changeset viewer.