diff --git a/encryptedstore/Android.bp b/encryptedstore/Android.bp
new file mode 100644
index 0000000..301e733
--- /dev/null
+++ b/encryptedstore/Android.bp
@@ -0,0 +1,30 @@
+package {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+rust_defaults {
+    name: "encryptedstore.defaults",
+    srcs: ["src/main.rs"],
+    edition: "2021",
+    prefer_rlib: true,
+    rustlibs: [
+        "libandroid_logger",
+        "libanyhow",
+        "libclap",
+        "libhex",
+        "liblog_rust",
+        "libnix",
+        "libdm_rust",
+    ],
+    multilib: {
+        lib32: {
+            enabled: false,
+        },
+    },
+}
+
+rust_binary {
+    name: "encryptedstore",
+    defaults: ["encryptedstore.defaults"],
+    bootstrap: true,
+}
diff --git a/encryptedstore/src/main.rs b/encryptedstore/src/main.rs
new file mode 100644
index 0000000..9a701ed
--- /dev/null
+++ b/encryptedstore/src/main.rs
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2022 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.
+ */
+
+//! `encryptedstore` is a program that (as the name indicates) provides encrypted storage
+//! solution in a VM. This is based on dm-crypt & requires the (64 bytes') key & the backing device.
+//! It uses dm_rust lib.
+
+use anyhow::{ensure, Context, Result};
+use clap::{arg, App};
+use dm::{crypt::CipherType, util};
+use log::info;
+use std::os::unix::fs::FileTypeExt;
+use std::path::Path;
+
+fn main() -> Result<()> {
+    android_logger::init_once(
+        android_logger::Config::default()
+            .with_tag("encryptedstore")
+            .with_min_level(log::Level::Info),
+    );
+    info!("Starting encryptedstore binary");
+
+    let matches = App::new("encryptedstore")
+        .args(&[
+            arg!(--blkdevice <FILE> "the block device backing the encrypted storage")
+                .required(true),
+            arg!(--key <KEY> "key (in hex) equivalent to 64 bytes)").required(true),
+        ])
+        .get_matches();
+
+    let blkdevice = Path::new(matches.value_of("blkdevice").unwrap());
+    let key = matches.value_of("key").unwrap();
+    ensure!(
+        std::fs::metadata(&blkdevice)
+            .context(format!("Failed to get metadata of {:?}", blkdevice))?
+            .file_type()
+            .is_block_device(),
+        "The path:{:?} is not of a block device",
+        blkdevice
+    );
+
+    enable_crypt(blkdevice, key, "cryptdev")?;
+    Ok(())
+}
+
+fn enable_crypt(data_device: &Path, key: &str, name: &str) -> Result<()> {
+    let dev_size = util::blkgetsize64(data_device)?;
+    let key = hex::decode(key).context("Unable to decode hex key")?;
+    ensure!(key.len() == 64, "We need 64 bytes' key for aes-xts cipher for block encryption");
+
+    // Create the dm-crypt spec
+    let target = dm::crypt::DmCryptTargetBuilder::default()
+        .data_device(data_device, dev_size)
+        .cipher(CipherType::AES256XTS) // TODO(b/259253336) Move to HCTR2 based encryption.
+        .key(&key)
+        .build()
+        .context("Couldn't build the DMCrypt target")?;
+    let dm = dm::DeviceMapper::new()?;
+    dm.create_crypt_device(name, &target).context("Failed to create dm-crypt device")?;
+
+    Ok(())
+}
diff --git a/microdroid/Android.bp b/microdroid/Android.bp
index c3e2692..68827df 100644
--- a/microdroid/Android.bp
+++ b/microdroid/Android.bp
@@ -108,6 +108,7 @@
                 "apkdmverity",
                 "authfs",
                 "authfs_service",
+                "encryptedstore",
                 "microdroid_crashdump_kernel",
                 "microdroid_kexec",
                 "microdroid_manager",
diff --git a/microdroid_manager/Android.bp b/microdroid_manager/Android.bp
index 4b06b3e..44b4c01 100644
--- a/microdroid_manager/Android.bp
+++ b/microdroid_manager/Android.bp
@@ -23,6 +23,7 @@
         "libdiced_sample_inputs",
         "libdiced_utils",
         "libglob",
+        "libhex",
         "libitertools",
         "libkernlog",
         "libkeystore2_crypto_rust",
diff --git a/microdroid_manager/src/dice.rs b/microdroid_manager/src/dice.rs
index 3881db3..499835f 100644
--- a/microdroid_manager/src/dice.rs
+++ b/microdroid_manager/src/dice.rs
@@ -38,6 +38,16 @@
     pub bcc: Vec<u8>,
 }
 
+impl DiceContext {
+    pub fn get_sealing_key(&self, salt: &[u8], identifier: &[u8], keysize: u32) -> Result<ZVec> {
+        // Deterministically derive a key to use for sealing data based on salt. Use different salt
+        // for different keys.
+        let mut key = ZVec::new(keysize as usize)?;
+        hkdf(&mut key, Md::sha256(), &self.cdi_seal, salt, identifier)?;
+        Ok(key)
+    }
+}
+
 /// Artifacts that are mapped into the process address space from the driver.
 pub enum DiceDriver<'a> {
     Real {
diff --git a/microdroid_manager/src/main.rs b/microdroid_manager/src/main.rs
index c18dd26..cc4b9dc 100644
--- a/microdroid_manager/src/main.rs
+++ b/microdroid_manager/src/main.rs
@@ -80,6 +80,12 @@
 // SYNC WITH virtualizationservice/src/crosvm.rs
 const FAILURE_SERIAL_DEVICE: &str = "/dev/ttyS1";
 
+/// Identifier for the key used for encrypted store.
+const ENCRYPTEDSTORE_BACKING_DEVICE: &str = "/dev/block/by-name/encryptedstore";
+const ENCRYPTEDSTORE_BIN: &str = "/system/bin/encryptedstore";
+const ENCRYPTEDSTORE_KEY_IDENTIFIER: &str = "encryptedstore_key";
+const ENCRYPTEDSTORE_KEYSIZE: u32 = 64;
+
 #[derive(thiserror::Error, Debug)]
 enum MicrodroidError {
     #[error("Cannot connect to virtualization service: {0}")]
@@ -350,7 +356,15 @@
 
     // To minimize the exposure to untrusted data, derive dice profile as soon as possible.
     info!("DICE derivation for payload");
-    let dice = dice_derivation(dice, &verified_data, &payload_metadata)?;
+    let dice_context = dice_derivation(dice, &verified_data, &payload_metadata)?;
+
+    // Run encryptedstore binary to prepare the storage
+    let encryptedstore_child = if Path::new(ENCRYPTEDSTORE_BACKING_DEVICE).exists() {
+        info!("Preparing encryptedstore ...");
+        Some(prepare_encryptedstore(&dice_context).context("encryptedstore run")?)
+    } else {
+        None
+    };
 
     // Before reading a file from the APK, start zipfuse
     run_zipfuse(
@@ -404,7 +418,12 @@
     // Wait until zipfuse has mounted the APK so we can access the payload
     wait_for_property_true(APK_MOUNT_DONE_PROP).context("Failed waiting for APK mount done")?;
 
-    register_vm_payload_service(allow_restricted_apis, service.clone(), dice)?;
+    register_vm_payload_service(allow_restricted_apis, service.clone(), dice_context)?;
+
+    if let Some(mut child) = encryptedstore_child {
+        let exitcode = child.wait().context("Wait for encryptedstore child")?;
+        ensure!(exitcode.success(), "Unable to prepare encrypted storage. Exitcode={}", exitcode);
+    }
 
     system_properties::write("dev.bootcomplete", "1").context("set dev.bootcomplete")?;
     exec_task(task, service).context("Failed to run payload")
@@ -802,3 +821,27 @@
 fn to_hex_string(buf: &[u8]) -> String {
     buf.iter().map(|b| format!("{:02X}", b)).collect()
 }
+
+fn prepare_encryptedstore(dice: &DiceContext) -> Result<Child> {
+    // Use a fixed salt to scope the derivation to this API.
+    // Generated using hexdump -vn32 -e'14/1 "0x%02X, " 1 "\n"' /dev/urandom
+    // TODO(b/241541860) : Move this (& other salts) to a salt container, i.e. a global enum
+    let salt = [
+        0xFC, 0x1D, 0x35, 0x7B, 0x96, 0xF3, 0xEF, 0x17, 0x78, 0x7D, 0x70, 0xED, 0xEA, 0xFE, 0x1D,
+        0x6F, 0xB3, 0xF9, 0x40, 0xCE, 0xDD, 0x99, 0x40, 0xAA, 0xA7, 0x0E, 0x92, 0x73, 0x90, 0x86,
+        0x4A, 0x75,
+    ];
+    let key = dice.get_sealing_key(
+        &salt,
+        ENCRYPTEDSTORE_KEY_IDENTIFIER.as_bytes(),
+        ENCRYPTEDSTORE_KEYSIZE,
+    )?;
+
+    let mut cmd = Command::new(ENCRYPTEDSTORE_BIN);
+    cmd.arg("--blkdevice")
+        .arg(ENCRYPTEDSTORE_BACKING_DEVICE)
+        .arg("--key")
+        .arg(hex::encode(&*key))
+        .spawn()
+        .context("encryptedstore failed")
+}
diff --git a/virtualizationservice/src/payload.rs b/virtualizationservice/src/payload.rs
index 233e74b..f6e8a7b 100644
--- a/virtualizationservice/src/payload.rs
+++ b/virtualizationservice/src/payload.rs
@@ -420,7 +420,7 @@
 
     if let Some(file) = storage_image {
         writable_partitions.push(Partition {
-            label: "encrypted-storage".to_owned(),
+            label: "encryptedstore".to_owned(),
             image: Some(ParcelFileDescriptor::new(file)),
             writable: true,
         });