?

Log in

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

Holy crap [May. 23rd, 2006|12:33 pm]
Arvind Narayanan
[Tags|, ]

I just found out that complexity theorists need Lebesgue measure to define a random oracle (more precisely, proofs relative to a random oracle). Talk about using a hammer to crack a nut.
LinkReply

Comments:
[User Picture]From: ephermata
2006-05-23 11:31 am (UTC)
This is part of why Impagliazzo and Rudich had to go through 40+ false proofs of their big result before getting it right. (From the acknowledgments to Rudich's thesis.)
(Reply) (Thread)
[User Picture]From: arvindn
2006-05-23 11:51 am (UTC)
You're right. One of the reasons I made this post was that I noticed their proof was needlessly complicated.

Incidentally, I need to define worlds where players have black box access to functionalities (inherently stateful) as opposed to functions. Do you have any idea if there's an infrastructure for making such definitions?
(Reply) (Parent) (Thread)
[User Picture]From: ephermata
2006-05-23 11:54 am (UTC)
Wait, why do you say "needlessly" ? If you really are going to prove things about random oracles, then you need to deal with the fact that you are picking a function uniformly at random from the space of all functions. Do you have a simpler way to deal with it than the Borel-Cantelli lemma?

With respect to your question, I don't know for sure. I'd take a look at the Universal Composability work; the ideal world there gives everyone black box access only to the functionalities.
(Reply) (Parent) (Thread)
[User Picture]From: arvindn
2006-05-23 01:36 pm (UTC)
Well, you have a family of functions/protocols/whatever indexed by a parameter k, so restrict the cryptosystem with the index k to the space of all oracles mapping {0,1}^{s(k)} to {0,1}^s(k) for some fixed polynomial s(k) [usually s(k) is just k], instead of {0,1}^* to {0,1}^*, and find the probablity \pi(k) that an oracle in this (finite) set is bad, and conclude that your statement is true for a random oracle because \pi(k) goes to 0 for large k. I mean, that's the way the Bellare Rogaway-model works, right?

P.S: 40+ proof attempts is insane!
(Reply) (Parent) (Thread)
[User Picture]From: paper_crystals
2006-05-23 07:15 pm (UTC)
This all sounds very interesting. Can you explain it?
(Reply) (Thread)
[User Picture]From: arvindn
2006-05-25 12:16 am (UTC)
Probably not the technical part (at least not without assuming a background in complexity theory) but the cultural aspect, certainly.

In a sentence, complexity theory, mother of the computer sciences, is the math behind how hard it is to perform a given computational task.

Crypto is a mishmash of different kinds of people: there are those who view it as a branch of complexity theory, and at the other extreme there are those who just want to build secure systems and protocols without having to worry about the math. Most people are interested in constructing protocols but want to be able to justify it complexity theoretically, but are not interested in complexity theory for its own sake.

A recurring issue is the tension between the believability of a definition and the hardness of doing proofs that meet that definition. Likewise, it is common for one faction to give a proof that involves constructing a number that encodes the bit-repesentation of an algorithm (or circuit), and the other faction to respond with a giant "WTF?"

Random oracles are objects that "magically" map strings into random strings. They are defined by quantifying over all functions over a certain space. What I was pointing out was that by defining these spaces in a convenient way, rather than in the most natural way, proofs can be considerably simplified -- in particular, made combinatorial. I (like many computer scientists, I suspect) have a natural aversion for any math that is not discrete. However, ephermata seems to disagree that this can be done, so don't take my word for it.
(Reply) (Parent) (Thread)
[User Picture]From: paper_crystals
2006-05-25 12:22 am (UTC)
Okay. That makes a little bit more sense. Thank you.
(Reply) (Parent) (Thread)