Prove security against passive attacks by reduction

Orla Mccoy

10/27/23, 7:35 AM

I have two private-key encryption ($Π$ and $Θ$) and their concatenation $Π\#Θ$. For example:
$$ Enc_{Π\#Θ}( \ ⟨k_Π, k_Θ⟩, \ ⟨m_Π, m_Θ⟩ \ ) = ⟨ \ Enc_Π(k_Π, m_Π),\ Enc_Θ(k_Θ, m_Θ) \ ⟩; $$ (Same for Gen and Dec)

I need to prove that if $Π\#Θ$ is secure against passive adversaries, then both $Π$ and $Θ$ are.

Actually I have proceeded by reduction, so I can prove that:
$$ Π \ is \ not \ secure \ || \ Θ \ is \ not \ secure \ \Rightarrow \ Π\#Θ \ is \ not \ secure $$

So I think I can suppose that exist an adversary A that breaks $Π$ (or $Θ$) such that:
$$ Pr(PrivK_{eat}^{Π,A}(n) = 1) = \frac{1}{2} + ε(n) $$
where $ε(n)$ is not negligible.

How can I continue the prove? What should I do now?

0 + 3

negligible

reduction

kelalaka

10/27/23, 9:28 AM

what does it mean to be secure for the concatenation?

Orla Mccoy

10/27/23, 9:51 AM

@kelalaka if we build a security scheme that is the concatenation of other two, we have to prove that if one of them two is not secure against passive attacks, then the concatenation of them is not secure against passive attacks

kelalaka

10/27/23, 10:38 AM

I usually don't upvote HW questions, though you are fast on editing, nice. You can use any $A$ to distinguish concatenation directly.

Elon Musk

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

EN: Prove security against passive attacks by reduction

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.