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,11 +1,13 @@
-# 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
 
-from collections import OrderedDict
 import itertools
 
+from collections import OrderedDict
+from typing import Iterable
+
 from swh.journal import serializers
 
 from .conftest import TEST_OBJECTS
@@ -51,3 +53,25 @@
 
             if isinstance(key, bytes):
                 assert pprinted_key == key.hex()
+
+
+def test_kafka_to_key():
+    """Standard back and forth serialization with keys
+
+    """
+    # All KeyType(s)
+    keys: Iterable[serializers.KeyType] = [
+        {"a": "foo", "b": "bar", "c": "baz",},
+        {"a": b"foobarbaz",},
+        b"foo",
+    ]
+    for object_type, objects in TEST_OBJECTS.items():
+        for obj in objects:
+            key = serializers.object_key(object_type, obj)
+            keys.append(key)
+
+    for key in keys:
+        ktk = serializers.key_to_kafka(key)
+        v = serializers.kafka_to_key(ktk)
+
+        assert v == key