Re: First Attempt at a Proof of Provably Trapdoor-free Encryption



Paul Tomkins <tomkinsp@xxxxxxxxxxxx> wrote:
M=XOR(f(R,k1),g(P,k2))

M: ciphertext
P: plaintext
R: true random stream that is as long as P, never reused, and generally
known to attacker
k1 and k2: keys
f: a one to one transformation function
g: a one to one transformation function
XOR: xor function

[...]

Case 1: Determine k1 and/or k2 assuming P and R are completely known and k1
and k2 are completely unknown. (Equivalent to solving one equation in two
unknowns.)

I'll explain why this sounds bad.

Your scheme takes bit strings R, P, k1 and k2 plus functions f, g,
and outputs a bit string M. We can write this as

M = h(R, P, k1, k2)

where h is some function that depends on f, g. f and g are known
to the attacker, which means that h is also known.

Let pi_i be the function that returns the i'th bit of its input.

Let h_i be the composition of h and pi_i, so h_i(R, P, k1, k2) would
be the i'th bit of M.

Suppose M = (m1, m2, ..., m_n), and k1 = (k1_1, ..., k1_l), k2 =
(k2_1, ..., k2_l). Then we get

m_1 = h_1(R, P, k1, k2) ,
m_2 = h_2(R, P, k1, k2) ,
...
m_n = h_n(R, P, k1, k2) .

This is n equations in 2l unknowns, not one equation in two unknowns.

--
Kristian Gjøsteen
.



Relevant Pages