29 reputation
2
bio website
location
age
visits member for 1 year, 9 months
seen Nov 27 '13 at 23:23

Feb
22
comment Computational indistinguishability and example of non polynomial algorithm
(cont.) You mentioned exhaustive search, which is indeed non polynomial. But what does it mean to do exhaustive search when trying to distinguish two probability ensembles? To give a concrete example, what would it mean to do an exhaustive search in order to try to distinguish the output of a PRNG from the uniform distribution? Does this clarify what I am trying to ask?
Feb
22
comment Computational indistinguishability and example of non polynomial algorithm
I'll try to clarify my question. I am familiar with run time analysis of algorithms, and big-O notation, my question is not about that; it's about algorithms (or statistical tests if you will) that are capable of distinguishing two different (but computationally indistinguishable) probability ensembles. From all I've read, being indistinguishable means that there is no non-uniform probabilistic polynomial time algorithm could tell one ensemble from the other. However, I could not find an example of an algorithm that could distinguish the two ensembles, and that's what I asked for.
Feb
22
comment Computational indistinguishability and example of non polynomial algorithm
I understand the examples you give, but how would you apply them to a (sample from a) probability distribution? What would exhaustive search be like in this case? I mean, there is no "key" for which to check for correctness!
Nov
9
comment Randomized algorithms and the one time pad
@bob, thank you for your answer, it has been insightful. However, one doubt remains: what's the problem of "the key (one-time pad) is to be changed for each plaintext"? Isn't this the way one time pads are supposed to work? I think you I are referring to the fact that "my" one time pad does not include (explicitly) a key generation algorithm. Say I added one; borrowing from another answer, the key generation is done throwing dice. Would it then be semantically secure?
Nov
8
comment Randomized algorithms and the one time pad
@bob probabilistic encryption refers to an algorithm receiving the same PT and key, and output varying output, right?