Not logged in. · Lost password · Register

Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
538 posts
Subject: Example of non-preimage-resistant, but collision-resistant function
For Ex7-1 I seek a hash function \Pi = (Gen, H) with H: {0,1}^n x {0,1}^* -> {0,1}^n such that

a) it is collision-resistant as in the lecture,

b) and it is non-preimage-resistant defined as follows:

// Note this probably heavily deviates from literature

ExpPreImageRes_{A,\Pi,y}(n)
-------------------------------
s <- Gen
x <- A(1^n, s, y)

return H(s, x) == y

H is called non-preimage-resistant iff. there is a ppt-adversary A such that for all y in {0,1}^n: Pr[ExpPreImageRes_{A,\Pi,y}(n) = 1] is a non-negligible function in n.

Note that the experiment is parametric in y, e.g. in contrast to ExpInvert for OWFs, which means I can use the adversary to query preimage values for arbitrarily-distributed image values.

Does anyone have an example?
tyr
Avatar
Member since Oct 2014
131 posts
First: I think that although this is indeed very interesting, you may solve 7.1 without such a construction, as far as I can see it in the "official" solution.

I expected that such a thing exists (I even said that in the exercise session), but it does not seem so:

https://news.ycombinator.com/item?id=16782085

(I highly recommend to read through the links mentioned there).


My intuition was not entirely wrong, as c.r. implies pre-image safety to another exponential (depending on the parameters = negligible) bound that is smaller than the c.r. bound.
=> So to break the c.r. of H(m0||m1) = m0 || H'(m1)  the brute force algorithm is negl.
But using this to store your password on a server means half your password is now leaked and brute forcing your whole password is faster (but still exponential).
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen