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
3
votes
1answer
62 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
0answers
44 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
59 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
85 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
20 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
35 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
43 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
74 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
33 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
69 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
179 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
60 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
64 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
15 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
45 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
47 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
83 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
93 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
48 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
122 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
56 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
112 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(...
27
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
90 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
71 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
161 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
87 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
74 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
187 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
151 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
336 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
38 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. ...
1
vote
3answers
91 views

Composition of weak one way function is not a strong one way function

Given $f(x)$, a weak one-way permutation, how to prove that $f^T(x)$ is not a strong one-way function? Here $f^T$ denotes $T$ times self composition of $f$ and $T$ is a polynomial in input length.
1
vote
1answer
43 views

Why the output length of a KDF should be the same as the underlying OWF?

Quote: The chosen output length of the key derivation function SHOULD be the same as the length of the underlying one-way function output. Could someone please help explain the benefits and ...
0
votes
1answer
64 views

What does approved one-way function mean?

In one of their documents, NIST recommends using an approved one-way function, followed by a list of such functions, such as HMAC, KMAC, etc.. However, the wikipedia page says: Unsolved problem in ...
2
votes
1answer
203 views

What is the one way function in ECC?

In the RSA algorithm it's the the integer factorisation problem, it's easy to multiply the two large primes to generate n, but given just n it's very difficult to find the constitutent primes. In the ...
1
vote
1answer
210 views

Is there a deterministic one-way collision-free crypto algorithm?

I use usernames encrypted using a function f as ids of records. Users see records identified by f(username). I must not know real usernames. I want to be protected from attack when adversary who has ...
2
votes
0answers
64 views

Are there any one-way operations that could be used for Diffie-Hellman post-quantum? (See criteria)

With quantum-computers looming, there is a need for Public Key Cryptosystems that can withstand attacks by quantum-computers. Are there any known one-way operations that fit the following criteria? ...
1
vote
1answer
45 views

DLP-based keyed one-way function

I am trying to understand if it possible to use DLP to build a keyed one-way function with the following properties: $H_a(H_b(M)) = H_c(M)$, where $a$ and $b$ are the keys, and $c=a*b$ The output of ...
1
vote
1answer
132 views

Function families from lattices

On this course, Micciancio talks about function families (functions parametrized by some value) that can be used in cryptography. On page 2, he presents the following function family parametrized by ...
2
votes
0answers
128 views

Concatenating a one way function

Let $f$ be a length preserving one way function. Show that $g(x)=f(x)|x_{[1:\log n]}$, where $|$ indicates concatenation and $x_{[1:\log n]}$ indicates the first $\log n$ bits of x, is also a one way ...
4
votes
1answer
348 views

Collision-free one-wayish function mapping 32 bit to 32 bit

As simple as it may sound, I was unable to find a collsion free one-way(ish) function which takes 32 bits of input and produces 32 bits of output. I apologize if I just didn't knew the right keywords ...
1
vote
1answer
216 views

Hash function composition - security level

When using two hash functions, g(x)=SHA-512 and f(x)=MD5 g(x) has 512 bit output (using salt) f(x) has 128 bit output. Let's say that z(x)=f(g(x)) meaning the output is 128 bit long. The Question: ...
1
vote
1answer
490 views

Is Diffie Hellman key exchange based on one-way function or trapdoor function?

I have a question for my information security lab, which I am not able to find online. As the title says, is Diffie Hellman key exchange based on a one-way or a trapdoor function? In case of RSA I ...
3
votes
1answer
166 views

How to show that the following function is not a OWF?

Given F, which is a Pseudo Random Permutation, I need to prove that the following function f is not a OWF: f(x, y) = Fx(y) My first thought would be to create an adversary which tries and compute Fx-...
0
votes
1answer
57 views

Signature scheme against an unbounded rival

I've seen this: Can a computationally unbounded adversary break any public-key encryption scheme? And I've read the following theorem: Theorem (Lamport, GMR, Naor-Yung, Rompel, Goldreich) If one-way ...
3
votes
1answer
105 views

Practical OWP of the set of $k$-bit bitstrings for low $k$

Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party ...
1
vote
1answer
82 views

What is the purpose of having a one-way function also be a permutation on it's on domain?

From a cryptographic sense, what value is added from setting the domain to be the image in the mapping?
0
votes
2answers
386 views

Making a one-way function harder to reverse

Let's suppose that for a crypto protocol a 32-byte-to-32-byte one-way function is needed. Proposals are: $\textrm{sha256}(x)$ $\textrm{hmac}(\textrm{sha256}, x, x)$ $\textrm{hmac}(\textrm{sha256}, x, ...