Not logged in. · Lost password · Register

 #faui2k15, GTI-Tutor a. D. Member since Nov 2015 538 posts 2019-12-13, 12:40   #1   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?
 Member since Oct 2014 131 posts 2019-12-14, 00:21   #2   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: Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys:
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen