who goes 1st problem

[Adam Back]

On Tue, May 11, 2004 at 09:10:35PM +0000, Jason Holt wrote:
> [...] issue [...] 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,
> [...]
> 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.

I think this is ok.  Would suggest you remove the nym field, have
one-use credentials (to avoid linkability across provers), and only
reveal separate nym cert after have satisfied policy.

> But I've always thought that was problematic, since why would honest
> people bother to connect then use fake certs?

Again ok.  You send either fake cert, or real cert for as many
attributes as the CA issues.  You may not even know what some of the
attributes that the CA issues are, all you know is the number of them.

You use and / or connectives between them (using k xor r, k; or r, r
respectively) but using OBSE algorithm (xor refers to improved HC
scheme by HC authors in http://eprint.iacr.org/2004/109/).

> 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.

Yes, that works, but is defined required part of protocol; that way
optimal cover (within limits of partial policy concealment) is given
for sensitive attributes, policies etc.

> 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.

Sounds same as above.

> 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.

That's true.  Think there is a trade-off between degree of
concealment, and amount of permutations prover has to try.  

You could perhaps define an ordering of attributes safely, followed by
dealing with unordered undeclared attributes.  


Other thought perhaps a FPGA like layout where all possible
connectives patterns are represented, might allow to specify arbitrary
boolean formulae with and / or connectives with full policy
concealment but less space and time efficient.


(Calling it prover is kind of odd I find when the prover convinces only
himselfhe satisfies policy by default and optionally chooses whether
to disclose that to verifier.  And "the prover" is the passive entity
receiving encrypted comms, which is back-to-front to usual
prover-verifier comms pattern.  Maybe sender and recipient is better.)

Adam