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.
282
questions
30
votes
5
answers
8k
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, ...
- 685
28
votes
6
answers
31k
views
Are there hash algorithms with variable length output?
I understand that for example MD5 produces a 128 bit hash value from a given text of variable size. My question is if there is a hash-like algorithm that will produce a hash value where one can ...
- 1,174
28
votes
2
answers
7k
views
What is a hard-core predicate?
I read this article on Wikipedia: Hard-core predicate.
Still I don't understand what exactly is a hard-core predicate. Is it possible to put this in simple English terminology, and perhaps with a ...
Kai
20
votes
5
answers
5k
views
Are there cryptographic hash functions that can be computed using only paper and pen without leaking any information about the plaintext?
I am looking for a cryptographic hash function that can be computed by a human using only paper and pen without ever leaking any information about the plaintext on the paper.
The cryptographic hash ...
- 372
19
votes
1
answer
2k
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 something ...
- 655
18
votes
5
answers
11k
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?
- 297
14
votes
3
answers
6k
views
Lamport signature: How many signatures are needed to forge a signature?
Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never ...
- 359
11
votes
2
answers
6k
views
How to show that a one-way function proves that P ≠ NP?
According to this, the existence of a one-way function proves P ≠ NP. What is the proof of this?
One way to show this is that if P = NP, then any function is easy to invert. P and NP are about ...
- 819
10
votes
1
answer
972
views
Can I use the ChaCha core as a 256-bit to 256-bit one-way function?
I'm looking to implement Lamport signatures as a little fun project, and I need a fast one way function that maps $\{0,1\}^{256} \rightarrow \{0,1\}^{256}$.
I was wondering whether I could safely use ...
- 4,240
9
votes
3
answers
348
views
How hard is to invert the function that computes the middle-bits of (x^2)?
I'm designing a function f that should be moderately hard to invert and very fast to evaluate in a modern CPU. The function will be used in a proof-of-work function.
I've read that the middle-bits of ...
- 1,867
9
votes
1
answer
2k
views
Is the AES Key Schedule weak?
After reading this paper entitled Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds, I was left wondering why AES's key schedule is invertible.
In the paper, the ...
user1449
9
votes
1
answer
927
views
One way function built from AES?
I'm implementing a Hash based signature algorithm and this paper recommends the use of $F(X,\mathit{salt})=\operatorname{AES}_\mathit{salt}(X)\oplus X$ as a hard one way function. The salt plays the ...
- 1,741
9
votes
1
answer
1k
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 $\mathbin\|$ denote string concatenation.
Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a ...
- 249
8
votes
2
answers
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 ...
- 201
8
votes
3
answers
2k
views
Quadratic residuosity problem reduction to integer factorization
How can one show how to reduce the quadratic residuosity problem to an integer factorization?
- 445
8
votes
3
answers
982
views
One-way permutation over a small interval?
I am wondering what concrete computable functions we know that
are a permutation over an integer interval of parameterizable size $s$, for relatively small $s$ starting circa $2^{64}$, to perhaps $2^{...
8
votes
3
answers
590
views
Pen-and-paper one-way function for externally-anonymous survey
When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being ...
8
votes
3
answers
1k
views
Slow one-way pseudo-random permutation?
I'm looking for a slow one-way pseudo-random permutation; or in other words a block cipher $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^b$ with moderate block size $b\approx 64$ bits, wide key $K$, ...
- 141k
8
votes
1
answer
199
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 ...
- 3,952
7
votes
2
answers
4k
views
Is $f(x)\oplus x$ a one-way function?
Given that $f$ is a OWF and $|f(x)|=|x|$ for all $x$, is $g(x)=f(x)\oplus x$ necessarily also a OWF?
- 73
7
votes
1
answer
2k
views
Help in understanding exactly how lattices are used as one-way functions for hashing
In my long-distance cryptography course, an assignment covers lattice-based cryptography. It is hard, and I am lost. There is no one to help me.
Thus far, I have understood that:
Lattices are a ...
- 73
7
votes
1
answer
2k
views
Collision Resistant Hashing from One-Way Functions?
In general, can we construct a collision resistant hash function from a one-way function?
- 655
7
votes
1
answer
2k
views
modular exponentiation as a one-way-hash
As far as I can tell most one-way hashes apply some iterated encryption algorithm to the input data.
What would be the issues with a one-way hash based on some fixed large prime $p$ and a generator $...
- 245
7
votes
1
answer
2k
views
Disadvantages of one-way accumulators?
One-way accumulators are built upon a (quasi)-commutative one-way function. With quasi-commutativity, I refer to the following property:
For $f : X \times Y \to X$, it is true that $f(f(x, y_1), y_2) ...
- 1,866
7
votes
3
answers
1k
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 ...
7
votes
1
answer
1k
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 ...
- 73
6
votes
2
answers
24k
views
What is the meaning of "trapdoor" in cryptography?
I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions:
What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
- 71
6
votes
2
answers
955
views
Is there a hash algorithm that is slow to calculate but relatively fast to check?
Or more generally, is there a function or algorithm that is slow to calculate/execute, has a reliable execution time, and has a result that can be tested much more quickly than the calculation took?
- 223
6
votes
3
answers
425
views
What other one-way functions are used in cryptosystems?
For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties ...
- 2,329
6
votes
1
answer
296
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 ...
- 107
6
votes
1
answer
1k
views
One-Way property of Random Oracle
I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but ...
- 1,431
6
votes
2
answers
2k
views
unique one-way hash
For a 10-digits numeric domain (swedish social security numbers), is there a hash function with the following properties?
no two numbers result in the same hash
it is not possible to deduce the ...
- 163
6
votes
1
answer
177
views
Does there exist a universal one-way permutation?
Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function.
But my question is, does there exist a universal one-way ...
6
votes
1
answer
169
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 ...
- 173
6
votes
1
answer
704
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 ...
- 163
6
votes
2
answers
2k
views
Trapdoor and RSA (Schneier)
Disclaimer: I'm new to cryptography.
Background: From Applied Cryptography (Bruce Schneier), page 30 of 2nd edition
A trapdoor one-way function is a special type of one-way function, one with a ...
- 209
6
votes
2
answers
273
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 ...
- 46k
6
votes
1
answer
380
views
Choice of the one-way function (OWF) for Lamport signatures
I am studying the Lamport signature scheme, and I found that in many sources (eg: Hash-based Digital Signature Schemes) the input and output bitstring of the OWF and the message digest have the same ...
- 219
6
votes
1
answer
163
views
Comparing two definitions of one-way function
I'm reading Rafael Pass's lecture notes on one-way function and came across two definitions.
The first one is: A function $f$ is one-way if $f$ can be computed in P.P.T. and there exists no non-...
- 326
6
votes
1
answer
759
views
Is there a cryptographic hash function that can be performed with pencil and paper?
Imagine I'm signing up for the 99th new web site this month.
I somehow take my secret key (which I have written down on a card in my wallet) and the domain name of the site and feed them both into ...
- 5,664
5
votes
4
answers
3k
views
How to construct a collision resistant hash function that is not a one-way function?
How to construct a CRHF (collision resistant hash function) that is not a OWF (one-way function)? Not sure but I think it probably needs another CRHF?
5
votes
2
answers
2k
views
Why do cryptographic hashes need to be fixed length?
Why do cryptographic hashes need to have a fixed length output?
I know that the shallow answer is that an output that varies by key size or file size can leak information somehow, leading to ...
- 303
5
votes
2
answers
3k
views
Composing two one-way functions such that the result is not a one-way function
Is it possible to have two distinct one-way functions (called, say, $h$ and $g$) such that their composition $h \circ g = [\, x \mapsto h(g(x)) \,]$ is not one-way?
- 165
5
votes
1
answer
2k
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:\...
- 153
5
votes
1
answer
947
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,484
5
votes
1
answer
3k
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 ...
- 153
5
votes
2
answers
593
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 ...
- 269
5
votes
2
answers
590
views
One-way function definition
I cannot understand why a one-way function $f$ is defined in this way
$\text{Pr}(f(A(f(x))) = f(x)) < \frac{1}{p(n)}$
and not
$\text{Pr}(A(f(x)) = x) < \frac{1}{p(n)}$
where $A$ is a ...
- 153
5
votes
1
answer
477
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 ...
- 236
5
votes
2
answers
3k
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 ...
- 151