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.

Filter by
Sorted by
Tagged with
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?
Geremia's user avatar
  • 148
0 votes
1 answer
70 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 ...
Craig Feinstein's user avatar
0 votes
1 answer
20 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 ...
Trev's user avatar
  • 296
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 ...
Trev's user avatar
  • 296
1 vote
2 answers
103 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 ...
David's user avatar
  • 25
2 votes
1 answer
154 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 $...
asdf's user avatar
  • 33
5 votes
1 answer
312 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?
porton's user avatar
  • 433
0 votes
0 answers
62 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 ...
QED's user avatar
  • 101
2 votes
1 answer
57 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$...
Tobias Hermann's user avatar
0 votes
1 answer
285 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 ...
Pedro Costa's user avatar
1 vote
1 answer
69 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 ...
Pedro Costa's user avatar
0 votes
1 answer
84 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?
Pedro Costa's user avatar
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?
blademan9999's user avatar
1 vote
1 answer
83 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 \...
Peter Hofschatter's user avatar
0 votes
0 answers
55 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 ...
Harald Thomson's user avatar
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 ...
quester's user avatar
  • 109
1 vote
1 answer
161 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 ...
Yamar69's user avatar
  • 1,073
1 vote
0 answers
73 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-...
user avatar
1 vote
3 answers
313 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 ...
user avatar
1 vote
0 answers
78 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 ...
user2712414's user avatar
1 vote
2 answers
77 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?
Laila's user avatar
  • 123
2 votes
1 answer
275 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 ...
user56834's user avatar
  • 3,752
4 votes
1 answer
366 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....
user56834's user avatar
  • 3,752
2 votes
1 answer
202 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$ ...
Sebastian Oberhoff's user avatar
2 votes
2 answers
346 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 ...
Sebastian Oberhoff's user avatar
-1 votes
2 answers
62 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[\...
Sebastian Oberhoff's user avatar
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 ...
Sebastian Oberhoff's user avatar
1 vote
1 answer
271 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 ...
AdC's user avatar
  • 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 – ...
T.Harish's user avatar
  • 222
1 vote
1 answer
394 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 ...
rasalghul's user avatar
2 votes
2 answers
2k 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 ...
user avatar
6 votes
2 answers
2k 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 ...
Atinesh's user avatar
  • 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 ...
Saptarshi Soham Mohanta's user avatar
4 votes
1 answer
421 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 ...
Cpt Wobbles 's user avatar
3 votes
1 answer
483 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 ...
Ari's user avatar
  • 1,621
2 votes
1 answer
529 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 ...
Gaganpreet's user avatar
3 votes
1 answer
115 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 ...
tafit3's user avatar
  • 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?
Turbo's user avatar
  • 2,891
4 votes
1 answer
994 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 ...
user13675's user avatar
  • 1,624
0 votes
1 answer
384 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-...
user13675's user avatar
  • 1,624
4 votes
1 answer
334 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 ...
Charlie Parker's user avatar
4 votes
3 answers
201 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 ...
LateralFractal's user avatar
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 ...
euna's user avatar
  • 105
3 votes
2 answers
303 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 ...
com's user avatar
  • 3,179
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 ...
com's user avatar
  • 3,179
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 ...
Kate Green's user avatar
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 ...
dbonadiman's user avatar
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 ...
LMG's user avatar
  • 255
9 votes
1 answer
448 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 ...
sam's user avatar
  • 357