# Questions tagged [one-way-function]

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

27 questions
Filter by
Sorted by
Tagged with
55 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 '...
342 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 ...
516 views

280 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 ...
273 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 $... 0answers 527 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 ... 2answers 727 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 ... 0answers 633 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 ... 1answer 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$... 2answers 248 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 ... 5answers 954 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 ...