Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a scheme and I don't know that this scheme is semantic security or not.

Secret keys $\{s_1,s_2, x_1,x_2\}$ and public parameter $p$ (large prime number).
Encryption E(m): $C_1 = s_1m + x_1k \bmod p$ and $C_2 = s_2m + x_2k \bmod p$ where $k$ is pseudo-random number.

share|improve this question
And how do you decrypt it? Or, is how $k$ is generated also part of the key? – poncho Jul 3 '15 at 4:07
$k$ is a pseudo-random number as the output of one-way function e.g., $k \leftarrow F_K(id_m)$ where $K$ is a secret key and $id_m$ is an identify of message $m$. Thanks. – Jenifer Tran Jul 3 '15 at 4:27
If $k$ is pseudorandom and not truly random, this is not a one-time pad. OTP is a very specific cryptosystem; if you don't have a truly random key which is never used for more than one message, you don't have it. – cpast Jul 3 '15 at 4:29
Ok, thanks @cpast, I edited the title of question. It is not OTP, I mean this scheme is very similar to the OTP encryption. – Jenifer Tran Jul 3 '15 at 5:05
You can't say "pseudorandom as output of one-way function". You can say "pseudorandom as output of pseudorandom function". – Yehuda Lindell Jul 3 '15 at 6:43

(Note: This answer is based on $k$ being generated by applying a pseudorandom function to a unique message-ID – counter – each time.)

It depends how many times you want to encrypt with it.

If you want it as a complicated OTP, then it's secure. In order to see this, just ignore the $x$ parts and note that $s_1m \bmod p$ and $s_2m \bmod p$ are to independent encryptions under random keys $s_1,s_2$ (note that $s_1$ and $s_2$ have to be uniform in $\{0,\ldots,p-1\}$. For this, you don't need $p$ to be large (just big enough to contain $m$).

If you want to encrypt many times, then it is certainly no longer information theoretically secure. However, just ignore $s_1,x_1,s_2,x_2$ and think of them as public constants. Then, you are encrypting by $m+k \bmod p$ where $k$ is pseudorandomly generated. This is like a type of "counter mode". As long as the RANGE of the pseudorandom function is $\{0,\ldots,p-1\}$ you should be able to prove it.

In both cases, it is overly complicated…

share|improve this answer
"Also, the question should" ... $\;$ – Ricky Demer Jul 3 '15 at 7:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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