2
$\begingroup$

In the original NTRU paper:NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level as an example:

Key size in Moderate security

I understand the calculation of the public key size: $len_{pk} = N\cdot \log(q)=107 \cdot 6=642$ bits, but why is the private key size 340 bits?

$\endgroup$
2
$\begingroup$

Because the entries are ternaries, you can encode them using 2 bits, which gives an encoding of size $2 \cdot 107 \cdot 2 = 428$ bits.

There are smarter way to represent things though. But for general ternary strings you can't do any better than $2 \cdot 107 \cdot \log_2(3) = 339.18 $ (though it may be painful/costly to encode and decode to such a compact size.). Maybe one could also exploit the fact that we know exactly how many $1$'s and $-1$'s there are, which decrease entropy, but encoding/decoding becomes even more costly...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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