diff --git a/services/identity/Cargo.lock b/services/identity/Cargo.lock
--- a/services/identity/Cargo.lock
+++ b/services/identity/Cargo.lock
@@ -1148,6 +1148,7 @@
  "curve25519-dalek",
  "derive_more",
  "futures-core",
+ "hex",
  "once_cell",
  "opaque-ke",
  "prost",
diff --git a/services/identity/Cargo.toml b/services/identity/Cargo.toml
--- a/services/identity/Cargo.toml
+++ b/services/identity/Cargo.toml
@@ -26,6 +26,7 @@
 siwe = "0.3"
 comm-opaque = { path = "../../shared/comm-opaque" }
 once_cell = "1.17"
+hex = "0.4"
 
 [build-dependencies]
 tonic-build = "0.8"
diff --git a/services/identity/src/database.rs b/services/identity/src/database.rs
--- a/services/identity/src/database.rs
+++ b/services/identity/src/database.rs
@@ -122,14 +122,6 @@
         .insert(":u".to_string(), AttributeValue::S(username));
     };
     if let Some(public_key) = signing_public_key {
-      update_expression_parts.push(format!(
-        "{}.#{} = :k",
-        USERS_TABLE_DEVICES_ATTRIBUTE, USERS_TABLE_DEVICES_MAP_ATTRIBUTE_NAME,
-      ));
-      expression_attribute_names.insert(
-        format!("#{}", USERS_TABLE_DEVICES_MAP_ATTRIBUTE_NAME),
-        public_key,
-      );
       let device_info = match session_initialization_info {
         Some(info) => info
           .iter()
@@ -137,8 +129,30 @@
           .collect(),
         None => HashMap::new(),
       };
-      expression_attribute_values
-        .insert(":k".to_string(), AttributeValue::M(device_info));
+
+      // How we construct the update expression will depend on whether the user
+      // already exists or not
+      if let GetItemOutput { item: Some(_), .. } =
+        self.get_item_from_users_table(&user_id).await?
+      {
+        update_expression_parts.push(format!(
+          "{}.#{} = :k",
+          USERS_TABLE_DEVICES_ATTRIBUTE, USERS_TABLE_DEVICES_MAP_ATTRIBUTE_NAME,
+        ));
+        expression_attribute_names.insert(
+          format!("#{}", USERS_TABLE_DEVICES_MAP_ATTRIBUTE_NAME),
+          public_key,
+        );
+        expression_attribute_values
+          .insert(":k".to_string(), AttributeValue::M(device_info));
+      } else {
+        update_expression_parts
+          .push(format!("{} = :k", USERS_TABLE_DEVICES_ATTRIBUTE));
+        let mut devices = HashMap::new();
+        devices.insert(public_key, AttributeValue::M(device_info));
+        expression_attribute_values
+          .insert(":k".to_string(), AttributeValue::M(devices));
+      };
     };
 
     self
diff --git a/services/identity/src/service.rs b/services/identity/src/service.rs
--- a/services/identity/src/service.rs
+++ b/services/identity/src/service.rs
@@ -351,8 +351,15 @@
       return Err(Status::invalid_argument("invalid message"));
     }
   };
+
+  let decoded_signature = hex::decode(siwe_signature.trim_start_matches("0x"))
+    .map_err(|e| {
+      error!("Failed to decode SIWE signature: {}", e);
+      Status::invalid_argument("invalid signature")
+    })?;
+
   match siwe_message.verify(
-    match siwe_signature.as_bytes().try_into() {
+    match decoded_signature.try_into() {
       Ok(s) => s,
       Err(e) => {
         error!("Conversion to SIWE signature failed: {:?}", e);