(FL- PQM) protocols allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. Such protocols were proposed as tools that enable Internet service providers to select high-performance paths through the Internet, or to enforce contractual obligations. We give the first formal definitions of security for FL-PQM protocols and construct:
A simple FL-PQM protocol that can localize a faulty link
a packet is not correctly delivered. This protocol’s communication overhead is
(1) additional messages of length
) per packet (where
is the security parameter).
A more efficient FL-PQM protocol that can localize a faulty link when a
of the packets sent during some time period are not correctly delivered. The number of additional messages is an arbitrarily small fraction of the total number of packets.
We also prove lower bounds for such protocols:
Every secure FL-PQM protocol requires
intermediate node on the path to have some shared secret information (
If secure FL-PQM protocols exist then so do one-way functions.
construction of a FL-PQM protocol from a random oracle that securely localizes every packet and adds at most
) messages overhead per packet requires
intermediate node to invoke the oracle.
These results show that implementing FL-PQM requires active cooperation (
maintaining keys and agreeing on, and performing, cryptographic protocols) from
of the intermediate nodes along the path. This may be problematic in the Internet, where links operate at extremely high speeds, and intermediate nodes are owned by competing business entities with little incentive to cooperate.