# Tag Info

## Hot answers tagged one-way-function

33

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 hash of each with the stored hash. Generally you don't have to deal with all telephone numbers, only a subsection of phone numbers anyway (for a specific country ...

22

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 hardness. In particular, the fact that the halting problem is hard merely means that for every algorithm there exists a TM $M$ for with the algorithm fails upon. ...

12

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 find an input value that matches the hash value is called the pre-image attack. In a secure Cryptographic hash functions pre-image attack requires $\mathcal{O}(... 12 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 0 and the vast majority of numbers is longer as 3 digits, as those are normally reserved for emergency services. This effectively leaves us with 10^11-10^3 possible ... 8 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 involves parsing the input to the OWF$y$as a pair$\langle M\rangle || x$, where$\langle M\rangle$is interpreted as the description of a Turing machine. Then ... 7 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 one order of magnitude of work (the adversary just has to recalculate all the hashs with the salted phone numbers). If you can keep the salt private raises the ... 6 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 it a permutation, since the way it works is by running arbitrary machines and then amplifying. Since there is no efficient way of checking if something is a ... 5 Knowing either$p$or$q$is sufficient to recover both of them (as$q = n/p$). So imagine we know all of$p, q$, and$n$. The chinese remainder theorem can be phrased many different ways. In general, it states that when working mod$n$(where$n$is a product of distinct primes ), you can instead work mod each prime separately. In this particular setting,... 5 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 major open problem. We know that there is no black-box construction of PKE from any OWF by a seminal result of Impagliazzo and Rudich. Of course, we cannot rule ... 4 take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets. You let them run for up to 𝑡 steps, and then see which ones have halted by that point. [...] Say you ran 1024 TMs; if you give each an index, and then toggle the corresponding bit depending on whether each one halts, you get a 1024-bit ... 4 It is a major open research question whether such a scheme exists, and how to construct one (see, for example, Open Problem 9.10). Of course, we do have schemes like (hashed) ElGamal, which are based on the conjectured hardness of the (computational or decisional) Diffie-Hellman problem. But it is unknown whether either of these problems is equivalent to the ... 3 An alternative is to encrypt the phone number as proposed in the previous answers. For example, Mobile connect identity service encrypts the MSISDN (aka phone number) using a specific algorithm. This GSMA specification gives information about decoding the payload : Following are the example of encrypted MSISDN passed: with URL encoding: login_hint=... 3 maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it Even that limited goal is beyond what we can prove. People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was ... 3 Would [$f_N(x)=x^2\bmod N$] lose the one-way property if$N$is prime and not a product of two primes? Yes, thanks to the Tonelli-Shanks algorithm (special cases here). [Is] Rabin function still one-way if factorization of$N=pq$is known? No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem ... 3 If there is an algorithm$B(H(x))$that get part of$x$, is$H(x)$a one-way function? That remains possible. Simplifying the definition of a One-Way Function in Katz and Lindel's Introduction to Modern Cryptography, it's an efficiently computable function$f$such that no algorithm$\mathcal A$exists that, given as input$y=f(x)$for a random$x$, outputs ... 2 Let's look at the definition in the linked thesis: Definition 2.2.2 (probabilistic one-way function). A probabilistic function,$F$(with randomness domain$R_n$), with a corresponding deterministic verifier,$V_F$, is called one-way with respect to a well-spread distribution,$\mathbb{X}$, if for any PPT,$A$:$$\Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(... 2 This construction is well-known as XORP = "XOR of independent permutations". In your case the permutations are obtained by invoking a block cipher$E$with different keys. If$E$is an ideal cipher, and$k_1, k_2$are distinct (fixed, public) keys, then$E_{k_1}(\cdot)$and$E_{k_2}(\cdot)$are independent, ideal permutations. Ideal permutation ... 2 In general, unless the OWP also happens to be a trapdoor permutation, there is no way to efficiently evaluate the inverse. So, no. 2 maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with$\Omega(n^7)$could suffice to build somewhat practical cryptography:$c⋅(2128)17≈c⋅319557$bits (for some constant$c$) would be required to obtain the same security level as a 128 bit key. Some people have ... 1 a one-way function, which given an input would generate an output that is unique for that input. A one-way function does not guarantee uniqueness of outputs. The definition of a one-way function gives us that given an output$y = f(x)$, is hard to find any preimage$x^*$of$y$for which$f(x^*) = y$holds. Discrete logarithms and factorials are, as far as ... 1 Length-regular: if$x$and$y$have the same length, then$f(x)$and$f(y)$have the same length. Length-preserving:$x$and$f(x)$have the same length. Examples:$f(x) = \overline{x}$(flip every bit in$x$): length-preserving.$f(x) = x \|x$(concatenate$x\$ with itself): length-regular but not length-preserving.

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