# 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.

42 questions
Filter by
Sorted by
Tagged with
21 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 ...
43 views

### Is this statistical group summation unambiguously reversible?

Given an (unordered) set of 2-tuples (X) of natural numbers (I'm using SQL here for easy reproducibility, and because I don't know better): ...
34 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 ...
47 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 ...
34 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?
41 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?
27 views

139 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 ...
54 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 ...
52 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?
107 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 ...
215 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....
98 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$ ...
56 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 ...
61 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[\...
66 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 ...
233 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 ...
137 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 – ...
286 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 ...
1k 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 ...
1k 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 ...
38 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 ...
257 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 ...
399 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 ...
340 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 ...
76 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 ...
50 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?
667 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 ...
254 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-...
146 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 ...
188 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 ...
1k 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 ...
234 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 ...
1k 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 ...
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 ...
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 ...
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 ...
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 ...