# 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.

238 questions
Filter by
Sorted by
Tagged with
39 views

### Is $f(x)=g(x)||g(\bar{x})$ a one-way function where $g(x)$ is a OWF?

Given that $g$ is a OWF, is $f(x)=g(x)||g(\bar{x})$ necessarily also a OWF?
52 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: ...
64 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. ...
47 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?
42 views

### Trapdoor One Way Functions [closed]

If y = F(x) is a relatively practical One Way Function. How can you construct a Trapdoor One Way Function using F?
58 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 ...
83 views

### One way text→text function

I need a way to map some printable text to other printable text. E.g.: Ian BoydKcp Zbas Notice some of the important ...
60 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 ...
53 views

99 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?
20 views

### Is it hard to determine an automorphism when the mapped value by several compositions of the automorphism is given

Generalization of the Discrete logarithm problem to non-abelian groups is discussed by many authors. One of the generalizations is shown in MOR cryptosystem as in the below link, by considering the ...
74 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 ...
46 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 ...
137 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&...
110 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 ...
42 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
91 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-...
71 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 ...
54 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 ...
108 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 ...
48 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 ...
313 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 ...
167 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’...
50 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 ...
75 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.
7k 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?
135 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 ...
92 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?
61 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'...
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 ...
91 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 ...
173 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 ...
73 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)$ ...
208 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 ...
196 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)=...
78 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? ...
263 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), ...
### 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 ...