Professor Rudich told me on Tuesday that he'd recently found a result
in cryptography concerning obfuscators, or methods of making programs
more difficult to understand. (This is a big deal, of course, in
copyright and in DRM -- all sorts of software publishers go to
great lengths to make their programs resistent to reverse engineering.)
The conclusion reached by Rudich and his collaborators is that
obfuscators don't exist, which is to say that a truly secure
obfuscator is a theoretical impossibility. The paper announcing
this is called "On the (Im)possibility of Obfuscating Programs", by
Barak et al.
This doesn't mean that obfuscators can't make things hard to
understand (so that someone would have to expend an extra effort to
read them), just that they can't, in general, make things
impossible to understand -- there is no algorithmic
technique which can accomplish that. The abstract says that
an obfuscator O is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) P and produces a
new program O(P) that has the same functionality as P yet is
"unintelligible" in some sense. Obfuscators, if they exist, would have
a wide variety of cryptographic and complexity-theoretic applications
[...] Our main result is that, even under very weak formalizations of
the above intuition, obfuscation is impossible.
I've been reading The Puzzle Palace by Bamford. Some
parts of it seem rather boring, where Bamford describes military
hierarchy and the succession of people who held any one office
(such as DIRNSA). The spy stories and the esoteric facts about
Fort Meade (the kind of physical security and approximate quantity of
computers there twenty or thirty years ago) are much more exciting to
me than, for example, discussions of whether one branch of the Armed
Forces tended to be favored over another in the selection of deputy
directors.
- "That was one of the best Free Dmitry parties ever!"
- "Yes, and it had that special ingredient: a Free Dmitry."
The Free Dmitry party was just excellent. We had a great turnout,
a great space, celebrity guests (Dmitry, his boss, his lawyer,
lots of local activists...), good sound (thanks, Fred and Patrick),
good food, etc. There are endless people to thank for all this.
You can
listen
to the speeches from the party on Radio EFF (MP3 format).
I saw lots of friends there, many of them from the local Linux and
free software community. There were also lots of reporters there,
and I gave several interviews, frequently interrupted by the fact
that this was a party.
Thanks to Katie, we had a birthday cake for Dmitry, whose 27th
birthday was Tuesday. We all gathered round and sang "Happy
Birthday" with much enthusiasm.
I also have to take a moment to praise the
21st Amendment for
their service, food, hospitality, and ambience. They gave us
the entire upstairs room on condition that we spend over $500
in all on food and drink (which we did). It was an excellent
venue, and I'd hold Free Dmitry parties there again (which,
fortunately, ought to be unnecessary now). Plus, as I mentioned
before, it has "1st Amendment" in the name!
Wow, Rudy
Rucker and I are mentioned in the same article.
"It's very tricky to collect information on one individual," Schoen
tells me.
I realized that I'd lost the partition code I wrote last summer,
so I went to write it again, using a somewhat different approach.
My new code is able to run much faster, finding the ZD(52)=180180
in under a minute (as opposed to around an hour for the old
version, running on a slower computer). It still seems that
there must be a more efficient way; that value was known in the
late 1800s, before the availability of computers.
For people who weren't reading my diary last summer, ZD(n) is the
largest order of any permutation over n elements -- the name comes
from HCSSiM '93 ("Zoe/Dan").
I'm still trying to optimize my program a bit, but I may be on
the wrong track entirely.
