ULNC: An untraceable linear network coding mechanism for mobile devices in wireless mesh networks

To protect user privacy in wireless mesh networks, it is important to address two major challenges, namely, flow untraceability and movement untraceability, which prevent malicious attackers from deducing the flow paths and the movement tracks of mobile devices. For these two privacy requirements, most existing approaches rely on encrypting the whole packet, appending random padding, and applying random delay for each message at every intermediate node, resulting in significant computational and communication overheads. Recently, linear network coding (LNC) has been introduced as an alternative, but the global encoding vectors (GEVs) of coded messages have to be encrypted by homomorphic encryption to conceal the relationships between incoming and outgoing messages. In this paper, we aim to explore the potential of LNC to ensure flow untraceability and movement untraceability. Specifically, we first determine the necessary and sufficient condition, with which the two privacy requirements can be achieved without encrypting either GEVs or message contents. We then design a deterministic untraceable LNC (ULNC) scheme to provide flow untraceability and movement untraceability when the sufficient and necessary condition is satisfied. We also provide extensive theoretical analysis on the probability that the condition is satisfied, as well as abundant discussions on the key parameters that affect the value of the probability. Finally, we discuss the effectiveness of the proposed ULNC scheme.