Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [one-way-function]

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

33 questions
Filter by
Sorted by
Tagged with
119 views

604 views

### Candidates for One-Way Function

Why are the candidates for one-way functions so few? Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!). Why one can not generate ...
277 views

### Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
194 views

### Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

(As for the question in the title: the answer must be no, but then I don't understand what is intended.) The Wikipedia page on one way functions states: Goldreich gives one construction of a ...
540 views

### What's known about basing one-way function on the $P \neq NP$ assumption?

Is there a conditional impossibility result or the question is completely open?
497 views

### One-Way Functions vs. perfectly binding commitments

If OWFs exist, then statistically binding bit commitment is possible.[1] Is it known that if OWFs exist then perfectly binding bit commitment is possible? If no, is there a known black-box ...
80 views

### Understanding the weak-OWF exists -> OWF exists proof

This is a proof that I've gone back to many times over the last few years and while I can read it and easily verify the steps, it seems like it's a proof, where I will always essentially forget the ...
4k views

### Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
111 views

### "Partial" invert a one-way permutation

First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then ...
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 ...
68 views

### one-way functions vs. secret-coin CRHFs

Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
293 views

### One-way functions with respect to various resource bounds

Informally, one-way functions are defined with respect to PTIME algorithms. They are computable in polynomial time but not invertible in average-case polynomial time. The existence of such functions ...
1k views

564 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 ...
284 views

260 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 ...