Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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.

0
votes
1answer
33 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
42 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
19 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
44 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 ...
1
vote
1answer
68 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
129 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
49 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
25 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
56 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
66 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
191 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
124 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
198 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
74 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
43 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
88 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
70 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
231 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, ...
1
vote
1answer
153 views

is the XOR of PRG outputs a PRG?

I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , ...
1
vote
1answer
308 views

Prove that pseudorandom generator is a one way function

Suppose the following PRG $G : \{0,1\}^n \rightarrow \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for: $l = \omega (\log n)$ $l = 1$ For $l = \log n$, ...
4
votes
2answers
520 views

Using ChaCha20 as a PRNG with a variable-length seed

As far as I understand, the key stream of the ChaCha20 cipher may be used as a seeded PRNG, where the seed is used to set the key and the nonce. As described in RFC7539, ChaCha20 can be used with a ...
0
votes
0answers
81 views

Do zero knowledge proof systems exist for all languages in NP?

I read online that this is a true statement, but haven't been able to convince myself. Is it indeed true? and if so are there any caveats?
0
votes
0answers
46 views

How can quantum one way functions be verified (public key) while not being reversible?

A classical one-way function as said above is based on a classical infeasible mathematical task, whereas a quantum one-way function exploits the uncertainty principle which makes it impossible ...
9
votes
1answer
237 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
7
votes
1answer
1k views

Collision Resistant Hashing from One-Way Functions?

In general, can we construct a collision resistant hash function from a one-way function?
1
vote
1answer
85 views

Why can't construct PRG from one-way function and hc, but only one-way permutation

In Katz & Lindell's book, theorem 7.19 stressed that let f be a one way permutation with hard-core predicate hc. Then algorithm $G(s)=f(s)||hc(s)$ is a PRG with expansion factor $\ell(n)=n+1$. ...
0
votes
1answer
156 views

Katz/Lindell Problem 7.6

Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator? The answer ...
1
vote
2answers
246 views

One Way Function - How to Prove?

Function $f$ is a length shortening function. It reduces to log of size of input, i.e $|f(x)|/\log(|x|) \leq$ $a\ positive\ constant$. Is this a one way function? Edit: $f$ is any function. Unknown ...
1
vote
1answer
69 views

Probability amplication in OWF without hardcore bits

We know that OWF $f$ such that none of its bits are hardcore exists. We also know that given an algorithm that solves a problem with non-negligible probability, we can repeat it many times and take ...
1
vote
0answers
89 views

Polynomially many iterations of one way permutation

I have seen that the existence of weak OWFs implies the existence of strong OWFs. It comes from repeating the weak OWF polynomially many times on different random inputs. However, I have a different ...
0
votes
0answers
78 views

Can we come up with a counterexample?

Suppose $\epsilon$ : $N\in~ [0,1]$ is not a negligible function. Does it follow that for some polynomial $p$ (where $p(k)$ > 0 for all $k$) and some $k_0$, $\epsilon(k) > \frac{1}{p(k)}$ for all $k ...
0
votes
0answers
91 views

Is this a one-way function?

Let $f$ be length preserving one way functions, i.e. $|f(x)|$ = $|x|$. Then, ${f^{'}_{p,h,y}}$ = $h^{x_1}y^{x_2} mod ~p$. Here $h,y$ <- ${Z^{*}_{p}}$ and $x_1,x_2$ <- $Z_{p-1}$ and $p$ is a ...
3
votes
1answer
342 views

Is the concatenation of two one-way functions a one-way function?

Suppose we are given two one way functions $f$ and $g$. We define a new function h that is the concatenation of f and g. That is, $h(x)=f(x), g(x)$, where the comma indicates concatenation. We want to ...
2
votes
1answer
243 views

How to prove that a one way function is uninvertible?

Suppose we define the "hard to invert" part in the definition of one-way functions differently: A function $\ f : \{0,1\}^* \to \{0,1\}^*$ is called uninvertible if it is easy to compute $f$ but ...
0
votes
3answers
487 views

Secure and efficient encryption of a continuous data stream on behalf of a third party using asymmetric cryptography

I want to design an API-based system that is able to securely encrypt a stream of data received on behalf of an external user in such a way that the data can only be decrypted using a secret that only ...
2
votes
1answer
154 views

Proof that a given function is not a OWF

I'm currently learning about one-way functions. I have a book with the following exercise (Sadly there is no solution in the book...) Let $g\colon \{0,1\}^n \to \{0,1\}^n$ be a one way function. ...
5
votes
1answer
255 views

Relationship between existence of OWFs and OWPs

OWPs are bijective OWFs, so every OWP is a OWF, but not the other way around. However, I'm wondering what the relationship between the existence of both types of functions is. Obviously if one ...
0
votes
0answers
64 views

Is there a one-way key for data depersonalization?

Given a secure database that continues to receive updates on user data, and permission from the users (that complies with laws and regulations in effect) to depersonalize that data, export to another ...
2
votes
2answers
208 views

Is there a standard one way function that does not produce collision

Is there any standard or accepted one way function that does not produce collisions? I'm not looking for hash functions. Does that make sense at all? for example given string with length ...
1
vote
1answer
241 views

Using states of a double pendulum as a one-way function [closed]

Hello, as a non-professional (at all) but a fan of cryptography, I have one idea and I would love to hear your input on it. As I understand cryptographic functions they should have following ...
0
votes
1answer
136 views

Sub exponentially hard OWF , PRF and iO

I'm currently reading the work "Obfuscation of probabilistic circuits and Applications' by Canetti Lin Tessaro and Vaikuntanathan 2015. It says sub exponentially hard OWF implies sub exponentially ...
6
votes
3answers
330 views

Standard lightweight one-way hash functions for IoT devices

What are the standard lightweight one-way hash functions used in current Internet of Things devices? I could find some proposal of hash functions in conference papers but I want to know the ones ...
8
votes
1answer
349 views

Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $f$ is a one-way function (OWF), and let $||$ denote string concatenation. Consider the function $g$ defined by $g(x) = f(x) || f(f(x))$. It is easy to prove that $g$ is a OWF as well, ...
4
votes
1answer
278 views

Relation between “P is not equal to NP” and “Existence of One-Way Function”

We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a polynomial time computable function that is hard ...
-1
votes
2answers
64 views

Is there some encryption scheme which is getting increase “noise” and then can't be indecipherable at last?

There's some function f() which has some "error", so "error" grows when decryption is failed every time and then finally it won't be able to decrypt. But, the "error" will be initialized when its ...
0
votes
0answers
38 views

OWF which flips input bits with constant probability

Consider length-preserving function F, which flips each bit of input X with some constant probability (i.e. Pr=0.6). Is F - a one way function? Given F(X) it's hard to find such X', for which F(X) = ...
6
votes
2answers
113 views

OWF by encrypting a constant?

This question is a generalization of this old, unanswered question. Suppose we're given a strong PRP $E:\mathcal K\times\mathcal M\to\mathcal C,(K,M)\mapsto C=E(K,M)$. Suppose further we pick a ...
8
votes
1answer
170 views

How would Private-key Cryptography be if we use quadratic polynomials as OWF's?

I am aware that one-way functions (OWF's) are the core of many of the primitives in symmetric crypto, in the sense that many cryptographic primitives in the private-key setting can be constructed from ...
0
votes
1answer
72 views

worst-case OWF from weak OWF

A function $f$ is a worst-case OWF if there is no adversary $\mathcal{A}$ such that $$\forall x,Pr[y=f(x): f(\mathcal{A}(y))=y]=1$$ A weak OWF is a function that the probability of inverting it is ...
0
votes
1answer
225 views

Weak one way functions from strong one way functions

I'm stuck in a simple question about weak one way functions. Suppose $f(x)$ is strong one way, is $g(x)=f(x)_0$, i.e. taking the first bit of $f(x)$ a weak one way function? Intuitively, it is, ...