4
$\begingroup$

I'm evaluating the performance of NTRU; and I got confused. the key size is said to be smaller than RSA but larger than ECC.

Using both the reference implementation when I choose APR2011_439 setting from BC I've thought that 439 would represent the key size in bits. But when I store the public key in byte array its size if 604 bytes (PKCS1Encoding encoding). I'm very consufed. With APR2011_439 I can encrypt blocks of max 54 bytes in size so that would indeed be the key size. But why does the key stored in a byte array take a huge ammount of 604 bytes? It is the same with reference implementation. Please explain I'm very short on time.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\begingroup$

I've thourgh that 439 would represent the key size in bits.

No, NTRU doesn't measure things like that. Instead, it's the number of elements in a ring. In addition, with the current parameter sets, each ring element is a value between 0 and 2047 (11 bits), and the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which compresses to 604 bytes.

Improve this answer
$\endgroup$
9
  • 5
    $\begingroup$ Yes, the NTRU sizes they have listed in table 1 is wrong. Other things in the paper are also bogus; NTRU is fast, but not nearly as fast as a symmetric system. Also, the paper calls NTRU 'new'; it was invented in 1996, and so it was 16 years old when the paper was written. $\endgroup$
    – poncho
    Commented Apr 21, 2017 at 19:16
  • 1
    $\begingroup$ For the record, the paper commented by poncho's comment above is there. $\endgroup$
    – fgrieu ♦
    Commented Apr 21, 2017 at 19:19
  • 3
    $\begingroup$ @Vega4: there is no standard NTRU parameter set with that low of security (and that's deliberate; Security Innovations does not want to endorse "weak crypto"). If I absolutely had to estimate the size of a parameter set with circa 80 bit security, that'd have circa 430 byte keys; if that's too much, NTRU is not for you... $\endgroup$
    – poncho
    Commented Apr 21, 2017 at 19:34
  • 1
    $\begingroup$ @fgrieu Why am I not surprised about the origin of the paper? $\endgroup$
    – Maarten Bodewes ♦
    Commented Apr 21, 2017 at 22:03
  • 1
    $\begingroup$ @floorcat: it worked for me $\endgroup$
    – poncho
    Commented Apr 22, 2017 at 3:22
5
$\begingroup$

Poncho's explanation is correct: the size is $N \log_2(q)$ rather than just $N$.

A better open-source implementation to use is here: https://github.com/NTRUOpenSourceProject/ntru-crypto -- this is the implementation endorsed by the inventors of NTRU and by Security Innovation, which owns the NTRU patents (and which I work for). It should be preferred to third-party implementations unless you have a particular reason to think the third-party implementation is likely to be better.

The exact parameters, the key sizes, and the motivation for those parameters is in https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/NewParameters.pdf.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.