Help needed with a proof...

From: Bartosz Zoltak (QPbzoltak_at_vmpcfunction.com*(without)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 00:08:25 +0200

I am trying to prove that computing M requires the knowledge of K:

Def 1.
Let f(K,V) be a function, where V is known and K unknown.
Let f have a property that relations between f(K,V1) and f(K,V2) are
undistinguishable from random for V1 != V2.

Def 2.
Let s(X) be a function with a property that s(X) is undistinguishable
from a random data-stream and relations between s(X1) and s(X2) are
undistinguishable from random for X1 != X2.

Def 3.
Let C = M + s(f(K,V)) be known for an unknown M.

Theorem.
To compute M, it is necessary to know K - even in the environment
where s(X) can be inverted and s(f(K,Vn)) is known for any Vn != V.
----------------------

Now the part I am unable to do by myself - prove the theorem (if it is
true). My attempt goes as following and I would really appraciate if
anybody could help me out with it :

1. By definition M = C - s(f(K,V)).

2. Prob[s(f(K,V))=s(f(K,V1))] = Prob[s(f(K,V))=s(f(K,V2))]
    for any V1 and V2.
       Result: even if s(f(K,Vn)) is known (Vn != V) , it gives
                    no advantage in computing s(f(K,V))

3. Prob[f(K,V)=f(K,V1)] = Prob[f(K,V)=f(K,V2)]
    for any V1 and V2
       Result: even if f(K,Vn) is known (Vn != V), it gives
                    no advantage in computing f(K,V)

4?. Prob(M is computed) = Prob(K is computed) =
      Prob( f(K,Vn) is inverted for Vn != V)...?

How to write step 4 formally to make it finish the proof? Is it
possible? Is the rest of the reasoning correct?

Thanks,

Bartosz 

--
Bartosz Zoltak
http://www.vmpcfunction.com
X@vmpcfunction.com; X=bzoltak

Relevant Pages

  • Re: Help needed with a proof...
    ... > I am trying to prove that computing M requires the knowledge of K: ... > Let fbe a function, where V is known and K unknown. ... it is necessary to know K - even in the environment ... My attempt goes as following and I would really appraciate if ...
    (sci.crypt)
  • Re: OPPOSITE OF all coin sequences are computable to infinite length ?
    ... > the TM for computing the halting problem. ... then you assign that to a variable, an unknown so to speak? ... Herc ...
    (sci.math)
  • Re: Registry Editor
    ... "The Unknown P" wrote in message ... > What do you get if you try the regedt32 engine. ... There are three types of people in computing, ... those that can't and those who don't quote. ...
    (microsoft.public.windowsxp.general)
  • RE: Deleting
    ... > "The Unknown P" wrote: ... >> There are three types of people in computing, those that can count and those that can't. ... >> "Claire" wrote: ... is it now not EVER possible to relocate this file? ...
    (microsoft.public.windowsxp.basics)
  • Re: a^(b^x) mod n?
    ... > Jean-Claude Arbaut wrote: ... >>> phiis unknown and b^x is so large it can't be used directly. ... and computing phiis infeasible. ... Prev by Date: ...
    (sci.math)