diff --git a/autoupdate.py b/autoupdate.py
index b02b7f5..5666ca3 100644
--- a/autoupdate.py
+++ b/autoupdate.py
@@ -286,24 +286,26 @@
   def FindCachedUpdateImageSubDir(self, src_image, dest_image):
     """Find directory to store a cached update.
 
-       Given one, or two images for an update, this finds which
-       cache directory should hold the update files, even if they don't exist
-       yet. The directory will be inside static_image_dir, and of the form:
+    Given one, or two images for an update, this finds which
+    cache directory should hold the update files, even if they don't exist
+    yet. The directory will be inside static_image_dir, and of the form:
 
-       Non-delta updates:
-         CACHE_DIR/12345678
+    Non-delta updates:
+      CACHE_DIR/12345678
+    Delta updates:
+      CACHE_DIR/12345678_12345678
 
-       Delta updates:
-         CACHE_DIR/12345678_12345678
-       """
-    # If there is no src, we only have an image file, check image for changes
-    if not src_image:
-      return os.path.join(CACHE_DIR, self._GetMd5(dest_image))
+    If self.private_key -- Signed updates:
+      CACHE_DIR/from_above+12345678
+    """
+    sub_dir = self._GetMd5(dest_image)
+    if src_image:
+      sub_dir = '%s_%s' % (self._GetMd5(src_image), sub_dir)
 
-    # If we have src and dest, we are a delta, and check both for changes
-    return os.path.join(CACHE_DIR,
-                        "%s_%s" % (self._GetMd5(src_image),
-                                   self._GetMd5(dest_image)))
+    if self.private_key:
+      sub_dir = '%s+%s' % (sub_dir, self._GetMd5(self.private_key))
+
+    return os.path.join(CACHE_DIR, sub_dir)
 
   def GenerateUpdateImage(self, image_path, output_dir):
     """Force generates an update payload based on the given image_path.
diff --git a/autoupdate_unittest.py b/autoupdate_unittest.py
index ace323b..13875b9 100755
--- a/autoupdate_unittest.py
+++ b/autoupdate_unittest.py
@@ -63,6 +63,25 @@
     dummy.client_prefix = 'ChromeOSUpdateEngine'
     return dummy
 
+  def testGetRightSignedDeltaPayloadDir(self):
+    """Test that our directory is what we expect it to be for signed updates."""
+    self.mox.StubOutWithMock(autoupdate.Autoupdate, '_GetMd5')
+    key_path = 'test_key_path'
+    src_image = 'test_src_image'
+    target_image = 'test_target_image'
+    hashes = ['12345', '67890', 'abcde']
+
+    autoupdate.Autoupdate._GetMd5(target_image).AndReturn(hashes[1])
+    autoupdate.Autoupdate._GetMd5(src_image).AndReturn(hashes[0])
+    autoupdate.Autoupdate._GetMd5(key_path).AndReturn(hashes[2])
+
+    self.mox.ReplayAll()
+    au_mock = self._DummyAutoupdateConstructor()
+    au_mock.private_key = key_path
+    update_dir = au_mock.FindCachedUpdateImageSubDir(src_image, target_image)
+    self.assertEqual(os.path.basename(update_dir), '%s_%s+%s' % tuple(hashes))
+    self.mox.VerifyAll()
+
   def testGenerateLatestUpdateImageWithForced(self):
     self.mox.StubOutWithMock(autoupdate.Autoupdate,
                              'GenerateUpdateImageWithCache')