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