5 votes
Accepted

How to prove that existence of one-way functions implies P≠NP?

Suppose that P=NP, and that $f\colon \{0,1\}^* \to \{0,1\}^*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \...
Yuval Filmus's user avatar
3 votes
Accepted

What is and amplification factor in pseudo-random generators?

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed. Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that ...
Ariel's user avatar
  • 13.4k
3 votes
Accepted

Is the sum $f+g$ of two one-way-functions a one-way-function?

The answer is no. Given $f$ one-way, consider $g(x) = -f(x)$. $g$ is then also one-way, because inverting $g$ would imply inverting $f$. In particular, supposing $g$ is not one-way, one can invert $...
dkaeae's user avatar
  • 5,017
3 votes
Accepted

Under what circumstances are one-way functions reducible to their hard-core bits?

Inverting a one way function is not always reducible to evaluating a hardcore bit. As an example, consider trivial hardcore predicates. Let $f$ be one way and define $g(x,b)=f(x)$ where $b\in\{0,1\}$. ...
Ariel's user avatar
  • 13.4k
3 votes
Accepted

How do these alternative definitions of one-way functions compare?

The expressions are equivalent. To see why, unfold the expectation and use the fact that $x,r$ are independent. $$ \mathop{\mathbb{E}}\limits_{x}\left[\Pr\limits_{r}\big(f(B(f(x),r))=f(x)\big)\right]=...
Ariel's user avatar
  • 13.4k
3 votes

How do these alternative definitions of one-way functions compare?

They're equivalent. In general, if $X$ is a 0-or-1 random variable, then $\mathbb{E}[X] = \mathbb{P}[X=1]$ holds. Also, if $E_{X,Y}$ is an event that depends on two independent random variables $X,Y$...
D.W.'s user avatar
  • 159k
3 votes

Any evidence that one way functions exist?

AES is widely believed to be secure: many smart people have tried to break it and haven't been able. This is not a proof, and it is arguable exactly how strong this evidence is, but it does count as ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

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$?

Before addressing your question, we should note that there are some subtleties when defining "inverting $f(x)$ reduces to finding $h(x)$". Suppose we aim towards something along the lines of a ...
Ariel's user avatar
  • 13.4k
2 votes

Is $x^2+x+1 (mod 2)$ a one-way function?

A one-way function is a function from $\{0,1\}^*$ to $\{0,1\}^*$ which satisfies certain properties. Your function only accepts a single bit as input, so in particular isn't a one-way function. We ...
Yuval Filmus's user avatar
2 votes
Accepted

Why can't hash coding be reversed?

Because, in general, hashing is not injective. Being injective is a property of a function which states that each distinct element of the domain is mapped to distinct element of codomain. It means ...
Sandro Lovnički's user avatar
2 votes
Accepted

One-way function is not injective when it is in NP

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. ...
Yuval Filmus's user avatar
2 votes
Accepted

Is this statistical group summation unambiguously reversible?

The answer is no . I found it helpful to think of the information in the form of a picture: mark each pair $(a, b)$ as a point on a grid, then in each column and row write both the count of the ...
Joppy's user avatar
  • 266
2 votes
Accepted

P = NP ==> there exists no OWF: proof using NTM and binary tree

The core idea is good. You might want to elaborate more on how this process is done in detail: Let us keep in mind that an OWF is a function $F$ that can be computed in $poly(n)$ time but $F^{-1}$ ...
nir shahar's user avatar
  • 11.6k
2 votes

Reversible computing as a path to a useful PRNG or hash function?

I am not aware of any reason to believe that the junk bits will be strongly pseudorandom (for instance, in the sense of polynomial-time indistinguishability from random or cryptographic ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Time bounded Kolmogorov complexity and one way functions

While intuitively it seems correct, in cryptography you can't assume anything about the particular algorithm an opponent runs. We don't know how to prove that there's no clever way to eliminate many ...
Command Master's user avatar
1 vote

Is this restatement of one-way functions accurate?

It might be close, but I don't think it's 100% right. It's not clear what you mean by "find any particular specific output". Typically there's no requirement that an adversary have to try ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Proof that pseudorandom generators implies one-way function

One-way functions need not be invertible. A one-way function which is invertible is known as a one-way permutation. Here is the definition of one-way function from Goldreich's primer: A function $f\...
Yuval Filmus's user avatar
1 vote

If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

Hint: Forget about the stretch of the PRG and let's instead focus on the whether the output of $f$ necessarily looks like a random string (even if we give it a truly random string instead of a PRG ...
shfk's user avatar
  • 11
1 vote
Accepted

Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function

A function $f$ is one-way if given $f(z)$ for random $z$, it is hard to find an input $w$ such that $f(w) = f(z)$. So in order to show that $f$ isn't one way, you need to show that given $f(z)$ for ...
Yuval Filmus's user avatar
1 vote

vector hashing function having collisions for permutations

With your limitations, you put all values into about 166,000 or so buckets, so yes, easily. If x, y, z are arbitrarily large, of course not.
gnasher729's user avatar
1 vote

Difficulty in proving the existence of one-way functions

Apparently proving the existence of these functions would be more difficult than proving $P\not =NP$? And I'd like to know the technical reasons for this, does it have something to do with the "for ...
Tom van der Zanden's user avatar
1 vote

Is the sum $f+g$ of two one-way-functions a one-way-function?

I think your error is that you expect that for OWF each and any f(x) computation should be hard to reverse. But it seems incorrect, f.e. modular squaring is easily ...
Bulat's user avatar
  • 1,873
1 vote

Why can't hash coding be reversed?

As Sandro said, the issue is that a hash function is not injective. This is easily understood by recognizing that you are mapping from a larger set to a smaller set, and thus losing information. ...
Sebastian's user avatar
  • 131
1 vote

What is the relation between reversible circuits and invertible functions?

There is quite a lot of work on the design of reversible programming languages that express total bijective functions operating on finite number of bits, by Amr Sabry and his collaborators. ...
vikraman's user avatar
  • 173
1 vote

Understanding Incentive Compatibility of pooled Bitcoin Mining paper

Let's assume $n=3$ and at round $t$, miner_1 reported 2 shares, miner_2 reported 3 shares, and miner_3 reported 5 shares. And we'll further assume that in rounds from 0 to $t-1$, none of them reported ...
Shravan's user avatar
  • 111
1 vote

How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

Both (1) and (2) are possible. (It's also possible to have a combination of them.) It doesn't really matter which holds; either way, that means that $f$ is not one-way. You say (2) is false because ...
D.W.'s user avatar
  • 159k

Only top scored, non community-wiki answers of a minimum length are eligible