One-way functions and P=NP
$begingroup$
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 '18 at 14:33
AlexisAlexis
1284
$endgroup$
add a comment |
$begingroup$
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 '18 at 14:33
AlexisAlexis
1284
$endgroup$
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56
add a comment |
$begingroup$
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 '18 at 14:33
AlexisAlexis
1284
$endgroup$
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 '18 at 14:33
AlexisAlexis
1284
asked Dec 17 '18 at 14:33
AlexisAlexis
1284
asked Dec 17 '18 at 14:33
AlexisAlexis
1284
asked Dec 17 '18 at 14:33
AlexisAlexis
1284
asked Dec 17 '18 at 14:33
AlexisAlexis
1284
1284
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56
add a comment |
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
$endgroup$
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '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
});
}
});
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
$begingroup$
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 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
$endgroup$
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
add a comment |
$begingroup$
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 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
$endgroup$
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
add a comment |
$begingroup$
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 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
$endgroup$
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 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
edited Dec 17 '18 at 14:51
answered Dec 17 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
answered Dec 17 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
answered Dec 17 '18 at 14:47
Geoffroy CouteauGeoffroy Couteau
8,32011532
8,32011532
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
add a comment |
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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$.
$endgroup$
– Alexis
Dec 17 '18 at 15:04
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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/…).
$endgroup$
– Geoffroy Couteau
Dec 17 '18 at 15:29
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
$begingroup$
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.
$endgroup$
– tylo
Dec 18 '18 at 11:56
add a comment |
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.
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
$begingroup$
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.
$endgroup$
– Joshua
Dec 17 '18 at 19:56