Questions tagged [one-way-functions]
One-way functions (OWF) are easy to compute, but hard to invert. They exists only if P$\ne$NP. Many cryptographic primitives are based on (or are implied by) the existence of one-way functions.
50
questions
0
votes
0
answers
25
views
Is `f.splitting_field()` a one-way function candidate?
Is computing the splitting field of a polynomial a candidate for a one-way function?
Let $K$ be a number field and $f, g \in K[x]$. Let L_f = f.splitting_field() ...
- 133
0
votes
0
answers
21
views
Why is the existence of one-way functions not proven? [duplicate]
Weisstein, Eric W. "One-Way Function." From MathWorld--A Wolfram Web Resource.:
The existence of one-way functions is not proven.
Why not?
- 154
0
votes
1
answer
77
views
Time bounded Kolmogorov complexity and one way functions
I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that ...
- 301
0
votes
1
answer
28
views
Reversible computing as a path to a useful PRNG or hash function?
There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation?
The most straightforward ...
- 306
0
votes
1
answer
33
views
Is this restatement of one-way functions accurate?
I realize this is sort of a trivial ask, but I want to make sure I understand OWFs and it's usually explained with some jargon that I don't find clarifying. So, I'd just like to know whether or not my ...
- 306
1
vote
2
answers
105
views
P = NP ==> there exists no OWF: proof using NTM and binary tree
I read a proof in my script:
If $P = NP\implies $ there exists no OWF $f$.
A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$
Their proof was a bit messy so I want to ask if ...
- 25
2
votes
1
answer
254
views
Proof that pseudorandom generators implies one-way function
I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.
My understanding is that pseudorandom generators are defined as
A function $...
- 33
5
votes
1
answer
347
views
How to prove that existence of one-way functions implies P≠NP?
Wikipedia:
The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.
How is this proved?
- 503
0
votes
0
answers
66
views
A set that is not polynomial time enumerable
For a set $I\subseteq \Bbb N$, defined $s_{I}(n)=\min\{i\in I\mid i>n\}$. The set $I$ is called polynomial-time-enumerable if $s_I(n)$ is computable in $\mathsf{poly}(n)$ time.
Most of the sets I ...
- 101
2
votes
1
answer
60
views
Is this statistical group summation unambiguously reversible?
Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation:
$A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$...
- 247
0
votes
1
answer
321
views
If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?
Just like the title states.
If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why?
My ...
- 77
1
vote
1
answer
71
views
What is and amplification factor in pseudo-random generators?
I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this ...
- 77
0
votes
1
answer
87
views
Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function
I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?
- 77
0
votes
0
answers
50
views
What complexity class results would be implied by a proof of the existence of one way functions
What complexity class results would be implied by a proof of the existence of one way functions. (Apart from the obvious $P \neq NP$)
I thik it would imply $P \neq UP$, but what else?
- 356
1
vote
1
answer
94
views
One-way function is not injective when it is in NP
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...
0
votes
0
answers
56
views
One-way-function based on Friedberg numberings
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
- 109
0
votes
1
answer
37
views
vector hashing function having collisions for permutations
let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for ...
- 109
1
vote
1
answer
173
views
Difficulty in proving the existence of one-way functions
By definition:
A polynomial-time computable function $f:$ $\{$0,1$\}$$^*$→ $\{$0,1$\}$$^*$ is a one-way function if for every probabilistic polynomial time Turing Machine $PTM$ there is a ...
- 1,073
1
vote
0
answers
76
views
Inverting a function [closed]
I posted this question on mathoverflow two years ago but got no answer:
Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$
Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-...
user41014
1
vote
3
answers
343
views
Is the sum $f+g$ of two one-way-functions a one-way-function?
Since there exists a bijection of sets from $\{0,1\}^*$ to $\mathbb{N_0}$, we might view one-way-functions as functions $f :\mathbb{N_0} \rightarrow \mathbb{N_0}$. My question is, suppose $f,g$ are ...
user41014
1
vote
0
answers
80
views
Is it possible to build a secure PRG from two functions one of them being a PRG?
Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG.
Being $\alpha$ a constant, is it possible ...
- 65
1
vote
2
answers
86
views
Why can't hash coding be reversed?
Why is it impossible to reverse a hash code? There could be some way to crack this coding?
- 123
2
votes
1
answer
286
views
What is the relation between reversible circuits and invertible functions?
A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in ...
- 4,072
4
votes
1
answer
385
views
Any evidence that one way functions exist?
There is no known proof that one way functions exist. But what is the heuristic evidence that they exist?
I sometimes read that the existence of cryptography is heuristic evidence that they exist. E....
- 4,072
2
votes
1
answer
206
views
Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?
I'm working with this definition for one-way functions:
We call $f$ a (strong) one-way function if
it is computable in polynomial time
for any polynomial time randomized algorithm $B$ ...
- 1,058
2
votes
2
answers
351
views
Under what circumstances are one-way functions reducible to their hard-core bits?
I've seen competing claims about hard-core predicates. On the one hand, there's the basic definition
Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable ...
- 1,058
-1
votes
2
answers
63
views
How do these alternative definitions of one-way functions compare?
I've seen competing requirements in the definitions for one-way functions. Namely
$$
\underset{x,r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big) = o(n^{-c})
$$
and
$$
\underset{x}{\mathbb{E}}\left[\...
- 1,058
3
votes
1
answer
95
views
How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?
I'm considering the following definition of one-way functions:
Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is ...
- 1,058
1
vote
1
answer
273
views
Is $x^2+x+1 (mod 2)$ a one-way function?
Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}[(-1)^{x}|x \rangle + |1-x \rangle]$ (Fourier transform). So, the 1-1 correspondence ...
- 11
3
votes
1
answer
143
views
Understanding Incentive Compatibility of pooled Bitcoin Mining paper
I'm trying to understand the paper Incentive Compatibility of
Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data
Security – ...
- 222
1
vote
1
answer
399
views
Proof of composition of one way function is not one way in general
In this How to show composition of one way function is not such? question, the accepted answer uses g(x,y) as a one way function.
But, for a given output of g(x,y) = 0|x| of length l (say), isn't the ...
- 13
2
votes
2
answers
3k
views
XOR of one-way function
Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”…
The function is no longer one-way.
we build a counter example ...
vrume21
6
votes
2
answers
3k
views
Do one way function exist?
I was recently going through the Wiki page List of unsolved Problems in Computer Science.
There was a problem which I do not understand
Do one-way functions exist ? [Is public-key cryptography ...
- 749
2
votes
1
answer
45
views
If a Ptime function loses x bits of data at every call, is it a one way function?
If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision ...
4
votes
1
answer
432
views
Hardcore Bit proof for discrete log
I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that $B(x)=(x<p/2)$ is a hardcore bit for ...
- 165
3
votes
1
answer
487
views
If one-way functions exist are we definitely using them?
I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are ...
- 1,631
2
votes
1
answer
534
views
Length Preserving One way function
In the proof of existence of length preserving one way functions assuming the existence of one way functions, see
Length-preserving one-way functions
We need $p(n)$ to be a function which can not ...
- 161
3
votes
1
answer
118
views
What are the examples of the easily computable "wild" permutations?
I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the ...
- 133
2
votes
0
answers
55
views
On possible existence of OWFs
Assuming $P\neq NP$, is there a computational model in which OWFs cannot exist? What more should we include beyond non-determinism, randomness, quantum model to preclude existence of OWFs?
- 2,919
4
votes
1
answer
1k
views
Universal One-Way Functions
The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions).
As a step to solving the conjecture, if one-way functions could be reduced to a ...
- 1,644
0
votes
1
answer
395
views
Is the Berman-Hartmanis Conjecture Solved?
The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on One-...
- 1,644
4
votes
1
answer
346
views
If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument
I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is ...
- 3,070
4
votes
3
answers
204
views
Using a proof-of-work system to discourage piracy or encourage donations
Background
A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed.
In a network setting this can be used to throttle peer requests ...
- 151
4
votes
2
answers
2k
views
Polynomial-time algorithm with exponential space is eligible?
I'm curious about two things.
When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For ...
- 105
3
votes
2
answers
307
views
Assumptions of One Way Functions
I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of ...
- 3,189
6
votes
1
answer
2k
views
Length-preserving one-way functions
Unfortunately my background in computational complexity is still weak, but I am working on it.
As I understand, the question of existence of one-way functions is very important in the field.
Assume ...
- 3,189
6
votes
1
answer
2k
views
If xor-ing a one way function with different input, is it still a one way function?
Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$?
$\oplus$ is exclusive disjunction (xor)
$||$ is ...
- 61
5
votes
1
answer
1k
views
What will i obtain if i apply a xor-ing a one way function and it's input?
I know that a one-way function is informally a function that it's easy to compute but hard to invert.
If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function?
My ...
- 507
4
votes
1
answer
2k
views
How to show composition of one way function is not such?
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?
Specifically: Say $f$ and ...
- 265
9
votes
1
answer
449
views
Attack on hash functions that do not satisfy the one-way property
I am revising for a computer security course and I am stuck on one of the past questions. Here is it:
Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
- 357