0
$\begingroup$

I am looking for a one-directional encryption algorithm that preserves the size of the input. Then I would like to be able to mix an encrypted with original data and to be able to receive the same result. It is probably hard to grasp, let me try to explain with an example: Let's say I have the input: This is some text to encrypt and the encrypted result with the same size says: xxxxxxxxxxxxxxxxxxxxxxxxxxxx. The algorithm should be able to calculate the same result from any input that mixes the original unencrypted bytes with the encrypted result: This is xxxx text to encrypt or This is some text xx xxxxxx. Note that providing a protocol that describes which area is the original and which is already encrypted is ok. It does not need it to determine this on its own.

An example use case that illustrates an application of such an algorithm: Alice and Bob play battleship. When Alice makes her choices, she encrypts them and sends them to Bob. Bob cannot make any sense of the data, else he will know where to attack. When bob plays his move, Alice reveals the field. Bob does not trust Alice that she did not change the order of the ships after he already told her his move - this is why Alice sends the board encrypted again with already stricken fields revealed. Bob now can apply the algorithm that can encrypt the revealed part to make sure that he will get the same result as the original send from Alice. NOTE: this is illustration use case - I am not looking for alternatives to solve this problem.

Can you give me ideas of algorithms that already provide this or something that I can base such thing on?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ This is a programming problem, not a cryptography problem. If both sides know which sections of the message are to be encrypted they can copy those sections to a buffer, apply a stream cipher then copy them back. If they don't know which sections are which the problem is impossible without increasing the message size. $\endgroup$ – Richard Thiessen May 13 '17 at 21:43
  • $\begingroup$ What two sides, what copies? The whole point is to be able to generate the same encrypted result without having the original message, but redacted version of it - which is a cryptographical problem, not a programmatical. $\endgroup$ – gsf May 17 '17 at 19:46
  • $\begingroup$ It sounds like you're describing a commitment scheme: en.wikipedia.org/wiki/Commitment_scheme $\endgroup$ – Macil May 24 '17 at 0:08
  • $\begingroup$ @AgentME Yes, this seems like what I was looking for - I did not know that there is a whole sub-discipline on the topic. Thanks. I need to do some reading to see if there is an algo that will do what I need. If you submit this as an answer I will accept it. $\endgroup$ – gsf May 24 '17 at 15:22
1
$\begingroup$

It sounds like you're describing a Commitment scheme.

A simple implementation would be that Alice makes a list of boat position + ":" + random 16 bytes (with a different random value per item). She sends Bob the hash of each list item at the start of the game, and later she can send Bob the plaintext of any of the hashes to prove the position of a boat is where it was when the game started. (The random value in the hash is to prevent Bob from brute-forcing the hash. If there only a small number of possible boat positions, then Bob could brute-force to reverse any hash easily if it weren't for the random value.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ hashing and salting every item is what I am doing right now. This though creates enormous overhead. The scale that I am talking about is thousands of new games per second and everyone takes at least 7 years to finish. The other big disadvantage of this is that it requires structured or semi-structured data, I wish to be able to find an algo that works on unstructured data at the time of the creation of the commitment. $\endgroup$ – gsf Jun 1 '17 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.