5
$\begingroup$

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell.

I am using a function having $F_{k}$ = $A_{k}(B_{k}(r,m),r)$, the random number is generated using the Linear feedback shift register, A and B are the functions such that the output of B and a random number r is taken as input to A. I have the following doubts:

  1. Is the above function using A and B a pseudorandom function as it is using LFSR to produce cipher text?

  2. If the above function is pseudorandom then how to prove it mathematically?

  3. Can any function which uses LFSR as the random number generator be considered CPA secure?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What's $k$ and $m$ in above function? I presume $r$ is the random seed. Do you have a reference to the question? $\endgroup$
    – Maarten Bodewes ♦
    Jun 7, 2016 at 9:08
  • $\begingroup$ You will not be able to unconditionally prove that a function is a PRF. You typically can only reduce the security of a higher level construction to the security of its parts. $\endgroup$
    – CodesInChaos
    Jun 7, 2016 at 9:38
  • $\begingroup$ @MaartenBodewes K is the key to the function and m is the input message $\endgroup$
    – Arjun Londhey
    Jun 7, 2016 at 11:13
  • $\begingroup$ $A$ could be a function always ending with a bit set to 1. That doesn't sound like a PRF to me. Using a LFSR doesn't sound like a good random function to me, but I could imagine one that is secure enough. $\endgroup$
    – Maarten Bodewes ♦
    Jun 7, 2016 at 20:39
  • $\begingroup$ For a practice question I would not call an LFSR secure. For more info check this $\endgroup$
    – Maarten Bodewes ♦
    Jun 7, 2016 at 20:46

1 Answer 1

Reset to default
1
$\begingroup$

As it is, there is not enough information, in particular on functions A and B, to answer. However, here are elements that may help:

  1. Is the above function using A and B a pseudorandom function as it is using LFSR to produce cipher text?

As mentioned in the comments, even if the LFSR does outputs completely random numbers (which I doubt), there is no guarantee that F is pseudorandom. As far as we know, A and B could be deterministic functions, always outputting, say 42.

  1. If the above function is pseudorandom then how to prove it mathematically?

You would have to use a proof by reduction, such as one depicted in this video tutoral. That is, you do not prove directly that your function F is pseudo-random. Rather, you would prove, in your case, that IF the LFSR function (or function B maybe) is pseudo-random, THEN F is pseudo-random.

  1. Can any function which uses LFSR as the random number generator be considered CPA secure?

IND-CPA is a property for encryption. There is some relation between encryption and pseudo-randomness, but not as you seem to be saying. Generally, an encryption scheme need to use a good pseudo-random number generator (or a truly random number generator) when used in practice, but that does not take part in the cryptographic proof of IND-CPA. Thus, short answer here would be: no, even if LFSR is somehow truly random. You need other assumptions, and to study a particular, fully defined encryption scheme.

Hope this helps. It may be possible to answer more clearly if the functions $A$ and $B$ were defined.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.