A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound Journal Article

Author(s): Kamath Hosdurg, Chethan; Chatterjee, Sanjit
Article Title: A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound
Affiliation IST Austria
Abstract: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and 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 multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , 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 success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single 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 concrete security of existing schemes employing multiple forking. 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.
Keywords: Provable security; Cryptography; Random oracle; Forking Lemma; Multiple Forking Lemma; Tightness
Journal Title: Algorithmica
Volume: 74
Issue 4
ISSN: 1432-0541
Publisher: Springer  
Date Published: 2016-04-01
Start Page: 1321
End Page: 1362
DOI: 10.1007/s00453-015-9997-6
Notes: We are grateful to the anonymous reviewers for their insightful comments. The detailed reports helped us a lot to address the technical mistakes as well as to improve the overall presentation of the paper.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work