diff --git a/src/security/v2/certificate-bundle-fetcher.cpp b/src/security/v2/certificate-bundle-fetcher.cpp
index 227a434..9375aa4 100644
--- a/src/security/v2/certificate-bundle-fetcher.cpp
+++ b/src/security/v2/certificate-bundle-fetcher.cpp
@@ -175,7 +175,7 @@
       m_certStorage->cacheUnverifiedCert(Certificate(block));
     }
 
-    auto cert = m_certStorage->getUnverifiedCertCache().find(certRequest->m_interest);
+    auto cert = m_certStorage->getUnverifiedCertCache().find(certRequest->interest);
     continueValidation(*cert, state);
   }
 }
diff --git a/src/security/v2/certificate-fetcher-direct-fetch.cpp b/src/security/v2/certificate-fetcher-direct-fetch.cpp
index 0f240a2..a155dad 100644
--- a/src/security/v2/certificate-fetcher-direct-fetch.cpp
+++ b/src/security/v2/certificate-fetcher-direct-fetch.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2017 Regents of the University of California.
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -53,7 +53,7 @@
     }
   }
   if (incomingFaceId != 0) {
-    Interest directInterest(keyRequest->m_interest);
+    Interest directInterest(keyRequest->interest);
     directInterest.refreshNonce();
     directInterest.setTag(make_shared<lp::NextHopFaceIdTag>(incomingFaceId));
     m_face.expressInterest(directInterest, nullptr, nullptr, nullptr);
diff --git a/src/security/v2/certificate-fetcher-from-network.cpp b/src/security/v2/certificate-fetcher-from-network.cpp
index 5d7bcaa..4337378 100644
--- a/src/security/v2/certificate-fetcher-from-network.cpp
+++ b/src/security/v2/certificate-fetcher-from-network.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2013-2017 Regents of the University of California.
+/*
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -34,6 +34,7 @@
 
 CertificateFetcherFromNetwork::CertificateFetcherFromNetwork(Face& face)
   : m_face(face)
+  , m_scheduler(face.getIoService())
 {
 }
 
@@ -42,7 +43,7 @@
                                        const shared_ptr<ValidationState>& state,
                                        const ValidationContinuation& continueValidation)
 {
-  m_face.expressInterest(certRequest->m_interest,
+  m_face.expressInterest(certRequest->interest,
                          [=] (const Interest& interest, const Data& data) {
                            dataCallback(data, certRequest, state, continueValidation);
                          },
@@ -80,16 +81,17 @@
                                             const ValidationContinuation& continueValidation)
 {
   NDN_LOG_DEBUG_DEPTH("NACK (" << nack.getReason() <<  ") while fetching certificate "
-                      << certRequest->m_interest.getName());
+                      << certRequest->interest.getName());
 
-  --certRequest->m_nRetriesLeft;
-  if (certRequest->m_nRetriesLeft >= 0) {
-    // TODO implement delay for the the next fetch
-    fetch(certRequest, state, continueValidation);
+  --certRequest->nRetriesLeft;
+  if (certRequest->nRetriesLeft >= 0) {
+    m_scheduler.scheduleEvent(certRequest->waitAfterNack,
+                              [=] { fetch(certRequest, state, continueValidation); });
+    certRequest->waitAfterNack *= 2;
   }
   else {
     state->fail({ValidationError::Code::CANNOT_RETRIEVE_CERT, "Cannot fetch certificate after all "
-                 "retries `" + certRequest->m_interest.getName().toUri() + "`"});
+                 "retries `" + certRequest->interest.getName().toUri() + "`"});
   }
 }
 
@@ -98,16 +100,16 @@
                                                const shared_ptr<ValidationState>& state,
                                                const ValidationContinuation& continueValidation)
 {
-  NDN_LOG_DEBUG_DEPTH("Timeout while fetching certificate " << certRequest->m_interest.getName()
+  NDN_LOG_DEBUG_DEPTH("Timeout while fetching certificate " << certRequest->interest.getName()
                       << ", retrying");
 
-  --certRequest->m_nRetriesLeft;
-  if (certRequest->m_nRetriesLeft >= 0) {
+  --certRequest->nRetriesLeft;
+  if (certRequest->nRetriesLeft >= 0) {
     fetch(certRequest, state, continueValidation);
   }
   else {
     state->fail({ValidationError::Code::CANNOT_RETRIEVE_CERT, "Cannot fetch certificate after all "
-                 "retries `" + certRequest->m_interest.getName().toUri() + "`"});
+                 "retries `" + certRequest->interest.getName().toUri() + "`"});
   }
 }
 
diff --git a/src/security/v2/certificate-fetcher-from-network.hpp b/src/security/v2/certificate-fetcher-from-network.hpp
index e5076c3..8b5068d 100644
--- a/src/security/v2/certificate-fetcher-from-network.hpp
+++ b/src/security/v2/certificate-fetcher-from-network.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2013-2017 Regents of the University of California.
+/*
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -23,6 +23,7 @@
 #define NDN_SECURITY_V2_CERTIFICATE_FETCHER_FROM_NETWORK_HPP
 
 #include "certificate-fetcher.hpp"
+#include "../../util/scheduler.hpp"
 
 namespace ndn {
 
@@ -59,9 +60,7 @@
   /**
    * @brief Callback invoked when interest for fetching certificate gets NACKed.
    *
-   * It will retry if certRequest->m_nRetriesLeft > 0
-   *
-   * @todo Delay retry for some amount of time
+   * Retries with exponential backoff while `certRequest->nRetriesLeft > 0`
    */
   void
   nackCallback(const lp::Nack& nack,
@@ -71,7 +70,7 @@
   /**
    * @brief Callback invoked when interest for fetching certificate times out.
    *
-   * It will retry if certRequest->m_nRetriesLeft > 0
+   * It will retry if `certRequest->nRetriesLeft > 0`
    */
   void
   timeoutCallback(const shared_ptr<CertificateRequest>& certRequest, const shared_ptr<ValidationState>& state,
@@ -79,6 +78,7 @@
 
 protected:
   Face& m_face;
+  Scheduler m_scheduler;
 };
 
 } // namespace v2
diff --git a/src/security/v2/certificate-fetcher-offline.cpp b/src/security/v2/certificate-fetcher-offline.cpp
index 8bf28e1..a59c58b 100644
--- a/src/security/v2/certificate-fetcher-offline.cpp
+++ b/src/security/v2/certificate-fetcher-offline.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2013-2017 Regents of the University of California.
+/*
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -31,7 +31,7 @@
                                    const ValidationContinuation& continueValidation)
 {
   state->fail({ValidationError::Code::CANNOT_RETRIEVE_CERT,
-               "Cannot fetch certificate " + certRequest->m_interest.getName().toUri() + " in offline mode"});
+               "Cannot fetch certificate " + certRequest->interest.getName().toUri() + " in offline mode"});
 }
 
 } // namespace v2
diff --git a/src/security/v2/certificate-fetcher.cpp b/src/security/v2/certificate-fetcher.cpp
index ffb4416..f6dc148 100644
--- a/src/security/v2/certificate-fetcher.cpp
+++ b/src/security/v2/certificate-fetcher.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2013-2017 Regents of the University of California.
+/*
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -49,7 +49,7 @@
                           const ValidationContinuation& continueValidation)
 {
   BOOST_ASSERT(m_certStorage != nullptr);
-  auto cert = m_certStorage->getUnverifiedCertCache().find(certRequest->m_interest);
+  auto cert = m_certStorage->getUnverifiedCertCache().find(certRequest->interest);
   if (cert != nullptr) {
     NDN_LOG_DEBUG_DEPTH("Found certificate in **un**verified key cache " << cert->getName());
     continueValidation(*cert, state);
diff --git a/src/security/v2/certificate-request.hpp b/src/security/v2/certificate-request.hpp
index 9bcb93b..543c46e 100644
--- a/src/security/v2/certificate-request.hpp
+++ b/src/security/v2/certificate-request.hpp
@@ -34,15 +34,12 @@
 class CertificateRequest : noncopyable
 {
 public:
-  CertificateRequest()
-    : m_nRetriesLeft(0)
-  {
-  }
+  CertificateRequest() = default;
 
   explicit
   CertificateRequest(const Interest& interest)
-    : m_interest(interest)
-    , m_nRetriesLeft(3)
+    : interest(interest)
+    , nRetriesLeft(3)
   {
   }
 
@@ -54,9 +51,11 @@
 
 public:
   /// @brief the name for the requested data/certificate.
-  Interest m_interest;
-  /// @brief the number of remaining retries after time out or NACK
-  int m_nRetriesLeft;
+  Interest interest;
+  /// @brief the number of remaining retries after timeout or NACK.
+  int nRetriesLeft = 0;
+  /// @brief the amount of time to wait before sending the next interest after a NACK.
+  time::milliseconds waitAfterNack = 500_ms;
 };
 
 } // namespace v2
diff --git a/src/security/v2/validator.cpp b/src/security/v2/validator.cpp
index aa651b1..24542bb 100644
--- a/src/security/v2/validator.cpp
+++ b/src/security/v2/validator.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2017 Regents of the University of California.
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -146,15 +146,15 @@
     return;
   }
 
-  if (state->hasSeenCertificateName(certRequest->m_interest.getName())) {
+  if (state->hasSeenCertificateName(certRequest->interest.getName())) {
     state->fail({ValidationError::Code::LOOP_DETECTED,
-                 "Validation loop detected for certificate `" + certRequest->m_interest.getName().toUri() + "`"});
+                 "Validation loop detected for certificate `" + certRequest->interest.getName().toUri() + "`"});
     return;
   }
 
-  NDN_LOG_DEBUG_DEPTH("Retrieving " << certRequest->m_interest.getName());
+  NDN_LOG_DEBUG_DEPTH("Retrieving " << certRequest->interest.getName());
 
-  auto cert = findTrustedCert(certRequest->m_interest);
+  auto cert = findTrustedCert(certRequest->interest);
   if (cert != nullptr) {
     NDN_LOG_TRACE_DEPTH("Found trusted certificate " << cert->getName());
 
diff --git a/tests/unit-tests/security/v2/certificate-fetcher-direct-fetch.t.cpp b/tests/unit-tests/security/v2/certificate-fetcher-direct-fetch.t.cpp
index 2f27878..68fe6b1 100644
--- a/tests/unit-tests/security/v2/certificate-fetcher-direct-fetch.t.cpp
+++ b/tests/unit-tests/security/v2/certificate-fetcher-direct-fetch.t.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2017 Regents of the University of California.
+ * Copyright (c) 2013-2018 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -140,7 +140,9 @@
 BOOST_FIXTURE_TEST_CASE_TEMPLATE(ValidateFailureData, T, Failures, CertificateFetcherDirectFetchFixture<T>)
 {
   VALIDATE_FAILURE(this->data, "Should fail, as all interests either NACKed or timeout");
-  BOOST_CHECK_GT(this->face.sentInterests.size(), 4);
+  // Direct fetcher sends two interests each time - to network and face
+  // 3 retries on nack or timeout (2 * (1 + 3) = 4)
+  BOOST_CHECK_EQUAL(this->face.sentInterests.size(), 8);
 
   // odd interests
   for (const auto& sentInterest : this->face.sentInterests | boost::adaptors::strided(2)) {
@@ -176,7 +178,9 @@
 BOOST_FIXTURE_TEST_CASE_TEMPLATE(ValidateFailureInterest, T, Failures, CertificateFetcherDirectFetchFixture<T>)
 {
   VALIDATE_FAILURE(this->interest, "Should fail, as all interests either NACKed or timeout");
-  BOOST_CHECK_GT(this->face.sentInterests.size(), 4);
+  // Direct fetcher sends two interests each time - to network and face
+  // 3 retries on nack or timeout (2 * (1 + 3) = 4)
+  BOOST_CHECK_EQUAL(this->face.sentInterests.size(), 8);
 
   // odd interests
   for (const auto& sentInterest : this->face.sentInterests | boost::adaptors::strided(2)) {
diff --git a/tests/unit-tests/security/v2/certificate-fetcher-from-network.t.cpp b/tests/unit-tests/security/v2/certificate-fetcher-from-network.t.cpp
index e4b1ec9..5a6b395 100644
--- a/tests/unit-tests/security/v2/certificate-fetcher-from-network.t.cpp
+++ b/tests/unit-tests/security/v2/certificate-fetcher-from-network.t.cpp
@@ -119,13 +119,15 @@
 BOOST_FIXTURE_TEST_CASE_TEMPLATE(ValidateFailure, T, Failures, CertificateFetcherFromNetworkFixture<T>)
 {
   VALIDATE_FAILURE(this->data, "Should fail, as interests don't bring data");
-  BOOST_CHECK_GT(this->face.sentInterests.size(), 2);
+  // first interest + 3 retries
+  BOOST_CHECK_EQUAL(this->face.sentInterests.size(), 4);
+
   this->face.sentInterests.clear();
 
   this->advanceClocks(1_h, 2); // expire validator caches
 
   VALIDATE_FAILURE(this->interest, "Should fail, as interests don't bring data");
-  BOOST_CHECK_GT(this->face.sentInterests.size(), 2);
+  BOOST_CHECK_EQUAL(this->face.sentInterests.size(), 4);
 }
 
 BOOST_AUTO_TEST_SUITE_END() // TestCertificateFetcherFromNetwork
diff --git a/tests/unit-tests/security/v2/validator.t.cpp b/tests/unit-tests/security/v2/validator.t.cpp
index af64557..ff33984 100644
--- a/tests/unit-tests/security/v2/validator.t.cpp
+++ b/tests/unit-tests/security/v2/validator.t.cpp
@@ -72,7 +72,8 @@
   m_keyChain.sign(data, signingByIdentity(subIdentity));
 
   VALIDATE_FAILURE(data, "All interests should get NACKed");
-  BOOST_CHECK_GT(face.sentInterests.size(), 1);
+  // 1 for the first interest, 3 for the retries on nack
+  BOOST_CHECK_EQUAL(face.sentInterests.size(), 4);
 }
 
 BOOST_AUTO_TEST_CASE(MalformedCert)