Due to energy and bandwidth limitations of wireless sensor networks (WSNs), it is crucial that data provenance for these networks be as compact as possible. Even if lossy compression techniques are used for encoding provenance information, the size of the provenance increases with the number of nodes traversed by the network packets. To address such issues, we propose a dictionary based provenance scheme. In our approach, each sensor node in the network stores a packet path dictionary. With the support of this dictionary, a path index instead of the path itself is enclosed with each packet.
Since the packet path index is a code word of a dictionary, its size is independent of the number of nodes present in the packet’s path. Furthermore, as our scheme binds the packet and its provenance through an AM-FM sketch and uses a secure packet sequence number generation technique, it can defend against most of the known provenance attacks. Through simulation and experimental results, we show that our scheme outperforms other compact provenance schemes with respect to provenance size, robustness, and energy consumption.