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.
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.