?

Log in

No account? Create an account
Work - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Work [Feb. 9th, 2006|08:05 am]
Arvind Narayanan
[Tags|]
[Current Mood |depresseddepressed]

Research has been a roller coaster ride. Vitaly and I have been trying to prove a major theorem ("There is no obfuscator for AC_0", for those who know the jargon) for more than 6 months, and we've been in the general obfuscation area for well over a year. Over this period, I have time and time again come up with something that looks like a proof but falls apart on deeper analysis. The partial/related results we've obtained trying to prove it are enough to fill a paper, which we're trying to send to CRYPTO, so its not been a complete waste of time. But I'm still hopeful of catching the big fish.

Incidentally, the theorem would be a considerable improvement (from a theoretical perspective anyway) over one of the main results of BGI+01 (On the (Im)possibility of Obfuscating Programs), which I'm sure a lot of non-cryptographers have heard about.
LinkReply

Comments:
[User Picture]From: ephermata
2006-02-09 12:02 pm (UTC)
Wow, that would be a big theorem! Good luck.
(Reply) (Thread)