[E-Lang] Quantum computing and capabilities

Ralph Hartley hartley@aic.nrl.navy.mil
Fri, 02 Feb 2001 14:15:21 -0500


Mark S. Miller wrote:

> At 11:49 AM Thursday 2/1/01, Marc Stiegler wrote:
> 
>> Though quantum computers can attack the encryption algorithms required for
>> all current forms of secure distributed programming (not just capability
>> systems), 
> 
> Ok, here's one for the Ripley's Believe it or Not of Capability Security.
> 
> As Vernor Vinge so vividly pointed out in A Fire Upon the Deep, there is one 
> form of cryptography that remains strong in the face of arbitrarily huge 
> increases in compute power -- one time pads.  In his novel, one time pads 
> were the only reliable form of encryption, and were the main reason for 
> engaging to interstellar travel -- to courier them.

But quantum cryptography is strictly stronger than one time pads, 
because it does not require a trusted courier.

In fact quantum cryptography can also do most (all?) of what public key 
does, even in the face of unlimited
computation with a quantum computer.

One hopeful fact is that quantum cryptography is much easier than 
quantum computation, it is actually existing
technology. The EPR pairs used by quantum cryptography can be 
transmitted as polarized photons over existing
fibers (with different receivers, transmitters, and relays). This has 
been tested, all that is needed is a bit of
infrastructure to make it universally available.

If quantum cryptography becomes widely available to the defenders before 
quantum computation is available
to the attackers, then there is not a serious problem. Quantum 
cryptography is almost a drop in replacement
for public key.

If the reverse happens, then we may have a problem.

> In deploying any cryptosystem, initial connectivity is bootstrapped via 
> (hopefully) trustworthy channels in previous media, such as sharing of PGP 
> keys on business cards at parties (with physical meat presence), or sending 
> "cap:" URI strings over PGP encrypted email.  The power of cryptography, at 
> least from a capability point of view, is to then continue to have trusted 
> interaction in the new medium, leveraging only the *initial* connectivity of 
> the old medium.

Without public key (or quantum) cryptography, if Alice introduces Bob to 
Carol, there is
no way that Bob and Carol can obtain a communication channel that is 
secure against Alice.
Whether this is a problem or not depends on semantics, if Bob's 
definition of Carol (and Carol's
of Bob) is "the entity introduced to me by Alice", we may still be OK; 
but we must be aware that
this semantics may eliminate otherwise implementable primitives.

The only example I can come up with right now is rather contrived. Is it 
possible to implement
the "If the channel Alice gave me actually allows me to receive genuine 
messages from a cooperating
entity not under Alice's control, send a secure message to that entity, 
otherwise send a message to
whomever" primitive without something like public key?

> By comparing the essences of Pluribus 
> http://www.erights.org/elib/capability/ode/ode-protocol.html (our PK-based 
> crypto capability protocol), and Unibus 
> 
> http://www.erights.org/elib/object-pluribus/unibus.html

Interesting. Until I read that I didn't see how the grant matching 
problem could be done with only private keys.

Ralph Hartley