Mixing
Strong One-Way Function
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation? 
security-definition
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
add a comment |Â
up vote
3
down vote
favorite
In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation?
security-definition
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation?
security-definition
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation?
security-definition
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
edited Sep 3 at 20:32
Maarten Bodewes
47.7k566175
47.7k566175
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
asked Sep 1 at 11:51
AmirHosein Adavoudi
398
398
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57
add a comment |Â
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
Suppose we live in a work where $mathsfPneqmathsfBPP$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $mathsfP = mathsfBPP$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $mathsfDTIME(2^O(n))$ which have circuit complexity $2^Omega(n)$, then $mathsfP = mathsfBPP$.
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
Suppose we live in a work where $mathsfPneqmathsfBPP$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $mathsfP = mathsfBPP$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $mathsfDTIME(2^O(n))$ which have circuit complexity $2^Omega(n)$, then $mathsfP = mathsfBPP$.
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
add a comment |Â
up vote
4
down vote
accepted
Suppose we live in a work where $mathsfPneqmathsfBPP$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $mathsfP = mathsfBPP$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $mathsfDTIME(2^O(n))$ which have circuit complexity $2^Omega(n)$, then $mathsfP = mathsfBPP$.
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
Suppose we live in a work where $mathsfPneqmathsfBPP$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $mathsfP = mathsfBPP$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $mathsfDTIME(2^O(n))$ which have circuit complexity $2^Omega(n)$, then $mathsfP = mathsfBPP$.
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
Suppose we live in a work where $mathsfPneqmathsfBPP$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $mathsfP = mathsfBPP$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $mathsfDTIME(2^O(n))$ which have circuit complexity $2^Omega(n)$, then $mathsfP = mathsfBPP$.
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
answered Sep 1 at 13:59
Geoffroy Couteau
7,31711431
7,31711431
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
add a comment |Â
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear.
– AmirHosein Adavoudi
Sep 1 at 14:14
add a comment |Â
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%2f61956%2fstrong-one-way-function%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
Possible duplicate of What does it mean for an adversary to run in PPT?
– fkraiem
Sep 1 at 11:57