# Tag Info

Accepted

• 5,027
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\}$. ...
• 13.4k
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]=...
• 13.4k

### 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$...
• 163k

### 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 ...
• 163k
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 ...
• 13.4k

### 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 ...
• 278k
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 ...
• 1,191
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$. ...
• 278k
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 ...
• 266
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}$ ...
• 11.6k

### 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 ...
• 163k
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 ...
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 ...
• 163k
1 vote
Accepted

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\... • 278k 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 ... • 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 ... • 278k 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. • 31.2k 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 ... • 13.3k 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 ... • 1,988 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. ... • 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. ... • 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 ... • 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 ...
• 163k

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