The DoD vision of real-time information sharing and net-centric services available to warfighters at the tactical edge is challenged by low-bandwidth and high-latency tactical network links. Secured tactical applications require transmission of digital certificates that contribute a major portion of data in most secure sessions, which further increases response time for users and drains device power. In this paper we present a simple and practical approach to alleviating this problem. We develop a dictionary of data common across DoD PKI certificates to prime general-purpose data compression of certificates, resulting in a significant reduction (about 50%) of certificate sizes. This reduction in message size translates in to faster response times for the users. For example, a mutual authentication of a client and a server over the Iridium satellite link is expected to be sped up by as much as 3 sec. This approach can be added directly to tactical applications with minimal effort, or it can be deployed as part of an intercepting network proxy, completely transparent to applications.