# Questions tagged [one-way-function]

Questions regarding easy-to-compute, but hard-to-invert functions.

32 questions
Filter by
Sorted by
Tagged with
4k views

### Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
• 4,041
539 views

• 163
385 views

### Function that is guaranteed to be one-way if one-way functions exist?

There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time. Essentially, one lists all polynomial time machines and multi-tasks over them. Is there an ...
• 7,550
293 views

### One-way functions with respect to various resource bounds

Informally, one-way functions are defined with respect to PTIME algorithms. They are computable in polynomial time but not invertible in average-case polynomial time. The existence of such functions ...
502 views

### Finite One-Way Permutation with Infinite Domain

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...
• 16.5k
492 views

### One-Way Functions vs. perfectly binding commitments

If OWFs exist, then statistically binding bit commitment is possible.[1] Is it known that if OWFs exist then perfectly binding bit commitment is possible? If no, is there a known black-box ...
363 views

### Consequences of OWFs for Complexity

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
• 2,803
378 views

• 2,208
637 views

### A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
445 views

### How is it proven that Key Exchange implies OWFs?

Page 38 says that Key Exchange implies the existence of one-way functions. When I try to work out the proof myself, I get that in the hypothetical case where there is Key Exchange but no one-way ...
260 views

### Hardness of approximation assuming the existence of one-way functions

This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP . Multiplication of two prime numbers of equal size is strong candidate for one-way ...
88 views

### Does there exist a cryptographic associative hash function?

Does there exist a function $f(x,y)$ with these properties: Computing $f(x,y)$ is in P. $f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$. $f$ is one-way (assuming P $\neq$ NP): Given the value ...
• 251
80 views

### Understanding the weak-OWF exists -> OWF exists proof

This is a proof that I've gone back to many times over the last few years and while I can read it and easily verify the steps, it seems like it's a proof, where I will always essentially forget the ...
• 151
338 views

### What are the different notions of one-way functions?

For instance, A function that is computable but not invertable in log space, Is it one-way function? What are the known definitions of one-way functions? (especially the ones that do not invoke ...
320 views

### A approximation version of the Goldreich-Levin Theorem

A little introduction The Goldreich-Levin Theorem says that let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core ...
• 445
194 views

### Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

(As for the question in the title: the answer must be no, but then I don't understand what is intended.) The Wikipedia page on one way functions states: Goldreich gives one construction of a ...
• 269
273 views

### Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
• 12.9k
68 views

### one-way functions vs. secret-coin CRHFs

Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
31 views

### Impossibility of uniform generation in random world

I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers. I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich ...
• 21
1 vote
74 views

### One way analogues of Logspace

When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$. Likewise we say a function is logspace one-way if the function is ...
• 12.9k
1 vote
70 views

### Describe Levins 'Tile Expansion' one way functon in layman terms

I'd like some explanation on the details of the 'Complete OWF' presented on this paper in 'layman terms'. See page 13 of https://arxiv.org/pdf/cs/0012023.pdf I'd prefer that the answerer had '...
• 129
155 views

### What is the simplest one-way function (in terms of boolean circuit complexity)?

What is the simplest known one-way function? By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity). (I'm trying to find ...
108 views

### Assume P != NP, does it imply that one-way functions exist?

I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
• 212
111 views

### "Partial" invert a one-way permutation

First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then ...
396 views

### One Way Boolean Function [closed]

If one way functions exist, what would the truth table of a one way boolean function look like?