[E-Lang] Quantum computing and capabilities

[Mark S. Miller]

At 12:06 PM Thursday 2/1/01, hal@finney.org wrote:
>This would mean that Bob cannot set up a secure channel to Carol that
>Alice cannot monitor, but I believe this is OK, as the security properties
>of capabilities do not allow him to establish such a channel.
>
>How far can we get in E with only symmetric crypto?

This can be thought of as the capability-analog of the man-in-the-middle 
issue.  Your statement above is correct as far as pure capabilities are 
concerned (as represented by systems like Actors, and Joule; maybe Toontalk 
too?). However, most capability systems (including E, Droplets, W7, EROS, 
KeyKOS; maybe E-Speak2.2 as well?) also have some kind of EQ primitive 
(equality testing on the capabilities themselves, rather than asking the 
object). Many many years of discussion around this issue led to Norm 
identifying the canonical scenario for showing the difference in power 
between these two kinds of capability system: The Grant Matcher Puzzle 
http://www.erights.org/elib/capability/grant-matcher/index.html .

Unibus does take this issue into account as well, and shows how to provide 
an EQ sufficient to solve the grant matcher, and so to cut out 
forwarders-in-the-middle.

Separately, Dean has shown that you can build EQ given sealer/unsealer 
rights amplification.  It's also known that you can build the latter given 
the former.  An important question is: can you build either (and therefore 
both) given only pure capabilities?  On occasion Dean has convinced me, but 
an hour later I'm never able to reproduce the argument.  Today I'm 
officially skeptical. ;)  In any case, I'm also being unfair to Joule, as I'm 
explaining only the benefits of adding EQ.  EQ has great costs as well, from 
an object oriented abstraction perspective independent of security, but to 
my knowledge only Actors and Joule have ever exploited that power.

While many concurrent logic/constraint programming languages are also 
capability languages, it's not clear how to classify them regarding EQ since 
unification is *so* strange.

Many people doing (usually insecure) distributed objects have noticed 
they're confused about the meaning of object identity in a distributed 
system.  I shared their confusion until Norm explained the Grant Matcher.  I 
now claim this is *the* sensible way to reason about distributed object 
identity.

I am aware that I'm simply stating many things above rather than explaining. 
If you'd like me to expand on something, please ask.


        Cheers,
        --MarkM