[Cryptography] Maybe those million-bit-key cryptosystems have something to offer after all...

[Patrick Chkoreff]

Grant Schultz wrote on 07/29/2018 10:22 PM:

> On 7/29/2018 11:00 AM, cryptography-request at metzdowd.com wrote:
>> A common theme of amateurish or over-hyped cryptosystems - at least a
>> couple of years back; this seems to have faded - was the use of
>> super-long keys for "higher security".
> Along this line, see Samid's paper, “Larger Keys, Less Complexity” A
> Strategic Proposition, at
> 
> https://eprint.iacr.org/2018/406.pdf
> 
> He's been thinking along those lines, although I can't say anything
> about the security of his proposed system(s).

I like the vision but I can't get past this key point:

  "key bits must be shared by the parties"

Certainly two parties could "dial up" the security all the way to
perfect by using a one-time pad, and that would in fact drive the
algorithmic complexity all the way down to XOR.  Problem is, that key is
toast once it's used up, and now the parties have to share a brand new
key.  It is mathematically impossible to use a one-time pad to
communicate the next one-time pad of the same size -- unless your
message size is zero in which case there is no communication at all.  So
now what?

The good thing about a shared 128-bit AES key is that you can use it to
encrypt a virtually unlimited amount of future information.  It never
"runs out."  But even the sharing of THAT key begs the question:  how do
you share it?  Aside from meeting in person and exchanging a slip of
paper, the only way I can think is to rely on mathematical "tricks" such
as discrete log and factoring, and now you're right back to high levels
of algorithmic complexity, and the possibility of someone finding a way
to break the scheme forever.

I can't help but think that his vision cannot in principle be achieved,
but I can't imagine how to prove that.  It is only a gut feeling brought
on by the simple fact that you can't use a one-time pad to communicate
both a message AND the next one-time pad of the same size.  However,
perhaps it can be demonstrated that with some minimal degree of
mathematical complexity a bit higher than XOR, it might be achievable.
I haven't looked at BitFlip so I don't know if that's a candidate.


-- Patrick