A mechanism for secure communication in large distributed systems is proposed. The mechanism, called Authenticated Datagram Protocol (ADP), provides message authentication and, optionally, privacy of data. ADP is a host-to-host datagram protocol, positioned below the transport layer; it uses public-key encryption to establish secure channels between hosts and to authenticate owners, and single-key encryption for communication over a channel and to ensure privacy of the messages. ADP is shown to satisfy the main security requirements of large distributed systems, to provide end-to-end security in spite of its relatively low level, and to exhibit several advantages over schemes in which security mechanisms are at a higher level. The results of a trace-driven measurement study of ADP performance show that its throughput and latency are acceptable even within the limitations of today's technology, provided single-key encryption-decryption can be done in hardware.