# Questions tagged [one-way-function]

Questions regarding easy-to-compute, but hard-to-invert functions.

31 questions
Filter by
Sorted by
Tagged with
38 views

### Impossibility of uniform generation in random world

I specify that this is a cross-post from crypto.stackexchange I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich when I got stuck on a sentence. First ...
100 views

### Assume P != NP, does it imply that one-way functions exist?

I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
152 views

### What is the simplest one-way function (in terms of boolean circuit complexity)?

What is the simplest known one-way function? By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity). (I'm trying to find ...
1 vote
72 views

### One way analogues of Logspace

When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$. Likewise we say a function is logspace one-way if the function is ...
1 vote
69 views

### Describe Levins 'Tile Expansion' one way functon in layman terms

I'd like some explanation on the details of the 'Complete OWF' presented on this paper in 'layman terms'. See page 13 of https://arxiv.org/pdf/cs/0012023.pdf I'd prefer that the answerer had '...
383 views

### Function that is guaranteed to be one-way if one-way functions exist?

There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time. Essentially, one lists all polynomial time machines and multi-tasks over them. Is there an ...
534 views

319 views

### A approximation version of the Goldreich-Levin Theorem

A little introduction The Goldreich-Levin Theorem says that let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core ...
283 views

Is there a trap-door-like function whose encoding complexity is polynomial time $n^{k_{1}}$ and inverting complexity(without secret key) is also a polynomial function in input length $n^{k_{2}}$ with $... 9 votes 0 answers 562 views ### VNP = VP versus complexity classes in Arithmetic Geometry What is the implication of$VNP = VP$to cryptography schemes such as Elliptic curve/Abelian Variety/Arithmetic Geometry based cryptography? Are there any papers or books that talk about sophisticated ... 9 votes 2 answers 972 views ### One-Way Permutations without Trapdoor In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor? More info: A one-way permutation is a permutation$\pi$which is easy to compute, but hard to invert (see the ... 8 votes 0 answers 637 views ### A generalisation of one-wayness$\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 ... 8 votes 1 answer 1k views ### NP-Complete Hard-on-Average Problems This question considers a special class of problems in (NP,P-samplable). The question is: Do there exists a problem$(L,\mu) \in \mbox{(NP,P-samplable)}$such that:$L$is$\rm{NP}$-complete, and$L$... 5 votes 2 answers 257 views ### Hardness of approximation assuming the existence of one-way functions This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP . Multiplication of two prime numbers of equal size is strong candidate for one-way ... 16 votes 5 answers 1k views ### Do "One Way Functions" have any applications outside crypto ? A function$f \colon \{0, 1\}^* \to \{0, 1\}^*$is one-way if$f$can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm$A$,$\Pr[f(A(f(x))) = f(x)] < ...
Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...