Decrypt Merkle-Hellman Knapsack Cryptosystem without public key

Question

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?

Answer 1

There is much more structure to this problem than a generic substitution cipher, and consequently much more that can benefit an attacker. As this is for the purposes of an exercise, I shall only suggest lines of enquiry rather than a complete answer. Please do ask for additional help if required. In the meantime, please consider:

1. How many different ciphertext values are there and what binary ASCII values do they likely represent?
2. Look at the differences between different ciphertext values. Do any of the differences repeat? What might cause these repeats?
3. Are there any repeated differences that are also ciphertext values? What might that represent?
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?