Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes 
throughout the world which permit him to observe all exchanged data and all
computations done inside the nodes.

Is it still possible under these conditions to ensure by mathematical means
that this secret service cannot find out who communicates with whom,
if one designs internet protocols in a suitable way?

My feeling is that the answer is likely "yes", but I am not working in cryptography.
-- Probably a cryptographer can tell more.