Multiplayer security level: Paranoid

I’ve recently read about Secure multi-party computation. It’s an interesting tool in cryptography that basically tries to make trust not necessary in multi-party communication. One does not have to reveal his secrets to tell something (and nothing more) the other person. One can say something useful actually, like in millionaires’ problem. It’s even been implemented already: .

The point is that, in theory, one could securely compute things that are currently computed on VCMI’s server, that is game mechanics. It’s totally crazy and even non-obvious. I think one would have to use symmetrically encrypted full gamestate (key is f.e. xor of each client’s partial key) and securely decrypt it, process events, encrypt and return calculated packages and send encrypted GS for further processing.

I don’t suggest it’s a good idea. I even think it isn’t. But if anyone says he wants more security, tell them the truth: it’s possible!

Of course it is. I don’t really see how you could use it in gamestate here though. A player is a player, why exactly would you anomize any move from a player so that others didn’t know about it? What’s the usecase?

I primarily restrict access to gamestate. Here is how:

  1. all players read map & generate random password
  2. [secure computation]:
    input: keys from players, read map
    output: initialized, encrypted map (symmetric key: xor of players’ keys), for all players; turn token info
  3. player makes move, processing [secure computation]:
    input: keys from players, encrypted gamestate from players, move from current player
    do: decrypt, update gamestate, encrypt
    output: new encrypted gamestate, player-specific info about action results, new turn token info

perform 3 until game ends.

Now nobody can cheat in any constructive way. Nobody knows the true, full state of the game. Nobody knows what others do, unless it affects them.

Once again, full gamestate is input and output of secure computation. It can only be encrypted or decrypted using all the keys, and that’s why hiding the input is so important: everyone has encrypted gamestate but only taking all the keys together one can actually use it.

In single player game I can in process of gaming move puzzle pieces files to other location temporarily (or before game replace puzzle pieces in LOD by transparent pieces.
This will show me the place for Grail.
In multiplayer this is also possible, I think.
The only solution, I think, is to load all needed puzzles at startup and add them to map information.

Yes, there are a few unfortunate corner cases in Heroes III like puzzles. Adding puzzles to gamestate and rendering the puzzle map securely would solve the problem.

Nope, it’s not about puzzle images that might not cover graal location on screen, but graal position itself - to be secure, client must not know it at all until discovered (in multiplayer online game).

I really don’t understand your idea.
The kinds of shared key schemes usually aren’t for keeping the data secret from the participants; but to confuse which participant signed, encoded or decoded it. Ex: a polynomial secret key can be used to: take any 4 out of 10 keys and decode the input (this one has secrecy, but only until N participants agree); or to sign a array of bytes without knowing who signed except that it’s one of the key of the participants (limited anonymity).

I have no recall of hiding computations from the computer completely except with a trusted server or with fully homomorphic encryption (which is just a ‘holy grail’ of crypto, of which there is no implementation because it would required special drivers or special hardware; because the input has to be decoded once it needs it hits driver level).

There are MANY ways to to resist tampering though; which i suppose it’s what’s actually needed?

edit: actually read the wiki link now. I’m not sure how a protocol like that would be used on a H3 game. The main stuff you’d need is to prevent people from
a ) finding the grail by introspection
b ) edit the gamestate with ‘illegal’ operations in their turn.
c ) secondary stuff would be to find what is in the cities or on the fog-of-war.

These all look like stuff that requires at least one trusted server (to generate keys, decrypt gamestate to check for consistency and update). Even if, for instance the coordinates of the grail could be checked with a homomorphic sum operation, the private key would be needed for decoding the result, so the answer would need to be sent to the server (unless you use this ), which seems to me especially useless.

It just doesn’t look like the millionaire problem situation, where two participants each wants to keep a secret. Rather, it looks like a server and a client (player) where the server’s secret is the grail location (for instance) and the client doesn’t have any pressing need to keep secret it’s dig location from the server (input for the ‘check for grail’ function). Of course, if the server is local too, just introspecting the memory of the server would be enough on that case to fuck everything.

I know it’s a nonstandard way of using secure multi-party computation and if fact it has little to do with fully homomorphic encryption.

Not quite. If map has fixed grail position then you’re right and IMO it shouldn’t be hidden in MP games because it cannot be hidden. When position is randomized, it could never hit the client (unless he digs it out).

a) Kind of troublesome, I’ve answered silmilar problem above.
b) c) Not possible – it’s encrypted all the time, everywhere. All processing on it is withing the securely computed function.

Think of client’s part of key as the secret. Only the one with all the keys can decrypt gamestate and do anything with it. And who has all the keys? Only securely computed function. … ptography/
It’s not mature enough to be used in VCMI (“it is fairly low-level, and is best through of as “assembly language for HE””), but looks promising:)

Does any scheme of fully homomorphic encryption solve the problem of authenticating users sending requests? Standard scenario is 1 client + 1 server, not k clients + 1 server. My scheme of secure computation solves this.

The grail situation is the other way around!

It’s not the client hiding stuff from a third party, but the game mechanics that need to hide something from the client - Therefore, that using HE to send that data to be checked at the client, would be a caching mechanism for something unchanging more than anything. You’d still need the server.
And worse; in HE you don’t know the result of the operation too without decrypting it. So it’s useless!

i30817, yes, of course. HE does not remove the necessity of server. If multi-stage, multi-user, authenticating HE is possible (I have no idea if it is) then we just don’t have to trust the server. Therefore one of the players can run it.