# Hidden treasure hunt

You are in a world where you trust no one. You never know whether anyone is your friend or foe. For the lust of conquering the world, you have taken up the challenge of risking your treasure. You have hidden it somewhere in the dark and braced yourself to find the hidden treasures of others. The first one to find all the treasures becomes the conquerer. Hold your breath and get ready!

You are completely blided and your powers are not useless, but you and your opponoents start equally. The one that learns the fastest wins. There is a global map known by all. It is a convolute****d overlapping map that hides information of how far is any treasure from a given position. But the global map is hidden and your powers are limited. You can only learn information about a single position at once. But no one knows the positions that are known to you. Your goal is, equipped with position of your treasure and positions that you gradually learn, to find all treasures before anyone else does.

But what is the convoluated global map? After hiding their treasure, each player creates a global map and writes at each position the distance between the position and their trasure. To make the life of opponents harder, they corrupt 50% of the positions. In other words, 50% of position reveal no information about how distant the position is from treasure. They then pick a value $offset$ at random and offset value at each position by $offset$. Then they encrypt the positions and share it with other players. Each player receives encrypted map from other player and the global map is product of all maps.

Turn by turn, each player uses their limited power to learn value at one of the postions of the global map. But no other player learns which position did the active player learnt and what the position value is. After very round, since the player used their power, they must pay for it. They do so by revealing 2 bits of information about their respective $offset$.

## Technical

1. Think of the map as a vector of size 2^15
2. Each player hides a treasure in one of the slots of the map
3. Each player constructs a signal vector that encodes how many blocks away is the given block from the treasure. Player can corrupt 50% of such blocks. That is, instead of encoding the correct distance from the treasure they can encode some gibberish value. Player then chooses a random value $error$ and offsets each slot in the vector by that value.
4. Each player encrypts and makes their signal vector ciphertext public.
5. The global map state is product of all encrypted signal vectors.

Play:
1. At their turn, the player picks a slot to learn from encrypted global state. Note that only the player learns the slot value and no one else learns the slot nor the slot value the player requested to learn.
2. After each player has picked their slot, each player reveals any of the 2 bits of their $error$ value.
3. The first one to find the slots for all treasure, takes the treasure.

Rought notes on rules
1. Let there be n players. Each player can claim to learn position only as many as n times. After which they either declare themselves the winner or are disqualified. To claim that they know a position they encrypt the position, and send it to other players. Other players then multiply the ciphertext with ciphertext of their position and return.
2. After a player has learnt all the positions they declare that they know all the positions and ask each other player for their secret. To ask for the secret the player encrypts the position and sends it to the other player. Other player multiplies their ciphertext encrypting their secret at correct position and returns the ciphertext. Each plyer only entertains such requests from other player once.