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.
270
questions
0
votes
0
answers
33
views
If mac M is defined as M(k,x) = f(k||x) where f is one way function, can M be UNF-CMA secure Mac scheme?
$f$ here can leak inputs that is $f(x_1 \| x_2) = f(x_1) \| x_2$, is still a one way function $(|x_1| = |x_2|)$. I don't think this should be a secure MAC but don't have any way to formulate it.
- 11
1
vote
0
answers
66
views
Does removing just last bit from output of one way function change its one wayness?
If $g(x)$ if length preserving one way function, is there a scenario where $h(x) := g(x)_{1\ldots |x|−1}$ . I.e., $h$ returns all bits that g returns, except for the last bit., is not a one way ...
- 11
1
vote
1
answer
101
views
Post-quantum EU-CMA security from OWF-only
In the paper: "Universal One-Way Hash Functions and their Cryptographic
Applications". The following is proven: "If 1-1 one-way functions exist, then the one-way based signature scheme ...
- 223
2
votes
0
answers
39
views
Deterministically secure PRG from deterministically secure OWF
Consider the construction of "A Pseudorandom Generator from any One-way Function" [HILL99] in Hastad et al.
One way to proof pseudorandomness of this construction is by contradiction.
That ...
- 161
0
votes
2
answers
93
views
Is it One Way Function?
I am currently studying a course in cryptography, and I have this exercise about OWF.
I'm failing to prove that this is an inverter to f. Am I in the right direction at all?
Thank you!
0
votes
2
answers
79
views
Technical feasibility of a theoritical compression mechanism
Considering that quantum computers (in theory) can break\reverse some of one-way-hashes a lot faster than conventional-computers. Is it technically feasible in any theoritical (but realistic) senarion,...
- 103
1
vote
1
answer
53
views
Existence of PRGs satisfying the following weaker definition
Consider the following definition. Let $p(n) > n$ be a polynomial, and $G_n: \{0, 1\}^n \rightarrow \{0, 1\}^{p(n)}$ a PRG. Moreover, given $x \leftarrow \{0, 1\}^n$, we say $S$ is a length $n-1$ ...
- 526
1
vote
3
answers
144
views
Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?
Let $(X, Y, Z)$ be a set of binary strings of length $n$. Let random $X$ be the private key for encoding (or decoding) message random $Y$ as $Z$. Let the encryption algorithm $m$ be a matching ...
- 139
0
votes
2
answers
204
views
Is sha3 a one-way funtion
If i store sensitive stuff (e.g passwords, salted passwords, Internet protacel adresss(so i know its not tamperd with), private keys(the keys are using a portion of the key on multiple disks in ...
- 13
1
vote
0
answers
89
views
Is every pseudorandom generator a one-way function, even if the output length has no extra restrictions?
Intuitively, if we can invert a PRG, then we can easily distinguish it with random distribution by checking g(inverse(y)) = y. So every PRG is a OWF?
Unlike the problem "Is every pseudorandom ...
- 21
4
votes
0
answers
70
views
Is $g(x_1||x_2) = f(x_1 \wedge x_2)$ a one way function assuming f is a one way function
Intuitively I think not because assuming the bit string $x_1,x_2 \sim \{0,1\}^{n/2}$, $x_1 \wedge x_2$ is not uniformly random so if $g$ were still a one-way function then the fact that the definition ...
- 41
1
vote
1
answer
22
views
Proving that the length-preserving OWF does not have polynomially bounded cycle
Here a cycle is the smallest positive integer such that $f^i(x) = x$.
Formally we want to prove that if $f$ is OWF then $\forall p(.)$ and sufficiently large $n$, $Exp(cyc_f(U_n))>p(n)$ where $n$ ...
- 55
2
votes
1
answer
48
views
A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs
Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a ...
- 526
1
vote
0
answers
37
views
Construct a OWF using two functions $f : X \rightarrow Y$ and $g: X \rightarrow Y$
Given two functions f,g we have to construct h; such that h is one way function. Either f or g is a one way function. We don't know which one is a one way function. Both f and g are defined over X->...
- 11
0
votes
1
answer
62
views
How to understand the argument “if the adversary outputs x then it queries (a, x) to oracle”？
When I read the work of Dodis et al. ref1, it looks as if I have encountered a simple logical bug. (I'm not concerned with the details of secure proof techniques, but with the logic of reasoning.)
In ...
- 1
1
vote
0
answers
43
views
Existence of universal one-way function
I have some troubles with this proof from Foundations of Cryptography by Oded Goldreich p.52.
Why exactly does the parsing of x to x'x'' take quadratic time in length x'x''? If I have |x'x''|=p(|x'|), ...
- 299
0
votes
0
answers
87
views
Cryptographic functions as feature map/kernel function?
Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario.
I was not able to ...
3
votes
2
answers
211
views
Is there a notion of information theoretic one-way function?
This is not a formal but intuitive concept of one-wayness. The intuition is that if you have a combinatorial object that requires $n$ bits to describe. A one way operation introduces noise in random ...
2
votes
1
answer
1k
views
Where is the definition of one-way trap-door function used in public key cryptography
This is a rather simple question but I've been unable to find a proper answer for this online.
When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to ...
1
vote
0
answers
47
views
Composition of one-way functions and private keys
Are there any functions f, g and h, such that:
f is one-way and is used to generate an encrypted message c when applied to message m with a public key (c = f(m, N))
Original message m can only be ...
- 111
1
vote
0
answers
72
views
Cryptographic hash function to map interval onto itself
Is there any existing approach to construct perfect hash function that map [0, M) to [0, M)? It should be one to one mapping and ...
- 111
0
votes
1
answer
207
views
Suppose there exists a one-way function, show that there exists a one-way function with none of its input bit is a hardcore bit
I just learnt the definition of hardcore bit, and I have no intuition about this. I want to know what are the possible approaches to this problem.
- 11
2
votes
2
answers
317
views
Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?
In Katz's Introduction to Modern Cryptography,
Chapter 7 Practical Constructions of Symmetric-Key Primitives
In previous chapters we have demonstrated how secure encryption
schemes and message ...
- 151
1
vote
0
answers
103
views
Is the concatenation of two one-way functions a one-way function when each function takes different inputs?
Similar to this question, but having two seperate inputs for each length preserving one way function $f$ and $g$, i.e. $h: \lbrace 0,1 \rbrace^{2\kappa} \to \lbrace 0,1 \rbrace^{2\kappa}, h(x) = f(x_1)...
- 41
3
votes
1
answer
211
views
Why is RSA not a hashfunction?
The RSA-Assumption says that $(GenSP,F,SampleX)$ is one-way. So if we initialize an instance of RSA $(n,e), (n,d)$ and fairly forget the secret-key and SampleX uniformly distributed over $X, F = x^e \...
- 299
2
votes
1
answer
364
views
Is a mapping of a k bit string to another k bit string containing 1's a one way function?
I'm new to cryptanalysis and I saw in another answer to a question that $f: \lbrace0, 1\rbrace^{\kappa}\to \lbrace0, 1\rbrace^{\kappa}, f(x) = 1^{\kappa} $ is a one way function. Why is this the case? ...
- 41
2
votes
1
answer
186
views
Deterministically produce an array of indexes based on input number
Please see the Reference section below for terms.
Is there a known one-way method to produce an array of indexes, based only on two input elements:
length of the resulting array
number, used as a key ...
- 143
1
vote
1
answer
173
views
OWF from PRG and OWF
Let $f : \mathcal{U}_{2\lambda} \to \mathcal{U}_{2\lambda}$ be a OWF, and $G : \mathcal{U}_{\lambda} \to \mathcal{U}_{2\lambda}$ be a PRG with $\lambda$-bit stretch. Establish whether the following ...
- 11
1
vote
1
answer
71
views
The existence of OWFs vs $\mathbf{EXP} \neq \mathbf{BPP}$
In CRYPTO 2021, Liu and Pass published a paper with title "On the Possibility of Basing Cryptography on $\mathbf{EXP} \neq \mathbf{BPP}$.
One of the main results of this work can be interpreted ...
- 1,582
0
votes
0
answers
138
views
Is this construction a OWF?
Given the OWF function $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ and the PRG $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$, is the following function $f^*$ a OWF?
\begin{align}
f^...
- 1
1
vote
0
answers
56
views
One way function with fixed point
As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following:...
- 21
2
votes
1
answer
113
views
Prove: If there exist strong OWFs then there exist weak OWFs that aren't strong
Please help me to understand the proof of the following claim:
Assume there exist strong OWFs, then there exist functions that are
weak $\frac{2}{3}$-one-way functions, but not strong one-way ones
...
- 23
1
vote
2
answers
148
views
What are security reductions of symmetric-key algorithms?
I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
- 71
0
votes
0
answers
61
views
I am confused on how to solve this question about one way hashing
I know that I have to use decryption, but I am confused about how it breaks one-way (preimage resistance)
0
votes
0
answers
506
views
PRG implies OWF Proof
I got the idea of this proof, that since PRG expands from n to 2n, it cannot project to all {0,1}^{2n}, only to a neglible part which we can abuse to make a good distinguisher just by telling if A ...
- 299
3
votes
2
answers
136
views
What's an algorithm for laypeople to make personal passwords
I'm going to be teaching an audience about algorithms. I'd like to give them one to create unique personal passwords for websites.
They could start with the domain name of the site and their own ...
- 31
1
vote
1
answer
229
views
OWF and iO Correlation
What is the relationship between one way functions(OWF) and indistinguishable obfuscation(iO)? I know that iO exists even when P=NP and OWF don't exist. But does the existence of OWF imply iO?
0
votes
3
answers
131
views
Deciphering input from known output using SHA512?
Basic question. I'm doing self-study on hash functions.
If I insert hello as input in a SHA512 hash function (e.g. using this) I get the following hash: ...
- 101
2
votes
0
answers
139
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.
...
- 722
0
votes
0
answers
117
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?
- 259
0
votes
1
answer
85
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 ...
- 173
2
votes
1
answer
79
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
1
vote
1
answer
226
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 ...
- 11
1
vote
2
answers
136
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 &...
- 113
0
votes
0
answers
74
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 ...
- 111
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 ...
- 21
2
votes
1
answer
99
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 ...
- 31
1
vote
1
answer
220
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
218
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 ...
- 53