One-way functions and P=NP
This site contains various discussions of one-way functions and their relation to P versus NP.
Some of these discussions use a language
$L={(x',y) ~mid~ x'le x text{ and } f(x)=y }$, where $f:Sigma^*toSigma^*$ is the one-way function and $x'le x$ is the prefix relation.
Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)in L$.
I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?
Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?
one-way-function
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis 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 |
This site contains various discussions of one-way functions and their relation to P versus NP.
Some of these discussions use a language
$L={(x',y) ~mid~ x'le x text{ and } f(x)=y }$, where $f:Sigma^*toSigma^*$ is the one-way function and $x'le x$ is the prefix relation.
Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)in L$.
I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?
Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?
one-way-function
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56
add a comment |
This site contains various discussions of one-way functions and their relation to P versus NP.
Some of these discussions use a language
$L={(x',y) ~mid~ x'le x text{ and } f(x)=y }$, where $f:Sigma^*toSigma^*$ is the one-way function and $x'le x$ is the prefix relation.
Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)in L$.
I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?
Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?
one-way-function
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This site contains various discussions of one-way functions and their relation to P versus NP.
Some of these discussions use a language
$L={(x',y) ~mid~ x'le x text{ and } f(x)=y }$, where $f:Sigma^*toSigma^*$ is the one-way function and $x'le x$ is the prefix relation.
Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)in L$.
I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?
Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?
one-way-function
one-way-function
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 17 at 14:33
Alexis
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 17 at 14:33
Alexis
1283
asked Dec 17 at 14:33
Alexis
1283
1283
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alexis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56
add a comment |
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56
add a comment |
1 Answer
1
active
oldest
votes
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P neq NP$. Intuitively, to fix this, modify your language as follows:
$L={(1^n, x',y) ~mid~ exists x, |x| = n, x'le x, text{ and } f(x)=y }$,
where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'le x$ means $x'$ is a prefix of $x$).
Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Alexis 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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f65937%2fone-way-functions-and-p-np%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P neq NP$. Intuitively, to fix this, modify your language as follows:
$L={(1^n, x',y) ~mid~ exists x, |x| = n, x'le x, text{ and } f(x)=y }$,
where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'le x$ means $x'$ is a prefix of $x$).
Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
add a comment |
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P neq NP$. Intuitively, to fix this, modify your language as follows:
$L={(1^n, x',y) ~mid~ exists x, |x| = n, x'le x, text{ and } f(x)=y }$,
where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'le x$ means $x'$ is a prefix of $x$).
Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
add a comment |
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P neq NP$. Intuitively, to fix this, modify your language as follows:
$L={(1^n, x',y) ~mid~ exists x, |x| = n, x'le x, text{ and } f(x)=y }$,
where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'le x$ means $x'$ is a prefix of $x$).
Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P neq NP$. Intuitively, to fix this, modify your language as follows:
$L={(1^n, x',y) ~mid~ exists x, |x| = n, x'le x, text{ and } f(x)=y }$,
where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'le x$ means $x'$ is a prefix of $x$).
Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
edited Dec 17 at 14:51
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
answered Dec 17 at 14:47
Geoffroy Couteau
8,05511532
8,05511532
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
add a comment |
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Thanks a lot for your kind explanations.
– Alexis
Dec 17 at 14:51
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$.
– Alexis
Dec 17 at 15:04
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…).
– Geoffroy Couteau
Dec 17 at 15:29
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly.
– tylo
Dec 18 at 11:56
add a comment |
Alexis is a new contributor. Be nice, and check out our Code of Conduct.
Alexis is a new contributor. Be nice, and check out our Code of Conduct.
Alexis is a new contributor. Be nice, and check out our Code of Conduct.
Alexis is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f65937%2fone-way-functions-and-p-np%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536.
– Joshua
Dec 17 at 19:56