69 votes
Accepted

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

Data integrity is another usage. For example, when you want to send/download data, you want to make sure that the data is not modified or transmitted/downloaded correctly. To achieve this the data ...
user avatar
  • 43.4k
35 votes

Is it easy to crack a hashed phone number?

No, it is not a good idea to hash phone numbers. There are only a limited number of phone numbers, so it is pretty easy for an adversary to try and hash all of them. Then you can simply compare the ...
user avatar
  • 85.1k
28 votes

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

Applications for one-way-functions in cryptography Hash-collisions may happen in rare cases, but are mostly disregarded here. Data integrity Integrity A quick way to ensure integrity of data is to ...
user avatar
  • 6,326
22 votes

(updated) Utilizing a non-computable function to create a one-way function

The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case ...
user avatar
14 votes
Accepted

Composing two one-way functions such that the result is not a one-way function

The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$). For convenience, let me quote that answer here: Assume that a one-way ...
14 votes
Accepted

Is $f(x)\oplus x$ a one-way function?

While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view. After all, we don't know whether $f(...
user avatar
  • 6,429
14 votes
Accepted

How to show that a one-way function proves that P ≠ NP?

It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist: Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $...
user avatar
  • 510
13 votes
Accepted

Collision Resistant Hashing from One-Way Functions?

Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner . The main idea is to use the ...
user avatar
  • 4,493
13 votes

Is it easy to crack a hashed phone number?

It is always a bad idea to hash data that has a limited set of length or characters. A phone number in Germany for example has normally no more than 12 digits. The first digit is always a ...
user avatar
12 votes

Quadratic residuosity problem reduction to integer factorization

Factoring $\longrightarrow$ square roots. Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of ...
user avatar
12 votes

Is it easy to crack a hashed phone number?

In the general sense, The problem is known as the small input space on the hash functions, and in short simple hashing won't be secure. If you hash data ( here a phone number) and an attacker tries to ...
user avatar
  • 43.4k
10 votes

How to construct a collision resistant hash function that is not a one-way function?

It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is ...
user avatar
10 votes
Accepted

Overview of relations between cryptographic primitives?

You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow ...
user avatar
  • 4,493
9 votes
Accepted

One-Way property of Random Oracle

This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven ...
user avatar
9 votes
Accepted

If a permutation $f$ is not one way, what can we say about $f^{p(n)}$?

If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is. ...
user avatar
  • 124k
8 votes
Accepted

Disadvantages of one-way accumulators?

An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for membership of values in the accumulator where the ...
user avatar
  • 12.1k
8 votes

Collision free one way function

No, it is not collision-free. All possible sequences of 0's produce the same output: ...
user avatar
  • 4,832
8 votes
Accepted

How do Hash functions work under the hood?

There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(...
user avatar
  • 19.2k
8 votes
Accepted

One-way functions and P=NP

Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its ...
user avatar
8 votes
Accepted

If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?

Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it ...
user avatar
  • 8,637
7 votes
Accepted

Are there cryptographic hash functions that can be computed using only paper and pen without leaking any information about the plaintext?

Check out Manuel Blum's human computable hash function. He calls it HCMU for Human Computable Machine Unbreakable. He claims you have to spend an hour memorizing the technique and then you can apply ...
user avatar
  • 202
7 votes

Is $f(x)\oplus x$ a one-way function?

No, you can find $f$ such that $f(x)$ is a OWF, but $f(x)\oplus x$ is not. One example would be $f(x) = AES_k(x) \oplus x$ (for a public key $k$, perhaps the all-zeros key). $f(x)$ is believed to be ...
user avatar
  • 132k
7 votes
Accepted

Periodic One Way Function

Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible ...
user avatar
7 votes
Accepted

Relationship between existence of OWFs and OWPs

Short answer: "No". The standard way to establish a statement of the form if a primitive $B$ exists then another primitive $A$ also exists is through a black-box reduction. This involves two steps: ...
user avatar
  • 4,493
7 votes

Is it easy to crack a hashed phone number?

As an alternative, you can salt the phone numbers to avoid pre-calculation attacks. A known salt will help against an adversary who has already done a hash of all possible phone numbers but just adds ...
user avatar
7 votes
Accepted

Does there exist a universal one-way permutation?

To the best of my knowledge, this is unknown. That is, Levin's construction is a one-way function but most certainly not a one-way permutation. I don't see any way in which it can be modified to make ...
user avatar
6 votes

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

There is a body of theorems that shows that a one-way function is sufficient to build many, many types of symmetric cryptography schemes. As the link puts it: The existence of a one-way function ...
user avatar
6 votes
Accepted

Has anyone implemented a public-key encryption scheme using a universal one-way function?

We don't know of any construction of PKE based on a universal OWF. Actually, we do not even have any plausible candidate PKE that would be based on an arbitrary OWF. Obtaining such constructions is a ...
user avatar
6 votes

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

The claim (which I can't find anywhere in the answers to the linked question) is incorrect. A constant function can't be one-way. To see why, let's recall the definition of a one-way function. A ...
user avatar
  • 6,429

Only top scored, non community-wiki answers of a minimum length are eligible