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