# Tag Info

9

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential ...

9

The function $h$ may not be one-way anymore. We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way. Assume $g$ is a one-way function that preserves size, and define $f$ on input $w=bx_1x_2$ in the following way, $$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$ (...

7

Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$. Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|f(x)| \le p(|x|)$ for all $x$ Define $$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way. We now have to force ...

6

One-way functions are an asymptotic concept. A function such as modular exponentiation with specific parameters doesn't qualify for being a one-way function since it only exists for a specific size. The same can be said about hash functions such as SHA1. In order to ask the question, you will need to specify an infinite family of functions of the type you're ...

6

No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just say that no one was able to find an algorithm accomplishing that so far, but there is no guarantee that tomorrow such an algorithm won't be found. In ...

6

You come up with an example: two functions $f,g$ which are one-way functions, but $f \circ g$ is not. To show that the latter is not a one-way function, you come up with an algorithm breaking it. Here is an example. Choose some genuine one-way function $h$. Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y ... 5 Let$h$be any one-way function, and define$f(x) = 0^{|x|} h(x)$. Note that$f$is also one-way: it is easy to compute, and if you can invert$f$you can invert$h$(so since$h$is hard to invert, so is$f$). But$g(x) = xh(x)$is easy to invert. 5 When we talk about quadratic running time, we mean$O(n^2)$running time where$n$is the length of the input -- i.e., the running time is a constant times the square of the length of the input. Make sure you understand what the length of the input is here. By padding the input, we've made the input longer. Even though the overall running time doesn't ... 4 A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function$f$such that given a random$y$, it is hard to find a preimage$x$satisfying$f(x) = y$. The exact sense of hardness isn't important here. Your function is not one-way since it fails the first requirement: it is not easy to compute. If ... 3 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 heuristic evidence of some sort. The fact that we haven't been able to find an algorithm to break AES does seem to count as some sort of heuristic evidence ... 3 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\}$. Obviously$b$(the rightmost bit of a string) is a hardcore predicate for$g$, however knowing it does not bring you any closer to finding the rest of the ... 3 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]= \sum\limits_{x}\Pr(x)\Pr\limits_{r}\big(f(B(f(x),r))=f(x)\big)= \sum\limits_{x}\Pr(x)\sum\limits_{r}\Pr(r)\mathbb{1}_{f(B(f(x),r))=f(x)}= \sum\limits_{x,r}\Pr(... 3 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$, then$\mathbb{P}_{X,Y}[E_{X,Y}] = \mathbb{E}_X[\mathbb{P}_Y[E_{X,Y}]]$. To see way, just expand the definitions, as Ariel suggests. (Comment on the ... 3 Another idea, similar to SCIP, is secure multi-party computation, which can provide a similar ability via secure function evaluation. This is essentially a function that you can run on an untrusted machine, without revealing the input-values. The function can provide an "easy-out" shortcut function via some one-way/trapdoor answer, same as above in my ... 3 Hypothesis Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm. Such converted proof-of-work algorithms can support proof-of-work shortcuts. Such converted proof-of-work algorithms can not be converted back to the original algorithm ... 3 That is an interesting question since there is no proof that one way functions exist. There is a lecture about this from Cornell's Cryptography course by Rafael Pass which can be found here To summarize the lecture: If one way functions exist then$P\neq NP$. There exists a function$f_{UNIV}$such that if there exists any one-way function, then$f_{...

3

The usual approach is to identify a randomized self-reduction. In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$. How does this help? Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one ...

3

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 $f(x)$ simply by negating it and applying the inverter for $g$ (and the success probability is even equal). In this setting, $h(x) = f(x) - f(x) = 0$ is not one-...

3

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 maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you ...

2

$p(n)$ is just a polynomial that indicates the length of the output of the function $g$, as a function of the length of the input. Imagine that it's something like $27n$ or $2n^2$, and then read through the proof and you'll see how it works. I didn't see any requirement to compute an inverse of $p(\cdot)$ in that proof. I'm not sure where you got that ...

2

Yes, such things exist. They have been studied in the cryptographic literature: the key name is "format-preserving encryption". To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto....

2

The conjecture remains open. Also there is a proof that shows that if the conjecture is true, then P=/=NP. To my knowledge no one has proven the opposite, that if the converse is true then P=NP, to be true.

2

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 don't know whether one-way functions exist, though many people conjecture that they do. Proving that one-way functions exist is harder than proving $\mathsf{P} \... 2 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 standard Turing reduction, then what does our oracle do? When feeding the oracle some string$y\in\{0,1\}^*$, where the only promise about$y$is that it lies in the ... 2 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 that given a value of a function, you will (if it is a valid value) know from what it came from. For more on this, see injective function. Therefore, if hashing ... 2 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 every" in the definition? The answer is in your question itself: I believe that since proving its existence would also prove$P\not =NP$This is indeed the ... 2 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$. Since$f$is injective, if$w \in L$then there is exactly one witness$z$, and so$L \in \mathsf{UP}$. Since$L$is always in$\mathsf{NP}$(using the very same ... 1 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. Perhaps it's easier to understand in terms of other non-injective functions. Say you have pairs of integers$(x,y)$and you map them to their projection$y$. You ... 1 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 of the preceding discussion, but I'm not exactly sure why you think it is false. One-wayness is not a property of a specific value of$x$; rather, it is a ... 1 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 any shares.$R$is the reward function that takes the history of the shares reported by all miners and returns a n-length vector,$a\$, consisting of real ...

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