0
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hint: How is IND-CCA related to NM-CCA? Can you selectively modify ciphertexts? $\endgroup$ Commented Apr 16, 2019 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$ Commented Apr 16, 2019 at 15:16
  • $\begingroup$ yes, can selectively modify ciphertexts $\endgroup$ Commented Apr 16, 2019 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$ Commented Apr 17, 2019 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$ Commented Apr 18, 2019 at 17:18

1 Answer 1

Reset to default
1
$\begingroup$

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
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.