diff --git a/include/selinux/android.h b/include/selinux/android.h
index 4971ff0..938d83f 100644
--- a/include/selinux/android.h
+++ b/include/selinux/android.h
@@ -43,6 +43,7 @@
 #define SELINUX_ANDROID_RESTORECON_RECURSE  4
 #define SELINUX_ANDROID_RESTORECON_FORCE    8
 #define SELINUX_ANDROID_RESTORECON_DATADATA 16
+#define SELINUX_ANDROID_RESTORECON_SKIPCE   32
 extern int selinux_android_restorecon(const char *file, unsigned int flags);
 
 extern int selinux_android_restorecon_pkgdir(const char *pkgdir,
diff --git a/src/android.c b/src/android.c
index 0856ff9..5206a9f 100644
--- a/src/android.c
+++ b/src/android.c
@@ -1089,6 +1089,13 @@
     return NULL;
 }
 
+/* The contents of these paths are encrypted on FBE devices until user
+ * credentials are presented (filenames inside are mangled), so we need
+ * to delay restorecon of those until vold explicitly requests it. */
+// NOTE: these paths need to be kept in sync with vold
+#define DATA_SYSTEM_CE_PREFIX "/data/system_ce/"
+#define DATA_MISC_CE_PREFIX "/data/misc_ce/"
+
 /* The path prefixes of package data directories. */
 #define DATA_DATA_PATH "/data/data"
 #define DATA_USER_PATH "/data/user"
@@ -1279,6 +1286,7 @@
     bool recurse = (flags & SELINUX_ANDROID_RESTORECON_RECURSE) ? true : false;
     bool force = (flags & SELINUX_ANDROID_RESTORECON_FORCE) ? true : false;
     bool datadata = (flags & SELINUX_ANDROID_RESTORECON_DATADATA) ? true : false;
+    bool skipce = (flags & SELINUX_ANDROID_RESTORECON_SKIPCE) ? true : false;
     bool issys;
     bool setrestoreconlast = true;
     struct stat sb;
@@ -1408,6 +1416,14 @@
                 continue;
             }
 
+            if (skipce &&
+                (!strncmp(ftsent->fts_path, DATA_SYSTEM_CE_PREFIX, sizeof(DATA_SYSTEM_CE_PREFIX)-1) ||
+                 !strncmp(ftsent->fts_path, DATA_MISC_CE_PREFIX, sizeof(DATA_MISC_CE_PREFIX)-1))) {
+                // Don't label anything below this directory.
+                fts_set(fts, ftsent, FTS_SKIP);
+                // but fall through and make sure we label the directory itself
+            }
+
             if (!datadata &&
                 (!strcmp(ftsent->fts_path, DATA_DATA_PATH) ||
                  !strncmp(ftsent->fts_path, DATA_USER_PREFIX, sizeof(DATA_USER_PREFIX)-1) ||