Blind encryption
George Hewitson
blind a list of tokens, send them to Bob who will then encrypt the tokens,
each with a different key, assign an ID to each token and then send the list
back to Alice who will unblind the tokens, leaving a list of tokens encrypted
by Bob.
Bob will randomize the order of the tokens in the list so the blinding factor
will need to be the same for all the tokens, as Alice will not know which
blinding factor is applied to which token after they come back from Bob.
Furthermore, at some time in the future, the plaintext of some of the tokens
will be revealed to Bob, but I do not want Bob to be able to deduce the blinding
factor and hence unblind all the tokens that he surreptitiously squirreled
away waiting for such an opportunity.
I have read (and have) Schneier's Applied Cryptography (1st edition), but
its treatment of blinding is related to signing blind text, not encrypting
it.
Unfortunately my understanding of a lot of the mathematics behind crypto is
rather lacking, so pointers to implementations of algorithms would be
most appreciated, though I will try and struggle through the math if
necessary.
Many thanks
George.
David Wagner
>I am looking for a blinding and an encryption algorithm, such that Alice can
>blind a list of tokens, send them to Bob who will then encrypt the tokens,
>each with a different key, assign an ID to each token and then send the list
>back to Alice who will unblind the tokens, leaving a list of tokens encrypted
>by Bob.
>
>Bob will randomize the order of the tokens in the list so the blinding factor
>will need to be the same for all the tokens, as Alice will not know which
>blinding factor is applied to which token after they come back from Bob.
If not for the second requirement, you could just use RSA
encryption. If E(x) = x^e mod n, note E(xb) = E(x)*E(b), hence
Alice can send xb to Bob, receive E(xb), and divide out by E(b).
(Of course, Alice can also simply encrypt on her own. Is that bad?)
The second requirement is a big problem for this idea, though, as
Bob will likely then be able to recognize pairs of ciphertexts obtained
in this way. If Bob receives xb and x'b, he can compute x/x' as (xb)/(x'b),
hence if he later sees a pair of messages he can test whether they are
likely to be the pair x,x' (even though he doesn't know either x or x').
I have an inkling that there is maybe a 30% chance that work in the
literature on MIX nets and electronic voting might be able to help you
(see, e.g., Markus Jakobsson's work). However, this is probably a
long shot. Sorry that I'm not able to be of more assistance.
Richard Parker
> I am looking for a blinding and an encryption algorithm, such that Alice can
> blind a list of tokens, send them to Bob who will then encrypt the tokens,
> each with a different key, assign an ID to each token and then send the list
> back to Alice who will unblind the tokens, leaving a list of tokens encrypted
> by Bob.
>
> Bob will randomize the order of the tokens in the list so the blinding factor
> will need to be the same for all the tokens, as Alice will not know which
> blinding factor is applied to which token after they come back from Bob.
>
> Furthermore, at some time in the future, the plaintext of some of the tokens
> will be revealed to Bob, but I do not want Bob to be able to deduce the
> blinding factor and hence unblind all the tokens that he surreptitiously
> squirreled away waiting for such an opportunity.
Perhaps a commutative cryptosystem like the Shamir three-pass
protocol/Massey-Omura cryptosystem is the solution to your problem?
Given a large prime modulus p such that p-1 has a large factor and an
encryption key Ea such that Ea is relatively prime to p-1, Alice blinds the
tokens by computing E(x) = x^Ea mod p and sends the blinded tokens to Bob.
Bob uses p and his own encryption key Eb, also relatively prime to p-1, to
encrypt the tokens blinded by Alice using E(x) = x^Eb mod p and sends these
encrypted blinded tokens back to Alice.
Alice uses her encryption key Ea to find the decryption key Da since she
knows that Da * Ea = 1 (mod p-1). This is why Ea was required to to be
relatively prime to p-1. With this decryption key she unblinds the
encrypted blinded tokens received from Bob using D(x) = x^Ea mod p. This
leaves Alice with tokens only encrypted by Bob's encryption key.
Basically, the encrypted tokens are computed as:
T' = D_A(E_B(E_A(T))
This works because exponentiations is commutative. Successive encryption of
a token T by Ea and Eb results in (T^Ea)^Eb or T^(Ea * Eb) which is the same
as (T^Eb)^Ea or T^(Eb * Ea).
-Richard
john bailey
wrote:
>I am looking for a blinding and an encryption algorithm, such that Alice can
>blind a list of tokens, send them to Bob who will then encrypt the tokens,
>each with a different key, assign an ID to each token and then send the list
>back to Alice who will unblind the tokens, leaving a list of tokens encrypted
>by Bob.
The challenge seems to have similar ingredients to Yao's Millionaire
problem, discussed here about a month ago. (Use Google groups to find)
Message-ID: <acrkfm$jbi$1...@news.iucc.ac.il>
Another reference is:
http://www.uk.research.att.com/pub/docs/att/tr.1999.4.pdf
Frank Stajano and Ross Anderson 1999: The Cocaine Auction Protocol: on
the Power of Anonymous Broadcast ( presented at, and in the
proceedings of, the 3rd International Workshop on Information Hiding,
Lecture Notes in Computer Science, Springer-Verlag.)
I think both of these are excessively complex and am looking for a
simpler means.
John Bailey
email me at my real email address found at:
http://home.rochester.rr.com/jbxroads/
Shai Halevi
Abe and/or Jakobsson from Eurocrypt'98. They use ElGamal encryption,
which seems to do most of what you need.
-- Shai
George Hewitson wrote:
> I am looking for a blinding and an encryption algorithm, [...]
Jason
> George Hewitson wrote on 7/29/02 10:18 PM:
> > Furthermore, at some time in the future, the plaintext of some of the tokens
> > will be revealed to Bob, but I do not want Bob to be able to deduce the
It looks like Richard's suggestion does about what you need, although
I'm curious how Alice computes the plaintext to send back to Bob.
>
> Perhaps a commutative cryptosystem like the Shamir three-pass
> protocol/Massey-Omura cryptosystem is the solution to your problem?
>
> Given a large prime modulus p such that p-1 has a large factor and an
> encryption key Ea such that Ea is relatively prime to p-1, Alice blinds the
> tokens by computing E(x) = x^Ea mod p and sends the blinded tokens to Bob.
>
> Bob uses p and his own encryption key Eb, also relatively prime to p-1, to
> encrypt the tokens blinded by Alice using E(x) = x^Eb mod p and sends these
> encrypted blinded tokens back to Alice.
Just to clarify, Alice now has x^Ea^Eb mod p.
> Alice uses her encryption key Ea to find the decryption key Da since she
> knows that Da * Ea = 1 (mod p-1). This is why Ea was required to to be
> relatively prime to p-1. With this decryption key she unblinds the
> encrypted blinded tokens received from Bob using D(x) = x^Ea mod p. This
[...] ^^^^^^^^^^^^^^^^^
Here I think Richard means x^Da mod p, which would expand to
x^Ea^Eb^Da mod p
= x^Ea mod p
Which is what we wanted. This is in Applied Crypto pp. 516-517, BTW,
and works with commutative encryption in general (with some caveats).
Cool.
-J
Richard Parker
>> Alice uses her encryption key Ea to find the decryption key Da since she
>> knows that Da * Ea = 1 (mod p-1). This is why Ea was required to to be
>> relatively prime to p-1. With this decryption key she unblinds the
>> encrypted blinded tokens received from Bob using D(x) = x^Ea mod p. This
> [...] ^^^^^^^^^^^^^^^^^
>
> Here I think Richard means x^Da mod p
Oops, typo. Thanks for the correction Jason.
-Richard
George Hewitson
>> George Hewitson wrote on 7/29/02 10:18 PM:
> [...]
>>> Furthermore, at some time in the future, the plaintext of some of the tokens
>>> will be revealed to Bob, but I do not want Bob to be able to deduce the
> [...]
>
> It looks like Richard's suggestion does about what you need, although
> I'm curious how Alice computes the plaintext to send back to Bob.
...to continue with the rest of the protocol...
After Alice unblinds the list of encrypted and tagged tokens, she then
encrypts the tokens herself, each with a separate key. This list of doubly-
encrypted tokens is then send back to Bob.
At this point, Alice and Bob share a list of identified doubly-encrypted
tokens, and each have a list of keys that they used to encrypt each token.
Now Alice can decide that a token should be revealed to Bob by sending Bob
the her key for that token. Bob will decrypt the token with Alice's key, then
with his key, revealing the plaintext to him.
Likewise Bob can decide that a token should be revealed to Alice by sending
Alice his key for that token. Alice will decrypt the token with her key, then
with Bobs key, revealing the plaintext to her.
The purpose of this protocol is to implement a card game similar to the
trading card games that you can buy now. With these games, each player starts
with a deck of cards, the contents of which is unknown to their opponent.
Only during the course of play do the cards in the deck get revealed to the
opponent.
The protocol is meant to allow each player to end up with a shuffled list
of cards, each that can only be revealed by the opponent agreeing that it
should be revealed.
Benjamin Goldberg
[snip]
> The purpose of this protocol is to implement a card game similar to
> the trading card games that you can buy now. With these games, each
> player starts with a deck of cards, the contents of which is unknown
> to their opponent. Only during the course of play do the cards in the
> deck get revealed to the opponent.
>
> The protocol is meant to allow each player to end up with a shuffled
> list of cards, each that can only be revealed by the opponent agreeing
> that it should be revealed.
The only way to do it is if you have a trusted third party as a dealer.
It's not otherwise possible, to the best of current knowledge. See:
http://groups.google.com/groups?q=group:sci.crypt+mental-poker
--
tr/`4/ /d, print "@{[map --$| ? ucfirst lc : lc, split]},\n" for
pack 'u', pack 'H*', 'ab5cf4021bafd28972030972b00a218eb9720000';
Douglas Wikström
Suppose you have a "perfect" scheme for playing poker or other card
games as a multiparty protocol. You still have the problem that the
play-sites have, namely offband collusion. I.e. if 5 persons are playing
poker over the internet using some protocol, with coinflipping, mix-nets
or whatever, it is still the case that 2 of them (a minority), may
decide to talk to each other over the telephone and play a joint
strategy. Having access to more knowledge they will statistically win,
if all else is equal.
The major playsites have experienced players and software that monitors
the tables and statistics, to avoid this situations. Hypothetically this
could be encorporated into a general multiparty AI scheme that did the
monitoring, but at (too?) great computational cost.
/Douglas
George Hewitson
> George Hewitson wrote:
> [snip]
> > The purpose of this protocol is to implement a card game similar to
> > the trading card games that you can buy now. With these games, each
> > player starts with a deck of cards, the contents of which is unknown
> > to their opponent. Only during the course of play do the cards in the
> > deck get revealed to the opponent.
> >
> > The protocol is meant to allow each player to end up with a shuffled
> > list of cards, each that can only be revealed by the opponent agreeing
> > that it should be revealed.
>
> The only way to do it is if you have a trusted third party as a dealer.
> It's not otherwise possible, to the best of current knowledge. See:
>
> http://groups.google.com/groups?q=group:sci.crypt+mental-poker
I dont understand which part of my protocol is not feasible.
There are only two players, so there can be no collusion to try and
cheat the system (otherwise why bother playing). While I haven't
explicitly stated this is for only two players until now, I've never
mentioned "Carol". There is no Carol :-) Given this, one of my primary
goals is to avoid Trent (the trusted third party).
My main concern is leakage of information during the game that will
reveal the blinding factor used during the setup phase. Since a single
factor is used for all tokens, if enough information is leaked during
the game to reveal this factor, you will be able to unblind the list of
tokens sent to you and then know what the hidden tokens are and their
order.
If not for this, I could have simply XORed the data with a blinding
key. While this is commutative, it is easily reversible and the entire
list could be unblinded after the first plaintext token is revealed.
So, as long as I can blind the list of tokens with a single factor and
then encrypt each token with a different key, while remaining secure
against a known plaintext attack on the blinding factor, I dont see
what part of the protocol will break down without a trusted third party
(given only two players).
Colin Andrew Percival
> The purpose of this protocol is to implement a card game similar to the
> trading card games that you can buy now. With these games, each player starts
> with a deck of cards, the contents of which is unknown to their opponent.
> Only during the course of play do the cards in the deck get revealed to the
> opponent.
Assuming that I'm understanding the problem correctly...
Alice has a set of cards {M_i}.
Step 1: Alice generates a set of random "salt" values {S_i}.
Step 2: Alice computes H_i = HASH(S_i . M_i) for each i.
Step 3: Alice stores the triplets (H_i, S_i, M_i).
Step 4: Alice generates the values {N_i} by reordering {H_i} randomly.
Step 5: Alice sends {N_i} to Bob.
Step 6: Bob generates a set of random "salt" values {T_i}.
Step 7: Bob computes G_i = HASH(T_i . N_i) for each i.
Step 8: Bob stores the triplets (G_i, T_i, N_i).
Step 9: Bob generates the values {D_i} by reordering {G_i} randomly.
Step 10: Bob sends {D_i} to Alice.
Alice and Bob now share the "shuffled deck" {D_i}. When Alice "plays" the
card D_i, she sends it to Bob, who finds G_j=D_i and sends (T_j,N_j) back to
Alice; Alice verifies that Bob isn't cheating (by checking that
HASH(T_j.N_j) = D_i), finds H_k=N_j and sends (S_k,M_k) to Bob. Bob
likewise verifies (by checking that HASH(S_k,M_k) = N_j).
The "card" M_k has now been identified, and neither player can pervert the
process without either breaking their opponent's random number generator or
finding collisions to the hash function.
Colin Percival
George Hewitson
> George Hewitson <bl...@bonbon.net> wrote:
> > The purpose of this protocol is to implement a card game similar to the
> > trading card games that you can buy now. With these games, each player starts
> > with a deck of cards, the contents of which is unknown to their opponent.
> > Only during the course of play do the cards in the deck get revealed to the
> > opponent.
>
> Assuming that I'm understanding the problem correctly...
>
> Alice has a set of cards {M_i}.
>
> Step 1: Alice generates a set of random "salt" values {S_i}.
> Step 2: Alice computes H_i = HASH(S_i . M_i) for each i.
> Step 3: Alice stores the triplets (H_i, S_i, M_i).
> Step 4: Alice generates the values {N_i} by reordering {H_i} randomly.
> Step 5: Alice sends {N_i} to Bob.
> Step 6: Bob generates a set of random "salt" values {T_i}.
> Step 7: Bob computes G_i = HASH(T_i . N_i) for each i.
> Step 8: Bob stores the triplets (G_i, T_i, N_i).
> Step 9: Bob generates the values {D_i} by reordering {G_i} randomly.
> Step 10: Bob sends {D_i} to Alice.
>
> Alice and Bob now share the "shuffled deck" {D_i}. When Alice "plays" the
> card D_i, she sends it to Bob, who finds G_j=D_i and sends (T_j,N_j) back to
> Alice; Alice verifies that Bob isn't cheating (by checking that
> HASH(T_j.N_j) = D_i), finds H_k=N_j and sends (S_k,M_k) to Bob. Bob
> likewise verifies (by checking that HASH(S_k,M_k) = N_j).
Unfortunately this does not allow a card to be revealed to Bob without
Alice knowning what it is. There are some plays in some games where your
opponent gets to see the top N cards of your deck, but you dont.
So I think both players will need to have the deck contents, which can
only be revealed with permission from the other player.
Colin Andrew Percival
> Unfortunately this does not allow a card to be revealed to Bob without
> Alice knowning what it is. There are some plays in some games where your
> opponent gets to see the top N cards of your deck, but you dont.
You didn't mention that requirement. In that case, I expect that what you
want is impossible, since Alice can't turn over the "right key" to decrypt a
particular card without knowing which card it is.
Colin Percival
Daniel Mehkeri
If you relax the requirement that cheating be detected immediately, and
only require that cheating be detected at a 'verification phase' at the
end of the match (but before any prize is paid), then it should be
possible.
For instance, you can use a Shamir 3-pass protocol, where additionaly each
side chooses a random permutation on the cards and posts a hash of the
permutation. The protocol roughly goes:
1. Alice -> E_Ka(Pa(deck)), H(Pa) Ka Alice's key, Pa Alice's permutation
2. Bob -> E_Kb(Pb(E_Ka(Pa(deck)))), H(Pb)
3. Alice -> D_Ka(E_Kb(Pb(E_Ka(Pa(deck)))))
4. Bob computes D_Kb(D_Ka(E_Kb(Pb(E_Ka(Pa(deck)))))) = Pb(Pa(deck))
If Bob is only supposed to see a card at a time, then in step 3 Alice
posts only the first card, then the second card, and so on.
At the end, Alice posts Pa, Ka; Bob posts Pb, Kb.
This assumes the P's and E_K's commute, which is feasilble.
--
To email me, remove my head.
Colin Andrew Percival
> At the end, Alice posts Pa, Ka; Bob posts Pb, Kb.
Unfortunately, that violates the requirement that Bob should only be able
to see the cards which were "shown" to him during the game.
Colin Percival
George Hewitson
> George Hewitson <bl...@bonbon.net> wrote:
> > Unfortunately this does not allow a card to be revealed to Bob without
> > Alice knowning what it is. There are some plays in some games where your
> > opponent gets to see the top N cards of your deck, but you dont.
>
> You didn't mention that requirement.
You're right. I haven't explicitly listed the requirements as I started
the discussion at one particular point of the protocol rather than describing
it in its entirety with the full set of goals, requirements and protocol
description. I did allude to this requirement in a previous message but that
could have been read as a (side-)effect of the protocol, rather than a
requirement.
> In that case, I expect that what you
> want is impossible, since Alice can't turn over the "right key" to decrypt a
> particular card without knowing which card it is.
The method to handle this is what triggered my posting in the first place.
I believe this is possible if an algorithm exists that allows Alice to
blind the cards, send them to Bob who encrypts the blinded cards and attaches
an identifier and returns that list back to Alice. Alice can then unblind
the cards and be left with a list of cards all encrypted by Bob. Alice then
encrypts the cards herself and sends that list to Bob. Using the identifiers
that Bob attached to the cards, each player can reveal the key they used to
encrypt the card without knowing what the card is.
The responses so far indicate that the required algorithm does exist,
which I have only just started to look into, but I'm worried that the
computation necessary will be excessive. For example, using the
Massey-Omura cryptosystem, Bob will have to generate one key for each
card, where the key (KBn) is relatively prime to (p-1). Generating keys
can be quite slow in my experience but I haven't yet checked out this
specific case.
I will write up a full description of the protocol and post it shortly.
Then you can all tear it to shreds :-)