diff --git a/services/identity/src/constants.rs b/services/identity/src/constants.rs
--- a/services/identity/src/constants.rs
+++ b/services/identity/src/constants.rs
@@ -124,19 +124,11 @@
 // One time keys table, which need to exist in their own table to ensure
 // atomicity of additions and removals
 pub mod one_time_keys_table {
-  // The `PARTITION_KEY` will contain "notification_${deviceID}" or
-  // "content_${deviceID}" to allow for both key sets to coexist in the same table
   pub const NAME: &str = "identity-one-time-keys";
-  pub const PARTITION_KEY: &str = "deviceID";
-  pub const DEVICE_ID: &str = PARTITION_KEY;
-  pub const SORT_KEY: &str = "oneTimeKey";
-  pub const ONE_TIME_KEY: &str = SORT_KEY;
+  pub const PARTITION_KEY: &str = "userID#deviceID#olmAccount";
+  pub const SORT_KEY: &str = "timestamp#keyNumber";
 }
 
-// One-time key constants for device info map
-pub const CONTENT_ONE_TIME_KEY: &str = "contentOneTimeKey";
-pub const NOTIF_ONE_TIME_KEY: &str = "notifOneTimeKey";
-
 // Tokio
 
 pub const MPSC_CHANNEL_BUFFER_CAPACITY: usize = 1;
diff --git a/services/terraform/modules/shared/dynamodb.tf b/services/terraform/modules/shared/dynamodb.tf
--- a/services/terraform/modules/shared/dynamodb.tf
+++ b/services/terraform/modules/shared/dynamodb.tf
@@ -238,17 +238,17 @@
 
 resource "aws_dynamodb_table" "identity-one-time-keys" {
   name         = "identity-one-time-keys"
-  hash_key     = "deviceID"
-  range_key    = "oneTimeKey"
+  hash_key     = "userID#deviceID#olmAccount"
+  range_key    = "timestamp#keyNumber"
   billing_mode = "PAY_PER_REQUEST"
 
   attribute {
-    name = "deviceID"
+    name = "userID#deviceID#olmAccount"
     type = "S"
   }
 
   attribute {
-    name = "oneTimeKey"
+    name = "timestamp#keyNumber"
     type = "S"
   }
 }