# Decrypt Merkle-Hellman Knapsack Cryptosystem without public key

I am reading the Lightweight Introduction to Lattices and it is a problem Challenge 8 that makes me quite struggle. Basically, the problem give us an encrypted version of a message using Merkle-Hellman Knapsack Cryptosystem. Each letter, before being encrypted, is converted into ASCII bytes (e.g. c: 01100011). Each number $$c_i$$ in the encrypted message $$C$$ has the value: $$c_i = \sum_{j=1}^{8} m_{ij} \cdot H_j$$

Where $$m_{ij}$$ is the $$j^{th}$$ bit of the $$i^{th}$$ letter in the plaintext, while $$H$$ is the hard knapsack.

They give us the size of the public key - the hard knapsack ($$n = 8$$), but does not give us the public key. It's also have this text in the challenge:

Encrypting long messages by repeatedly using small length hard knapsack yield some risks. In the next puzzle, you have to recover the encrypted message Alice sent to Bob. The private and public key are different from the one generated in the previous example. However, you know that the length of H is the same as before: n = 8.

So how can one decrypt the message without the public key? The only approach that I can think of now is using frequency of codewords in the message to do some frequency attack on it. Are there better solutions?

4. How many ciphertext values would you have to recover to be likely to be able to compute the $$H_j$$ values? How would the recovery work mathematically?
5. Once you know the $$H_j$$ values how can you solve everything?