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

C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362.


Journal Article | Published | English
Author
Department
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.
Publishing Year
Date Published
2016-04-01
Journal Title
Algorithmica
Acknowledgement
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.
Volume
74
Issue
4
Page
1321 - 1362
IST-REx-ID

Cite this

Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 2016;74(4):1321-1362. doi:10.1007/s00453-015-9997-6
Kamath Hosdurg, C., & Chatterjee, S. (2016). A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica, 74(4), 1321–1362. https://doi.org/10.1007/s00453-015-9997-6
Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” Algorithmica 74, no. 4 (2016): 1321–62. https://doi.org/10.1007/s00453-015-9997-6.
C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound,” Algorithmica, vol. 74, no. 4, pp. 1321–1362, 2016.
Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.
Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” Algorithmica, vol. 74, no. 4, Springer, 2016, pp. 1321–62, doi:10.1007/s00453-015-9997-6.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar