History

NTRU was created in 1996 by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman and patented one year later by NTRU Cryptosystems Inc, a company the three inventors established with Daniel Lieman. The name they gave the new system stands for “N-th degree Truncated polynomial Ring Units” (NTRU). The NTRU cryptosystem consists of two algorithms: NTRUEncrypt for encryption and NTRUSign for digital signatures, however only NTRUEncrypt is currently of interest to us.

In the beginning the new cryptosystem was praised for its speed and efficiency, however there were some worries that for smaller N (degree of the polynomial) some attacks performed well. With the possible advent of Quantum computing however NTRU drew new attention and the different attacks were studied much better, as it is more and more obvious that it (or something based on it) is one of the foremost contenders for the title quantum secure cryptosystem of the future, and allows for a lot of further development on its basic structure and concepts. These developments have been happening at a somewhat slow pace since its invention, however in recent times a lot of new research is put into NTRU, and its properties have been studied in much greater detail. A greater scrutiny upon the possible values of the parameters proved certain rings to be weaker and others to be more robust and some provably secure versions were created as soon as 2013. As of 2017 NTRU entered public domain and is free to use by anyone. Currently NTRU has been entered into the Post-Quantum Standardization Project of the US National institute of Standards and Technology.

We have already established, that quantum security is of utmost priority to us, and our chosen system is quantum secure, as well as efficient and quick to use. However, there is also another reason that makes NTRU the perfect fit for Tixl and possibly other currencies with similar goals. As we have already pointed out, one of the great innovations that we bring to the market is encryption of the amount of currency transferred from one account to another. But any transaction must be ready to be verified by anyone and when the amount is encrypted that becomes harder. However, if we use a cryptosystem, which allows the encrypted values to be added and subtracted while they are encrypted and then still be properly decrypted, that allows the transaction to be verified independently without knowledge of any of the actual numbers and sums involved.

Imagine that A wants to transfer n Tixl to B. We encrypt the amount in A’s balance into the number C and the amount in B’s balance into a number D and the transferred amount x into the number y. Then we transfer the amount y from C to D. A’s balance becomes C-y and B’s balance becomes D+y. Anyone can verify that the transaction took place, that account A’s balance has decreased with the same number y that account B’s balance has increased, but nobody knows what those balances are and what that number is.

Thus for our innovation we need a cryptosystem with the property, that you can add and subtract the numbers while they are encrypted. This property is called homomorphism and such a cryptosystem is called homomorphic to addition. Unlike RSA and ElGamal and many others which are homomorphic to multiplication, but not to addition, NTRU is, with some restrictions — homomorphic to a limited number of additions. However this restriction does not apply to us, since we need just one addition, as soon as the encrypted amount goes to the receiver’s account it is decrypted and included. Thus, our chosen cryptosystem is perfect for the use of any cryptocurrency which wants to preserve the transaction amounts hidden, which, combined with the generally excellent speed performance and, of course, the omnipresent danger of the quantum computer is why we have chosen the NTRU system for our product.

First of all, NTRU is a lattice-based cryptosystem. A lattice-based cryptosystem is any cryptosystem based on a problem in the field of lattices, which is considered hard to solve. A lattice is a set of all integer linear combinations of basis vectors and cryptosystems based on lattices generally deal with vectors with integer coefficients. There are several computational problems based on lattices that are considered hard to solve efficiently using both normal and quantum computers. The most important of those is the Shortest Vector Problem, or SVP, which looks for the shortest Euclidean length of a non-zero lattice vector. NTRU and almost every other lattice-based cryptosystem is based on the assumption that this problem, or one of its close relatives — is hard to solve (some versions are provably hard, others are not) and the general consensus is, that even with the advent of quantum computers this problem will still not have a solution. As we will see, NTRU is based on the truncated polynomial ring R and thus generally deals with polynomials and the coefficients of each one of those polynomials form a vector in a lattice. Factoring the multiplication of those polynomials is thus very similar to reducing the basis of a lattice, which is generally the way to solve the SVP. Here, we would not go into much detail about the whole field of lattice mathematics, as NTRU is better understood with a focus on the polynomials and not the lattice.

So what is NTRU? The general definition is that it is a family of cryptosystems based on a truncated polynomial ring

R=Z[x]/X^(N-1)

In that equation R is the name of the ring, Z[x] indicates that the coefficients of x are integer numbers and X^(N-1) indicates the greatest possible degree of the polynomial.

Imagine a polynomial of the form a0 + a1x + a2x^2 +…an-1x^(N-1). The set of all possible polynomials of this form with integer coefficients (a0, a1…an-1) is the so called truncated polynomial ring R, where NTRU is based. So for example the polynomial 6+2x+3x^2 is a polynomial, belonging to the truncated polynomial ring of degree N=3, upon which we can build a (very basic) NTRU cryptosystem.

The value of N (the maximal degree of the polynomials in the ring +1) is one of the three components that determine the particular NTRU cryptosystem (in contrast with the other NTRU cryptosystems in the family). Some particular rings (and thus N-s) are better for the usage of NTRU than others, but generally the rule is — the bigger N, the bigger the set of polynomials, and thus — the more secure the system (and also a bit slower). Some traditionally used values of N are N=167 for quicker applications, N=251 for standard and N=367 for applications with emphasis on security. The other two components determining the NTRU cryptosystem are two co-prime (having no common divisor different from 1) numbers, usually named p and q. Usually p is a very small integer number, almost always 3 is used, while q is usually some power of the number 2 (for example 128 or 256). Since 3 and any number that is a power of 2 have no common divisor, they are co-prime and we can use them for our NTRU encryption. The three system parameters (N, p and q) can be known by anybody.

In the basic cryptographic notation, we usually have Alice (A) who wants to send a message (m) to Bob (B), without divulging its content to the eavesdropper Eve (E). The act of encoding the message is called encryption, the act of decoding it — decryption, the encoded message (e) is called the ciphertext and the mathematical device used for encryption or decryption is called a key. Those are the standard names used for notation in all kinds of cryptographic content and have become the standard and we will use them too. Of course, the role of the potential eavesdropper is not necessarily malicious, for example for our purposes when the currency amount that is transferred is hidden, everyone should be able to verify that the transaction took place and thus operate on the encrypted message, without getting the information hidden in it.

So, Alice wants to send a message to Bob. This means Alice needs a key to encrypt the message and Bob needs a key to decrypt it. Almost all modern cryptosystems are asymmetric, which means that Alice’s key for encrypting the message is different from Bob’s key for decrypting it and NTRU is no exception. In most cases, including ours — the key that Alice has is called a public key and is available to everyone, however Bob’s key, called a private key — is available only to him. Bob generates both keys before the message exchange starts and then releases the public key to the public, including Alice.

Our cryptosystem (and most others) consists of completing three distinct action elements: Key generation, which is the action taken by Bob to create a public key for Alice (or anyone) and a private key for himself; Encryption, which is the action taken by Alice, who has a message that wants to be sent secretly and uses the public key generated by Bob to encrypt it; and finally — Decryption — which is an action taken by Bob to read the secret message using his private key.

So, next time we will look at the three elements one by one and explain how that connects to the lattices mentioned above. Brace yourselves for some more serious mathematics.

Related posts:

Para determinar a data aproximada em que engravidou e estimar a data para o nascimento do seu bebé, a nossa calculadora de gravidez tem em consideração dois eventos: a data do primeiro dia da sua…