Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
27 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 ...
1
vote
2answers
47 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?
1
vote
0answers
15 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 ...
4
votes
1answer
117 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....
2
votes
1answer
67 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$ ...
2
votes
2answers
41 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 ...
-1
votes
2answers
56 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[\...
3
votes
1answer
62 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 ...
1
vote
1answer
197 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 ...
3
votes
1answer
112 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 – ...
1
vote
1answer
188 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 ...
1
vote
2answers
738 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 ...
5
votes
1answer
631 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 ...
2
votes
1answer
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 ...
4
votes
1answer
162 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 ...
3
votes
1answer
361 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 ...
2
votes
1answer
225 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 ...
3
votes
1answer
66 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 ...
2
votes
0answers
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?
4
votes
1answer
488 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 ...
0
votes
1answer
175 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-...
4
votes
1answer
133 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 ...
4
votes
3answers
185 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 ...
3
votes
2answers
842 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 ...
3
votes
2answers
195 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 ...
7
votes
1answer
953 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 ...
7
votes
1answer
1k 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 ...
4
votes
1answer
804 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 ...
4
votes
1answer
1k 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 ...
9
votes
1answer
338 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 ...