The wager was to " study the possibility of erecting an iron tower on the Champ-de-Mars with a square base, 125 metres across and 300 metres tall". One such slow solution for approximating the shortest vector is Babai’s algorithm, or Nearest Plane Algorithm, which you can read about in the links provided.The plan to build a tower 300 metres high was conceived as part of preparations for the World's Fair of 1889.īolting the joint of two crossbowmen.(c): Collection Tour Eiffel Like RSA with classical computers, it is hard to find the shortest vector of a large lattice, especially if it exists in many dimensions. A zero vector doesn’t work as an answer, we consider it trivial. Simply put, the goal of SVP is for the attacker to find the shortest vector from the origin (above in red) when given the basis of a lattice (above in blue). The shortest vector problem (SVP) is one of the fundamentals problems presented by lattices that allow them to be useful in cryptography. Many believe that lattice math could be an answer. For this reason, we need quantum-safe algorithms. Shor’s algorithm on quantum computers can crack RSA in less than exponential time. In the quantum world, things don’t look so peachy. There are no known solutions to find prime factors of a number reliably in less than exponential time. RSA works great with classical computers. However, if I told you that 48,554,491 and 575,016,749 are prime factors, all you have to do is multiply them together to verify my answer. If I told you to find prime factors of 27,919,645,564,169,759, that would be hard. □ How Does This Help With Crypto?Ĭryptographic algorithms are typically based on mathematical problems that are easy to verify the answer of, but hard to calculate.įor example, RSA is based on prime factorization. With lattices, we can only scale by whole integers. There is no way to scale v1 (0,3) and v2 (3,0) to reach those points without using fractional scalars. Similarly, we could create an entirely new lattice by changing our basis vectors toĪs you can see, now the intermediary points (0,1) and (0,1) no longer exist in our lattice. For example, the point (2,0) is in our lattice because it can be reached by 2*v1 Our lattice is the set of all values that can be reached by any combination and scale of our basis vectors. The definition of our lattice contains only 2 basis vectors, More simply put, a lattice is defined by basis vectors, which are only able to be scaled by integers… yay no fractions!įor example, let’s create a lattice of all the integers in a two-dimensional plane: □ What is a Lattice?Īccording to Wikipedia, a lattice is the set of all integer linear combinations of basis vectors: b1.,bn E R^n Lattice-based cryptography has promising aspects that give us hope for cryptographic security in a post-quantum world. In January 2019, Many of the semifinalists in the NIST post-quantum-cryptography competition were based on lattices. Lattices, as they relate to crypto, have been coming into the spotlight recently. Lattice-based cryptography, an important contender in the race for quantum-safe encryption, describes constructions of cryptographic primitives that involve mathematical lattices.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |