System and method for providing end-to-end security of data and metadata

A method for encrypting metadata of a message in a network comprising a plurality of nodes, wherein each pair of adjacent nodes have or share the same symmetric key, wherein the symmetric key comprises a first x-value and a first y-value of a first metadata share, and a second x-value, the plurality of nodes comprising a source node, a destination node, and a plurality of intermediate nodes, wherein at least one of the intermediate nodes is an anchor node, the at least one anchor node adjacent to the source node in the social network, thus having a symmetric key with the source node, the method comprising:

• encrypting the data of the message by:
• constructing a polynomial of degree k−1, wherein the data is derivable from the polynomial;
• choosing at least k different xi values and calculating respective yi values of the polynomial for each of the xi values, wherein each pair of an xi value and a respective yi value constitutes a data share (xi, yi),
• wherein the portion of the encrypted data comprises the data share (xi, yi), wherein no intermediate node on the at least one path obtains k or more data shares, wherein the data of the message is a free coefficient of the polynomial;
• sending, by a source node to a destination node through a plurality of intermediate nodes, at least a portion of the data of the message in at least one path;
• wherein sending a portion of the data of the message in a path comprises:
• dividing the path into a plurality of sub-paths, wherein each two contiguous sub-paths are connected by the at least one anchor node;
• calculating a secret value comprising 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 in the path, and a metadata share comprising 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 of the data of the message together with the first random point to the first intermediate node in the path.

A system for encrypting metadata of a message in a social network, the system comprising:

• a plurality of nodes, wherein each node comprises a hardware processor, wherein each pair of adjacent nodes share a symmetric key, wherein the symmetric key comprises a first x-value and a first y-value of a first metadata share, and a second x-value, and wherein the plurality of nodes comprises:
• a source node;
• a destination node;
• a plurality of intermediate nodes, wherein some of the intermediate nodes are anchor nodes, wherein each of the anchor nodes is adjacent to the source node in the social network, thus having a symmetric key with the source node, wherein a plurality of paths from the source node to the destination node through the intermediate nodes and the anchor nodes are defined;
• wherein the source node is configured to send a message to the destination node by:
• sending at least a portion of data of the message to the destination node in at least one path;
• wherein sending a portion of the data of the message in a path comprises:
• dividing the path into a plurality of sub-paths, wherein each two contiguous sub-paths are connected by one of the anchor nodes;
• calculating a secret value comprising 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 in the path, and a metadata share comprising 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 of the data of the message together with the first random point to the first intermediate node in the path,
• wherein an intermediate node is configured to, upon receiving a second random point from a previous node in the path:
• reconstruct a line equation connecting the first metadata share of the symmetric key of the previous node in the path and the intermediate node, and the second random point;
• calculate a current secret value based on the line equation and on the second x-value of the symmetric key of the previous node in the path and the intermediate node;
• if the intermediate node is an anchor node, decrypt a next sub-path using the symmetric key of the anchor node and the source node;
• calculate a new secret value, comprising a list of nodes of a remaining portion of a sub-path, and an encrypted form of a remaining portion of the path;
• calculate a new random point on a new linear line connecting a first metadata share of a symmetric key of the intermediate node and a next intermediate node in the path, and a metadata share comprising a second x-value of the symmetric key of the intermediate node and a next intermediate node in the path and the new secret value;
• and
• send the portion of the data of the message together with the new random point to the next intermediate node in the sub-path.