diff --git a/java/service/src/com/android/system/virtualmachine/SecretkeeperJobService.java b/java/service/src/com/android/system/virtualmachine/SecretkeeperJobService.java
new file mode 100644
index 0000000..473fbfb
--- /dev/null
+++ b/java/service/src/com/android/system/virtualmachine/SecretkeeperJobService.java
@@ -0,0 +1,184 @@
+/*
+ * Copyright (C) 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.system.virtualmachine;
+
+import static android.content.pm.PackageManager.MATCH_UNINSTALLED_PACKAGES;
+
+import android.app.job.JobInfo;
+import android.app.job.JobParameters;
+import android.app.job.JobScheduler;
+import android.app.job.JobService;
+import android.content.ComponentName;
+import android.content.pm.ApplicationInfo;
+import android.content.pm.PackageManager;
+import android.content.pm.PackageManager.ApplicationInfoFlags;
+import android.os.RemoteException;
+import android.os.ServiceSpecificException;
+import android.os.UserHandle;
+import android.system.virtualizationmaintenance.IVirtualizationMaintenance;
+import android.system.virtualizationmaintenance.IVirtualizationReconciliationCallback;
+import android.util.Log;
+
+import com.android.server.LocalServices;
+import com.android.server.pm.UserManagerInternal;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicReference;
+
+/**
+ * A job scheduler service responsible for triggering the Virtualization Service reconciliation
+ * process when scheduled. The job is scheduled to run once per day while idle and charging.
+ *
+ * <p>The reconciliation process ensures that Secretkeeper secrets belonging to apps or users that
+ * have been removed get deleted.
+ *
+ * @hide
+ */
+public class SecretkeeperJobService extends JobService {
+    private static final String TAG = SecretkeeperJobService.class.getName();
+    private static final String JOBSCHEDULER_NAMESPACE = "VirtualizationSystemService";
+    private static final int JOB_ID = 1;
+    private static final AtomicReference<SecretkeeperJob> sJob = new AtomicReference<>();
+
+    static void scheduleJob(JobScheduler scheduler) {
+        try {
+            ComponentName serviceName =
+                    new ComponentName("android", SecretkeeperJobService.class.getName());
+            scheduler = scheduler.forNamespace(JOBSCHEDULER_NAMESPACE);
+            if (scheduler.schedule(
+                            new JobInfo.Builder(JOB_ID, serviceName)
+                                    // We consume CPU and power
+                                    .setRequiresDeviceIdle(true)
+                                    .setRequiresCharging(true)
+                                    .setPeriodic(24 * 60 * 60 * 1000L)
+                                    .build())
+                    != JobScheduler.RESULT_SUCCESS) {
+                Log.e(TAG, "Unable to schedule job");
+                return;
+            }
+            Log.i(TAG, "Scheduled job");
+        } catch (Exception e) {
+            Log.e(TAG, "Failed to schedule job", e);
+        }
+    }
+
+    @Override
+    public boolean onStartJob(JobParameters params) {
+        Log.i(TAG, "Starting job");
+
+        SecretkeeperJob job = new SecretkeeperJob(getPackageManager());
+        sJob.set(job);
+
+        new Thread("SecretkeeperJob") {
+            @Override
+            public void run() {
+                try {
+                    job.run();
+                    Log.i(TAG, "Job finished");
+                } catch (Exception e) {
+                    Log.e(TAG, "Job failed", e);
+                }
+                sJob.set(null);
+                // We don't reschedule on error, we will try again the next day anyway.
+                jobFinished(params, /*wantReschedule=*/ false);
+            }
+        }.start();
+
+        return true; // Job is running in the background
+    }
+
+    @Override
+    public boolean onStopJob(JobParameters params) {
+        Log.i(TAG, "Stopping job");
+        SecretkeeperJob job = sJob.getAndSet(null);
+        if (job != null) {
+            job.stop();
+        }
+        return false; // Idle jobs get rescheduled anyway
+    }
+
+    private static class SecretkeeperJob {
+        private final UserManagerInternal mUserManager =
+                LocalServices.getService(UserManagerInternal.class);
+        private volatile boolean mStopRequested = false;
+        private PackageManager mPackageManager;
+
+        public SecretkeeperJob(PackageManager packageManager) {
+            mPackageManager = packageManager;
+        }
+
+        public void run() throws RemoteException {
+            IVirtualizationMaintenance maintenance =
+                    VirtualizationSystemService.connectToMaintenanceService();
+            maintenance.performReconciliation(new Callback());
+        }
+
+        public void stop() {
+            mStopRequested = true;
+        }
+
+        class Callback extends IVirtualizationReconciliationCallback.Stub {
+            @Override
+            public boolean[] doUsersExist(int[] userIds) {
+                checkForStop();
+                int[] currentUsers = mUserManager.getUserIds();
+                boolean[] results = new boolean[userIds.length];
+                for (int i = 0; i < userIds.length; i++) {
+                    // The total number of users is likely to be small, so no need to make this
+                    // better than O(N).
+                    for (int user : currentUsers) {
+                        if (user == userIds[i]) {
+                            results[i] = true;
+                            break;
+                        }
+                    }
+                }
+                return results;
+            }
+
+            @Override
+            public boolean[] doAppsExist(int userId, int[] appIds) {
+                checkForStop();
+
+                // If an app has been uninstalled but its data is still present we want to include
+                // it, since that might include a VM which will be used in the future.
+                ApplicationInfoFlags flags = ApplicationInfoFlags.of(MATCH_UNINSTALLED_PACKAGES);
+                List<ApplicationInfo> appInfos =
+                        mPackageManager.getInstalledApplicationsAsUser(flags, userId);
+                int[] currentAppIds = new int[appInfos.size()];
+                for (int i = 0; i < appInfos.size(); i++) {
+                    currentAppIds[i] = UserHandle.getAppId(appInfos.get(i).uid);
+                }
+                Arrays.sort(currentAppIds);
+
+                boolean[] results = new boolean[appIds.length];
+                for (int i = 0; i < appIds.length; i++) {
+                    results[i] = Arrays.binarySearch(currentAppIds, appIds[i]) >= 0;
+                }
+
+                return results;
+            }
+
+            private void checkForStop() {
+                if (mStopRequested) {
+                    throw new ServiceSpecificException(ERROR_STOP_REQUESTED, "Stop requested");
+                }
+            }
+        }
+    }
+}
diff --git a/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java b/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
index 3f973b4..2461755 100644
--- a/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
+++ b/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
@@ -16,6 +16,7 @@
 
 package com.android.system.virtualmachine;
 
+import android.app.job.JobScheduler;
 import android.content.BroadcastReceiver;
 import android.content.Context;
 import android.content.Intent;
@@ -58,6 +59,8 @@
 
         mHandler = BackgroundThread.getHandler();
         new Receiver().registerForBroadcasts();
+
+        SecretkeeperJobService.scheduleJob(getContext().getSystemService(JobScheduler.class));
     }
 
     private void notifyAppRemoved(int uid) {
@@ -78,7 +81,7 @@
         }
     }
 
-    private static IVirtualizationMaintenance connectToMaintenanceService() {
+    static IVirtualizationMaintenance connectToMaintenanceService() {
         IBinder binder = ServiceManager.waitForService(SERVICE_NAME);
         IVirtualizationMaintenance maintenance =
                 IVirtualizationMaintenance.Stub.asInterface(binder);
diff --git a/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationMaintenance.aidl b/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationMaintenance.aidl
index 76d7309..08d61c1 100644
--- a/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationMaintenance.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationMaintenance.aidl
@@ -16,6 +16,8 @@
 
 package android.system.virtualizationmaintenance;
 
+import android.system.virtualizationmaintenance.IVirtualizationReconciliationCallback;
+
 interface IVirtualizationMaintenance {
     /**
      * Notification that an app has been permanently removed, to allow related global state to
@@ -32,5 +34,13 @@
      */
     void userRemoved(int userId);
 
-    // TODO(b/294177871): Something for daily reconciliation
+    /*
+     * Requests virtualization service to perform reconciliation of Secretkeeper secrets.
+     * Secrets belonging to apps or users that no longer exist should be deleted.
+     * The supplied callback allows for querying of existence.
+     * This method should return on successful completion of the reconciliation process.
+     * It should throw an exception if there is any failure, or if any of the callback
+     * functions return {@code ERROR_STOP_REQUESTED}.
+     */
+    void performReconciliation(IVirtualizationReconciliationCallback callback);
 }
diff --git a/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationReconciliationCallback.aidl b/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationReconciliationCallback.aidl
new file mode 100644
index 0000000..6466aa2
--- /dev/null
+++ b/virtualizationservice/aidl/android/system/virtualizationmaintenance/IVirtualizationReconciliationCallback.aidl
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.system.virtualizationmaintenance;
+
+/*
+ * Callback interface provided when reconciliation is performed to allow verifying whether users
+ * and apps currently exist.
+ */
+interface IVirtualizationReconciliationCallback {
+    /*
+     * Service-specific error code indicating that the job scheduler has requested that we
+     * stop
+     */
+    const int ERROR_STOP_REQUESTED = 1;
+
+    /*
+     * Determine whether users with selected IDs currently exist. The result is an array of booleans
+     * which indicate whether the corresponding entry in the {@code userIds} array is a valid
+     * user ID.
+     */
+    boolean[] doUsersExist(in int[] userIds);
+
+    /*
+     * Determine whether apps with selected app IDs currently exist for a specific user.
+     * The result is an array of booleans which indicate whether the corresponding entry in the
+     * {@code appIds} array is a current app ID for the user.
+     */
+    boolean[] doAppsExist(int userId, in int[] appIds);
+}
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index c0024f1..bbfb220 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -51,7 +51,10 @@
 use std::sync::{Arc, Mutex, Weak};
 use tombstoned_client::{DebuggerdDumpType, TombstonedConnection};
 use virtualizationcommon::Certificate::Certificate;
-use virtualizationmaintenance::IVirtualizationMaintenance::IVirtualizationMaintenance;
+use virtualizationmaintenance::{
+    IVirtualizationMaintenance::IVirtualizationMaintenance,
+    IVirtualizationReconciliationCallback::IVirtualizationReconciliationCallback,
+};
 use virtualizationservice::{
     AssignableDevice::AssignableDevice, VirtualMachineDebugInfo::VirtualMachineDebugInfo,
 };
@@ -427,6 +430,14 @@
         }
         Ok(())
     }
+
+    fn performReconciliation(
+        &self,
+        _callback: &Strong<dyn IVirtualizationReconciliationCallback>,
+    ) -> binder::Result<()> {
+        Err(anyhow!("performReconciliation not supported"))
+            .or_binder_exception(ExceptionCode::UNSUPPORTED_OPERATION)
+    }
 }
 
 // KEEP IN SYNC WITH assignable_devices.xsd