Join Log in
Score:1
CCS avatar Crypto

Number property preserving encryption

de flag
CCS

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?

112
2 + 5
kelalaka avatar
in flag
kelalaka
Check the [Format Preserving Encryption](https://en.wikipedia.org/wiki/Format-preserving_encryption) and that is [already a draft standard by NIST](https://csrc.nist.gov/publications/detail/sp/800-38g/rev-1/draft)
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
@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.
2
Reply
kelalaka avatar
in flag
kelalaka
@MaartenBodewes If Ind-CPA is required ( as it seems so) there are work on this like [A New Method for Format Preserving Encryption](https://ieeexplore.ieee.org/abstract/document/8966348)
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
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.
0
Reply
CCS avatar
de flag
CCS
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.
0
Reply
Score:4
ShAr avatar Crypto
cn flag
ShAr

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.

0 + 2
CCS avatar
de flag
CCS
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?
0
Reply
ShAr avatar
cn flag
ShAr
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
1
Reply
Score:4
Yehuda Lindell avatar Crypto
us flag
Yehuda Lindell

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.

0 + 2
CCS avatar
de flag
CCS
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?
0
Reply
Yehuda Lindell avatar
us flag
Yehuda Lindell
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).
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.