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 signifi cant 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 di fferent rounds of the wrapper in the MF Algorithm. The (in)dependency conditions lead to a general framework for multiple forking and signi ficantly 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 eff ect 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)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]