Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [one-way-function]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
58 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 '...
user avatar
  • 129
14 votes
1 answer
358 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 ...
user avatar
  • 7,073
18 votes
2 answers
521 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 ...
user avatar
  • 13.5k
3 votes
0 answers
236 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 ...
user avatar
  • 12.5k
3 votes
1 answer
178 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 ...
user avatar
  • 269
8 votes
2 answers
507 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?
user avatar
5 votes
0 answers
79 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 ...
user avatar
  • 151
8 votes
3 answers
575 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
3 votes
0 answers
67 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 ...
user avatar
13 votes
1 answer
252 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 ...
user avatar
10 votes
2 answers
347 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 ...
user avatar
  • 2,743
-3 votes
1 answer
361 views

One Way Boolean Function [closed]

If one way functions exist, what would the truth table of a one way boolean function look like?
user avatar
10 votes
2 answers
462 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 ...
user avatar
25 votes
4 answers
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-...
user avatar
  • 3,993
6 votes
1 answer
396 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 ...
user avatar
10 votes
1 answer
369 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 ...
user avatar
4 votes
0 answers
294 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 ...
user avatar
  • 445
8 votes
1 answer
277 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 $...
user avatar
  • 2,198
9 votes
0 answers
537 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 ...
user avatar
  • 2,198
9 votes
2 answers
810 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 ...
user avatar
  • 16.3k
8 votes
0 answers
634 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 ...
user avatar
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$...
user avatar
  • 16.3k
5 votes
2 answers
249 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 ...
user avatar
16 votes
5 answers
979 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)] < ...
user avatar
10 votes
1 answer
486 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 ...
user avatar
  • 16.3k
4 votes
2 answers
320 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 ...
user avatar