# Digital signature with collision

Let's assume a digital signature scheme such that there's a probability of 0.2 for two random messages to have the same signature.

How can I exploit this sheme?

I'm having difficulties in finding an exploit since the messages has to be random.

• Just generate generate a hundred random messages, request one signature and check if any other message verifies, request another signature, check for any other message verifies, ... – SEJPM May 28 '16 at 18:30
• Yes but how can I exploit this in my favor? Random messages are meaningless. – Jjang May 28 '16 at 19:19
• This really depends on your definition of "exploit". If you want to break the standard security notions for signatures, my above explanation suffices, if you want to construct a meaningful / chosen message this looks impossible (to me). – SEJPM May 28 '16 at 19:24
• I have to show some "exploit", something useful I could cheat people with. I think breaking the standard is obvious due to the collision with prob. 0.2. – Jjang May 28 '16 at 19:53
• This is for educational purpose of course. – Jjang May 28 '16 at 19:54

Thus, generating a large bunch of pairs of (random) messages $(m_1,m_2)$, and requesting a signature for one $(m_1)$ of them and verifying if the signature also verifies the other message is a strategy that will yield you a new message-signature-pair $(m_2,s_1)$ rather sooner than later.