Let P be a family of trapdoor permutations with hardcore predicates. Let Samp be a PPT...

 

Transcribed Image Text:

Let P be a family of trapdoor permutations with hardcore predicates. Let Samp be a PPT algorithm which, on input the security parameter A and the description of P, outputs a uniformly random trapdoor permutation p with trapdoor t and hardcore predicate b(.). Let Inv be a PPT algorithm which, on input a trapdoor permutation p, its trapdoor t and a value p(x), outputs the preimager for all x in the domain of p. Consider the following public-key encryption scheme PKE = PKE. (KGen, Enc, Dec) built atop P: (pk, sk) KGen(1) ← (p, t, b) Samp(1^, P) ← - return (pk: = (p, b), sk = t) c← Enc(pk, me {0, 1}) r← {0, 1}^ co← p(r) C₁ + m b(r) return c = = (co, C₁) (a) (5 marks.) Please give/describe the detaills of Dec. (b) (20 marks.) Prove the CPA-security of PKE. (Hint: If an adversary A can break its CPA-security, then another adversary can make black-box use of A to break the security of hardcore predicate.). Let P be a family of trapdoor permutations with hardcore predicates. Let Samp be a PPT algorithm which, on input the security parameter A and the description of P, outputs a uniformly random trapdoor permutation p with trapdoor t and hardcore predicate b(.). Let Inv be a PPT algorithm which, on input a trapdoor permutation p, its trapdoor t and a value p(x), outputs the preimager for all x in the domain of p. Consider the following public-key encryption scheme PKE = PKE. (KGen, Enc, Dec) built atop P: (pk, sk) KGen(1) ← (p, t, b) Samp(1^, P) ← - return (pk: = (p, b), sk = t) c← Enc(pk, me {0, 1}) r← {0, 1}^ co← p(r) C₁ + m b(r) return c = = (co, C₁) (a) (5 marks.) Please give/describe the detaills of Dec. (b) (20 marks.) Prove the CPA-security of PKE. (Hint: If an adversary A can break its CPA-security, then another adversary can make black-box use of A to break the security of hardcore predicate.). Let P be a family of trapdoor permutations with hardcore predicates. Let Samp be a PPT algorithm which, on input the security parameter A and the description of P, outputs a uniformly random trapdoor permutation p with trapdoor t and hardcore predicate b(.). Let Inv be a PPT algorithm which, on input a trapdoor permutation p, its trapdoor t and a value p(x), outputs the preimager for all x in the domain of p. Consider the following public-key encryption scheme PKE = PKE. (KGen, Enc, Dec) built atop P: (pk, sk) KGen(1) ← (p, t, b) Samp(1^, P) ← - return (pk: = (p, b), sk = t) c← Enc(pk, me {0, 1}) r← {0, 1}^ co← p(r) C₁ + m b(r) return c = = (co, C₁) (a) (5 marks.) Please give/describe the detaills of Dec. (b) (20 marks.) Prove the CPA-security of PKE. (Hint: If an adversary A can break its CPA-security, then another adversary can make black-box use of A to break the security of hardcore predicate.).

Answer rating: 100% (QA)

Answer a The decryption algorithm Dec for the given PKE scheme is as follows Decsk c Invp t c1 c2 where sk t is the trapdoor of the permutation p pk c ... View the full answer