Algorithm to create a superincreasing sequence

Question

I am building an implementation of the [Merkle-Hellman Knapsack Cryptosystem] for my study.(https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem)

One of the things I would like to do, is to create a new private key. A private key in the Knapsack Cryptosystem consists mostly* of a so-called superincreasing knapsack. This is a sequence of numbers K where K[n] > (K[0] + K[1] + ... + K[n-1].

I am wondering if there are smart methods to construct a new sequence for which this holds true. It is easy to create a superincreasing knapsack (such as 1, 2, 4, 8, 16, ...), but I've found it relatively hard until now to do this properly for a sequence that is not predictable.

Are there any algorithms (that probably incorporate a value from a random number generator in there) that can do this?

*there are also two more numbers to compute for the private key, but that is outside of the scope of this question.

Answer 1

I don't suppose this has to be difficult. You know the sum of elements 0 through n-1, so generating n is as simple as picking some value larger than that. A cryptographically secure random number generator should work just fine when doing this, making your answer:

K[n] = sum(K[0] ... K[n-1]) + random(1, c)

Select some value c such that you don't encounter overflow when generating the list, and use that to generate a list as long as you want.

• Martin Maat: And you do not want to recalculate the sum of all priors each time, remember the sum and just add the latest every time instead.
• Qqwy: This is a good answer, and I will probably select it as accepted answer unless someone else places a better answer during the next few days. The most important issue I still have with this approach is what value to select for c, because regardless of what (finite) value is selected, you are leaking entropy: the algorithm will then never be able to create a Knapsack having a jump > c between consecutive elements. Of course, in practice, the Knapsack cryptography has other problems that make it insecure, but it still is an interesting problem.