Topic: [Semi-OT] Using tree-secrets to reduce bandwidth in cut-and-choose (Read 1130 times)

So, there are 2 trees. The seed secret produces 65536 numbers and then Alice sends the merkle root hash of those numbers.


So, something like this


It is (very) likely that E[ i ] is the encryption of a validly shuffled deck.

[Just a random OT cryptographic though, which I thought I'd write down before I forget it.]

Bob would like to have some Alice provide him with a randomly permuted deck of cards which is encrypted with secrets unknown to him. He doesn't trust Alice to perform this task faithfully. They can use this protocol:

First, Alice selects a secret value. Alice then expands that secret value into two secret values using H(Secret|1) and H(Secret|2), where H is some cryptographic hash. Alice repeats this process recursively, producing a tree of secret values until she has a final set of— say— 65536 secret values.

Alice then computes a tree commitment over these 65536 secret values hashing them up in pairs to form a hash tree root.

Alice then commits to this root by telling it to Bob.

Bob then picks a long random number and tells it to Alice.

Alice generates 65536 ordered decks of cards and proceeds to encrypt them using the first half of each of her 65536 secret values.

Alice then hashes the second half of the secret value with Bob's random number and uses the result to drive a PRNG to fairly shuffle the decks.

Alice then computes another tree commitment, this time over the encrypted permuted decks, and gives the result to Bob.

Bob then picks 1 deck to use and 65535 out of the 65536 decks for Alice to decrypt reveal to him.  Alice the considers the tree of secret values and sends the minimum number of secrets needed for Bob to recover all the secrets except the one for the non-revealed deck: this will be no more than log2(n)=16 values.

Alice also sends the non-revealed encrypted deck.

Bob can now repeat Alice's computation and recompute the root be and confident that the deck he has is good (with security related to the number of decks, p>=65555/65536 of being caught for this example).

The use of the tree structured CSPRNG in this protocol to generate the secrets reduces sending 65536 decks down to sending 16 secret values.

I originally had the idea of using tree structured secrets when thinking about ways to make lamport signatures smaller. The compression in the case of a lamport signature is not very great because the value being signed is a random hash (so it only reduces the average size by 1/3rd or something like that).  In a protocol like this where all but one secret is revealed the proof is incredibly sparse and the compression is tremendous.

If you replace decks of cards in this toy example with ballots in a homomorphic reencryption mixer used for secure voting for a less silly example of how this can be used. Or, for that matter, as a mechanism to securely shuffle transaction data to improve privacy for Bitcoin users.

For lamport signatures in Bitcoin we could further compress signatures by moving everything but the signature root out of the block then using the hash of the block as our validator's randomness to deterministically pick small subsets of the proofs to include with the block, which we decrease in size as the block becomes further buried... as the computational cost of mining prevents an unfaithful signer from rebinding a signature by continually retrying. ... and this could be accomplished in a single block, rather than needing a space wasting two stage commitment that a guy fawkes signature normally requires, since the full uncompressed proof could be sent to the miners.

This is a tremendous reduction in the bandwidth needed for reasonable security levels for cut-and-choose protocols for proofs of faithfulness in these environments. (Other methods may be smaller and easier to compute, but this requires smaller amounts of fancy math which is beneficial if trust requires your users to understand the protocol).