Skip to main content

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
1 vote
2 answers
122 views

Looking for a lightweight hashing algorithm

I'm looking for a hashing algorithm with some unique properties: Most important: It has to be small. Ideally ~400 bytes of x86 assembly Resistant to preimage & collision attacks with no known ...
Mark Nelson's user avatar
0 votes
0 answers
43 views

One way function bulit by singular matrices

Our one-way function $F:\mathbb{F}_q^{n\times n}\times \mathbb{F}_q^{n\times n}\to\mathbb{F}_q^{n\times n}$ differs from traditional OWFs, which focus on being hard to invert. Instead, ours aims to be ...
X.H. Yue's user avatar
  • 392
1 vote
0 answers
61 views

Do one-way functions imply target collision resistance?

I'm reading the paper: One-Way Functions are Necessary and Sufficient for Secure Signatures, by John Rompel, which gives answer to the question in the title; but I'm confused about these sketched ...
Zijun Zhuang's user avatar
1 vote
0 answers
39 views

One Way Functions with Non-Uniform Inputs

It is well-known that a One-Way Function is hard to invert on uniformly random inputs. As per Wikipedia, for [sic] all randomized algorithms $F$, all positive integers $c$ and all sufficiently large $...
Lt. Commander. Data's user avatar
0 votes
0 answers
44 views

One-way function constructed by multivariable polynomials

Although the conjecture regarding the existence of one-way functions remained open, there are numerous NP-based methods for constructing diverse one-way functions, including DL, lattice, and subset ...
X.H. Yue's user avatar
  • 392
1 vote
1 answer
62 views

Can I generalize trapdoor information to trapdoor functions for one-way function?

We know that, for one-way function $y=f(x)$, it's hard to compute $x=f^{-1}(y)$, but there exists an efficient algorithm $A(y,t)=f^{-1}(x)$ once we know the trapdoor information $t$. I'm wondering, ...
Marc_12's user avatar
  • 41
0 votes
0 answers
42 views

On Constructing Universal One-Way Hash Functions from Arbitrary One-Way Functions | Claim 9 Proof Clarification

I'm reading Katz and Koo's paper that constructs UOWHFs from OWFs. I'm trying to rigorously understand every proof, and I'm having a hard time understanding an equality. This lemma is trying to prove ...
Boran Erol's user avatar
5 votes
0 answers
455 views

Public one-way bijection [duplicate]

What methods do we know to construct a function $f:D\to D$ with domain $D=[0,n)\cap\mathbb N$ (thus $n\in\mathbb N$ elements); demonstrably surjective (thus bijective since $D$ is finite); with ...
fgrieu's user avatar
  • 142k
2 votes
1 answer
40 views

About Levin's constructure of universal OWF, why $\log n$ bits TM can work?

In Pass's lecture notes 2.13 section, a universal OWF is constructed. But I have some confusion about: Let $M_g$ be the smallest machine which computes function $g$. Since $M_g$ is a uniform ...
Yang's user avatar
  • 78
0 votes
0 answers
82 views

Are there examples of XOR of OWF still being OWF?

I am trying to prove that given two OWF $f$ and $g$ the function $h$ given as: $$\text{h}(x)=(\text{f}(x),\text{g}(x))$$ is not always OWF. As a counter example I am considering $\text{f}(x) = \text{g}...
tehger's user avatar
  • 1
4 votes
0 answers
107 views

Impossibility of uniform generation in random world

I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich when I got stuck on a sentence. First of all, they define a polynomial relation that is any relation ...
Pur2all's user avatar
  • 60
0 votes
0 answers
110 views

What is the AEGIS design rationale for one way rounds and slow diffusion?

The AEGIS reference document doesn't specify why the authors chose a slow diffusion process and a one way round transformation. As you can see the previous state is XORed with AES applied to itself ...
LightTunnelEnd's user avatar
5 votes
1 answer
479 views

What is a non-OWF?

We know that A function $f:\Bbb Z_2^n \longrightarrow\Bbb Z_2^m$ is a (strong) one-way function (OWF), if: $f$ can be computed by a PT algorithm. Equivalently, there exists a PPT algorithm that on ...
Chris's user avatar
  • 236
0 votes
1 answer
69 views

On the construction and notation of a certain OWF

I am studying a little bit about one-way functions from Dr Goyal's notes. He constructs the following OWF: Let $D=\Bbb Z_2^{n^3}$ and $R=\Bbb Z_2^{2 n}$. Given $x \in D$, $f$ interprets $x$ as a set $...
Chris's user avatar
  • 236
1 vote
1 answer
114 views

Worst-case one-way permutations under P different from NP

This is probably obvious, but I cannot find it anywhere, since all textbooks define OWFs for average-case hardness. Do we known if worst-case one-way permutations exist assuming $\mathbf{P} \neq \...
Noel Arteche's user avatar
1 vote
0 answers
165 views

Does removing just last bit from output of one way function change its one wayness?

If $g(x)$ if length preserving one way function, is there a scenario where $h(x) := g(x)_{1\ldots |x|−1}$ . I.e., $h$ returns all bits that g returns, except for the last bit., is not a one way ...
truncet's user avatar
  • 11
2 votes
1 answer
144 views

Post-quantum EU-CMA security from OWF-only

In the paper: "Universal One-Way Hash Functions and their Cryptographic Applications". The following is proven: "If 1-1 one-way functions exist, then the one-way based signature scheme ...
Ilk's user avatar
  • 233
2 votes
0 answers
50 views

Deterministically secure PRG from deterministically secure OWF

Consider the construction of "A Pseudorandom Generator from any One-way Function" [HILL99] in Hastad et al. One way to proof pseudorandomness of this construction is by contradiction. That ...
Nicholas Brandt's user avatar
0 votes
2 answers
156 views

Is it One Way Function?

I am currently studying a course in cryptography, and I have this exercise about OWF. I'm failing to prove that this is an inverter to f. Am I in the right direction at all? Thank you!
Niv Peretz's user avatar
0 votes
2 answers
84 views

Technical feasibility of a theoritical compression mechanism

Considering that quantum computers (in theory) can break\reverse some of one-way-hashes a lot faster than conventional-computers. Is it technically feasible in any theoritical (but realistic) senarion,...
Giorgos Xou's user avatar
1 vote
1 answer
56 views

Existence of PRGs satisfying the following weaker definition

Consider the following definition. Let $p(n) > n$ be a polynomial, and $G_n: \{0, 1\}^n \rightarrow \{0, 1\}^{p(n)}$ a PRG. Moreover, given $x \leftarrow \{0, 1\}^n$, we say $S$ is a length $n-1$ ...
user918212's user avatar
1 vote
3 answers
160 views

Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?

Let $(X, Y, Z)$ be a set of binary strings of length $n$. Let random $X$ be the private key for encoding (or decoding) message random $Y$ as $Z$. Let the encryption algorithm $m$ be a matching ...
virtuolie's user avatar
  • 139
0 votes
2 answers
362 views

Is sha3 a one-way funtion

If i store sensitive stuff (e.g passwords, salted passwords, Internet protacel adresss(so i know its not tamperd with), private keys(the keys are using a portion of the key on multiple disks in ...
Downvoter's user avatar
1 vote
0 answers
123 views

Is every pseudorandom generator a one-way function, even if the output length has no extra restrictions?

Intuitively, if we can invert a PRG, then we can easily distinguish it with random distribution by checking g(inverse(y)) = y. So every PRG is a OWF? Unlike the problem "Is every pseudorandom ...
Wan's user avatar
  • 21
4 votes
0 answers
96 views

Is $g(x_1||x_2) = f(x_1 \wedge x_2)$ a one way function assuming f is a one way function

Intuitively I think not because assuming the bit string $x_1,x_2 \sim \{0,1\}^{n/2}$, $x_1 \wedge x_2$ is not uniformly random so if $g$ were still a one-way function then the fact that the definition ...
CHTM's user avatar
  • 141
1 vote
1 answer
35 views

Proving that the length-preserving OWF does not have polynomially bounded cycle

Here a cycle is the smallest positive integer such that $f^i(x) = x$. Formally we want to prove that if $f$ is OWF then $\forall p(.)$ and sufficiently large $n$, $Exp(cyc_f(U_n))>p(n)$ where $n$ ...
Archies's user avatar
  • 65
2 votes
1 answer
49 views

A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs

Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a ...
user918212's user avatar
1 vote
0 answers
44 views

Construct a OWF using two functions $f : X \rightarrow Y$ and $g: X \rightarrow Y$

Given two functions f,g we have to construct h; such that h is one way function. Either f or g is a one way function. We don't know which one is a one way function. Both f and g are defined over X->...
anon1234's user avatar
0 votes
1 answer
79 views

How to understand the argument “if the adversary outputs x then it queries (a, x) to oracle”?

When I read the work of Dodis et al. ref1, it looks as if I have encountered a simple logical bug. (I'm not concerned with the details of secure proof techniques, but with the logic of reasoning.) In ...
Duan's user avatar
  • 1
1 vote
0 answers
47 views

Existence of universal one-way function

I have some troubles with this proof from Foundations of Cryptography by Oded Goldreich p.52. Why exactly does the parsing of x to x'x'' take quadratic time in length x'x''? If I have |x'x''|=p(|x'|), ...
killertoge's user avatar
0 votes
0 answers
89 views

Cryptographic functions as feature map/kernel function?

Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario. I was not able to ...
Omar Shehab's user avatar
3 votes
2 answers
247 views

Is there a notion of information theoretic one-way function?

This is not a formal but intuitive concept of one-wayness. The intuition is that if you have a combinatorial object that requires $n$ bits to describe. A one way operation introduces noise in random ...
Mohammad Al-Turkistany's user avatar
2 votes
1 answer
2k views

Where is the definition of one-way trap-door function used in public key cryptography

This is a rather simple question but I've been unable to find a proper answer for this online. When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to ...
Crypto Newbie's user avatar
1 vote
0 answers
51 views

Composition of one-way functions and private keys

Are there any functions f, g and h, such that: f is one-way and is used to generate an encrypted message c when applied to message m with a public key (c = f(m, N)) Original message m can only be ...
lanzalibre's user avatar
1 vote
0 answers
74 views

Cryptographic hash function to map interval onto itself

Is there any existing approach to construct perfect hash function that map [0, M) to [0, M)? It should be one to one mapping and ...
Tomilov Anatoliy's user avatar
1 vote
1 answer
512 views

Suppose there exists a one-way function, show that there exists a one-way function with none of its input bit is a hardcore bit

I just learnt the definition of hardcore bit, and I have no intuition about this. I want to know what are the possible approaches to this problem.
CaulCaul's user avatar
2 votes
2 answers
394 views

Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
Tim's user avatar
  • 151
2 votes
0 answers
144 views

Is the concatenation of two one-way functions a one-way function when each function takes different inputs?

Similar to this question, but having two seperate inputs for each length preserving one way function $f$ and $g$, i.e. $h: \lbrace 0,1 \rbrace^{2\kappa} \to \lbrace 0,1 \rbrace^{2\kappa}, h(x) = f(x_1)...
amlearn369's user avatar
3 votes
1 answer
250 views

Why is RSA not a hashfunction?

The RSA-Assumption says that $(GenSP,F,SampleX)$ is one-way. So if we initialize an instance of RSA $(n,e), (n,d)$ and fairly forget the secret-key and SampleX uniformly distributed over $X, F = x^e \...
killertoge's user avatar
2 votes
1 answer
370 views

Is a mapping of a k bit string to another k bit string containing 1's a one way function?

I'm new to cryptanalysis and I saw in another answer to a question that $f: \lbrace0, 1\rbrace^{\kappa}\to \lbrace0, 1\rbrace^{\kappa}, f(x) = 1^{\kappa} $ is a one way function. Why is this the case? ...
amlearn369's user avatar
2 votes
1 answer
222 views

Deterministically produce an array of indexes based on input number

Please see the Reference section below for terms. Is there a known one-way method to produce an array of indexes, based only on two input elements: length of the resulting array number, used as a key ...
Dima's user avatar
  • 143
1 vote
1 answer
239 views

OWF from PRG and OWF

Let $f : \mathcal{U}_{2\lambda} \to \mathcal{U}_{2\lambda}$ be a OWF, and $G : \mathcal{U}_{\lambda} \to \mathcal{U}_{2\lambda}$ be a PRG with $\lambda$-bit stretch. Establish whether the following ...
ellemr's user avatar
  • 11
1 vote
1 answer
75 views

The existence of OWFs vs $\mathbf{EXP} \neq \mathbf{BPP}$

In CRYPTO 2021, Liu and Pass published a paper with title "On the Possibility of Basing Cryptography on $\mathbf{EXP} \neq \mathbf{BPP}$. One of the main results of this work can be interpreted ...
Blanco's user avatar
  • 1,622
0 votes
0 answers
145 views

Is this construction a OWF?

Given the OWF function $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ and the PRG $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$, is the following function $f^*$ a OWF? \begin{align} f^...
zingiest's user avatar
1 vote
0 answers
69 views

One way function with fixed point

As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following:...
yankovs's user avatar
  • 21
2 votes
1 answer
146 views

Prove: If there exist strong OWFs then there exist weak OWFs that aren't strong

Please help me to understand the proof of the following claim: Assume there exist strong OWFs, then there exist functions that are weak $\frac{2}{3}$-one-way functions, but not strong one-way ones ...
stupido's user avatar
  • 23
1 vote
2 answers
209 views

What are security reductions of symmetric-key algorithms?

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
nimrodel's user avatar
0 votes
0 answers
61 views

I am confused on how to solve this question about one way hashing

I know that I have to use decryption, but I am confused about how it breaks one-way (preimage resistance)
Dominic Teplicky's user avatar
0 votes
0 answers
765 views

PRG implies OWF Proof

I got the idea of this proof, that since PRG expands from n to 2n, it cannot project to all {0,1}^{2n}, only to a neglible part which we can abuse to make a good distinguisher just by telling if A ...
killertoge's user avatar
3 votes
2 answers
149 views

What's an algorithm for laypeople to make personal passwords

I'm going to be teaching an audience about algorithms. I'd like to give them one to create unique personal passwords for websites. They could start with the domain name of the site and their own ...
DocWriter's user avatar

1
2 3 4 5 6