The first step is that Alice and Bob randomly pick permutations F and G of 1..52. The deck they’ll use will be shuffled by the composition G*F; this means that neither can cheat by picking something less than random—since it will be composed with the other permutation and randomized anyway—and neither has any information on the resulting shuffle. Alice and Bob send commitments of their permutations to each other, but keep the permutations secret for now.
If Bob needs to draw the Nth card, he lets Alice know and Alice reveals F(N) to him. Then Bob applies G to this result and gets G(F(N)) -- this lets him know which card is the Nth card. Note that Alice gains no information about the Nth card through this protocol.
Alice’s drawing scheme is more complicated. She uses a public-key homomorphic encryption scheme, and sends the key to Bob. When she needs to draw the Nth card, she sends the encryption of F(N) to him. Bob encrypts G, which allows him to compute the encryption of G(F(N)), and sends this back. Alice deciphers this in order to find G(F(N)), without gaining any additional information.
Alice and Bob could have cheated throughout this process. Since by assumption Bob does not know Alice’s cards, Alice could have claimed they were whatever she wanted. However, they can check if cheating occurred after the end of the game by revealing their permutations, which they bit-committed to and cannot later change. Once Alice and Bob both know F and G, they can compute F(G(N)) for any N and verify that all cards drawn were correct.
I have played a secure implementation of Poker; I don’t remember the link, but someone has written an API for doing this. For my final project in AP computer science in high school, I implemented a card game in a secure way under some non-standard cryptographic assumption.
In fact any number of players can play any game involving cards which can be turned face down, shuffled arbitrarily, revealed to a subset of the players, have only some properties revealed, etc. This involves much more complicated technology, but once you can do secure function evaluation, it shouldn’t be too surprising.
The unofficial Magic: the Gathering program “Apprentice” was notoriously vulnerable to cheating. I asked because I was wondering how practical a “cheat-proof” implementation that didn’t require a trusted third party server would be.
I remember dealing with that. A completely cheat-proof implementation would be more technically sophisticated than the rest of Apprentice put together, but you could eliminate deck stacking pretty easily.
Overall, I’d estimate it would be no harder than carefully implementing any well-known cryptographic protocol.
There are two implementation details I left out above: the bit commitment to the permutation, and the homomorphic encryption. Commitment is easy: it can be done using RSA (you first encrypt the permutation, padding with extra noise to avoid known-plaintext attacks, using your public key, and send that; then send the plaintext in verification).
Homomorphic encryption is more complicated, because the algorithms are newer. Something like this should be sufficient, but the security requirements are weird: breaking the encryption is as hard as the approximate GCD problem, which I’ve never heard of outside the context of this paper. I imagine in the next few years people will be working on finding similar schemes but with more standard security assumptions.
To actually do computations on the homomorphic encryption, we need to describe the operation of permutation—that is, given parameters N, G(1), …, G(52) all in the range 1...52, find G(N) -- as a logic circuit. Fortunately, this isn’t too hard. We then write the logic circuit as a polynomial (with AND being multiplication, XOR being addition, so that true and false correspond to 1 and 0 mod 2).
In this case, if the inputs and output are encoded as 6-bit integers, we can write down the circuit as 6 polynomials of degree 7, and all you need is the algorithm on the first page of the paper I linked to (there’s a disclaimer about that algorithm being homomorphic for low-degree polynomials only; I’m pretty sure that for any security parameter high enough you can’t brute force the encryption to break it, 7 is “low”). Just plug the encrypted inputs into the polynomial and send the result back to Alice.
I am leaving out a few details here—for securely making this algorithm public-key, we need to include a bunch of “encryptions of 0” and add them in at various points—but this is not relevant to the difficulty of the problem.
The first step is that Alice and Bob randomly pick permutations F and G of 1..52. The deck they’ll use will be shuffled by the composition G*F; this means that neither can cheat by picking something less than random—since it will be composed with the other permutation and randomized anyway—and neither has any information on the resulting shuffle. Alice and Bob send commitments of their permutations to each other, but keep the permutations secret for now.
If Bob needs to draw the Nth card, he lets Alice know and Alice reveals F(N) to him. Then Bob applies G to this result and gets G(F(N)) -- this lets him know which card is the Nth card. Note that Alice gains no information about the Nth card through this protocol.
Alice’s drawing scheme is more complicated. She uses a public-key homomorphic encryption scheme, and sends the key to Bob. When she needs to draw the Nth card, she sends the encryption of F(N) to him. Bob encrypts G, which allows him to compute the encryption of G(F(N)), and sends this back. Alice deciphers this in order to find G(F(N)), without gaining any additional information.
Alice and Bob could have cheated throughout this process. Since by assumption Bob does not know Alice’s cards, Alice could have claimed they were whatever she wanted. However, they can check if cheating occurred after the end of the game by revealing their permutations, which they bit-committed to and cannot later change. Once Alice and Bob both know F and G, they can compute F(G(N)) for any N and verify that all cards drawn were correct.
Thanks for answering. Yes, that looks like it would work. How hard would it be to actually implement something like this?
I have played a secure implementation of Poker; I don’t remember the link, but someone has written an API for doing this. For my final project in AP computer science in high school, I implemented a card game in a secure way under some non-standard cryptographic assumption.
In fact any number of players can play any game involving cards which can be turned face down, shuffled arbitrarily, revealed to a subset of the players, have only some properties revealed, etc. This involves much more complicated technology, but once you can do secure function evaluation, it shouldn’t be too surprising.
The unofficial Magic: the Gathering program “Apprentice” was notoriously vulnerable to cheating. I asked because I was wondering how practical a “cheat-proof” implementation that didn’t require a trusted third party server would be.
I remember dealing with that. A completely cheat-proof implementation would be more technically sophisticated than the rest of Apprentice put together, but you could eliminate deck stacking pretty easily.
Overall, I’d estimate it would be no harder than carefully implementing any well-known cryptographic protocol.
There are two implementation details I left out above: the bit commitment to the permutation, and the homomorphic encryption. Commitment is easy: it can be done using RSA (you first encrypt the permutation, padding with extra noise to avoid known-plaintext attacks, using your public key, and send that; then send the plaintext in verification).
Homomorphic encryption is more complicated, because the algorithms are newer. Something like this should be sufficient, but the security requirements are weird: breaking the encryption is as hard as the approximate GCD problem, which I’ve never heard of outside the context of this paper. I imagine in the next few years people will be working on finding similar schemes but with more standard security assumptions.
To actually do computations on the homomorphic encryption, we need to describe the operation of permutation—that is, given parameters N, G(1), …, G(52) all in the range 1...52, find G(N) -- as a logic circuit. Fortunately, this isn’t too hard. We then write the logic circuit as a polynomial (with AND being multiplication, XOR being addition, so that true and false correspond to 1 and 0 mod 2).
In this case, if the inputs and output are encoded as 6-bit integers, we can write down the circuit as 6 polynomials of degree 7, and all you need is the algorithm on the first page of the paper I linked to (there’s a disclaimer about that algorithm being homomorphic for low-degree polynomials only; I’m pretty sure that for any security parameter high enough you can’t brute force the encryption to break it, 7 is “low”). Just plug the encrypted inputs into the polynomial and send the result back to Alice.
I am leaving out a few details here—for securely making this algorithm public-key, we need to include a bunch of “encryptions of 0” and add them in at various points—but this is not relevant to the difficulty of the problem.