Paper 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 forking. 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.