1
$\begingroup$

Is there an encryption function that preserves the properties of the numbers that are inputted into it?

For example, is there an encryption function that, when two numbers are inputted into this function, e.g., 2 and 4, and those numbers are encrypted using the same encryption key, the raw encrypted output of 2 is always half of the raw encrypted output of 4?

$\endgroup$
5
  • $\begingroup$ Check the Format Preserving Encryption and that is already a draft standard by NIST $\endgroup$
    – kelalaka
    Jun 19, 2021 at 7:15
  • 2
    $\begingroup$ @kelalaka Isn't FPS basically a permutation using the same base as the input values? I don't think it has this property. And I think we'd loose a lot more than just IND_CPA on this one. I mean, if you know the encryption of 4 then you'd just half it to get the encryption of 2. Without randomization you would not have to decrypt without knowing the values, even if you have just one plaintext / ciphertext pair. $\endgroup$
    – Maarten Bodewes
    Jun 19, 2021 at 7:40
  • $\begingroup$ @MaartenBodewes If Ind-CPA is required ( as it seems so) there are work on this like A New Method for Format Preserving Encryption $\endgroup$
    – kelalaka
    Jun 19, 2021 at 7:49
  • $\begingroup$ Thanks for the info - that's helpful for me. I think however that this question requires more operations to be possible, not more security. The ciphertext directly would leak information, not just $x$ if $x$ is repeated (as you would expect from PFS). Please do reread it. $\endgroup$
    – Maarten Bodewes
    Jun 19, 2021 at 8:15
  • $\begingroup$ In my case, it does not matter if the security of the encryption is compromised by the fact that the numbers retain their properties (it still has to be very strong encryption though), however, the main goal is just to encrypt 2 mathematically related numbers in a way that the 2 raw outputs will also be mathematically related in the same way. $\endgroup$
    – CCS
    Jun 19, 2021 at 9:42

2 Answers 2

4
$\begingroup$

Regarding your last comment, you can not do both; these are two contradicting constraints.

  • If the mathematical relations were preserved as you describe, anyone can deceive you by sending say $a \cdot \text{Cipher}[X]$ and the recipient will believe him that $a.X$ has been sent to him

This is a very basic property like in chapter 1 in Stallings, but I'm sorry I can't remember what it's called since I last taught the course 10yrs ago.

$\endgroup$
2
  • $\begingroup$ Will this method work? ( ENCRYPTED_TEXT_NUMBER = encrypt(data_number , secret_key), ENCRYPTED_TEXT_2 = encrypt(2, secret_key_1), ENCRYPTED_TEXT_4 = encrypt(4, secret_key_1), ENCRYPTED_TEXT_4 / ENCRYPTED_TEXT_2 = 2 ) This way, if someone wants to derive the two original numbers that were encrypted, they will also need the corresponding secret key and without the corresponding secret key, they will not be able to guess the encrypted numbers, but will this method necessarily work? $\endgroup$
    – CCS
    Jun 19, 2021 at 13:13
  • 1
    $\begingroup$ Cryptanalysis depends on the possibility of existing known plain-cipher pairs. For ex. if after Cipher[X] that the adversary didn't know Alice transfers or even exchanges X units of money, then ur way he could just send 2*C[X]. Concluding info from known/leaked plain-cipher pairs is called Differential Attacks. If u don't want a heavy material or search, search for Enigma or watch the movie "the imitation game" he got plain-cipher pairs for common encrypted sentences like good morning, weather forecast,... Then broke it all $\endgroup$
    – ShAr
    Jun 19, 2021 at 13:31
4
$\begingroup$

This would be extremely insecure. In particular, if you received an encryption of $1$, denoted $C_1$, then you could decrypt any ciphertext $C$ by finding $m$ such that $m \cdot C_1 = C$. Something that has been done that is close to what you refer to is "order-preserving encryption". This has the property that if $m_1 < m_2$ then $Enc_K(m_1) < Enc_K(m_2)$. This is enough to enable many operations on the ciphertexts without decrypting. However, this is also very insecure (albeit a lot better than knowing the exact ratio between the plaintexts). A good place to read about the security of this is the paper What Else is Revealed by Order-Revealing Encryption? by Durak, DuBuisson and Cash from ACM CCS 2016.

$\endgroup$
2
  • $\begingroup$ Will it still be insecure even if extra parameters such as secret keys are used? Because if they are, then doesn't that mean an attacker will not be able to just decrypt ciphertext C by finding m so that m * C1, since they will also need the corresponding secret key to get the correct decrypted output? $\endgroup$
    – CCS
    Jun 20, 2021 at 8:20
  • 1
    $\begingroup$ Any encryption must use secret keys. The attack that I wrote works without knowing the key. If an encryption of 4 is double that of an encryption of 2, and so on, then an encryption of $m$ is $m$ times an encryption of 1. So with simple division it is possible to find $m$, given $C=Enc_K(m)$ and given $C_1 = Enc_K(1)$ (where the attacker knows that $C_1$ encrypts 1). $\endgroup$ Jun 20, 2021 at 9:28

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.