Re: Help needed with a proof...

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 11:54:30 -0400

"Bartosz Zoltak" <X@vmpcfunction.com; X=bzoltak> wrote in message
news:c6r4u4$hps$1@nemesis.news.tpi.pl...
> Sigh, I guess me level of humbleness for provable security, even
> though high for me, is still insufficient...
>
> Let's take something much simpler (elementary?):
>
> Def 1.
> f(x) is any function A --> B; x \in A
>
> Def 2.
> g(z) is any function B --> C; z \in B
>
> Theorem 1.
> If g(f(x1)) is known and g(x) is computationally easy to invert, then
> inverting f(x1) is a necessary condition for recovering x1.
>

Is g independant of f? If g is the inverse of f, then the combination
is the identity function, and not very "secure". That's just an extreme
example. You might want to look at the paper on the security
of multiple encryption.

--Anton