This research was motivated by the expanding scope of Public Key Infrastructure (PKI) implementation held by Indonesia State Cryptography Agency (Lembaga Sandi Negara - Lemsaneg). Previously it was only within the scope of the Government Electronic Procurement Service, and now it must be expanded to meet the needs of government agencies services in general. With the expanding scope of the PKI, the Certificate Policy must also be reevaluated and a new policy is formulated. In this study, the new Certificate Policy (CP) is formulated using Soft Systems Methodology process. The proposed Certificate Policy is based on Levels of Assurance (LoA) to accommodate the need of different government bodies. The certificate profile analysis follows the Certificate Policy Framework of IETF RFC 3647. NIST Internal Report 7924 has been selected as the template for the Certificate Policy document due to its closeness to PKI implementation requirements in Lemsaneg and the latest information system security demands.