diff --git a/swh/journal/serializers.py b/swh/journal/serializers.py
--- a/swh/journal/serializers.py
+++ b/swh/journal/serializers.py
@@ -99,7 +99,7 @@
 
 def kafka_to_key(kafka_key: bytes) -> KeyType:
     """Deserialize a key"""
-    return msgpack.loads(kafka_key, raw=False, strict_map_key=False)
+    return msgpack.loads(kafka_key, raw=False)
 
 
 def value_to_kafka(value: Any) -> bytes:
diff --git a/swh/journal/tests/test_serializers.py b/swh/journal/tests/test_serializers.py
--- a/swh/journal/tests/test_serializers.py
+++ b/swh/journal/tests/test_serializers.py
@@ -1,4 +1,4 @@
-# Copyright (C) 2017 The Software Heritage developers
+# Copyright (C) 2017-2020 The Software Heritage developers
 # See the AUTHORS file at the top-level directory of this distribution
 # License: GNU General Public License version 3, or any later version
 # See top-level LICENSE file for more information
@@ -51,3 +51,20 @@
 
             if isinstance(key, bytes):
                 assert pprinted_key == key.hex()
+
+
+def test_kafka_to_key():
+    """Standard back and forth serialization with keys
+
+    """
+    keys = [
+        b"foo",
+        b"bar",
+        b"baz",
+    ]
+
+    for key in keys:
+        ktk = serializers.key_to_kafka(key)
+        v = serializers.kafka_to_key(ktk)
+
+        assert v == key