3 ms·

In the example, the vertices colors for a graph edge are requested, but how can one trust that those colors aren't being generated on-the-fly? Effectively, how

In the example, the vertices colors for a graph edge are requested, but how can one trust that those colors aren't being generated on-the-fly? Effectively, how can I trust that the "warehouse" isn't cheating me?

eemax 12y ago
The OP glosses over this a bit, but it's mentioned in the footnotes: the "hats" represent a commitment scheme, which is a way for the prover commit to a specific color assignment, before revealing what that assignment actually is. When the verifying party chooses the two vertices he wants to see, the prover can reveal only those two, and the verifier actually has two things to check: 1) the colors revealed are actually two different colors (otherwise the purported solution obviously isn't correct) 2) the colors revealed are consistent with the prover's overall commitment. (in other words, that the prover didn't change his answer "on-the-fly")
p4bl0 12y ago
You physically can't put a crayons under the hat on the fly. Similarly in the equivalent digital experiences, the prover commits to a value and must be able to prove that it didn't change it (for instance it must provide the verifier a hash of the chosen color + some random salt).
VLM 12y ago
Check out http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing Encrypt the answer and maybe some salt or if you're really brave, some known plaintext provided by the other guy (here be dragons), give the pub key for every node to everyone, split the private key using SSSS or some other strategy, and give all SSSS key-halve to the other guy and google only gives up precisely two of their halves upon request so you only get to SSSS reassemble the private keys for two nodes and thus only know two nodes. There are some other schemes involving hashing that I feel a little fuzzier about. Also look into "double spend" algos for digital cash. Go ahead, opfor, make my day, you double spend a token and you get more data but GOOG gets the transaction's swiss bank account number so the financial transaction auto-completes. That might take a little more fooling around at the protocol level to set up.

eemax 12y ago

The OP glosses over this a bit, but it's mentioned in the footnotes: the "hats" represent a commitment scheme, which is a way for the prover commit to a specific color assignment, before revealing what that assignment actually is. When the verifying party chooses the two vertices he wants to see, the prover can reveal only those two, and the verifier actually has two things to check: 1) the colors revealed are actually two different colors (otherwise the purported solution obviously isn't correct) 2) the colors revealed are consistent with the prover's overall commitment. (in other words, that the prover didn't change his answer "on-the-fly")

p4bl0 12y ago

You physically can't put a crayons under the hat on the fly. Similarly in the equivalent digital experiences, the prover commits to a value and must be able to prove that it didn't change it (for instance it must provide the verifier a hash of the chosen color + some random salt).

VLM 12y ago

Check out http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing Encrypt the answer and maybe some salt or if you're really brave, some known plaintext provided by the other guy (here be dragons), give the pub key for every node to everyone, split the private key using SSSS or some other strategy, and give all SSSS key-halve to the other guy and google only gives up precisely two of their halves upon request so you only get to SSSS reassemble the private keys for two nodes and thus only know two nodes. There are some other schemes involving hashing that I feel a little fuzzier about. Also look into "double spend" algos for digital cash. Go ahead, opfor, make my day, you double spend a token and you get more data but GOOG gets the transaction's swiss bank account number so the financial transaction auto-completes. That might take a little more fooling around at the protocol level to set up.