Exercise 2
1 view
Skip to first unread message
Ron Rothblum
May 22, 2011, 4:33:56 AM5/22/11
to weizmann...@googlegroups.com
Hi Everyone,
I finished checking the second exercise and you can come pick them up from my room.
There were two minor issues that most of you missed and I think are worth noting:
1. (public-key signature -> OWF) Most/all of you correctly claimed that the function that given random coins returns the verification key is a OWF. Notice that the assumption that an adversary inverts this function just means that it finds random coins that lead to the same verification key BUT not necessarily the original random coins (the function may be many-to-one). This means that even when the inverter succeeds, the signing key that you get may not be the original one. To fix this issue just observe than you can forge even with the new signing key.
The above applies also to the analogous question about encryption.
2. (Deterministic Signing) - In the reduction one needs to argue that wlog the adversary only asks the signing oracle for one signature of each message (if it asks for more you can simulate the responses because it is deterministic). Try to see where the argument fails without this assumption.
Happy burning :-)
Ron
I finished checking the second exercise and you can come pick them up from my room.
There were two minor issues that most of you missed and I think are worth noting:
1. (public-key signature -> OWF) Most/all of you correctly claimed that the function that given random coins returns the verification key is a OWF. Notice that the assumption that an adversary inverts this function just means that it finds random coins that lead to the same verification key BUT not necessarily the original random coins (the function may be many-to-one). This means that even when the inverter succeeds, the signing key that you get may not be the original one. To fix this issue just observe than you can forge even with the new signing key.
The above applies also to the analogous question about encryption.
2. (Deterministic Signing) - In the reduction one needs to argue that wlog the adversary only asks the signing oracle for one signature of each message (if it asks for more you can simulate the responses because it is deterministic). Try to see where the argument fails without this assumption.
Happy burning :-)
Ron
Reply all
Reply to author
Forward
0 new messages