diff --git a/keyserver/src/database/migration-config.js b/keyserver/src/database/migration-config.js
--- a/keyserver/src/database/migration-config.js
+++ b/keyserver/src/database/migration-config.js
@@ -730,6 +730,17 @@
     },
   ],
   [57, synchronizeInviteLinksWithBlobs],
+  [
+    58,
+    async () => {
+      await dbQuery(
+        SQL`
+          ALTER TABLE updates
+            MODIFY \`key\` varchar(255) CHARSET latin1 COLLATE latin1_bin
+        `,
+      );
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
diff --git a/keyserver/src/database/setup-db.js b/keyserver/src/database/setup-db.js
--- a/keyserver/src/database/setup-db.js
+++ b/keyserver/src/database/setup-db.js
@@ -171,7 +171,7 @@
         id bigint(20) NOT NULL,
         user varchar(255) CHARSET latin1 COLLATE latin1_bin NOT NULL,
         type tinyint(3) UNSIGNED NOT NULL,
-        \`key\` bigint(20) DEFAULT NULL,
+        \`key\` varchar(255) CHARSET latin1 COLLATE latin1_bin DEFAULT NULL,
         updater bigint(20) DEFAULT NULL,
         target bigint(20) DEFAULT NULL,
         content mediumtext CHARACTER SET utf8mb4 COLLATE utf8mb4_bin,
diff --git a/lib/shared/relationship-utils.js b/lib/shared/relationship-utils.js
--- a/lib/shared/relationship-utils.js
+++ b/lib/shared/relationship-utils.js
@@ -13,9 +13,13 @@
 import type { UserInfo } from '../types/user-types.js';
 
 function sortIDs(firstId: string, secondId: string): string[] {
-  return [Number(firstId), Number(secondId)]
-    .sort((a, b) => a - b)
-    .map(num => num.toString());
+  if (!isNaN(Number(firstId)) && !isNaN(Number(secondId))) {
+    return [Number(firstId), Number(secondId)]
+      .sort((a, b) => a - b)
+      .map(num => num.toString());
+  }
+
+  return [firstId, secondId].sort();
 }
 
 function getAvailableRelationshipButtons(