Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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:
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?
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...
