I have an encryption scheme where the secret keys are $(\alpha_1, \alpha_2)$ and $(y_1, y_2)$. $(y_1', y_2')$ are public information. The ciphertext is:

\begin{align*} \mathit{ct}_1 &= r_1 \cdot (\alpha_1 y_1 + \alpha_2 y_2), \\ \mathit{ct}_2 &= r_2 \cdot (\alpha_1 y_1 + \alpha_2 y_2), \\ \mathit{ct}_3 &= r_1' \cdot (\alpha_1 y_1' + \alpha_2 y_2'), \\ \mathit{ct}_4 &= r_2' \cdot (\alpha_1 y_1' + \alpha_2 y_2'), \\ \mathit{ct}_0 &= r_1 \cdot r_2 \cdot r_1' \cdot r_2'\cdot m, \end{align*}

where all $r_1, r_2, r_1', r_2'$ are random elements from $\mathbb Z/p\mathbb Z$.

Is this a CPA secure encryption scheme? If so, how can I formally argue about it's security? (possibly reducing to some hard problem?)

  • 2
    $\begingroup$ Besides being over-engineered (without gaining security) it's impossible to build an encryption scheme with just addition and multiplication and without exponentiation in $\mathbb{Z}_p$ - there is no such hardness assumption. That means it's either 1) impossible to decrypt uniquely, 2) actually impossible to encrypt or 3) doesn't hide anything. In this case it is number 2) :How would someone know how to encrypt without being able to construct $\alpha_1 y_1 + \alpha_2 y_2$, where all the values are part of the secret key? $\endgroup$ – tylo Jul 13 '18 at 14:16

No this is not CPA secure. You can compute $\bar{c}=\frac{c_1c_2c_3c_4}{c0}$, and $\bar{c}$ is deterministic with regard to $m$, which is $\frac{(a_1y_1+a_2y_2)^2(a_1y_1’+a_2y_2’)^2}{m}$. The adversary can easily distinguish ciphertexts of $m_0,m_1$ by querying $m_1$ first, then sends $m_0,m_1$ to the oracle, and outputs 1 if $\bar{c}$ from the returned ciphertext is the same as it got before, 0 otherwise.


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.