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
2
votes
1answer
96 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
0answers
42 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
1answer
60 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.
13
votes
5answers
6k 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
1answer
114 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
0answers
50 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
0answers
56 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
2answers
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
0answers
57 views

Composition of an injective/surjective function and a one way function is still a one way function

recently I have been reading about OWF and realized that composition of two OWFs g,f are not necessarily a OWF. However if I modify the question a little bit and fix g to be a injective function, and ...
0
votes
1answer
73 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
0answers
40 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
1answer
80 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
1answer
119 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
1answer
64 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? ...
2
votes
1answer
165 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
1answer
62 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
1answer
64 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
1answer
88 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
1answer
184 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
1answer
96 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
1answer
166 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
1answer
95 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
1answer
53 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
0answers
53 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 ...
1
vote
1answer
119 views

Question about the Proof of “Pseudorandom generators imply one-way functions” in “Foundations of Cryptography”

In "Foundations of Cryptography, Volume 1" by Oded Goldreich, chapter 3.3.6 states the following theorem: Let $G$ be a pseudorandom generator with expansion factor $l(n) = 2n$. Then the function $f\...
1
vote
0answers
91 views

One way authentication

I need an advice: I found a paper describing an authentication exchange using a PSK done in this way: A ---> B "A" and "B" have a common PSK. "A" extracts a random number and then send 2 ...
3
votes
2answers
491 views

Would SHA-256(SHA-256(x)) produce collisions?

Was reviewing some Bitcoin public-key hash literature and the use of RIPEMD-160 and the SHA-256 as below: RIPEMD160(SHA256(ECDSA_publicKey)) The Proof-of-work ...
1
vote
1answer
38 views

W-OTS+ one-wayness property

I am reading the "W-OTS⁺ – Shorter Signatures for Hash-Based Signature Schemes," by Andreas Hülsing, and I am stuck in understanding the success probability of an adversary, $\mathcal A$, against the ...
3
votes
1answer
81 views

General factoring and one-way functions

Let a function $f$ be one-way, if there exists a probabilistic polynomial time algorithm to find the preimage of $y = f(x)$ for uniformly chosen $x$ with non-negligible probability. Define the ...
3
votes
1answer
144 views

Is $g(x)$, the first $(n -\log(n))$ bit of $f(x)$, a (strong) one-way function?

Given a (strong) n-bit-by-n-bit one-way function $f$, is $g(x)$, the first $(n - \log(n))$ bit of $f(x)$, a (strong) one-way function, too? When reading Prof. Sanjam Garg's Graduate Cryptography ...
2
votes
1answer
346 views

Collision resistant hash function implies one-way function

I'm struggling to give a formal proof that $CRH \implies OWF$ using the definition below. Intuitively, I see why a $CRH$ would be "hard to predict" and might be used as a $PRF$, but I'm unable to ...
1
vote
1answer
670 views

Toy one-way hash function for six digit number

I need to copy some data from a secure server to my laptop to work on it with a program (this description is very vague, I know). The data have six digit employee numbers and we are strictly ...
2
votes
1answer
120 views

pwd-hash like algorithm which can be computed on paper

"Common password problem" is well known problem, when user uses one password for many resources (web sites, logins to computers, etc...) For example, if one web site loses it' database, ...
0
votes
0answers
23 views

Pratical implementation of a Sibling Intractable Function

I have seen in several places the statement "k-SIFF can be constructed from any one-way function", but I cannot understand how this is realized in practice? For instance, in Sibling Intractable ...
0
votes
0answers
51 views

Lower bound for the length of a one-way function's value?

Let $f\colon \{0,1\}^n \to \{0,1\}^n$ be a length-preserving (i.e., $|f(x)| = |x|$) one-way function. Then, for $k \in \mathbb{N}$ and $m = n^k$, the function $g\colon \{ 0,1\}^m \to \{0,1\}^n$ with $$...
3
votes
0answers
80 views

Does weak hardcore bit(s) implies strong hardcore bit(s)?

It is well known that weak OWF implies strong OWF by concatenating several evaluations of weak OWF (see e.g. here), where weak OWF is defined as $ \exists $ poly $Q$, $\forall$ PPT $\mathcal A$ such ...
1
vote
1answer
156 views

How simple hash provide message authentication?

This structure provides message authentication. My question is if someone finds the key he can simply change the message and compute new hash according new message and send it to the receiver. If so, ...
0
votes
1answer
98 views

Difference between one-way encryption, Transparent data encryption (TDE) and data encryption

What is the main difference between one-way encryption, Transparent data encryption (TDE) and data encryption? If one needs to store passwords or credit card details in the DB, which one is best to ...
1
vote
2answers
83 views

Is a random permutation “hiding”?

Let's say I tell you $G: \mathbb{F} \rightarrow \mathbb{F}$ is a random permutation (some finite field). Does that mean: $G$ is one-way, so that if I give you $G(x)$, it is infeasible to determine ...
4
votes
2answers
252 views

Assumptions on one-way functions

What are the assumptions we make to propose a one-way function? I only know of some number theoretic assumptions, but what are the other assumptions you can possibly make, which if true, would imply ...
3
votes
0answers
81 views

Impossible to construct collision resistant hash function from one way function

[Simon 98] showed that it is impossible to construct collision resistant hash function from one way functions in a black-box way. I read the paper but barely understood it. Is there any source, where ...
2
votes
1answer
91 views

In the proof that weak OWFs imply strong OWFs, why must the position of $y$ be random?

When proving weak OWFs imply the existence of strong OWFs, the standard construction goes by concatenating several applications of the weak OWF (see, e.g., here). That is, given a weak OWF $f$, the ...
0
votes
0answers
16 views

Order preserving hashes [duplicate]

Are there hash functions that dynamically take integers a and b, and output h(a) and h(b) such that if a>b we have h(a) > h(b)?
1
vote
0answers
70 views

Simple reduction of commitments to one way functions

I am looking for an explicit and simple reduction of commitments to one way functions. I don't care about the number of rounds, only simplicity. I am aware of the simple reductions you can find in ...
1
vote
1answer
150 views

How to prove that weak one way functions cannot have polynomial-sized ranges?

I figured how to show that strong OWFs cannot have polynomial sized ranges. But I am unable to prove the same for weak OWFs.
1
vote
1answer
124 views

A modification of the Blum-Micalli construction

Consider the following modification of the Blum-Micalli construction (denoted by BM): $G_l(x) = f^l(x) || BM^l(x)$ I am asked the following questions about it: Show it is a PRG of fixed stretch ...
2
votes
1answer
182 views

Moni Noar One Way Function: What does input is partioned mean?

I am trying to understand An Implementation of Efficient Pseudo-Random Functions. There, the following hash function is defined: We define $\hat{h}=\hat{h}_{r}: {\{0,1\}}^* \rightarrow {\bf Z}_R$ ...
0
votes
1answer
82 views

One-way function with combination sets as output / image

One-way functions generally operate on bit strings, for the input and the output. Are there any examples of one-way functions that produce a combination set in output? Let's call this function $f$. ...
4
votes
1answer
315 views

Simple explanation of weak one way function

I find difficult to understand what a weak one way function is. From textbooks: $\exists$ poly $Q$, $\forall$ PPT $\mathcal{A}$ such that: $$\Pr[x\leftarrow\{0,1\}^n; y=f(x); \mathcal{A}(1^n, f(x))=...
2
votes
1answer
79 views

Given a SHA-256 message block, is it possible to undo the transformation of the internal state?

Consider the transformation described in section 6.2 of RFC4634 ("US Secure Hash Algorithms (SHA and HMAC-SHA)"). Given the message block M(i), and hence the ...

1
2 3 4 5