diff --git a/src/hello-protocol.hpp b/src/hello-protocol.hpp
index a307a94..bc5267d 100644
--- a/src/hello-protocol.hpp
+++ b/src/hello-protocol.hpp
@@ -1,7 +1,8 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  University of Memphis,
- *                     Regents of the University of California
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,15 +17,14 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
  **/
+
 #ifndef NLSR_HELLO_PROTOCOL_HPP
 #define NLSR_HELLO_PROTOCOL_HPP
 
 #include <boost/cstdint.hpp>
 #include <ndn-cxx/face.hpp>
+#include <ndn-cxx/management/nfd-control-parameters.hpp>
 #include <ndn-cxx/util/scheduler.hpp>
 
 namespace nlsr {
diff --git a/src/nlsr.cpp b/src/nlsr.cpp
index 3923ffe..bbc9f88 100644
--- a/src/nlsr.cpp
+++ b/src/nlsr.cpp
@@ -63,14 +63,15 @@
                          m_confParam.getRouterPrefix(),
                          m_keyChain)
   , m_certificateCache(new ndn::CertificateCacheTtl(ioService))
-  , m_validator(m_nlsrFace, DEFAULT_BROADCAST_PREFIX, m_certificateCache)
+  , m_validator(m_nlsrFace, DEFAULT_BROADCAST_PREFIX, m_certificateCache, m_certStore)
   , m_prefixUpdateProcessor(m_nlsrFace,
                             m_namePrefixList,
                             m_nlsrLsdb,
                             m_syncLogicHandler,
                             DEFAULT_BROADCAST_PREFIX,
                             m_keyChain,
-                            m_certificateCache)
+                            m_certificateCache,
+                            m_certStore)
   , m_faceMonitor(m_nlsrFace)
   , m_firstHelloInterval(FIRST_HELLO_INTERVAL_DEFAULT)
 {
diff --git a/src/nlsr.hpp b/src/nlsr.hpp
index dd8a478..9d6679f 100644
--- a/src/nlsr.hpp
+++ b/src/nlsr.hpp
@@ -32,22 +32,23 @@
 #include <ndn-cxx/management/nfd-face-event-notification.hpp>
 #include <ndn-cxx/management/nfd-face-monitor.hpp>
 
+#include "adjacency-list.hpp"
 #include "common.hpp"
 #include "conf-parameter.hpp"
-#include "adjacency-list.hpp"
-#include "name-prefix-list.hpp"
-#include "lsdb.hpp"
-#include "sequencing-manager.hpp"
-#include "route/routing-table.hpp"
-#include "route/name-prefix-table.hpp"
-#include "route/fib.hpp"
-#include "communication/sync-logic-handler.hpp"
 #include "hello-protocol.hpp"
+#include "lsdb.hpp"
+#include "name-prefix-list.hpp"
+#include "sequencing-manager.hpp"
 #include "test-access-control.hpp"
-#include "publisher/lsdb-dataset-interest-handler.hpp"
-#include "utility/name-helper.hpp"
-#include "update/prefix-update-processor.hpp"
 #include "validator.hpp"
+#include "communication/sync-logic-handler.hpp"
+#include "publisher/lsdb-dataset-interest-handler.hpp"
+#include "route/fib.hpp"
+#include "route/name-prefix-table.hpp"
+#include "route/routing-table.hpp"
+#include "security/certificate-store.hpp"
+#include "update/prefix-update-processor.hpp"
+#include "utility/name-helper.hpp"
 
 
 namespace nlsr {
@@ -250,20 +251,18 @@
   void
   loadCertToPublish(ndn::shared_ptr<ndn::IdentityCertificate> certificate)
   {
-    if (static_cast<bool>(certificate))
-      m_certToPublish[certificate->getName().getPrefix(-1)] = certificate; // key is cert name
-                                                                           // without version
+    m_certStore.insert(certificate);
   }
 
   ndn::shared_ptr<const ndn::IdentityCertificate>
   getCertificate(const ndn::Name& certificateNameWithoutVersion)
   {
-    CertMap::iterator it = m_certToPublish.find(certificateNameWithoutVersion);
+    shared_ptr<const ndn::IdentityCertificate> cert =
+      m_certStore.find(certificateNameWithoutVersion);
 
-    if (it != m_certToPublish.end())
-      {
-        return it->second;
-      }
+    if (cert != nullptr) {
+      return cert;
+    }
 
     return m_certificateCache->getCertificate(certificateNameWithoutVersion);
   }
@@ -315,6 +314,12 @@
     }
   }
 
+  security::CertificateStore&
+  getCertificateStore()
+  {
+    return m_certStore;
+  }
+
 private:
   void
   registerKeyPrefix();
@@ -347,8 +352,6 @@
   static const ndn::Name LOCALHOST_PREFIX;
 
 private:
-  typedef std::map<ndn::Name, ndn::shared_ptr<ndn::IdentityCertificate> > CertMap;
-
   ndn::Face& m_nlsrFace;
   ndn::Scheduler& m_scheduler;
   ConfParameter m_confParam;
@@ -371,7 +374,7 @@
 
 private:
   ndn::shared_ptr<ndn::CertificateCacheTtl> m_certificateCache;
-  CertMap m_certToPublish;
+  security::CertificateStore m_certStore;
   Validator m_validator;
   ndn::KeyChain m_keyChain;
   ndn::Name m_defaultIdentity;
diff --git a/src/security/certificate-store.hpp b/src/security/certificate-store.hpp
new file mode 100644
index 0000000..5818aa5
--- /dev/null
+++ b/src/security/certificate-store.hpp
@@ -0,0 +1,73 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
+ *
+ * This file is part of NLSR (Named-data Link State Routing).
+ * See AUTHORS.md for complete list of NLSR authors and contributors.
+ *
+ * NLSR is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#ifndef NLSR_CERTIFICATE_STORE_HPP
+#define NLSR_CERTIFICATE_STORE_HPP
+
+#include "../common.hpp"
+#include "../test-access-control.hpp"
+
+#include <ndn-cxx/interest.hpp>
+#include <ndn-cxx/security/identity-certificate.hpp>
+
+namespace nlsr {
+namespace security {
+
+class CertificateStore
+{
+public:
+  void
+  insert(shared_ptr<ndn::IdentityCertificate> certificate)
+  {
+    if (certificate != nullptr) {
+      // Key is cert name without version
+      m_certificates[certificate->getName().getPrefix(-1)] = certificate;
+    }
+  }
+
+  shared_ptr<const ndn::IdentityCertificate>
+  find(const ndn::Name& certificateNameWithoutVersion) const
+  {
+    CertMap::const_iterator it = m_certificates.find(certificateNameWithoutVersion);
+
+    if (it != m_certificates.end()) {
+      return it->second;
+    }
+
+    return nullptr;
+  }
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  void
+  clear()
+  {
+    m_certificates.clear();
+  }
+
+private:
+  typedef std::map<ndn::Name, shared_ptr<ndn::IdentityCertificate>> CertMap;
+  CertMap m_certificates;
+};
+
+} // namespace security
+} // namespace nlsr
+
+#endif // NLSR_CERTIFICATE_STORE_HPP
diff --git a/src/update/prefix-update-processor.cpp b/src/update/prefix-update-processor.cpp
index 75e6bae..12e066a 100644
--- a/src/update/prefix-update-processor.cpp
+++ b/src/update/prefix-update-processor.cpp
@@ -43,13 +43,14 @@
                                              SyncLogicHandler& sync,
                                              const ndn::Name broadcastPrefix,
                                              ndn::KeyChain& keyChain,
-                                             ndn::shared_ptr<ndn::CertificateCacheTtl> certificateCache)
+                                             ndn::shared_ptr<ndn::CertificateCacheTtl> certificateCache,
+                                             security::CertificateStore& certStore)
   : m_face(face)
   , m_namePrefixList(namePrefixList)
   , m_lsdb(lsdb)
   , m_sync(sync)
   , m_keyChain(keyChain)
-  , m_validator(m_face, broadcastPrefix, certificateCache)
+  , m_validator(m_face, broadcastPrefix, certificateCache, certStore)
   , COMMAND_PREFIX(ndn::Name(Nlsr::LOCALHOST_PREFIX).append(MODULE_COMPONENT))
 {
 }
diff --git a/src/update/prefix-update-processor.hpp b/src/update/prefix-update-processor.hpp
index 164bb49..6dc6c09 100644
--- a/src/update/prefix-update-processor.hpp
+++ b/src/update/prefix-update-processor.hpp
@@ -41,6 +41,10 @@
 class Lsdb;
 class SyncLogicHandler;
 
+namespace security {
+  class CertificateStore;
+}
+
 namespace update {
 
 typedef boost::property_tree::ptree ConfigSection;
@@ -65,7 +69,8 @@
                         SyncLogicHandler& sync,
                         const ndn::Name broadcastPrefix,
                         ndn::KeyChain& keyChain,
-                        ndn::shared_ptr<ndn::CertificateCacheTtl> certificateCache);
+                        ndn::shared_ptr<ndn::CertificateCacheTtl> certificateCache,
+                        security::CertificateStore& certStore);
 
   void
   loadValidator(ConfigSection section, const std::string& filename);
diff --git a/src/validator.hpp b/src/validator.hpp
index 365a863..02dfaa7 100644
--- a/src/validator.hpp
+++ b/src/validator.hpp
@@ -1,7 +1,8 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  The University of Memphis,
- *                     Regents of the University of California
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,13 +17,14 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Yingdi Yu <yingdi@cs.ucla.edu>
  **/
 
 #ifndef NLSR_VALIDATOR_HPP
 #define NLSR_VALIDATOR_HPP
 
+#include "common.hpp"
+#include "security/certificate-store.hpp"
+
 #include <ndn-cxx/security/validator-config.hpp>
 
 namespace nlsr {
@@ -44,9 +46,11 @@
   Validator(ndn::Face& face,
             const ndn::Name broadcastPrefix,
             const ndn::shared_ptr<ndn::CertificateCache>& cache,
+            security::CertificateStore& certStore,
             const int stepLimit = 10)
     : ndn::ValidatorConfig(face, cache, ndn::ValidatorConfig::DEFAULT_GRACE_INTERVAL, stepLimit)
     , m_broadcastPrefix(broadcastPrefix)
+    , m_certStore(certStore)
   {
     m_broadcastPrefix.append("KEYS");
   }
@@ -69,47 +73,46 @@
   }
 
 protected:
-  typedef std::vector<ndn::shared_ptr<ndn::ValidationRequest> > NextSteps;
+  typedef std::vector<ndn::shared_ptr<ndn::ValidationRequest>> NextSteps;
 
   virtual void
-  checkPolicy(const ndn::Data& data,
-              int nSteps,
-              const ndn::OnDataValidated& onValidated,
-              const ndn::OnDataValidationFailed& onValidationFailed,
-              NextSteps& nextSteps)
+  afterCheckPolicy(const NextSteps& nextSteps,
+                   const OnFailure& onFailure)
   {
-    ndn::ValidatorConfig::checkPolicy(data, nSteps,
-                                      onValidated, onValidationFailed,
-                                      nextSteps);
+    if (m_face == nullptr) {
+      onFailure("Require more information to validate the packet!");
+      return;
+    }
 
-    for (NextSteps::iterator it = nextSteps.begin(); it != nextSteps.end(); it++)
-      {
-        ndn::Name broadcastName = m_broadcastPrefix;
-        broadcastName.append((*it)->m_interest.getName());
+    for (const shared_ptr<ndn::ValidationRequest>& request : nextSteps) {
 
-        (*it)->m_interest.setName(broadcastName);
+      ndn::Interest& interest = request->m_interest;
+
+      // Look for certificate in permanent storage
+      shared_ptr<const ndn::IdentityCertificate> cert = m_certStore.find(interest.getName());
+
+      if (cert != nullptr) {
+        // If the certificate is found, no reason to express interest
+        shared_ptr<ndn::Data> data = make_shared<ndn::Data>(interest.getName());
+        data->setContent(cert->wireEncode());
+
+        Validator::onData(interest, *data, request);
       }
-  }
-
-  virtual void
-  checkPolicy(const ndn::Interest& interest,
-              int nSteps,
-              const ndn::OnInterestValidated& onValidated,
-              const ndn::OnInterestValidationFailed& onValidationFailed,
-              NextSteps& nextSteps)
-  {
-    ndn::ValidatorConfig::checkPolicy(interest, nSteps,
-                                      onValidated, onValidationFailed,
-                                      nextSteps);
-
-    for (NextSteps::iterator it = nextSteps.begin(); it != nextSteps.end(); it++)
-      {
+      else {
+        // Prepend broadcast prefix to interest name
         ndn::Name broadcastName = m_broadcastPrefix;
-        broadcastName.append((*it)->m_interest.getName());
+        broadcastName.append(interest.getName());
+        interest.setName(broadcastName);
 
-        (*it)->m_interest.setName(broadcastName);
+        // Attempt to fetch the certificate
+        m_face->expressInterest(interest,
+                                bind(&Validator::onData, this, _1, _2, request),
+                                bind(&Validator::onTimeout,
+                                     this, _1, request->m_nRetries,
+                                     onFailure,
+                                     request));
       }
-
+    }
   }
 
   virtual ndn::shared_ptr<const ndn::Data>
@@ -122,9 +125,9 @@
 
 private:
   ndn::Name m_broadcastPrefix;
+  security::CertificateStore& m_certStore;
 };
 
-
 } // namespace nlsr
 
 #endif // NLSR_VALIDATOR_HPP
diff --git a/tests-integrated/test-validator.cpp b/tests-integrated/test-validator.cpp
index 9364811..308bc77 100644
--- a/tests-integrated/test-validator.cpp
+++ b/tests-integrated/test-validator.cpp
@@ -1,7 +1,8 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  University of Memphis,
- *                     Regents of the University of California
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,17 +17,17 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Yingdi Yu <yingdi@cs.ucla.edu>
- *
  **/
 
 #include "validator.hpp"
-#include <ndn-cxx/util/scheduler.hpp>
-#include <ndn-cxx/security/key-chain.hpp>
+
 #include <ndn-cxx/security/certificate-cache-ttl.hpp>
+#include <ndn-cxx/security/key-chain.hpp>
+#include <ndn-cxx/util/scheduler.hpp>
+
 #include "boost-test.hpp"
 #include "common.hpp"
+#include "security/certificate-store.hpp"
 
 namespace nlsr {
 
@@ -39,12 +40,13 @@
   ValidatorFixture()
     : m_face2(m_face.getIoService())
     , m_scheduler(m_face.getIoService())
+    , m_keyPrefix("/ndn/broadcast/KEYS")
     , m_certificateCache(new ndn::CertificateCacheTtl(m_face.getIoService()))
-    , m_validator(m_face2, ndn::Name("/ndn/broadcast"), m_certificateCache)
+    , m_validator(m_face2, ndn::Name("/ndn/broadcast"), m_certificateCache, m_certStore)
     , m_identity("/TestValidator/NLSR")
+    , m_wasValidated(false)
   {
-    ndn::Name keyPrefix("/ndn/broadcast/KEYS");
-    m_face.setInterestFilter(keyPrefix,
+    m_face.setInterestFilter(m_keyPrefix,
                              ndn::bind(&ValidatorFixture::onKeyInterest, this, _1, _2),
                              ndn::bind(&ValidatorFixture::onKeyPrefixRegSuccess, this, _1),
                              ndn::bind(&ValidatorFixture::registrationFailed, this, _1, _2));
@@ -89,7 +91,7 @@
       "  filter\n"
       "  {\n"
       "    type name\n"
-      "    regex ^<TestValidator><NLSR><KEY><ksk-.*><><>$\n"
+      "    regex ^<TestValidator>([^<KEY><NLSR>]*)<NLSR><KEY><ksk-.*><><>$\n"
       "  }\n"
       "  checker\n"
       "  {\n"
@@ -135,11 +137,11 @@
     if (certName != m_cert->getName().getPrefix(-1))
       return; //No such a cert
 
-    ndn::Data data(interestName);
-    data.setContent(m_cert->wireEncode());
-    m_keyChain.signWithSha256(data);
+    shared_ptr<ndn::Data> data = make_shared<ndn::Data>(interestName);
+    data->setContent(m_cert->wireEncode());
+    m_keyChain.signWithSha256(*data);
 
-    m_face.put(data);
+    m_face.put(*data);
   }
 
   void
@@ -158,7 +160,7 @@
   void
   onValidated(const ndn::shared_ptr<const ndn::Data>& data)
   {
-    BOOST_CHECK(true);
+    m_wasValidated = true;
   }
 
   void
@@ -166,7 +168,7 @@
                      const std::string& failureInfo)
   {
     std::cerr << "Failure Info: " << failureInfo << std::endl;
-    BOOST_CHECK(false);
+    m_wasValidated = false;
   }
 
   void
@@ -187,12 +189,16 @@
   ndn::Face m_face;
   ndn::Face m_face2;
   ndn::Scheduler m_scheduler;
+  const ndn::Name m_keyPrefix;
   ndn::shared_ptr<ndn::CertificateCacheTtl> m_certificateCache;
+  security::CertificateStore m_certStore;
   nlsr::Validator m_validator;
 
   ndn::KeyChain m_keyChain;
   ndn::Name m_identity;
   ndn::shared_ptr<ndn::IdentityCertificate> m_cert;
+
+  bool m_wasValidated;
 };
 
 BOOST_FIXTURE_TEST_CASE(InfoCertFetch, ValidatorFixture)
@@ -207,6 +213,58 @@
   m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
                             ndn::bind(&ValidatorFixture::terminate, this));
   BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+
+  BOOST_CHECK(m_wasValidated);
+}
+
+BOOST_FIXTURE_TEST_CASE(CertificateStorage, ValidatorFixture)
+{
+  std::vector<ndn::CertificateSubjectDescription> subjectDescription;
+
+  // Create an operator identity
+  ndn::Name opIdentity("/TestValidator/operator/NLSR");
+  m_keyChain.createIdentity(opIdentity);
+
+  // Create an operator cert signed by the trust anchor
+  ndn::Name keyName = m_keyChain.generateRsaKeyPairAsDefault(opIdentity, true);
+  shared_ptr<ndn::IdentityCertificate> opCert =
+    m_keyChain.prepareUnsignedIdentityCertificate(keyName,
+                                                  m_identity,
+                                                  ndn::time::system_clock::now(),
+                                                  ndn::time::system_clock::now()
+                                                    + ndn::time::days(1),
+                                                  subjectDescription);
+  m_keyChain.signByIdentity(*opCert, m_identity);
+  m_keyChain.addCertificateAsIdentityDefault(*opCert);
+
+  // Sign data with operator cert
+  ndn::Name dataName = opIdentity;
+  dataName.append("INFO").append("neighbor").append("version");
+  ndn::shared_ptr<ndn::Data> data = ndn::make_shared<ndn::Data>(dataName);
+  m_keyChain.signByIdentity(*data, opIdentity);
+
+  // Check without cert in CertificateStore
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(200),
+                            ndn::bind(&ValidatorFixture::validate, this, data));
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
+                            ndn::bind(&ValidatorFixture::terminate, this));
+
+  BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+  BOOST_CHECK_EQUAL(m_wasValidated, false);
+
+  // Check with cert in CertificateStore
+  m_certStore.insert(opCert);
+
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(200),
+                            ndn::bind(&ValidatorFixture::validate, this, data));
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
+                            ndn::bind(&ValidatorFixture::terminate, this));
+
+  BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+  BOOST_CHECK(m_wasValidated);
+
+  // Cleanup
+  m_keyChain.deleteIdentity(opIdentity);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/tests/security/test-certificate-store.cpp b/tests/security/test-certificate-store.cpp
new file mode 100644
index 0000000..0ede9bf
--- /dev/null
+++ b/tests/security/test-certificate-store.cpp
@@ -0,0 +1,77 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
+ *
+ * This file is part of NLSR (Named-data Link State Routing).
+ * See AUTHORS.md for complete list of NLSR authors and contributors.
+ *
+ * NLSR is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "security/certificate-store.hpp"
+
+#include "../test-common.hpp"
+
+#include <ndn-cxx/security/key-chain.hpp>
+
+namespace nlsr {
+namespace security {
+namespace test {
+
+using std::shared_ptr;
+
+class CertificateStoreFixture
+{
+public:
+  CertificateStoreFixture()
+  {
+    // Create certificate
+    ndn::Name identity("/TestNLSR/identity");
+    identity.appendVersion();
+
+    ndn::KeyChain keyChain;
+    keyChain.createIdentity(identity);
+    ndn::Name certName = keyChain.getDefaultCertificateNameForIdentity(identity);
+    certificate = keyChain.getCertificate(certName);
+
+    BOOST_REQUIRE(certificate != nullptr);
+
+    certificateKey = certificate->getName().getPrefix(-1);
+  }
+
+public:
+  shared_ptr<ndn::IdentityCertificate> certificate;
+  ndn::Name certificateKey;
+};
+
+BOOST_FIXTURE_TEST_SUITE(TestSecurityCertificateStore, CertificateStoreFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+  CertificateStore store;
+
+  BOOST_REQUIRE(store.find(certificateKey) == nullptr);
+  store.insert(certificate);
+
+  BOOST_CHECK(*store.find(certificateKey) == *certificate);
+
+  store.clear();
+  BOOST_REQUIRE(store.find(certificateKey) == nullptr);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace test
+} // namespace security
+} // namespace nlsr
diff --git a/tests/test-conf-file-processor.cpp b/tests/test-conf-file-processor.cpp
index e5f709d..50cc872 100644
--- a/tests/test-conf-file-processor.cpp
+++ b/tests/test-conf-file-processor.cpp
@@ -471,6 +471,53 @@
   BOOST_CHECK_EQUAL(processConfigurationString(SECTION_GENERAL_NEGATIVE_VALUE), false);
 }
 
+BOOST_AUTO_TEST_CASE(LoadCertToPublish)
+{
+  ndn::Name identity("/TestNLSR/identity");
+  identity.appendVersion();
+
+  ndn::KeyChain keyChain;
+  keyChain.createIdentity(identity);
+  ndn::Name certName = keyChain.getDefaultCertificateNameForIdentity(identity);
+  shared_ptr<ndn::IdentityCertificate> certificate = keyChain.getCertificate(certName);
+
+  const boost::filesystem::path CERT_PATH =
+      (boost::filesystem::current_path() / std::string("cert-to-publish.cert"));
+  ndn::io::save(*certificate, CERT_PATH.string());
+
+  const std::string SECTION_SECURITY =
+  "security\n"
+  "{\n"
+  "  validator\n"
+  "  {\n"
+  "    trust-anchor\n"
+  "    {\n"
+  "      type any\n"
+  "    }\n"
+  "  }\n"
+  "  prefix-update-validator\n"
+  "  {\n"
+  "    trust-anchor\n"
+  "    {\n"
+  "      type any\n"
+  "    }\n"
+  "  }\n"
+  "  cert-to-publish \"cert-to-publish.cert\"\n"
+  "}\n\n";
+
+  BOOST_CHECK(processConfigurationString(SECTION_SECURITY));
+
+  // Certificate should now be in the CertificateStore
+  const security::CertificateStore& certStore = nlsr.getCertificateStore();
+  const ndn::Name certKey = certificate->getName().getPrefix(-1);
+
+  BOOST_CHECK(certStore.find(certKey) != nullptr);
+
+  // Cleanup
+  keyChain.deleteIdentity(identity);
+  boost::filesystem::remove(CERT_PATH);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } //namespace test
diff --git a/tests/test-nlsr.cpp b/tests/test-nlsr.cpp
index ed41d9b..ee9b7e7 100644
--- a/tests/test-nlsr.cpp
+++ b/tests/test-nlsr.cpp
@@ -1,7 +1,8 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  University of Memphis,
- *                     Regents of the University of California
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,8 +17,6 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- *
  **/
 
 #include "test-common.hpp"
@@ -279,6 +278,38 @@
   BOOST_CHECK_EQUAL(parameters.getName(), nameToAdvertise);
 }
 
+BOOST_FIXTURE_TEST_CASE(GetCertificate, UnitTestTimeFixture)
+{
+  shared_ptr<ndn::util::DummyClientFace> face = ndn::util::makeDummyClientFace(g_ioService);
+  Nlsr nlsr(g_ioService, g_scheduler, ndn::ref(*face));
+
+  // Create certificate
+  ndn::Name identity("/TestNLSR/identity");
+  identity.appendVersion();
+
+  ndn::KeyChain keyChain;
+  keyChain.createIdentity(identity);
+  ndn::Name certName = keyChain.getDefaultCertificateNameForIdentity(identity);
+  shared_ptr<ndn::IdentityCertificate> certificate = keyChain.getCertificate(certName);
+
+  const ndn::Name certKey = certificate->getName().getPrefix(-1);
+
+  BOOST_CHECK(nlsr.getCertificate(certKey) == nullptr);
+
+  // Certificate should be retrievable from the CertificateStore
+  nlsr.loadCertToPublish(certificate);
+
+  BOOST_CHECK(nlsr.getCertificate(certKey) != nullptr);
+
+  nlsr.getCertificateStore().clear();
+
+  // Certificate should be retrievable from the cache
+  nlsr.addCertificateToCache(certificate);
+  this->advanceClocks(ndn::time::milliseconds(10));
+
+  BOOST_CHECK(nlsr.getCertificate(certKey) != nullptr);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } //namespace test