who goes 1st problem

[Jason Holt]

[Adam and I are taking this discussion off-list to spare your inboxes, but
this message seemed particularly relevant.  Perhaps we'll come back later if
we come up with anything we think will be of general interest.]

					-J

On Tue, 11 May 2004, Adam Back wrote:

> Anyway the who goes 1st problem definition has my interest piqued: I
> am thinking this would be a very practically useful network protocol
> for privacy, if one could find a patent-free end-2-end secure (no
> server trust), efficient solution.  Another desirable feature I think
> is to not use too much funky crypto, people are justifiably nervous
> about putting experimental crypto into standards, even if it has
> security proofs until some peer review has happened.

Agreed.  Ninghui Li's RSA OSBEs might be the answer; they're not quite as
elegant as the IBE version, but they work with blinded RSA signatures, and so
should be patent-free by next year, assuming Ninghui doesn't seek any patents.  
Section 4 of his PODC paper describes the RSA implementation.  He also has a
new paper which does neat things with commitments that I haven't wrapped my
mind around yet.

Actually, we might also consider contacting Dan Boneh at some point; he seems
to be interested in the proliferation of IBE, and might be sympathetic to the
needs of the IETF to have free standards, especially considering the exposure
it'd get for his system.

However, we need to define just what we need to accomplish.  Since my lab
works in trust negotiation, we think in terms of policies a lot, whereas SSL
just assumes you know what certs you want to send to whom.  But let's assume
the SSL model for simplicity.

The second issue, now that I think of it in this context, would be how you
actually get your certs to the other guy.  Hidden credentials, as Ninghui
pointed out, assume you have some means for creating the other guy's cert,
eg., a template "(nym):Senior_Agent:(current year)" producing
"Bob:Senior_Agent:2004".

The OSBE paper, OTOH, assumes we're going to exchange our certificates, just
without the CA signatures.  Then I can send you messages you can only read if
you really do have a signature on that cert.  But I've always thought that was
problematic, since why would honest people bother to connect then use fake
certs?  The attacker doesn't need to see the signature - he believes you.  So
honest users would need to regularly give out fake certs so they can hide
their legit behavior among the fake connects.  Will Winsborough also suggests
this with the notion of ACK policies - you *always* give people something they
ask for, so they can't tell what you have and what you don't.

So maybe what we really want is some sort of fair exchange or something, where
I can show you my valid certs as you show me the valid certs of your own.  

If one side is guessable, we've discussed this sort of thing with hidden
creds:

E("Hi Bob, since you're a senior agent, you can see my agent credential:
'Alice:Denver field office agent (apprentice):2004",
	"Bob:Senior_Agent:2004")

E("Hi Bob, since you're a BYU alumnus, you can see my BYU credential:
'Alice:Senior:computer science:3.96 gpa:2004",
	"Bob:Senior_Agent:2004")

etc.

So that's an open problem.  But let's assume guessable-certs, since that's the
only way I know how to really keep certs and policies safe for now. The
OSBE-RSA math still works.  So we're good so far, except that the RSA approach
is interactive.  Section 4 says that in the RSA scheme, Alice sends her cert
/and blinded signature/ to Bob (which may or may not be bogus), and then Bob
can send back an encrypted message.  (In HC and IBE-OSBEs, Bob doesn't need
the blinded signature to use as a public key).

But maybe Robert's improved secret sharing scheme from the new HC paper can 
give us some ideas:

1. Alice sends blinded signatures for each of her relevant certs, not
revealing which signature goes with each cert, and not revealing the cert
contents.

2. Bob generates the contents of each of Alice's certs relevant to his policy,
and simply generates each possible combination of hash-of-cert-contents and
blinded-signature.  One from each row will be a match-up between contents and
signature, and Alice will have to figure out which.  Unfortunately, this
requires n^2 multiplies and exponentiations.

						-J