A new public key cryptosystem: NTRU
Csilla Endrődi <endrodi@mit.bme.hu>
BUTE, Department of Measurement and
Instrument Engineering
Zoltán Hornák
<hornak@mit.bme.hu>
BUTE, Department of Measurement and
Instrument Engineering
Endre Selényi, Dr. <selenyi@mit.bme.hu>
BUTE, Department of Measurement and
Instrument Engineering
The increasingly
applied electronic systems indispensably must comprehend most of the data
security functions, thus application of the public key cryptography in practice
is spreading widely.
In our days the
most commonly used public key cryptosystem is the twenty-five-year-old RSA[1].
Younger cryptosystems are the DLP[2]-based
ElGamal Encryption Scheme and the DSA[3],
while recently scientists show increasing interest about the elliptic curve
cryptography (ECC[4]).
Nevertheless continuously great efforts are made for elaborating new public key
algorithms, which support the diverse applications and fulfill the different
requirements better and better.
NTRU, which was
first presented in 1996 at the Crypto’96, is a definitely promising new
cryptosystem. Differently from the previous cryptosystems, which have already
proven their applicability in practice, NTRU is based on a new problem, the CVP[5].
In the past years, many mathematicians and cryptoanalysts – including for
example Adi Shamir and Don Coppersmith – have examined the
algorithm, its applicability and the possible attacks. However the equivalency
of NTRU and CVP is not yet proven – similarly to the identity of RSA and IFP[6]
–, the results of the researches firmly confirm the security of NTRU.
At present
hardware and software implementations of the cryptosystem, including the
encryption (NTRUEncrypt) and the digital signature (NTRUSign) schemes together
with some other important data security algorithms are available as commercial
products. The developers and the inventors of the algorithm claim that the
products have extremely good properties in practical usage: they are fast,
efficient, secure and scalable. However full-scope
analysis of the efficiency properties and the comparison with the other
public-key systems are open for further examinations, the foregoing results
have already proven that NTRU is worth to be presented in large.
In the lecture we
will introduce the algorithm itself, the suggested parameter choices and the
application modes. We will also describe the important parameters of security
(required time for attacks) and practical applicability (speed, data size, code
size), and present a short comparison with other public key systems.
Summarising, presented facts justify that even though NTRU also has also
weakness in practical usage, taking everything into consideration, NTRU is a
well-accomplished, widely usable, promising cryptosystem.