So I'm looking for a minimum cost transformation with _only_ the
following characteristic:
Given a set of m input bits X, produce a set of n output bits Y such
that knowledge of some subset of X and Y gives a minimum knowledge of
the remainder (of Y if that makes it simple, but of X would be nice).
This is not unlike the all-or-nothing package transform proposed
by Rivest; the basic idea is that you have to know all of X in order
to know anything about Y - sort of.
My first iteration is as follows:
Let ^ represent xor.
Let p be the exclusive or of all bits of x (i.e. the parity).
Let Y = f(X), where f(x) = p ^ x
Basically, each bit of Y is the xor of every _other_ bit of x
(x was actually xored into p, so by xoring again, it cancels out)
However, my problem is that no matter how few bits of X you know, you
only have to guess one bit, p, in order to know the bits of Y that
correspond to the bits you know of X.
Let me be concrete; suppose that I know only bits 0 of X and bit
0 of Y. I can then compute p, and from that I can use any further
knowledge of bits of X to compute corresponding bits of Y.
Note that p = x[0] ^ y[0].
Then if I know x[1], I can reveal y[1] = p ^ x[1].
And so forth.
Obviously I need something more complex. The problem seems to be that
the equations for every bit y depend only on x and p; that is, if we
know x, we only have to guess p once for the whole array.
In a way, this reminds me of an idea I had earlier, whereby this
variable p is what I call a common subexpression, a key which unlocks
the equation, a sort of trapdoor.
Suppose I had written Y = f(X) as follows:
y[0] = x[1] ^ x[2] ^ x[3] ^ x[4]
y[1] = x[0] ^ x[2] ^ x[3] ^ x[4]
y[2] = x[0] ^ x[1] ^ x[3] ^ x[4]
...
A novice may have not have realized that each bit of y depends _only_
on x ^ p, and that knowing or guessing p would reveal every bit of Y
for each known bit of X, without having to know any other bit of X.
Now, what I sometimes wonder is whether the equations and tables in
things like DES or SHA-1 are not similar... a table allows for several
boolean logic representations, and depending on which you pick for
each output bit, it may be possible that a common subexpression like p
falls out of the equations, minimizing the amount of unknowns, or
the amount of compute power necessary to brute-force it.
For a Feistel cipher like DES, one might pick different boolean logic
representations in different rounds, to minimize the complexity of
the equations you get at the end.
This is why I don't try to design ciphers. I could possibly come up
with some complicated-looking tables and equations, but I'd have no
assurance that a simple common subexpression did not exist.
Do I need to resort to a conventional hash like SHA-1? I am not
convinced that it is necessary, or that I'd have any more assurance
from SHA-1 than I'd have with a randomly-generated set of equations.
Does it have to be random? Isn't there a regular structure I could
exploit here? It seems like there should be!
Randomly-generated equations remind me a bit of the following AI Koan:
In the days when Sussman was a novice, Minsky once came to him as he
sat hacking at the PDP-6.
What are you doing?, asked Minsky.
I am training a randomly wired neural net to play Tic-Tac-Toe,
Sussman replied.
Why is the net wired randomly?, asked Minsky.
I do not want it to have any preconceptions of how to play, Sussman
said.
Minsky then shut his eyes.
Why do you close your eyes?, Sussman asked his teacher.
So that the room will be empty.
At that moment, Sussman was enlightened.
--
URL:http://www.subspacefield.org/~travis/ -- dharma advaita
For a good time on my UBE blacklist, email [EMAIL PROTECTED]
pgpdBhbOliHn7.pgp
Description: PGP signature
