Density in terms of knapsack public-key cryptosystems

Question

I am quite new to knapsack cryptosystems (specifically the merkle-hellman cryptosystem) and don't quite understand what exactly is the density $d(a) = \frac{n}{\log_2max_i a_i}$ defined here among other things. The denominator of the formula of $d(a)$ is the largest element of the weights (i.e. the public key)? What exactly is the paramter $n$ in this?

And then what is the general meaning of density? Is it about the ratio of plaintext bits to ciphertext bits (as in the information rate formula $d(a) = \frac{\text{number of bits in plaintext messag}}{\text{average number of bits in cipher-text message}}$ below in the paper)?

Maybe you can also give me an example, it's just not clear to me yet, thanks a lot.

Answer 1

Your expression for the density should read $$d(a):=\frac n{\log_2\max_i\log a_i}.$$ In this case, $n$ is the number of weights. It's sort of a measure of how "spread out" different ciphertexts are. If I had a system of five weights each around size 1,000,000 $\approx 2^{20}$ the density is roughly $5/20=1/4$ and my set of 32 possible plaintext messages is roughly the fourth root of the size of the set of numbers around the size of the ciphertext.