Let $m$ and $k$ be positive integers ($m$ bit plain text) ; let $Q$ be a family of trapdoor one-way permutations such that $f : \{0,1\}^k \rightarrow \{0,1\}^k$ for all $f$ in $Q$; and let $G : \{0,1\}^k \rightarrow \{0,1\}^m$ be a random oracle. Let $P = \{0,1\}^m$ and $C = \{0,1\}^k \times \{0,1\}^m$, and define

$K = \{(f, f^{(-1)},G) : f$ in $Q\}$

For $K = (f,f^{(-1)},G)$, let $r$ in $\{0,1\}^k$ be chosen randomly, and define

encryption of $x = (y_1,y_2) = (f(r),G(r) \oplus x)$, where $y_1$ in $\{0,1\}^k$, $y_2$ in $\{0,1\}^m$

decryption of $(y_1,y_2) = G(f^{(-1)}(y_1)) \oplus y_2$

The functions $f$ and $G$ are public key; the function $f^{(-1)}$ is the private key

  • 1
    $\begingroup$ Hint: How is IND-CCA related to NM-CCA? Can you selectively modify ciphertexts? $\endgroup$ – Squeamish Ossifrage Apr 16 '19 at 14:39
  • $\begingroup$ @SqueamishOssifrage I would like to show that cryptosystem is not semantically secure against a chosen ciphertext attack. As usually given x1,x2, a ciphertext (y1,y2) that is an encryption of xi (i=1 or i=2). Also we have access to a decryption oracle DECRYPT for this cryptosystem, which decrypts with any input except for given ciphertext, and will output the corresponding plaintext $\endgroup$ – Askhat Apr 16 '19 at 15:16
  • $\begingroup$ yes, can selectively modify ciphertexts $\endgroup$ – Askhat Apr 16 '19 at 15:20
  • $\begingroup$ Just checking the operations. Seems like encryption should be different.. $G(r) \oplus x$ isn't correct because the the output of $G$ and $x$ are in different spaces $\endgroup$ – Marc Ilunga Apr 17 '19 at 19:36
  • $\begingroup$ @MarcIlunga The plaintext $x$ is an $m$-bit string, and the range of $G$ is $m$-bit strings—what's the issue? $\endgroup$ – Squeamish Ossifrage Apr 18 '19 at 17:18

Given two plaintexts x1; x2 and a ciphertext (y1; y2) where y1 = f(r) and y2 = G(r) xor xi for a random i(1,2) a CCA can query the decryption of (y1; ~y) where ~y != y2. Upon receiving the answer x, the attacker can recover G(r) = ~y xor x. Then the attacker can compute xi = G(r) xor y2 and find i.

| improve this answer | |

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.