diff --git a/Ext4Crypt.cpp b/Ext4Crypt.cpp
index dc0f191..495a0fa 100644
--- a/Ext4Crypt.cpp
+++ b/Ext4Crypt.cpp
@@ -521,7 +521,9 @@
 }
 
 static bool destroy_volkey(const std::string& misc_path, const std::string& volume_uuid) {
-    return android::vold::destroyKey(volkey_path(misc_path, volume_uuid));
+    auto path = volkey_path(misc_path, volume_uuid);
+    if (!android::vold::pathExists(path)) return true;
+    return android::vold::destroyKey(path);
 }
 
 bool e4crypt_add_user_key_auth(userid_t user_id, int serial, const std::string& token_hex,
@@ -767,6 +769,40 @@
     return res;
 }
 
+static bool destroy_volume_keys(const std::string& directory_path, const std::string& volume_uuid) {
+    auto dirp = std::unique_ptr<DIR, int (*)(DIR*)>(opendir(directory_path.c_str()), closedir);
+    if (!dirp) {
+        PLOG(ERROR) << "Unable to open directory: " + directory_path;
+        return false;
+    }
+    bool res = true;
+    for (;;) {
+        errno = 0;
+        auto const entry = readdir(dirp.get());
+        if (!entry) {
+            if (errno) {
+                PLOG(ERROR) << "Unable to read directory: " + directory_path;
+                return false;
+            }
+            break;
+        }
+        if (entry->d_type != DT_DIR || entry->d_name[0] == '.') {
+            LOG(DEBUG) << "Skipping non-user " << entry->d_name;
+            continue;
+        }
+        res &= destroy_volkey(directory_path + "/" + entry->d_name, volume_uuid);
+    }
+    return res;
+}
+
+bool e4crypt_destroy_volume_keys(const std::string& volume_uuid) {
+    bool res = true;
+    LOG(DEBUG) << "e4crypt_destroy_volume_keys for volume " << escape_empty(volume_uuid);
+    res &= destroy_volume_keys("/data/misc_ce", volume_uuid);
+    res &= destroy_volume_keys("/data/misc_de", volume_uuid);
+    return res;
+}
+
 bool e4crypt_secdiscard(const std::string& path) {
     return android::vold::runSecdiscardSingle(path);
 }
diff --git a/Ext4Crypt.h b/Ext4Crypt.h
index d0afd85..4226f15 100644
--- a/Ext4Crypt.h
+++ b/Ext4Crypt.h
@@ -16,12 +16,8 @@
 
 #include <string>
 
-#include <stdbool.h>
-#include <sys/cdefs.h>
-
 #include <cutils/multiuser.h>
 
-// General functions
 bool e4crypt_initialize_global_de();
 
 bool e4crypt_init_user0();
@@ -39,4 +35,6 @@
                                   int flags);
 bool e4crypt_destroy_user_storage(const std::string& volume_uuid, userid_t user_id, int flags);
 
+bool e4crypt_destroy_volume_keys(const std::string& volume_uuid);
+
 bool e4crypt_secdiscard(const std::string& path);
diff --git a/VolumeManager.cpp b/VolumeManager.cpp
index 3194e59..f54fb00 100644
--- a/VolumeManager.cpp
+++ b/VolumeManager.cpp
@@ -48,18 +48,21 @@
 
 #include <private/android_filesystem_config.h>
 
-#include "model/EmulatedVolume.h"
-#include "model/ObbVolume.h"
-#include "VolumeManager.h"
-#include "NetlinkManager.h"
+#include <ext4_utils/ext4_crypt.h>
+
+#include "Devmapper.h"
+#include "Ext4Crypt.h"
 #include "Loop.h"
+#include "NetlinkManager.h"
+#include "Process.h"
+#include "Utils.h"
+#include "VoldUtil.h"
+#include "VolumeManager.h"
+#include "cryptfs.h"
 #include "fs/Ext4.h"
 #include "fs/Vfat.h"
-#include "Utils.h"
-#include "Devmapper.h"
-#include "Process.h"
-#include "VoldUtil.h"
-#include "cryptfs.h"
+#include "model/EmulatedVolume.h"
+#include "model/ObbVolume.h"
 
 using android::base::StringPrintf;
 using android::base::unique_fd;
@@ -300,13 +303,18 @@
         return -1;
     }
 
+    bool success = true;
     std::string keyPath = android::vold::BuildKeyPath(normalizedGuid);
     if (unlink(keyPath.c_str()) != 0) {
         LOG(ERROR) << "Failed to unlink " << keyPath;
-        return -1;
+        success = false;
     }
-
-    return 0;
+    if (e4crypt_is_native()) {
+        if (!e4crypt_destroy_volume_keys(fsUuid)) {
+            success = false;
+        }
+    }
+    return success ? 0 : -1;
 }
 
 int VolumeManager::linkPrimary(userid_t userId) {