It’s the EOWFAWKI!

December 10, 2014

Modern cryptograpy is a sprawling subject and the latest illumination in my endless education is the existence of extractable one way functions, EOWF’s…
“A function f is extractable if it is possible to algorithmically “extract,” from any adversarial program
that outputs a value y in the image of f, a preimage of y.” : On the Existence of Extractable One-Way Functions. Bitansky et.al, May 2014.
That’s potentially bad news for my OWF as, if you’ve studied it, it’s obvious that any ‘within parameter’ guess of x yields a preimage x’. The good news is, the hash fn & trapdoor file in this OWF are obfuscated by virtue of each recieving only half of the stream identity. Some up-to-date discussion of obfuscation here: Poly-Many Hardcore Bits for Any One-Way Function and a Framework for Differing-Inputs Obfuscation Bellare et.al, Sept 2014. 
Additionally, even if an adversary guesses a preimage correctly, they still have to know the iterative private key. An in parameter guess may yield a trivial sequence of preimages but it’s a ‘Tar-Baby’ in terms of discerning where & when the sequence diverges. It’s diabolical & I don’t believe it can be ‘black boxed’ or even ‘non black boxed’ given its poly pre-image span and trapdoor obfuscation.
Comment and corrections welcome.
*Papers linked in Related-Useful archive.

Advertisements

One Response to “It’s the EOWFAWKI!”


  1. Mihir Bellare’s papers stand out like a beacon in the ocean of crypto-theory. Smart bloke, that.
    I haven’t exhaustively read his entire bibliography but another of his papers which appears to support the primitive I’ve proposed on this site is, Many-to-One Trapdoor Functions and Their Relation to Public-Key Cryptosystems, 1998.

    Like


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: