Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
32 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 ...
user avatar
1 vote
0 answers
61 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 ...
user avatar
0 votes
1 answer
46 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.
user avatar
2 votes
2 answers
124 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 ...
user avatar
  • 151
1 vote
0 answers
37 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)...
user avatar
3 votes
1 answer
146 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 \...
user avatar
2 votes
1 answer
345 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? ...
user avatar
2 votes
1 answer
139 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 ...
user avatar
  • 143
0 votes
0 answers
58 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 ...
user avatar
  • 1
1 vote
1 answer
65 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 ...
user avatar
  • 1,532
0 votes
0 answers
124 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^...
user avatar
1 vote
0 answers
45 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:...
user avatar
  • 21
0 votes
0 answers
30 views

Building an adversary for a OW-CCA game

Let K_rsa be a RSA genertor with associated security parameter k >= 1024. Let game OW-CCA_Krsa be as follows: How can I build a O(k^3)-time adversary A making at most 2 queries to Invert and ...
user avatar
2 votes
1 answer
66 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 ...
user avatar
  • 23
1 vote
2 answers
106 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 ...
user avatar
0 votes
0 answers
59 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)
user avatar
0 votes
0 answers
125 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 ...
user avatar
0 votes
0 answers
23 views

Securely and Deterministically select a combination of objects from hash (cryptographic seed)

I am working on a project that is using a bit-commitment concept to authenticate information. I need to select a combination of objects securely from a secure hash, then distribute that hash later. ...
user avatar
  • 1
2 votes
2 answers
116 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 ...
user avatar
1 vote
1 answer
189 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?
user avatar
0 votes
3 answers
82 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: ...
user avatar
2 votes
0 answers
98 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. ...
user avatar
  • 511
0 votes
0 answers
76 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?
user avatar
  • 249
0 votes
1 answer
67 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 ...
user avatar
  • 99
2 votes
1 answer
71 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 ...
user avatar
0 votes
0 answers
53 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 $...
user avatar
  • 1
1 vote
1 answer
198 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 ...
user avatar
  • 11
1 vote
2 answers
118 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 &...
user avatar
0 votes
0 answers
64 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 ...
user avatar
  • 111
2 votes
0 answers
42 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 ...
user avatar
  • 21
2 votes
1 answer
78 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 ...
user avatar
1 vote
1 answer
114 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
user avatar
4 votes
2 answers
165 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 ...
user avatar
2 votes
1 answer
75 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-...
user avatar
  • 197
1 vote
0 answers
76 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 ...
user avatar
0 votes
1 answer
103 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?
user avatar
  • 707
2 votes
2 answers
140 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 ...
user avatar
  • 652
0 votes
1 answer
47 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 ...
user avatar
  • 155
0 votes
0 answers
145 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&...
user avatar
4 votes
1 answer
154 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 ...
user avatar
0 votes
1 answer
58 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
user avatar
0 votes
1 answer
168 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-...
user avatar
0 votes
0 answers
83 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 ...
user avatar
0 votes
0 answers
66 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 ...
user avatar
5 votes
1 answer
120 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 ...
user avatar
0 votes
0 answers
63 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 ...
user avatar
3 votes
2 answers
501 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 ...
user avatar
3 votes
1 answer
245 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’...
user avatar
1 vote
0 answers
51 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 ...
user avatar
  • 959
0 votes
1 answer
92 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.
user avatar

1
2 3 4 5 6