Suppose, I have PRNG with seed key length of $|K_s|$ and output sequence length of $2^{|K_s|}$, so the complexity of the PRNG is of the order of $2^{|K_s|}$. Now, if there is any measurement error in the output of the PRNG, how this measurement error works in the overall complexity of the PRNG?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is a "measurement error"? In general you cannot study the security of a PRNG without knowing the inner details (because it will be impossible to create a function that describes the relationship between errors in the randomness for anything other than trivial ones). So without the algorithm the answer is very likely: it depends on the PRNG. $\endgroup$– Maarten Bodewes ♦Commented Aug 25, 2016 at 16:32
-
$\begingroup$ Actually,this is a generic question: if I want to measure the output of a typical PRNG for example LFSR and I introduce error while measuring the output of that PRNG for crypt-analysis,so how this error contributes to the overall complexity of the PRNG? $\endgroup$– Mitun TalukderCommented Aug 25, 2016 at 16:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Unless the measurement error is huge (e.g. you read every bit correctly with probability $p = 0.5$), it doesn't add significantly to the work required to find the key.
To give a concrete example, let us consider a measurement error where we read each bit correctly with probability $p = 0.75$ (and for simplicity, let us assume that the errors are independent of each other, and whether the correct bit was a 0 or a 1).
Then, what the attacker can do is cycle through every possible key, and generate the first 1000 bits of the PRNG with that key, and check if at least 600 of those bits agree with the first 1000 bits of the noisy sample he was given. With extremely high probability, the correct key will generate a sample with that many bits set, and no incorrect key will.
This procedure still takes $O(2^{|K_s|})$ time, and so all you've done is increase the time required by a constant factor.
-
$\begingroup$ I guess you assume probability $p$ of being flipped? Since 0.5 probability of being randomized would be fine. $\endgroup$– otusCommented Aug 25, 2016 at 18:25
-
$\begingroup$ @otus: actually, the same argument for any type of measurement error where there's an efficient procedure for distinguishing the actual measurement from the measured values (and if there isn't, well, that goes rather beyond what I would typically call measurement error). I uses bitflip errors (with $p=0.75$) as a simple example; the same argument could be used for (say) an occasional dropped bit... $\endgroup$– ponchoCommented Aug 25, 2016 at 18:32
-
$\begingroup$ @poncho: In case of bit flip error example as you mentioned, can we describe the overall complexity as: O($2^{|K_s|}$) + O(measurement error($P_e$))? $\endgroup$ Commented Aug 25, 2016 at 19:41
-
$\begingroup$ @MitunTalukder: you might make the case that it's in the form $O(d(P_e)2^{|K_s|})$ (where $d(P_e)$ is the time it would take to distinguish a valid measurement with the given measurement error; the form of $d(P_e)$ would depend on the actual measurement error. I ignored it because I considered the case that the distinguishing time was constant independent of the key size, and so it ended up being rolled into the $O$ constant... $\endgroup$– ponchoCommented Aug 25, 2016 at 19:44