In emergency tasks, cross-agency operations being carried out in disaster-hit areas require some supporting communication system for command and control. Mobile Ad hoc Network (MANET) is a very suitable way to meet such communication requirements since it can function without any pre-installed communication infrastructure. Owing to potential threats in the field environment and the unique features of MANET (e.g. the open nature of wireless links and the absence of security infrastructure), security of communications over MANET is a serious issue that is typically addressed by asymmetric cryptographic mechanisms. In this paper, we tackle issues critical to asymmetric key management in MANET, which almost invariably serves as a basis of security services in a network environment. To address the deficiencies of existing key management schemes, we propose the concept of mission-specific certificate to manage public keys in our scenario. For issuance and/or revocation of mission-specific certificate, a Mission-specific Certificate Authority (MCA), which consists of a collection of server nodes to operate the threshold cryptographic scheme, is proposed. Furthermore, to cater for the occurrence of network partitioning, which is common in highly dynamic MANET, we propose a partition-tolerant mechanism for MCA by introducing the notion of auxiliary server nodes. We discuss the security and performance of our scheme and show that our approach is a secure and partition-tolerant mechanism can effectively improve availability of the MCA. Copyright (C) 2009 John Wiley & Sons, Ltd.