
New Counterexamples to Sequential Composition Adaptive Insecurity
Author(s) -
Liqing Yu
Publication year - 2025
Publication title -
ieee access
Language(s) - English
Resource type - Magazines
SCImago Journal Rank - 0.587
H-Index - 127
eISSN - 2169-3536
DOI - 10.1109/access.2025.3592932
Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation
At CRYPTO 2005, Pietrzak demonstrated an intriguing result: the sequential composition of two non-adaptively secure pseudorandom functions does not necessarily imply adaptive security, assuming the decisional Diffie-Hellman (DDH) assumption holds. To support this claim, they constructed a cleverly designed counterexample consisting of two functions, F and G. While both F and G are non-adaptively secure, their sequential composition G ◦ F fails to achieve adaptive security. Such a counterexample is highly non-trivial, requiring sophisticated designs and a deep understanding of the distinctions between non-adaptive and adaptive security. In this work, we show that such well-crafted counterexample is not unique by presenting two novel counterexamples derived from entirely different intuitions. These new constructions imply that there may be potential systematic approaches to designing such counterexamples, providing new insights into the relationship between non-adaptive and adaptive security.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom