# Questions tagged [one-way-function]

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

27 questions
Filter by
Sorted by
Tagged with
1 vote
59 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 '...
• 129
367 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 ...
• 7,113
525 views

• 101
300 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 ...
• 445
277 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 $... • 2,198 9 votes 0 answers 547 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 ... • 2,198 9 votes 2 answers 848 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 ... • 16.4k 8 votes 0 answers 636 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 ... 7 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$... • 16.4k 5 votes 2 answers 250 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 984 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)] < ...
• 163
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 ...