Mixing
Is a one-way function pseudorandom?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
For one-way function $f$ I understand that $g(x)=0^nmathbin|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.
However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?
pseudo-random-generator one-way-function
edited 2 hours ago
fgrieu
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
2
down vote
favorite
For one-way function $f$ I understand that $g(x)=0^nmathbin|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.
However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?
pseudo-random-generator one-way-function
edited 2 hours ago
fgrieu
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
For one-way function $f$ I understand that $g(x)=0^nmathbin|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.
However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?
pseudo-random-generator one-way-function
edited 2 hours ago
fgrieu
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
For one-way function $f$ I understand that $g(x)=0^nmathbin|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.
However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?
pseudo-random-generator one-way-function
pseudo-random-generator one-way-function
edited 2 hours ago
fgrieu
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
fgrieu
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
fgrieu
72.7k6149310
edited 2 hours ago
fgrieu
72.7k6149310
edited 2 hours ago
fgrieu
72.7k6149310
72.7k6149310
asked 3 hours ago
eggroem
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
eggroem
111
asked 3 hours ago
eggroem
111
111
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
eggroem is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):
 If $f$ is a $n$-bit one-way function, then $g(x)=0^nmathbin|f(x)$ is a $2n$-bit one-way function.
We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.
Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $mathttfalse$ if all the left $leftlfloor m/2rightrfloor$ bits of the result are zero; otherwise output $mathtttrue$.
That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $mathttfalse$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $mathttfalse$ with probability $2^-n$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^-n$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.
We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.
Note, per comment: this answer, and the question, assimilate a pseudorandom function and a pseudorandom generator, by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.
answered 2 hours ago
fgrieu
72.7k6149310
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):
 If $f$ is a $n$-bit one-way function, then $g(x)=0^nmathbin|f(x)$ is a $2n$-bit one-way function.
We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.
Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $mathttfalse$ if all the left $leftlfloor m/2rightrfloor$ bits of the result are zero; otherwise output $mathtttrue$.
That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $mathttfalse$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $mathttfalse$ with probability $2^-n$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^-n$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.
We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.
Note, per comment: this answer, and the question, assimilate a pseudorandom function and a pseudorandom generator, by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.
answered 2 hours ago
fgrieu
72.7k6149310
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
add a comment |Â
up vote
2
down vote
Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):
 If $f$ is a $n$-bit one-way function, then $g(x)=0^nmathbin|f(x)$ is a $2n$-bit one-way function.
We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.
Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $mathttfalse$ if all the left $leftlfloor m/2rightrfloor$ bits of the result are zero; otherwise output $mathtttrue$.
That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $mathttfalse$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $mathttfalse$ with probability $2^-n$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^-n$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.
We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.
Note, per comment: this answer, and the question, assimilate a pseudorandom function and a pseudorandom generator, by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.
answered 2 hours ago
fgrieu
72.7k6149310
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):
 If $f$ is a $n$-bit one-way function, then $g(x)=0^nmathbin|f(x)$ is a $2n$-bit one-way function.
We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.
Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $mathttfalse$ if all the left $leftlfloor m/2rightrfloor$ bits of the result are zero; otherwise output $mathtttrue$.
That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $mathttfalse$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $mathttfalse$ with probability $2^-n$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^-n$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.
We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.
Note, per comment: this answer, and the question, assimilate a pseudorandom function and a pseudorandom generator, by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.
answered 2 hours ago
fgrieu
72.7k6149310
Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):
 If $f$ is a $n$-bit one-way function, then $g(x)=0^nmathbin|f(x)$ is a $2n$-bit one-way function.
We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.
Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $mathttfalse$ if all the left $leftlfloor m/2rightrfloor$ bits of the result are zero; otherwise output $mathtttrue$.
That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $mathttfalse$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $mathttfalse$ with probability $2^-n$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^-n$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.
We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.
Note, per comment: this answer, and the question, assimilate a pseudorandom function and a pseudorandom generator, by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.
answered 2 hours ago
fgrieu
72.7k6149310
edited 16 mins ago
answered 2 hours ago
fgrieu
72.7k6149310
answered 2 hours ago
fgrieu
72.7k6149310
answered 2 hours ago
fgrieu
72.7k6149310
72.7k6149310
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
add a comment |Â
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
The question is about pseudorandom generators, not pseudorandom functions.
– fkraiem
2 hours ago
add a comment |Â
eggroem is a new contributor. Be nice, and check out our Code of Conduct.
eggroem is a new contributor. Be nice, and check out our Code of Conduct.
eggroem is a new contributor. Be nice, and check out our Code of Conduct.
eggroem is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62374%2fis-a-one-way-function-pseudorandom%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password