# Tag Info

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 ...
• 49.3k

### 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 ...
• 93.9k

### 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 ...
• 6,502

### (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 ...
• 28.1k
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 ...
• 5,408
Accepted

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 $... • 570 14 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 ... • 49.1k 14 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 ... • 5,408 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 ... • 378 13 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 ... • 49.3k 10 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. ... • 144k 9 votes Accepted ### Can one-way permutations be constructed from one-way functions? It was shown by Rudich in his PhD thesis [R] that it is not possible to construct one-way permutations (OWPs) from one-way functions (OWFs) in the framework of black-box reductions.$^1$This was later ... • 5,408 9 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 ... • 28.1k 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(... • 19.8k 8 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: ... • 5,408 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 ... • 20.8k 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 ... • 13.8k 7 votes Accepted ### One-way permutation over a small interval? How about this. Find an elliptic curve mod$p$, say$E:y^2=x^3+ax+b$for some 256-bit prime$p$such that the curve$E$and its twist$E':dy^2=x^3+ax+b$with$(\frac dp)_L=-1$are both of prime order. ... • 25.4k 7 votes Accepted ### Is every pseudorandom generator a one way function? Prove by contradiction. Assume that it is not a one-way function and that it can be inverted with non-negligible probability. Use this to construct a distinguisher that can distinguish truly random ... • 28.1k 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 ... • 179 6 votes Accepted ### Are there simple, cryptographically safe one-way hashing functions? Designing a conceptually simple one-way function is a very hard challenge in itself - and conceptual simplicity is not such a well defined concept, so the answers you will receive might be a bit ... • 20.8k 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 ... • 14.6k 6 votes ### Simple explanation of weak one way function The part that I find confusing is:$1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert? This is relaxation from Strong OWF, in which, any polynomial ... • 49.3k 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 ... • 20.8k 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 ... • 7,038 5 votes ### why can't use only one way function to construct a PRG, and don't use the hard core predicate? The first one is really simple, you already said it yourself: as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that? I guess ... • 12.8k 5 votes Accepted ### If$P \neq NP$why doesn't this prove the existence of OWF? an answer from Goldwasser and Bellare's lecture notes. P ≠ NP is not a sufficient one. P ≠ NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the ... • 383 5 votes Accepted ### Relation between "P is not equal to NP" and "Existence of One-Way Function" Why can we not conclude that if P ≠ NP, then there exists a one-way function? Because so far no one has been able to prove this statement, see here. The statement "if one-way functions exist, then$...
• 12.8k
The proof of Theorem 7.19 explicitly uses that $f(r)$ for a uniformly random bitstring $r$ is distributed like $r$ when $f$ is a permutation*. I don't have the energy to reprint the proof here to show ...
This follows essentially from the security of the one-time pad: if you have some arbitrary distribution $D$ over a group $G$, and the uniform distribution $U$ over the same group $G$. If $D$ and $U$ ...