Discussion:
PrivacyPass
(too old to reply)
Trevor Perrin
2017-11-11 16:52:51 UTC
Permalink
Nice elliptic curve / zero-knowledge protocol:

https://medium.com/@alxdavids/privacy-pass-6f0acf075288
https://privacypass.github.io/

The underlying crypto looks to me like a "blinded" VRF ("blinded" in
the sense of "blind signatures", since VRFs can be viewed as a type of
signature). It's being called a "verifiable oblivious PRF", perhaps
because it was arrived at by adding the "verifiable" property to an
"oblivious PRF" rather than vice versa?

For efficiency it's batched, so that a single "signature" is a proof
for multiple VRF outputs.

The VRF is used to blind-issue anonymous credentials (i.e. the server
signs nonces, but is blind to the nonce or signature values, and the
client checks that the signature is "verifiably unique" to prevent the
server from tagging the signature in some way).

These credentials are less sophisticated than most "anonymous
credentials" schemes in the literature: They don't prove anything
beyond "the server gave me a credential", and are single-use because
multiple presentations would be linkable.

But that's sufficient for proving that a Tor user solved a captcha, so
this seems like a great match of problem to a (relatively) simple and
efficient solution.


Trevor
z***@manian.org
2017-11-11 17:05:07 UTC
Permalink
This design evolved out of a prior design based on RSA blind signatures.
The switch to curve based cryptography significantly simplified
implementation from an engineering point of view. All of the cryptography
was pretty easy to implement using implementations of p256 in golang and
javascript.

If anyone is inventing a protocol that calls for blinded RSA, I think they
would be far happier using a curve based OPRF.

Signal/WhatsApp/Phone: +1650-862-5992
Post by Trevor Perrin
https://privacypass.github.io/
The underlying crypto looks to me like a "blinded" VRF ("blinded" in
the sense of "blind signatures", since VRFs can be viewed as a type of
signature). It's being called a "verifiable oblivious PRF", perhaps
because it was arrived at by adding the "verifiable" property to an
"oblivious PRF" rather than vice versa?
For efficiency it's batched, so that a single "signature" is a proof
for multiple VRF outputs.
The VRF is used to blind-issue anonymous credentials (i.e. the server
signs nonces, but is blind to the nonce or signature values, and the
client checks that the signature is "verifiably unique" to prevent the
server from tagging the signature in some way).
These credentials are less sophisticated than most "anonymous
credentials" schemes in the literature: They don't prove anything
beyond "the server gave me a credential", and are single-use because
multiple presentations would be linkable.
But that's sufficient for proving that a Tor user solved a captcha, so
this seems like a great match of problem to a (relatively) simple and
efficient solution.
Trevor
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Jeff Burdges
2017-11-11 18:43:37 UTC
Permalink
I'll summarize our discussion from the ***@gnu.org list.


There are shades of a "bug door" in their no certificates arguments :
- "The only thing edge to manage is a private scalar. No certificates."
- The edge's public key xG is "posted publicly [similar] to a
Certificate Transparency Log [and] "verifiable by all users and so the
deanonymization attack above would not be possible."

In other words, there is no plan for the Tor Project to control any
certificate authorizing the edge's public keys, ala an auditor key in
Taler. Afaik, there are no promises being made about any particular
certificate transparency scheme to keep edges from employing unique
keys.

I think their client software could track the public keys they see
themselves easily enough, but if different edge servers use different
keys then this becomes mostly useless. In fact, if the transparency log
posts 256 keys supposedly used concurrently by 256 different edge
servers, but secretly all edge servers used all keys, then your edge
server plus your edge public key gives CF 8 bits of identifying
information, but nothing looks suspicious in the transparency log.
Post by z***@manian.org
If anyone is inventing a protocol that calls for blinded RSA, I think
they would be far happier using a curve based OPRF.
If you're actually doing money, like we do in Taler, then no you
actually do want RSA blind signatures, not OPRFs plus DLEQ proofs.


These batched DLEQ proofs provide roughly a Schnoor signature for the
withdrawal, so they suffice for many purposes, but..

You loose the blinding when using the DLEQ proof because their hash
incorporates the blinded T. As a result, users must deanonymize
themselves for many activities, like to expose fraud by a merchant, or
show a receipt with fair exchange properties, so all these activities
become privacy minefields with stupidly complex user interfaces. Worse,
you cannot batch the DLEQ proofs like they do lest you deanonymize
multiple transactions, which triples the computational and bandwidth
overhead for OPRFs plus DLEQ proofs.

You loose offline transactions too. We do not require true offline
transaction from a payment system today, and Taler intentionally does
not support them, but.. First, merchants with delayed delivery could
benefit from batching their deposits, so OPRFs make their deposits more
fragile. Second, completely centralized verification for OPRFs turns
merchants into a DoS vector.


In principle, the OPRF described here has extremely secure blinding
because an adversary must compromise both the scalar multiplication and
the hash function that produces the blinding scalar. Against a quantum
adversary, there is likely a slight security regression vs RSA blinding
because the blinding scalar is unlikely to be full domain anymore. In
curve25519, the group order would produce a negligible risk, but against
a quantum adversary the clamping is catastrophic, not sure about P256.

Also, these Schnorr signatures are extremely sensitive to nonce reuse
issues, so you require a good PRNG or else you might reveal your
denomination key through the DLEQ proof. It's fine if you're CF who can
throw serious security at just protecting blogs from SPAM, but it sounds
kinda risky if you want to roll out a payment system in a country
disliked by the NSA or even a refugee camp.

Best,
Jeff
Joe
2018-05-02 18:08:43 UTC
Permalink
Post by Trevor Perrin
The underlying crypto looks to me like a "blinded" VRF ("blinded" in
the sense of "blind signatures", since VRFs can be viewed as a type of
signature). It's being called a "verifiable oblivious PRF", perhaps
because it was arrived at by adding the "verifiable" property to an
"oblivious PRF" rather than vice versa?
FWIW it reminded me of Mathias Hall-Andersen's implementation [1] of a
scheme [2] by Masayuki ABE and Tatsuaki OKAMOTO that proposes a
"partially blinded" ECC scheme, something like "blind signatures with
additional data"

I found it interesting.

[1] https://medium.com/@alxdavids/privacy-pass-6f0acf075288
[2] https://www.iacr.org/archive/crypto2000/18800272/18800272.pdf
Loading...