Topic: Proof of Knowledge without Trusting? - page 2. (Read 2629 times)

This has actually been discussed elsewhere, but my potential application is a card game. You can take a guess which card game.

1. Some cards are known to everyone watching. Just reveal it and it's associated hash.
2. Some cards are known only to the player. Just reveal it to that particular player.
3. The rest are still in the deck. Everyone sees the hash of the cards in the deck without seeing the face of the cards. It's as if each card is individually and uniquely marked at the back. But no one knows
4. The player can prove to himself he got the cards he was supposed to get.
5. The other players have no clue except that the first player did get some cards, but they don't know which ones.
6. It's possible the other players will never be able to tell what those cards are.

Without reading the rest of the literature already available on the subject, I independently came up with something that does the first 2 above. I also came up with a way to shuffle the deck fairly, by having the players cut the deck.

I originally did not want to mention the application, but it seems after reading a lot on the subject, the original problem spawned all sorts of solutions to different cryptographic questions. Everything is related to Poker.

I read the old papers of SRA about Mental Poker and a bunch of others.

I am focusing on the solution where I am the dealer, thus I know all the cards; however I must be trusted. The other solutions being studied consider that there is no trusted third party, and while I think this might be possible (and someone already claims to have achieved it) it's really hard on the computer and the players.

So I need to find a way, to show to Alice that Bob got the cards he was supposed to get without revealing those cards to Alice.

I may have already achieved this but it doesn't seem obvious, so I need to make it apparent or point it out to the people how it is so. Otherwise I will have to do all sorts of advanced math that most people can't even begin to understand so it might defeat the whole point of it.


In the poker world, that is called collusion. We will have to go by some assumptions that they do not do this, especially if they are direct opponents. Let's pretend that Alice and Bob do not want the other person to know what they are holding. If they did, they would send messages through an alternate channel (IM, chat, irc, phone call, or they are in the same room physically.)

We make an assumption that Alice and Bob will not tell each other their cards unless it goes to a show down.

The answer to this, in case this is not possible, is that, if Bob folds, Alice does not care what cards Bob had. Alice wins the pot.

But there are people out there who want to make sure that everyone got the cards they were supposed to get. Again, I think I have already achieved this, but it is just not obvious or I'm thinking I just have have a high probability of it.

I understand that using hashes just means that there is a 2 in 2^256 or 2^512 odds of 2 strings hashing to the same value or a collision, and not actual mathematical proof. But for most people, they'll accept it as proof enough. That's all I really need at this point. I think the SRA paper also accepts this and shows why it is impossible.

Don't need to be so complicated: public-key cryptography is exactly what you need.......

There is an entirely subfield of cryptography that deals with zero-knoweldge signatures of knowledge which are mathematical systems for producing convincing evidence that a person with knowledge of some specific secret data, matching a criteria set by an arbitrary computable function, signed a given public value without revealing anything about the secret data at all, except that the person knew it.

Though without a more concrete description of what you're actually trying to accomplish I can't say what else might meet the criteria you're going for... for many things involving a finite number of people set up in advance who can all interact there are other options beyond signatures of knowledge, including interactive proof protocols and secure group computing.

For some kinds of proof systems can be easily and understably constructed from nothing more than authenticated data-structures, or simple elliptic curve homomorphism.  I'd be happy to tell you exactly how to do so with one of these simple techniques if what you want is possible, but you've managed to write a lot of text without actually communicating to me what you're trying to accomplish.

Going from what you've said, I can't determine where this procedure fails you: Alice picks a random value, publishes the hash.  Bob picks a random value, publishes the hash. Done.

Obviously you want to accomplish more/different than that, but I can't tell what.

I believe that proving something known to one party is _unknown_ to another party, when they potentially could have cooperated is impossible (until you upload humans and can subject their minds to mathematical proofs).

Hi,

I don't know where to place this as this is not exactly bitcoin, but rather a more general technical question.

How do you prove or assert beyond practical doubt that someone knows a secret without revealing the secret?

There is one way I know now, and it is through cryptographic hashes, such as SHA-256.

For example, the word "secret1" when hashed using SHA-256 results to 5b11618c2e44027877d0cd0921ed166b9f176f50587fc91e7534dd2946db77d6.

I can show the result, without revealing the secret until later or until after the required event. But what if I don't want to actually reveal the secret but still somehow prove I knew that?

So far, what I can see is to use another secret and add it to the first secret.

For example, the word "secret2" when hashed results to 35224d0d3465d74e855f8d69a136e79c744ea35a675d3393360a327cbf6359a2.

I can then combine both to make one longer word, such as "secret1secret2" which when hashed results to 9b1623d3c6e5c3e33ac15559b400d554868a3673efd4c088f575696b35d76407.

In this example, I publish the hash of "secret1" but keeping the secret secret. No one else knows it, yet. Then someone else publishes the hash of "secret2", but also keeping their secret secret. Both secrets are now essentially committed, and can't be changed.

Then that other person has to reveal his "secret2" to me or to the public, so that I can use both to come up with the combined hash of "secret1secret2" which is published. Two parties come up with the same result, without revealing the first secret, to prove that they both knew it, while the public only knows the second secret.

However that leaves the problem of me having to know both secrets. Is this enough proof that I knew the other secret without revealing it at all because of the relationship of both secrets and their resulting hashes?

That begs the question that the other party must be honest about the hash result of his "secret2". He can lie, and it breaks the whole concept.

My goal is in a scenario of 3 or more people. I'll use the "standard" names of Alice, Bob, and Charlie. Alice has a secret. Bob has a secret. How can Charlie tell that Alice and Bob have different secrets that remain unknown to the other, and to the public, but reasonably assume those secrets remain unchanged and in fact belong to the same set of unique secrets? I can, at this point, introduce a 4th person called "Dabs" who actually held all the secrets and distributed them to both Alice and Bob randomly.

One method I am using now is to hash each secret, and hand out those hashes publicly to both Alice and Bob. Alice will then be told the secret by Dabs. She can verify the secret against the hash. Bob is also told his secret by Dabs, who in turn can verify the secret against it's hash as well.

Without completely trusting Alice or Bob or Dabs, how can Charlie determine that Alice and Bob got their correct secrets from Dabs? Without Dabs, Alice or Bob revealing the secrets at all.

I've been reading a bit about zero knowledge proofs and other related matters, but their math is beyond me, so I attempted to do the same using hashes as that is much simpler to understand. We know, with a 1 in 2^256 probability, that if the hash result is one thing, the secret must be the original secret. I'm assuming the collision resistance of hash functions as more than enough reasonable proof that the secret is the secret.

A similar system is used in bitcoin gambling casinos, and they call it "Provably Fair".

Ok, this might be confusing and I may have mixed it up already. But I'm posting this anyway so I can get the discussion started, and if this is in the wrong forum, can be moved by a moderator.