# Questions tagged [one-way-function]

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

28 questions
Filter by
Sorted by
Tagged with
41 views

### Examples of inverse of trapdoor functions non-learnable with black-box query access?

The (informal) definition of trapdoor function is a one-way function with a trapdoor $t$ such that given $f$, it is easy to compute $f(x)$ for any $x$, but hard to compute $f^{-1}(y)$ efficiently ...
52 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 '...
317 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 ...
508 views

267 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 ...
271 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 499 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 695 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 629 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 972 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 244 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 924 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 ...