In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for the success of the MF Algorithm. A careful analysis of the protocols (and corresponding security argument) employing multiple forking allow us to relax the overly restrictive conditions of the original MF Algorithm. To achieve this, we club two consecutive invocations of the underlying wrapper into a single logical unit of wrapper Z. We then use Z to formulate the notion of "dependence" and "independence" among different rounds of the wrapper in the MF Algorithm. The (in)dependence conditions lead to a general framework for multiple forking and significantly better bound for the MF Algorithm. Leveraging (in)dependence to the full reduces the degradation from O(q^2n) to O(q^n). By implication, the cost of a forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking).
Finally, we study the effect of these observations on the security of the existing schemes. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.Category / Keywords: Oracle Replay Attack, Forking Lemma, Multiple-Forking Lemma, Provable Security, Tightness. Date: received 10 Oct 2013, last revised 2 Jan 2014 Contact author: chethan0510 at csa iisc ernet in Available format(s): PDF | BibTeX Citation Version: 20140102:112854 (All versions of this report) Discussion forum: Show discussion | Start new discussion