diff --git a/keystore2/Android.bp b/keystore2/Android.bp
index a48396a..154b675 100644
--- a/keystore2/Android.bp
+++ b/keystore2/Android.bp
@@ -21,6 +21,7 @@
         "libanyhow",
         "libkeystore_aidl_generated",
         "libkeystore2_selinux",
+        "liblazy_static",
         "liblibsqlite3_sys",
         "liblog_rust",
         "librand",
@@ -40,6 +41,7 @@
         "libanyhow",
         "libkeystore_aidl_generated",
         "libkeystore2_selinux",
+        "liblazy_static",
         "liblibsqlite3_sys",
         "liblog_rust",
         "librusqlite",
diff --git a/keystore2/selinux/src/lib.rs b/keystore2/selinux/src/lib.rs
index 30a235a..05f9db8 100644
--- a/keystore2/selinux/src/lib.rs
+++ b/keystore2/selinux/src/lib.rs
@@ -25,6 +25,7 @@
 use std::ffi::{CStr, CString};
 use std::fmt;
 use std::io;
+use std::marker::{Send, Sync};
 pub use std::ops::Deref;
 use std::os::raw::c_char;
 use std::ptr;
@@ -141,6 +142,10 @@
     handle: *mut selinux::selabel_handle,
 }
 
+// KeystoreKeyBackend is Sync because selabel_lookup is thread safe.
+unsafe impl Sync for KeystoreKeyBackend {}
+unsafe impl Send for KeystoreKeyBackend {}
+
 impl KeystoreKeyBackend {
     const BACKEND_TYPE: i32 = SELABEL_CTX_ANDROID_KEYSTORE2_KEY as i32;
 
@@ -164,6 +169,9 @@
     }
 }
 
+// Because KeystoreKeyBackend is Sync and Send, member function must never call
+// non thread safe libselinux functions. As of this writing no non thread safe
+// functions exist that could be called on a label backend handle.
 impl Backend for KeystoreKeyBackend {
     fn lookup(&self, key: &str) -> Result<Context> {
         let mut con: *mut c_char = ptr::null_mut();
diff --git a/keystore2/src/permission.rs b/keystore2/src/permission.rs
index a5a63ee..0db56dd 100644
--- a/keystore2/src/permission.rs
+++ b/keystore2/src/permission.rs
@@ -30,12 +30,25 @@
 
 use selinux::Backend;
 
+use lazy_static::lazy_static;
+
 // Replace getcon with a mock in the test situation
 #[cfg(not(test))]
 use selinux::getcon;
 #[cfg(test)]
 use tests::test_getcon as getcon;
 
+lazy_static! {
+    // Panicking here is allowed because keystore cannot function without this backend
+    // and it would happen early and indicate a gross misconfiguration of the device.
+    static ref KEYSTORE2_KEY_LABEL_BACKEND: selinux::KeystoreKeyBackend =
+            selinux::KeystoreKeyBackend::new().unwrap();
+}
+
+fn lookup_keystore2_key_context(namespace: i64) -> anyhow::Result<selinux::Context> {
+    KEYSTORE2_KEY_LABEL_BACKEND.lookup(&namespace.to_string())
+}
+
 /// The below example wraps the enum MyPermission in the tuple struct `MyPerm` and implements
 ///  * `From<i32> for `MyPerm`, where each unknown numeric value is mapped to the given default,
 ///    here `None`
@@ -369,20 +382,11 @@
     key: &aidl::KeyDescriptor,
 ) -> anyhow::Result<()> {
     use aidl::Domain;
-    use selinux::KeystoreKeyBackend;
 
     let target_context = match key.domain {
         Domain::App => getcon().context("check_grant_permission: getcon failed.")?,
-        Domain::SELinux => {
-            // TODO cache an open backend, possible use a lazy static.
-            let backend = KeystoreKeyBackend::new().context(concat!(
-                "check_grant_permission: Domain::SELinux: ",
-                "Failed to create selinux keystore backend."
-            ))?;
-            backend
-                .lookup(format!("{}", key.namespace_).as_str())
-                .context("check_grant_permission: Domain::SELinux: Failed to lookup namespace")?
-        }
+        Domain::SELinux => lookup_keystore2_key_context(key.namespace_)
+            .context("check_grant_permission: Domain::SELinux: Failed to lookup namespace.")?,
         _ => return Err(KsError::sys()).context(format!("Cannot grant {:?}.", key.domain)),
     };
 
@@ -429,20 +433,12 @@
     access_vector: &Option<KeyPermSet>,
 ) -> anyhow::Result<()> {
     use aidl::Domain;
-    use selinux::KeystoreKeyBackend;
 
     let target_context = match key.domain {
         // apps get the default keystore context
         Domain::App => getcon().context("check_key_permission: getcon failed.")?,
-        Domain::SELinux => {
-            // TODO cache an open backend, possible use a lasy static.
-            let backend = KeystoreKeyBackend::new().context(
-                "check_key_permission: Domain::SELinux: Failed to create selinux keystore backend.",
-            )?;
-            backend
-                .lookup(format!("{}", key.namespace_).as_str())
-                .context("check_key_permission: Domain::SELinux: Failed to lookup namespace")?
-        }
+        Domain::SELinux => lookup_keystore2_key_context(key.namespace_)
+            .context("check_key_permission: Domain::SELinux: Failed to lookup namespace.")?,
         Domain::Grant => {
             match access_vector {
                 Some(pv) => {
@@ -468,10 +464,7 @@
             return Err(KsError::sys()).context("Cannot check permission for Domain::KeyId.");
         }
         Domain::Blob => {
-            let backend = KeystoreKeyBackend::new()
-                .context("Domain::Blob: Failed to create selinux keystore backend.")?;
-            let tctx = backend
-                .lookup(format!("{}", key.namespace_).as_str())
+            let tctx = lookup_keystore2_key_context(key.namespace_)
                 .context("Domain::Blob: Failed to lookup namespace.")?;
             // If DOMAIN_KEY_BLOB was specified, we check for the "manage_blob"
             // permission in addition to the requested permission.