Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [one-way-function]

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

14
votes
1answer
260 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 ...
18
votes
2answers
479 views

Is it possible to encrypt a CNF?

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$. $\Psi(\mathcal ...
3
votes
0answers
174 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 ...
4
votes
1answer
167 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 ...
8
votes
2answers
408 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?
5
votes
0answers
71 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 ...
7
votes
3answers
486 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 ...
0
votes
0answers
108 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 ...
3
votes
0answers
63 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 ...
13
votes
1answer
212 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 ...
7
votes
1answer
239 views

Consequences of OWFs for Complexity

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
-3
votes
1answer
304 views

One Way Boolean Function [closed]

If one way functions exist, what would the truth table of a one way boolean function look like?
10
votes
2answers
402 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 ...
25
votes
4answers
3k 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-...
6
votes
1answer
332 views

How is it proven that Key Exchange implies OWFs?

Page 38 says that Key Exchange implies the existence of one-way functions. When I try to work out the proof myself, I get that in the hypothetical case where there is Key Exchange but no one-way ...
10
votes
1answer
331 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. Assuming the problem of FACTORING:[Given $N ...
4
votes
0answers
261 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 ...
8
votes
1answer
261 views

One-way functions with polynomial inverting complexity

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
0answers
450 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
2answers
663 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 ...
8
votes
0answers
626 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 ...
6
votes
1answer
864 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}$-...
5
votes
2answers
236 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
5answers
872 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)] < ...
10
votes
1answer
437 views

Finite One-Way Permutation with Infinite Domain

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 ...
4
votes
2answers
314 views

What are the different notions of one-way functions?

For instance, A function that is computable but not invertable in log space, Is it one-way function? What are the known definitions of one-way functions? (especially the ones that do not invoke ...