Semantic Security of Modified Textbook/Raw RSA

user759

10/25/23, 5:37 PM

Here's a modification of the textbook RSA scheme, in an attempt to achieve semantic security.

Key generation: chooses public key $pk = (N,e)$ and secret key $sk = d$ as in any RSA-based encryption scheme.

Encrypting message $m \in \mathbb{Z}^*_N$ using $pk$: Choose $x\gets \mathbb{Z}^*_N$, output $\mathsf{ct}_1 = x^e \bmod N$, $\mathsf{ct}_2 = (m + x \bmod N)^e \mod N$. Output $(\mathsf{ct}_1, \mathsf{ct}_2)$.

Decryption of ciphertext using $sk$: Recover $x$ and $m+x$ from the two ciphertext components, then compute $m$.

Is this scheme IND-CPA secure? (that is, the adversary receives the public key, then must output two messages $m_0, m_1$. It receives the encryption of one of them, and must guess which one was encrypted) The usual attacks against textbook RSA don't seem to work here.

Thanks!

0 + 5

chosen-plaintext-attack

semantic-security

user759

10/25/23, 6:08 PM

@fgrieu Thanks, by semantic security I meant IND-CPA security. You are right, if $\mathbb{Z}_N$ was used, then one of the messages could be $0$ itself, and its encryption will be distinguishable from a non-zero element's encryption. However, if the message space is $\mathbb{Z}^*_N$, would we have an IND-CPA attack? Thanks a lot!

fgrieu

10/25/23, 6:11 PM

Yes $m_0=0$ was the attack I had in mind. I do not immediately see another. I think you mean $\mathbb Z_N\setminus\{0\}$, not $\mathbb Z_N^*$ (the later also excludes $p$, $q$, $2p$…) Note: mathematically, $\mathsf{ct}_2=(m+x)^e\bmod N$ works just as well as the new version.

kelalaka

10/26/23, 10:33 AM

Is there an origin for this?

user759

10/26/23, 10:47 AM

I am teaching textbook RSA, and a few students in the class proposed this variant. I couldn't find an attack (but also don't see how to prove this secure). I wonder if it makes sense to look at this scheme in some idealised model (such as the generic ring model).

kelalaka

10/26/23, 3:54 PM

By some pizza to those students...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Semantic Security of Modified Textbook/Raw RSA

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.