Pseudorandom Generators against CFL/n

Details Pseudorandom Generators against CFL/n Pseudorandom Generators against CFL/n

2009-02-16

arxiv.org/abs/0902.2774v1

Computer Science

Formal Languages and Automata Theory

13 pages, 10 pt, 1 fugure, letter size

Scientific paper

Pseudorandomness has played a central role in modern cryptography, finding theoretical and practical applications to various fields of computer science. A function that generates such pseudorandom strings from shorter but truly random seeds is known as a pseudorandom generator. Our generators are designed to fool languages, rather than probabilistic algorithms. In particular, our generators take context-free languages with advice as their adversaries. We present an explicit example of such a pseudorandom generator, which can be also computed by a single-tape deterministic Turing machine running in time O(n^2). In contrast, we show that there is no almost 1-1 pseudorandom generator against even context-free languages (without advice) if we demand it should be computed by a nondeterministic pushdown automaton equipped with a write-only output tape. Our proofs are all elementary, requiring no complicated proof techniques as in a polynomial-time setting, and utilize a specific feature of nondeterministic pushdown automata, which is interesting on its own light.

Affiliated with

Also associated with

No associations

Rating

Pseudorandom Generators against CFL/n does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pseudorandom Generators against CFL/n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudorandom Generators against CFL/n will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-309859