Most online services, from e-mail to social networking to banking, use strong cryptography to secure the data between different parties. Whether it is login information, e-mail content or bank account details, this data must travel through channels that are assumed to be insecure. An attacker may intercept the communication and use the gained information for their own ends.
Since every cryptographic algorithm needs a key with which the information may be encrypted by the sender and decrypted by the receiver, this also poses a problem for cryptographers: if the channel is supposed to be insecure, how does one share the cryptographic key so that the attacker is not able to get hold of it and thus use it to decrypt the secret message?
The problem is solved by a technique known as the public-key cryptography. Its main advantage is that not one but two keys are used – one (the public key) for encrypting and another (the secret key) – for decrypting the message. This way one party may use the receiver’s public key to encrypt a secret message. This message can be read only with use of their secret key, which, as the name suggests, the receiver must keep secret.
Most public-key schemes today are based on one of two number-theoretic problems: the prime factorization and the discrete logarithm problem. The two problems are solvable in principle, but all of the methods known as of today would take hundreds of years to perform.
However, with the possible event of appearance of quantum computers, capable of exponentially faster parallel processing, prime factorization as well as discrete logarithm problem may become cryptographically redundant. For this reason, the subfield of post-quantum cryptography has been gaining ground in academic study during the recent years.
Post-quantum cryptography is all about algorithms that could not be broken (solved using known techniques or simply brute-forced) by superfast quantum computers. One of the most promising developments in this field is lattice-based cryptography. The term generically refers to public-key cryptography whose main primitive is a structure in vector algebra known as a lattice.
Lattice is a mathematical object with a certain periodic structure. A common example of a lattice-like formation is a stack of oranges, where the pattern formed by the centers of piled up orange-spheres can be easily described by very few vectors.
Although elegantly defined, the lattice structure is known for remarkable computational difficulties in solving some of the problems associated with finding certain points within that structure. For this reason it has been an object of interest for many mathematicians, cryptographers and complexity scientists.
As an effort to familiarize general audience with lattice-based cryptography, researchers and developers funded by Inra, a French institute for research in computer science, have developed a tetris-like game called Cryptris, which aims to explain the principles behind lattice-based cryptosystems.
A player is asked to manipulate blocks of two shades of blue to generate their private key from the secret key. Blocks of same color stack up while opposite-color blocks cancel each outher out. The tetris-like operations (canceling out of the colors and moving the blocks around) correspond to mathematical operations in vector algebra. In particular, the color interaction corresponds to vector addition while moving around of blocks corresponds to vector permutation. These operations form the basis for key generation in lattice-based cryptography.
The game is accompanied by two articles – one explaining the correspondence between the rules of Cryptris and vector algebra, the other explaining lattices and the more detailed workings of the kind of cryptography based on them
The lattice-based cryptography was also the first scheme to be used to implement fully homomorphic encryption – a technique to perform computations on data without the requirement that it be read in plaintext. Seen in this light, the efforts by Cryptris team to familiarize non-professionals with lattice-based cryptography are rather noble, given its future potential.
As of now both the game and the articles are in French only. The authors are looking for English translators to make the exposition available to speakers of other languages.
Anthony Teston, Mathieu Jouhet, Léo Ducas-Binda et Thierry Viéville Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en… jouant à Tetris. Source link.
Anthony Teston, Mathieu Jouhet, Léo Ducas-Binda et Thierry Viéville Cryptris 2/2. Les dessous géométriques de Cryptris : la cryptographie sur les réseaux euclidiens. Source link.