Questions tagged [one-way-function]
A function which is easy to compute but hard to invert (i.e. find preimages for). The existence of one-way functions implies the possibility of many useful cryptographic schemes. No one-way functions have so far been proven to exist, but many likely candidates exist.
282
questions
2
votes
0
answers
159
views
It is possible to verify the computation of a hash function without actually proving it in zero knowledge?
Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively.
...
0
votes
0
answers
165
views
XOR of all bits of $f(x)$ a hard-core bit
Why consider a random $r$ in building a hardcore predicate in Goldreich Levin theorem? Why not consider just the XOR of all bits of the input?
0
votes
1
answer
89
views
Why is a fixed permutation not oneway?
This may not be a good question, but I am just start to learn cryptography.
I would like to ask why a fix permutation is not one way.
An adversary is given y=f(x) and try to invert y, x and y are n ...
2
votes
1
answer
89
views
Security of Hash Functions
Given a Hash Function H, how are the properties such as collision resistance, target collision resistance, one wayness, and non-malleability proved? I have read about hash function and stating that it ...
0
votes
0
answers
56
views
I'm having trouble understanding this [duplicate]
Let $x=(x_1,x_2,...x_n)∈\{0,1\}^n$ for $n∈\mathbb N$. Prove that if one-way functions (OWFs) exist, then there exists a one-way function f such that for every bit $i∈[1, n]$ there exists an algorithm $...
1
vote
1
answer
236
views
One way function existence
Let $x = (x_1, x_2,...,x_n)\in\{0,1\}^n$ for $n\in\mathbb{N}$. Prove that if one-way functions (OWFs) exist, then there exists a one-way function $f$ such that for every bit $i\in[1,n]$ there exists ...
1
vote
2
answers
148
views
Rigorous practical pseudorandom generators
It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem.
I am curious if someone developed kind of &...
0
votes
0
answers
89
views
Do I understand $P = NP$ correctly in relation to one-way functions?
If I understand this relation correctly is, that any function whose inverse can be found in polynomial time is not a one way function. The $P = NP$ proved would cause that any candidate for a one-way ...
2
votes
0
answers
48
views
How can one-way hash functions in the signatures help by using same algorithm for encryption and signature verification?
I read some documents about digital signatures and one way hash functions, etc., but everything was too complicated and I don't have much experience in cryptography. Can anyone explain to me in a ...
2
votes
1
answer
101
views
A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?
I came up with this question while I was reading this paper: Pilaram, Hossein, and Taraneh Eghlidos. "An efficient lattice based multi-stage secret sharing scheme." IEEE Transactions on ...
1
vote
1
answer
250
views
In the reduction proof below, where OWF exists only if is a PRG. I am not able to understand the highlighted part
I am able to understand how G(x) id generated. But then what is the use of variable z. Also if the probability is >1/2 + e then the distinguisher wins! Then how is this still a OWF
4
votes
2
answers
224
views
Single-block hash construction based on a block cipher with two fixed keys
Let k1, k2 be two arbitrary fixed keys (nothing-up-my-sleeve values like "foo" and "bar") and ...
2
votes
1
answer
159
views
Does Rabin function lose its one-way property if squaring mod a prime?
I am looking into various one way functions and I stumbled upon a Rabin function, which is squaring modulo an RSA modulus $N=pq$, where $p,q$ are prime: $R_N(x) = x^2 \mod N$.
Would it lose the one-...
1
vote
0
answers
85
views
Does this break the pre-image resistance of the hash function?
Supposing a secure hash function $f(\cdot): \{0,1\}^* \rightarrow \{0,1\}^n$ satisfies pre-image resistance.
That is, given a hash value $y$ it should be difficult to find any message $x$ such that $y ...
0
votes
1
answer
116
views
If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function?
Assume $S$ is a domain. $S' \subseteq S$ and all elements in $S'$ are invertible. $H:S'\rightarrow S$. If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function?
2
votes
2
answers
172
views
Provable Lower Bounds for some Algorithmic Problems?
Are there any problems for which we have known lower bounds?
For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons.
Edit: I'm aware that this requires restricting ...
0
votes
1
answer
74
views
Generator of one-way functions
Please pardon my question if it seems silly, but I am very keen on knowing: in applied cryptography, there is such a thing as a one-way function, which given an input would generate an output that is ...
0
votes
0
answers
161
views
Does this qualify as a one-way function?
First, we observe that the expression X*Y mod P (where X and Y are secret and P is a large public prime) reveals no useful information.
Next we define an extending function E(U, M) which "somehow&...
4
votes
1
answer
318
views
Are there any public-key encryption schemes based on DLog?
There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the ...
0
votes
1
answer
195
views
Length Regular and Length Preserving
What does it mean to say a function is length regular and Length preserving? Does any one of them implies the other? Example if any could be useful
0
votes
1
answer
412
views
Do probabilistic one-way functions imply deterministic one-way functions?
Suppose $f$ is a probabilistic one-way function. Then my question is, does there exist a construction of a deterministic one-way function $g$ based on $f$?
Or is it possible that probabilistic one-...
0
votes
0
answers
172
views
What one-way functions are there based on the Diffie-Hellman problem?
Mathematical hardness assumptions like that of the factoring problem, the RSA problem, and the discrete log problem all straightforwardly lead to one-way functions. But what about the computational ...
0
votes
0
answers
112
views
Is this really a universal one-way function?
This PDF supposedly gives a construction of a universal one-way function, i.e. a function which is one-way as long as there exists a one-way function:
Recall that there are only countably many Turing ...
6
votes
1
answer
177
views
Does there exist a universal one-way permutation?
Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function.
But my question is, does there exist a universal one-way ...
0
votes
0
answers
86
views
Are there any universal PRG’s or PRF’s?
Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
3
votes
2
answers
983
views
Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem
Problem statement:
"Bob is a paranoid cryptographer who does not trust dedicated hash functions such as SHA1 and SHA-2. Bob decided to build his own hash function based on some ideas from number ...
3
votes
1
answer
528
views
Has anyone implemented a public-key encryption scheme using a universal one-way function?
There exists a function $f$ such that if one-way functions exist then $f$ is a one-way function. Such a function is called a universal one-way function.
Now the public-key encryption schemes that I’...
1
vote
0
answers
52
views
When is a OWF practically insecure?
Let's say we got a one way function (OWF). Such a function takes 512-bit input and gives 256-bit output. And let's say we can easly invert some specific inputs. There is exactly $2^{256}$ such blocks ...
0
votes
1
answer
146
views
One way permutation and its inverse
Is the following statement correct?
Let $F$ be a OWP. Then the inverse $F^{-1}$ of $F$ is also a OWP.
18
votes
5
answers
11k
views
Is it easy to crack a hashed phone number?
I want to SHA256 hash phone numbers in order to hide them. Is this a good idea? Are there any other ways I could make this safe?
6
votes
1
answer
169
views
If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?
We have several candidates for OWF, like multiplication/factoring and discrete exponencial/logarithm. What I am asking is:
Does the existence of one way functions imply that our candidate functions ...
1
vote
0
answers
179
views
Is $f(g)$ a PRG if $f$ is a OWF and $g$ a PRG?
If we have a PRG $g$ and a OWF $f$, can we say that $g' = f(g)$ is a PRG?
And what if $g$ stretches its input by a factor of 2?
0
votes
0
answers
76
views
What is the probability that a random function is invertible?
Having a random function - $R\in{}\mathcal{R}$
s.t.
$R:\{0,1\}^n\rightarrow{}\{0,1\}^n$.
What is the probability that $R$ is invertible?
I know calculating it suppose to be straight forward, but I'...
8
votes
2
answers
2k
views
(updated) Utilizing a non-computable function to create a one-way function
Why can't uncomputable functions be adapted to serve as theoretically perfect one-way functions? This has been bugging me for years, and I've never been able to track down an explanation of why it ...
1
vote
0
answers
183
views
Composition of an injective/surjective function and a one-way function remains a one-way function?
I recently read about OWFs and realized that the composition of two OWFs (called, say, $g$ and $f$) are not necessarily an OWF. However, if I modify the question a little bit and fix $g$ to be an ...
0
votes
1
answer
588
views
Are all public-key encryption protocols based on one-way functions? [duplicate]
Are there any public-key cryptography protocols which don't rely on one-way (or trapdoor) functions?
RSA and Diffie-Hellman cryptographic protocols both rely on one-way functions (prime factorization ...
0
votes
0
answers
146
views
How can I show, that RSA with OWP is IND-CPA secure by using H function?
How can I show, that RSA with OWP is IND-CPA secure by using H function , a random oracle model.
The Encryption goes like: $\text{Encryption_H_PK}(M)\gets(C_1,C_2)\gets(f(x),H(x)\oplus M)$
...
1
vote
1
answer
1k
views
Can one-way permutations be constructed from one-way functions?
We can construct various symmetric key primitives like PRGs, PRFs, SPRPs etc., assuming the existence of either one-way permutations or one-way functions with the former assumption allowing simpler ...
2
votes
1
answer
318
views
A hash functin based on XOR and matrix multiplication
Imagine an $n$ bit to $n$ bit hash function defined as follows: Let $K$ and $K'$ be two random predetermined $n\times n$ matrices. Then the hash function $h$ of an $n$ bit number $a$ would be:
$$h(a)=...
3
votes
1
answer
185
views
Can the input to a one way function be pseudorandom?
I know that normally a one-way function takes in a completely random input, but can a one-way function take in something pseudorandom instead of completely random? Will it still be a one-way function? ...
3
votes
1
answer
755
views
Why does the one-time pad not imply $P \not= NP$?
I apologize that this is a rather trivial question, but I haven't been able to find an answer anywhere. If the one-time pad is unconditionally secure and impossible to crack (with just ciphertext), ...
1
vote
1
answer
76
views
Permutation of first $k$ prime powers as a one-way function?
Let $a_1$ through $a_k$ be some permutation of the first $k$ primes. Let $n \in [1,k!]$ be a parameter specifying the exact ordering by taking the $n$th permutation in a sorted list or by some other ...
0
votes
1
answer
70
views
Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted?
Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:
$m = (n(n+1)/2)\ \bmod 2^{64}$
It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\...
1
vote
1
answer
159
views
Does adding OWF of the private key to encryption scheme hurts security?
Suppose I have a symmetric semantic-secure encryption system $\Pi = (Enc, Dec)$ and an OWF $f$.
Now, define the following encryption scheme $\Pi^{'} = (Enc^{'}, Dec^{'})$ where , $Dec^{'} = Dec$ and $...
6
votes
1
answer
296
views
If a permutation $f$ is not one way, what can we say about $f^{p(n)}$?
Consider a permutation $f:\{0,1\}^*\rightarrow \{0,1\}^*$, which is not a one-way function, i.e. there exists an efficient probabilistic adversary $\mathcal{A}$ and some polynomial $q(n)$ such that ...
1
vote
1
answer
394
views
Can a One way function also be its inverse?
This is from my homework:
Prove that if there exists a one-way function, then there exists a one-way function f such that
$f(0^n ) = 0^n$ for every $n$.
Note that now for infinitely many values $y$...
4
votes
1
answer
423
views
Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?
Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows:
Let $s \in \{0,1\}^n$ ...
2
votes
1
answer
289
views
Existence of MAC implies existence of OWF
I'm having trouble understanding how the existence of a MAC implies the existence of an OWF.
If the MAC protocol is $(\operatorname{Gen}, \operatorname{MAC}, \operatorname{Ver})$ such that for any ...
0
votes
1
answer
97
views
One-way Functions for Floating Points
Are there any commutative one-way functions for floating points?
I tried to explain why I need these functions.
First, I describe the problem on a high level and then I further formalize it;
There ...
0
votes
0
answers
168
views
Subset-sum one way function is one way on it's iterates if subset-sum is one-way
Working through the Moni Naor's slides from his lecture Foundations of cryptography (Lecture 3), the slides state that the subset sum function is one-way on its iterates if it is one-way, where the ...