[cap-talk] Distributed Equality Challenge (was: Alice Frames Carol (was: horton questions))

[Mark Miller]

On 6/12/07, Peter Amstutz <tetron at interreality.org> wrote:
> Yes, I understand the reasoning now, and I think part of my
> misunderstanding is that I'm working from a slightly different set of
> assumptions: I assume that the capability includes both a public,
> self-authenticating portion (a public key) in addition to the actual
> private object capability string.  In that case, if Carol digitally
> signs the capability before sealing it and passing it to Alice, Bob
> knows that a) no one but him knows the capability, because only he can
> unseal it and b) the capability must have come from Carol, because only
> Carol could have signed it.

Performance aside (public key ops are expensive), the logical
difference between this form of solution and Horton is that, in your
solution, Bob can show this signed cap to judge Judy as evidence that
it actually came from Carol (i.e., cryptographic non-repudiation). In
Horton, Bob can know that he should hold Carol responsible, but he'd
have more trouble presenting evidence of this to a third party
(deniable authentication).


> I see how in a system that doesn't use public key cryptography, this
> might need to work sightly differently.

E's distributed capability protocol, Pluribus (CapTP + VatTP) does use
public key ops for connection setup, but the overhead of this is
amortized over everything that happens using that connection. At
<http://erights.org/elib/distrib/captp/unibus.html> we sketch a
distributed capability protocol we name Unibus (in fond memory of the
PDP-11), which uses only single key operations. Interestingly, Unibus
is able to support distributed eventual equality strong enough for
Grant Matching but not for Horton. This surprised me! I had not
previously known of a use case for distributed eventual equality
stronger than Grant Matching.

Unibus supports, and Grant Matching requires, only the ability to
write a join function

    def c := join(a, b)

such that, iff a and b both become fulfilled to the same target, then
c eventually becomes fulfilled to that same target. Note the careful
language on the Grant Matcher page
<http://erights.org/elib/equality/grant-matcher/>: c must be a valid
interpretation of what a meant, and a valid interpretation of what b
meant, such that the providers of a and b have no grounds for
complaint if the Grant Matcher uses c in lieu of the a and b that they
provided.

E primitively provides an immediate equality primitive (==) that,
given two resolved references, returns a boolean rather than a new
reference. If == returns true, then either of its arguments must be a
valid interpretation of the other. In Dean's terminology, join is a
coercing equality primitive, in that it produces a new reference that
should be used instead of the original, whereas == is an
authenticating equality primitive, in that it states that its
arguments themselves are good enough as is. Given ==, we can implement
distributed eventual authenticating equality as:

    def eventuallyEq(a, b) {
        return when (a,b) -> { a == b }
    }

Given eventuallyEq, we can implement join as:

    def join(a, b) {
        def ok := eventuallyEq(a,b)
        return when (ok) -> {
            if (ok) { a } else { throw("not the same") }
        }
    }

But Unibus is only able to support join directly. It is not able to
support an == operation strong enough for the above code to be a valid
implementation of join.

For Horton, once Carol receives a corroborating introduction to Bob,
she needs to know not only that these two Bob's are henceforth the
same, but that this is the same Bob which she already knew, to which
she has already attributed some actions. Only with this retroactive
assurance can Carol reinterpret old evidence of Bob's misbehavior in
light of new evidence of Bob's independence, in order for Carol to
stop blaming Alice for Bob's old misbehavior.

I wonder whether it is possible to build a distributed crypto cap
protocol using only single key ops, which supports equality strong
enough for Horton.

-- 
Text by me above is hereby placed in the public domain

    Cheers,
    --MarkM