Bram's page

The following is a public key algorithm I came up with, and some thoughts on it.

The private key consists of a positive integer, p.

The public key consists of a set of k randomly chosen integers significantly longer than the private key, all about the same size and about half of them negative, such that each of them is less than p/2k modulo p.

To send a bit, the encrypter picks half of the integers in the public key at random and adds them together. She then sends the result or it's negation to communicate either a 0 or a 1 bit, respectively.

The decrypter takes the number sent to him and finds it's value modulo p. If the result is less than p/2, he can deduce that the sent bit is a 0, otherwise it's a 1.

That's the entirety of the algorithm.

Say you have a heavily overconstrained knapsack problem - that is, one where the numbers involved are so large that if numbers of that size were chosen at random the chances of there being a solution would be virtually nil, but a single solution was manually inserted. Obviously, if there exists a p such that the sum of n mod p for all numbers in the problem except one is less than p/2 and the remaining number mod p is greater than p/2, that number can't be in the solution. I believe that the chances of there being such a p for all numbers not in the hidden solution is quite high, which would imply that any technique which breaks the algorithm given above is very powerful for finding hidden solutions to overconstrained knapsack problems.

I looked at the techniques used to break other knapsack-based cryptosystems but they don't seem to apply to this one because the amount of pattern hidden in the public key is so much less. I'm incapable of any forther cryptanalysis.

There are simple adaptive attacks which can be fixed with a proper encoding. Specifically, which subsets to sum up to create the numbers which might or might not be negated should be selected using a PRNG, and the seed for that PRNG should be sent as the encrypted bits. Each new message should use a randomly chosen seed. The seed can then be used as the key to a symmetric cipher, and the meat of the message can be encrypted without all the public key bloating.

I figured out this technique in early 1998 and explained it to a couple people at crypto '98. None of them had seen it before or could immediately see a way of cracking it, but the general feeling was that it's very similar to some known broken public key cryptosystems and can probably be broken with similar techniques.

Given it's simplicity, I think it's quite likely that this algorithm was discovered much earlier.

If you have any thoughts, comments, relevant references, breaks, or information on prior inventions, please mail them to me.

-Bram Cohen