Unpredictable, ubiquitously rng seed
With most pbm/pbem that I have played there would be a host (or host program) and a client (or client program). As an example; The Vga Planets host program would set the seeds for the battles once the turn files were in and being processed by the host program. Once you received your new turn file, each player would see the same seeded battles play out.
Even if there wasn't a host program, why do you think you would have to show one players actual move to the other player? You could simply have a image (e.g. red light/green light) to tell if the other player has made their move. Once both players locked in their moves you could then have whoever is acting as the host process get both moves and then create a random seed for the results of that turns actions.
Isn't it a problem that if I receive the other player's move I can pick my move in response? You can still solve that problem with my two-step approach (I am sure I am not the first person to think of it, but I don't know of a better name).
It's called a commitment scheme.
Isn't it a problem that if I receive the other player's move I can pick my move in response? You can still solve that problem with my two-step approach (I am sure I am not the first person to think of it, but I don't know of a better name).
It's called a commitment scheme.
Oh, yes, thanks! I asked a friend of mine that used to work in cryptography and he gave me the same name.
I hadnt even considered that, having been focused on the rng algorithm.
so, along with this commitment scheme.
1) Players choose their actions
2) the file is encrypted with a locally random number as the key.
3) players share key when they have the other players actions. In order to prevent collusion each player would need to have the encrypted actions of all other players, not just the player they are sharing with.
so in order to have simultaneous action resolution with accurate information (the results of your last action), each player (except the last to commit actions) must use two communications per turn?
so in order to have simultaneous action resolution with accurate information (the results of your last action), each player (except the last to commit actions) must use two communications per turn?
Either that or you have a trusted server that each player communicates with, and then you only need to send and receive one message per turn.
The security of your key-exchanging mechanism relies on the difficulty of generating two keys where the same message means different things. Really, using a cryptographic hash makes more sense, because collision resistance is an explicit goal of their design, and that's precisely the feature you need.
So again, the mechanism I propose is:
* Player chooses a move MOVE and a long (say 128-bit) random number SALT.
* First message is HASH(CONCATENATE(MOVE,SALT)).
* Once you have the message(s) from the other player(s), you submit a second message, which is CONCATENATE(MOVE,SALT).
* Collect the second message(s) from the other player(s), and verify HASH(SECOND_MESSAGE) == FIRST_MESSAGE.
* Compute the XOR of all the salts, and use that as the seed for a PRNG to be used in resolving the turn.
So again, the mechanism I propose is:
* Player chooses a move MOVE and a long (say 128-bit) random number SALT.
* First message is HASH(CONCATENATE(MOVE,SALT)).
* Once you have the message(s) from the other player(s), you submit a second message, which is CONCATENATE(MOVE,SALT).
* Collect the second message(s) from the other player(s), and verify HASH(SECOND_MESSAGE) == FIRST_MESSAGE.
* Compute the XOR of all the salts, and use that as the seed for a PRNG to be used in resolving the turn.
Another benefit of this approach is that the seed will be uniformly random as long as at least one player generates a uniformly random salt, unconditionally. If exactly all players collude, they can force the seed to be the same as last turn's, or anything really, but this scenario is not interesting as if all players collude then they need not perform any commitment scheme to begin with and can just do whatever.
Although I would personally use PRF(SALT, MOVE) with the salt keying the pseudorandom function family (HMAC with a strong hash function is ubiquitous as a PRF and will do nicely) instead of concatenating the salt and the move. Naive concatenation of bitstrings feeding into plain hash functions tends to lead to subtle but devastating vulnerabilities such as length extension attacks, especially if not all of the inputs are fixed-length. If you're not careful you could accidentally (and completely invisibly) destroy the binding properties of your scheme.
