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
101 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
58 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
134 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
55 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
63 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
85 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
169 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
87 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
154 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
92 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
49 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
32 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
81 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
82 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 ...
2
votes
2answers
322 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
37 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
74 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
136 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
201 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
294 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
110 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, which contains ...
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
48 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
75 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$ ...
1
vote
1answer
120 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
78 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
80 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
225 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
73 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
89 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
63 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
99 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
112 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
174 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
68 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
261 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
63 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 ...
5
votes
1answer
1k views

One-way functions and P=NP

This site contains various discussions of one-way functions and their relation to P versus NP. Some of these discussions use a language $L=\{(x',y) ~\mid~ x'\le x \text{ and } f(x)=y \}$, where $f:\...
-1
votes
2answers
169 views

Determining whether functions are one-way or not

I read a book about one-way function. In this book, I saw 2 exercises that I can't understand and don't know how to solve. Can anyone help me to solve these? Is $f(x,y)=x+y$ a one way function? Is $f(...
30
votes
5answers
7k views

Other than password hashes, are there other uses for non-reversible crypto

Hashing is useful for checking that an input matches expectations without giving away the stored expected version - so confirming passwords etc. But are there other use cases? In general, ...
-2
votes
1answer
116 views

Prove: If there exist OWF then there exist OWF $f$ such that $ \forall x$ $f(x,x)=x$

I wrote the definition, but I don't know what should I do. Can you help me? I want to prove the following: If there exist one-way function then there exist a one-way function $f$ such that for every ...
2
votes
0answers
141 views

Is the concatenation of one-way compression functions one-way?

Given two independently keyed compression functions $h_1$ and $h_2$: $h_b(x): \{0,1\}^{3n} \to \{0,1\}^{n}$, where $b \in \{1,2\}$. Let $h(x) = h_1(x) \| h_2(x)$. Given at least one of $h_1$ and $...
3
votes
0answers
317 views

Can we construct a PRF directly from a one way permutation function?

In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
0
votes
1answer
96 views

Newbie question: one-way functions in cryptography

I'm reading this article on the basics of cryptography and it says that the main principle is about taking such an algorithm that knowing the end result and the algorithm, an eavesdropper wouldn't be ...
3
votes
0answers
82 views

If trapdoor OWF exists then f is a trapdoor OWF, is there such a construction?

Is there a known construction of f, such that given that a trapdoor OWF exists then f is a trapdoor OWF, so we can construct inefficient cryptomania, ala Levin's construction for minicrypt in "The ...
1
vote
2answers
342 views

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

Let $g$ be a one-way function, and let $f(x) = g(x) ⊕ g(\bar{x})$ (where the bar over x denotes bitwise complement). Is $f$ necessarily a one-way function?
1
vote
2answers
272 views

Clarification of one-way property of hash functions

One-way property: computationally infeasible to find data mapping to specific hash The definition above is a little vague, if we have h(x) = floor(log(x)), ...
4
votes
1answer
542 views

Is a one-way function pseudorandom?

For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second ...
0
votes
1answer
41 views

Concept of hashing a group of data and validating if a value exists within the group

When learning about cryptography and hashing, I remember seeing a concept where you could hash a number of values (ID's for example) and then validate against the hash, not storing the original IDs. ...