A communication network (10) includes any number of interconnected nodes (20), including a sending node (22), a sending gateway (24), a receiving gateway (26), and a destination node (28). A low capacity or expensive communication channel (30) resides between the sending and receiving gateways (24, 26). An original digitally signed message is sent from the sending node (22) toward the destination node (28). When the original message arrives at the sending gateway (24), the original signature is verified. If verified, the sending gateway (24) shrinks the original message into a reduced message and re-signs the message with a gateway digital signature before sending the message onward through the communication channel (30) toward the destination node (28). The destination node (28) verifies the gateway digital signature against the reduced message and is not required to de-compress the reduced message into a precise duplicate of the original message.