Re: Help needed with a proof...
From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 04/29/04
- Next message: ebay This: "Re: Pat Tillman's Used Jock Strap on Ebay"
- Previous message: FRMook: "Re: pseudo-random key generator, not bad says i"
- In reply to: Bartosz Zoltak: "Help needed with a proof..."
- Next in thread: David Wagner: "Re: Help needed with a proof..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 28 Apr 2004 22:45:54 GMT
You need to give the set of K, V, M and C. And The range and domain of
s() and f().
Even if you did... I think you're missing something profound to think
your attept at (4) will produce anything.
JLC
Bartosz Zoltak <QPbzoltak@vmpcfunction.com*(without "qp")> wrote:
> 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
--
- Next message: ebay This: "Re: Pat Tillman's Used Jock Strap on Ebay"
- Previous message: FRMook: "Re: pseudo-random key generator, not bad says i"
- In reply to: Bartosz Zoltak: "Help needed with a proof..."
- Next in thread: David Wagner: "Re: Help needed with a proof..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
