A system and method for encrypting metadata in a communication system, including defining paths from a source node to a destination node through intermediate nodes and anchor nodes; dividing messages and sending a portion in each path by: dividing the path into sub-paths, where each two contiguous sub-paths are connected by an anchor node; calculating a secret value including a list of nodes of a first sub-path and an encrypted form of a remaining portion of the path; calculating a first random point on a linear line connecting a first metadata share of a symmetric key of the source node and a first intermediate node, and a metadata share including a second x-value of the symmetric key of the source node and the first intermediate node in the path and the secret value; and sending the portion together with the first random point to the first intermediate node.