Let $F$ be a pseudorandom function and $G$ be a pseudorandom generator with expansion factor $\ell(n)=n+1$. For each of the following encryption schemes, state whether the scheme has indistinguishable encryption in the presence of an eavesdropper and whether it is CPA-secure The shared key is a uniform $k\in\{0,1\}^n\}$.

To encrypt $m\in\{0,1\}^{n+1}$, choose uniform $r\in\{0,1\}^n$ and output the ciphertext $(r,G(r)\oplus m)$.

Definition: A private-key encryption scheme $\prod=({Gen,Enc,Dec})$ has indistinguishable encryption under a chosen-plaintext attack, or is \textbf{CPA-secure}, if for all probabilistic polynomial-time adversaries $\mathcal{A}$ there is a negligible function negl such that $$Pr\left[{PrivK}_{\mathcal{A},\prod}^{eav}(n)=1\right]\leq \dfrac{1}{2}+{negl}(n),$$ where the probability is taken over the randomness used by $\mathcal{A}$ and the randomness used in the experiment.

I have been having a problem with these type of problems. I guess where I am most confused is when it comes to applying the inequality in the definition to a given problem

share|improve this question
    
Ask your instructor for guidance; this site is not intended to serve as a substitute therefor. – fkraiem yesterday
1  
Please don't get me wrong, but what research have you done and what have you tried? I'm asking because sharing research efforts helps everyone and is as simple as a minor edit to your Q where you tell us what research you did, what you found, and why it didn’t meet your needs. That shows other users you took time trying to help yourself, it saves us from reiterating obvious answers, and (most important) it helps you to get more relevant, on-point answers. At worst it will help you frame “a better question”; at best it might even answer it. – e-sushi 23 hours ago
    
I did ask my instructor and he did not give me any guidance. I come from a pure math background and the CS "symbols"/concepts are what are mainly messing me up – Username Unknown 23 hours ago
    
If you quoted the construction correctly (which is not at all clear. Your question mentions "each of the following" but then specifies about half of an encryption scheme.) then the encryption does not even use a key and is obviously publicly reversible. ¯\_(ツ)_/¯ – Maeher 19 hours ago
    
Sorry. The question has three different scheme. I didn't want to post all three because I truly want to understand what is going on. – Username Unknown 19 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.