A method and system for providing communication over arbitrary distances with a desired probability of security is disclosed. In accordance with one embodiment of the invention shares of a random key are encoded, the random key for effecting communication of a message through a network employing a cryptographically strong forward security system having a limited effective communications distance. A distributed re-randomization of the encoded shares is then effected at a plurality of intermediate network nodes.