<p>$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More generally, a standard one-way function can be viewed as an average-case-hard (search) problem in $\mathbf{NP}$ relative to $\mathbf{P}$. Can this notion be extended to two arbitrary complexity classes?</p>

CC BY-SA 3.0
2011-09-22T19:22:59.507Z
Thanks. So the difference is if instance/solution pairs can be generated easily. Now if we always require this on top of average-case hardness, do we arrive at a reasonable generalisation of OWFs?
Pooya Farshim
CC BY-SA 2.5
2010-12-05T01:35:24.497Z
While inverting a one-way function is hard-on-average, it does not mean that every hard-on-average problem represents a one-way function. Am I right?
Sadeq Dousti
CC BY-SA 2.5
2010-12-05T01:39:53.917Z
**PS:** I'm interested in your motivation. Could you please [tell us why you care](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306)?
Sadeq Dousti
CC BY-SA 2.5
2010-12-05T02:04:19.203Z
You may be interested in the following paper of Pavan Aduri et al: http://www.cs.iastate.edu/~pavan/papers/acwcnc.pdf
Aaron Sterling
CC BY-SA 2.5
2010-12-22T01:59:08.687Z
@Aaron: Thanks for the reference. It seems to be dealing with a lot of relevant topics.
Pooya Farshim
CC BY-SA 2.5
2010-12-22T09:15:48.673Z
@Pooya: From CLRS: "We define an **abstract problem** $Q$ to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions." So, a problem is not a function, and a hard-on-average problem is not necessarily a one-way function.
Sadeq Dousti
CC BY-SA 2.5
2010-12-23T13:20:40.683Z
@Pooya: In addition, it might be the case that hard-on-average problems exist, but one-way functions do not. See the definition of Pessiland in http://cstheory.stackexchange.com/q/1026/873.
Sadeq Dousti
CC BY-SA 2.5
2011-01-05T02:18:48.203Z
As Sadeq said, it is not justified to call one-way functions the “average-case counterpart” of NP-complete problems.  Inverting a fixed one-way function is an example of hard-on-average problems (by definition), but there are other problems which are hard on average.  Because of this, I do not know what you are looking for.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes><cr.crypto-security><one-way-function><average-case-complexity>
A generalisation of one-wayness
Pooya Farshim
# A generalisation of one-wayness

(Asked by: username_0 on 2010-12-05)

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More generally, a standard one-way function can be viewed as an average-case-hard (search) problem in $\mathbf{NP}$ relative to $\mathbf{P}$. Can this notion be extended to two arbitrary complexity classes?

**Tags:** cc.complexity-theory, complexity-classes, cr.crypto-security, one-way-function, average-case-complexity
> **Comments:**
> **username_1**: While inverting a one-way function is hard-on-average, it does not mean that every hard-on-average problem represents a one-way function. Am I right?  
> **username_1**: **PS:** I'm interested in your motivation. Could you please [tell us why you care](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306)?  
> **username_2**: You may be interested in the following paper of Pavan Aduri et al: http://www.cs.iastate.edu/~pavan/papers/acwcnc.pdf  
> **username_0**: @Aaron: Thanks for the reference. It seems to be dealing with a lot of relevant topics.  
> **username_1**: @Pooya: From CLRS: "We define an **abstract problem** $Q$ to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions." So, a problem is not a function, and a hard-on-average problem is not necessarily a one-way function.  
> **username_1**: @Pooya: In addition, it might be the case that hard-on-average problems exist, but one-way functions do not. See the definition of Pessiland in http://cstheory.stackexchange.com/q/1026/873.  
> **username_3**: As Sadeq said, it is not justified to call one-way functions the “average-case counterpart” of NP-complete problems.  Inverting a fixed one-way function is an example of hard-on-average problems (by definition), but there are other problems which are hard on average.  Because of this, I do not know what you are looking for.  
> **username_0**: Thanks. So the difference is if instance/solution pairs can be generated easily. Now if we always require this on top of average-case hardness, do we arrive at a reasonable generalisation of OWFs?  

---

## 0 answers

