Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Fix a symmetric-key encryption scheme SE (K, E, D). We consider alternative notions of security to IND-CPA below. First consider the MROR (message real-or-
Fix a symmetric-key encryption scheme SE (K, E, D). We consider alternative notions of security to IND-CPA below. First consider the MROR (message real-or- random) notion via game MRoR-1 below left and MROR-0 below right. proe INITIALIZE K+K proc RoR(m) Return E (m) Define the MROR-advantage of A against SE as Adve (A) = Pr [MROR-1 outputs 1] - Pr [MROR-0 outputs 1]. proc INITIALIZE KIK proc INITIALIZE K-sk Now consider the CROR (ciphertext real-or-random) notion via game CROR-1 below left and CROR-0 below right. proe RoR(m) Return Ex(m) proc ROR(m) m's {0, 1] Return Ex(m) Define the CROR-advantage of A against. SE as proc INITIALIZE K-K proc ROR(m) ex Ek(m) {0, 134 Return Adve (4) Pr [CROR-15 outputs 1] Pr [CROR-05 outputs 1]. (Part A.). Show that IND-CPA implies MROR. Namely, show that for every MROR-adversary A there is an IND-CPA adversary B such that indepa SE Furthermore, the resources usage of B is about that of A. Adv (A) Adv (B). uror (Part B.). Show that MROR implies IND-CPA. Namely, show that for every IND-CPA adversary A there is an MROR-adversary B such that Advse ind-cpa Furthermore, the resources usage of B is about that of A. (A) 2. Adv (B). mror SE Show IND-CPA does not imply CROR. To show this, assume there is a scheme SE (K, E, D) that is IND-CPA (as otherwise the claim is vacuous). Show how to modify SE into SE' = (K',E, D) such that: (1) SE' is IND-CPA but (2) SE' is not CROR. Namely, first provide a description of the algorithms of SE'. Then show that for every IND-CPA adversary A there is an IND-CPCA adversary B such that Adv SE' (A) Adv (B). SE Furthermore, the resources usage of B is about that of A. Finally, show that there is a resource- efficient CROR-adversary A such that Adv (A) 2 1 1
Step by Step Solution
★★★★★
3.33 Rating (150 Votes )
There are 3 Steps involved in it
Step: 1
Part A Showing that INDCPA implies MROR To prove this we need to show that for every MRORadversary A there exists an INDCPA adversary B such that AdvA AdvB and the resource usage of B is about that of ...Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started