1
$\begingroup$

Universal reencryption is an interesting encryption primitive. Attempts to build signatures schemes or protocols with authentication incorporating it have frequently failed though.

A plausible application of a signature scheme employing universal reencryption might be:

Alice's software obtains a blind signed credential from a signing authority, perhaps stating her age. Alice wishes to use this credential with multiple websites, but obviously using the same signature on multiple websites violates the browser's cross origin policy because a typical signature depends upon a nonce that could be used to track Alice. A signature scheme based upon reencryption might allow Alice to mutate the nonce embedded in the signature.

There is an easy solution to this problem if the signing authority simply gives Alice thousands of single use blind singed tokens and keeps her stocked up, but that entails some logistical complications.

It'd be lovely if Alice could just use the same signature over and over, mutating it each time through universal reencryption or similar. Are there any signature schemes that support anonymizing the signature like this?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ And your question is? $\endgroup$
    – DrLecter
    Feb 24, 2016 at 13:10
  • $\begingroup$ Oops. I've clarified the question. now $\endgroup$
    – Jeff Burdges
    Feb 24, 2016 at 13:40
  • $\begingroup$ Do you have precise security properties in mind? ​ Can the signing process be interactive? ​ If no, can Alice assume that a compatible private key exists? ​ (compatible with the alleged public key) ​ ​ ​ ​ $\endgroup$
    – user991
    Feb 24, 2016 at 14:08
  • $\begingroup$ An interactive signing process is fine since actually blind signatures are preferable. It's not quite as bad to violate the cross origin policy between the signing authority and the verifiers as it would be to violate it between multiple verifiers. An interactive verification process sounds more problematic. $\endgroup$
    – Jeff Burdges
    Feb 24, 2016 at 17:04

1 Answer 1

Reset to default
1
$\begingroup$

If we have a signature scheme with deterministic verifier and a non-interactive protocol which is [co-non-malleable as an argument of knowledge] and statistically witness-indistinguishable, then we can get a fully non-interactive version of what you want by letting "mutate" be
"run that protocol's prover on", and letting "verify" be "run that protocol's verifier on".
If the protocol is only in the CRS model but has the property that
statistical witness-indistinguishability holds for all possible outputs of the CRS generator, then assuming the existence of a compatible private key would be enough leave the CRS model
by letting the "CRS" be part of the public key, since the signer would store enough about the generator's randomness to let one verify that the "CRS" is a possible output of the generator. ​ Section 8.3 gives such a protocol. ​ Given a statistically hiding commitment scheme,
this paper's proof of Theorem 4 lets "assuming the existence of a compatible private key"
be replaced with "letting the signing phase be interactive".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.