Questions tagged [one-way-function]
Questions regarding easy-to-compute, but hard-to-invert functions.
34 questions
-1
votes
1
answer
52
views
is the set of all numbers that sum up a subset sum problem a one way function?
I have difficulties checking whether $f^{-1}(x)$ is a one way function. $x \leq 2^n$ is the sum that we want the set of numbers $a_1,...,a_m$ to be. $m \leq 2^n$.
There are $4^n$ different ways to sum ...
6
votes
0
answers
138
views
Is there a known correlation between the Strong Exponential Time Hypothesis (SETH) and the existence of one-way functions?
It is known that (one-way functions exist $\implies$ $\textbf{P}\neq \textbf{NP}$) and as far as my knowledge goes, the converse is not known to be true. Are there any known results correlating $\...
- 379
5
votes
0
answers
101
views
Does there exist a cryptographic associative hash function?
Does there exist a function $f(x,y)$ with these properties:
Computing $f(x,y)$ is in P.
$f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$.
$f$ is one-way (assuming P $\neq$ NP): Given the value ...
- 251
2
votes
0
answers
36
views
Impossibility of uniform generation in random world
I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers.
I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich ...
- 21
0
votes
0
answers
120
views
Assume `P != NP`, does it imply that one-way functions exist?
I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
- 212
0
votes
1
answer
160
views
What is the simplest one-way function (in terms of boolean circuit complexity)?
What is the simplest known one-way function?
By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity).
(I'm trying to find ...
1
vote
0
answers
78
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 13.3k
1
vote
0
answers
76
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
14
votes
1
answer
402
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,620
18
votes
2
answers
545
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 ...
- 14.2k
4
votes
0
answers
285
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 ...
- 13.3k
3
votes
1
answer
197
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 ...
- 289
9
votes
2
answers
545
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?
- 93
5
votes
0
answers
81
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 ...
- 151
8
votes
3
answers
615
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 ...
- 181
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 ...
- 1
3
votes
0
answers
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 ...
user6973
13
votes
1
answer
295
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 ...
- 21.1k
10
votes
2
answers
368
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 ...
- 2,813
-3
votes
1
answer
402
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
2
answers
518
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 ...
user6973
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-...
- 4,061
6
votes
1
answer
455
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 ...
user6973
10
votes
1
answer
384
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 ...
- 101
4
votes
0
answers
324
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 ...
- 455
8
votes
1
answer
293
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 $...
- 2,228
9
votes
0
answers
565
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,228
9
votes
2
answers
1k
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.6k
9
votes
0
answers
638
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 ...
- 129
8
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.6k
5
votes
2
answers
262
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 ...
- 21.1k
16
votes
5
answers
1k
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
10
votes
1
answer
505
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 ...
- 16.6k
4
votes
2
answers
340
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 ...
- 21.1k