2
$\begingroup$

Is there any standard or accepted one way function that does not produce collisions? I'm not looking for hash functions.

Does that make sense at all? for example given string with length n, the function will always output same obfuscated string that is not possible to reverse engineer. something that is mathematically one way function but also doesn't produce collision.

So I don't want to store the actual input, but just a successor of input that cant be decrypted at all, this will be used only to see if duplicate input is received or not.

Improve this question
$\endgroup$
4
  • $\begingroup$ Does it have to be keyless or can you just use AES in ECB mode? $\endgroup$
    – Elias
    Commented Jun 26, 2017 at 20:37
  • 2
    $\begingroup$ It sounds like you're looking for ​ one-way injections . ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jun 26, 2017 at 20:40
  • $\begingroup$ crypto.stackexchange.com/questions/48601/… may have some related insights regarding function collisions... $\endgroup$
    – Paul Uszak
    Commented Jun 26, 2017 at 20:59
  • $\begingroup$ Is it necessary that the input be arbitrary in size? $\endgroup$
    – Daffy
    Commented Jun 27, 2017 at 2:04

2 Answers 2

Reset to default
1
$\begingroup$

With a fixed length output (ala today's hash functions)? No.

You cannot map an infinite space to a finite space, no matter how vast that finite space may be, without the possibility of collisions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ that's true, but I wanted to map infinite space into infinite space. so even increase in output size (by a few margin) is acceptable. $\endgroup$
    – M.kazem Akhgary
    Commented Jun 26, 2017 at 20:49
  • $\begingroup$ @M.kazemAkhgary I don't think it's possible to have a $\{0,1\}^* \rightarrow \{0,1\}^*$ transformation such that the output gives no information about the input, and is resistant to preimage attacks. $\endgroup$
    – Daffy
    Commented Jun 27, 2017 at 2:02
0
$\begingroup$

The easiest way to be sure that there are no collisions in a function is for it to have an inverse, but in your case we don't want to be able to actually compute the inverse. It seems like we can use some kind of public key solution, where we have destroyed the private key. For instance, choose sufficiently large $p$ and $q$ and define a one-way function as $h = m^e \mod p*q$. If you had kept $d$ (or $p$ or $q$) you could get back $m$, but without it it's not practical. For large enough message values you'll need to break the input into blocks, and you'll want to chain the blocks together if partial matches leak information in your case.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.