Cryptology ePrint Archive: Report 2013/651
A Closer Look at Multiple-Forking: Leveraging (In)dependence for a Tighter Bound
Sanjit Chatterjee and Chethan Kamath
Abstract: Boldyreva et al. introduced the notion of multiple forking (MF) as an extension of (general) forking to accommodate nested oracle replay attacks. The primary objective of a (multiple) forking algorithm is to separate out the oracle replay attack from the actual simulation of protocol to the adversary, and this is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing the MF Algorithm incurs a significant degradation of O(q^2n), where q denotes the upper bound on the underlying random oracle calls and n, the number of forkings. 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 "dependency" and "independency" among different rounds of the wrapper in the MF Algorithm. The (in)dependency conditions lead to a general framework for multiple forking and significantly better bound for the MF Algorithm. Leveraging (in)dependency to the full reduces the degradation from O(q^2n) to O(q^n). 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: public-key cryptography / Oracle Replay Attack, Forking Lemma, Multiple-Forking Lemma, Provable Security, Tightness.
Date: received 10 Oct 2013
Contact author: chethan0510 at csa iisc ernet in
Available format(s): PDF | BibTeX Citation
Version: 20131015:064946 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]