diff --git a/src/zoneinfo/__init__.py b/src/zoneinfo/__init__.py
index 82f855b..da6e5a6 100644
--- a/src/zoneinfo/__init__.py
+++ b/src/zoneinfo/__init__.py
@@ -1,6 +1,7 @@
-__all__ = ["ZoneInfo", "reset_tzpath", "TZPATH"]
+__all__ = ["ZoneInfo", "reset_tzpath", "TZPATH", "ZoneInfoNotFoundError"]
 
 from . import _tzpath
+from ._common import ZoneInfoNotFoundError
 from ._version import __version__
 
 try:
diff --git a/src/zoneinfo/_common.py b/src/zoneinfo/_common.py
index 6972948..568a487 100644
--- a/src/zoneinfo/_common.py
+++ b/src/zoneinfo/_common.py
@@ -4,15 +4,14 @@ import struct
 def load_tzdata(key):
     import importlib.resources
 
-    # TODO: Proper error for malformed keys?
     components = key.split("/")
     package_name = ".".join(["tzdata.zoneinfo"] + components[:-1])
     resource_name = components[-1]
 
     try:
         return importlib.resources.open_binary(package_name, resource_name)
-    except (ImportError, FileNotFoundError) as e:
-        raise ValueError(f"No time zone found with key {key}") from e
+    except (ImportError, FileNotFoundError, UnicodeEncodeError) as e:
+        raise ZoneInfoNotFoundError(f"No time zone found with key {key}") from e
 
 
 def load_data(fobj):
@@ -155,3 +154,7 @@ class _TZifHeader:
         args = args + struct.unpack(">6l", stream.read(24))
 
         return cls(*args)
+
+
+class ZoneInfoNotFoundError(KeyError):
+    """Exception raised when a ZoneInfo key is not found."""
diff --git a/src/zoneinfo/_tzpath.py b/src/zoneinfo/_tzpath.py
index 4767eda..799eaa0 100644
--- a/src/zoneinfo/_tzpath.py
+++ b/src/zoneinfo/_tzpath.py
@@ -37,6 +37,7 @@ def reset_tzpath(to=None):
 
 def find_tzfile(key):
     """Retrieve the path to a TZif file from a key."""
+    _validate_path(key)
     for search_path in TZPATH:
         filepath = os.path.join(search_path, key)
         if os.path.isfile(filepath):
@@ -45,5 +46,34 @@ def find_tzfile(key):
     return None
 
 
+_TEST_PATH = os.path.normpath(os.path.join("_", "_"))[:-1]
+
+
+def _validate_path(path, _base=_TEST_PATH):
+    if os.path.isabs(path):
+        raise ValueError(
+            f"ZoneInfo keys may not be absolute paths, got: {path}"
+        )
+
+    # We only care about the kinds of path normalizations that would change the
+    # length of the key - e.g. a/../b -> a/b, or a/b/ -> a/b. On Windows,
+    # normpath will also change from a/b to a\b, but that would still preserve
+    # the length.
+    new_path = os.path.normpath(path)
+    if len(new_path) != len(path):
+        raise ValueError(
+            f"ZoneInfo keys must be normalized relative paths, got: {path}"
+        )
+
+    resolved = os.path.normpath(os.path.join(_base, new_path))
+    if not resolved.startswith(_base):
+        raise ValueError(
+            f"ZoneInfo keys must refer to subdirectories of TZPATH, got: {path}"
+        )
+
+
+del _TEST_PATH
+
+
 TZPATH = ()
 reset_tzpath()

Enforce that all inputs are relative directories
To avoid path traversal attacks, the PEP requires that inputs be relative and not absolute paths.
diff --git a/tests/test_zoneinfo.py b/tests/test_zoneinfo.py
index a4d78d8..5af2e18 100644
--- a/tests/test_zoneinfo.py
+++ b/tests/test_zoneinfo.py
@@ -196,10 +196,25 @@ class ZoneInfoTest(TzPathUserMixin, ZoneInfoTestBase):
     def test_bad_keys(self):
         bad_keys = [
             "Eurasia/Badzone",  # Plausible but does not exist
+            "BZQ",
+            "America.Los_Angeles",
             "🇨🇦",  # Non-ascii
             "America/New\ud800York",  # Contains surrogate character
         ]
 
+        for bad_key in bad_keys:
+            with self.assertRaises(self.module.ZoneInfoNotFoundError):
+                self.klass(bad_key)
+
+    def test_bad_keys_paths(self):
+        bad_keys = [
+            "/America/Los_Angeles",  # Absolute path
+            "America/Los_Angeles/",  # Trailing slash - not normalized
+            "../zoneinfo/America/Los_Angeles",  # Traverses above TZPATH
+            "America/../America/Los_Angeles",  # Not normalized
+            "America/./Los_Angeles",
+        ]
+
         for bad_key in bad_keys:
             with self.assertRaises(ValueError):
                 self.klass(bad_key)

pip install -e .[dev]
parse_log_pytest
pytest
coverage[toml] hypothesis>=5.7.0 pytest pytest-cov pytest-randomly pytest-subtests pytest-xdist
apt-get update apt-get install -y gcc
3.8
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
attrs==25.3.0
coverage==7.6.1
exceptiongroup @ file:///croot/exceptiongroup_1706031385326/work
execnet==2.1.1
hypothesis==6.113.0
importlib_metadata==8.5.0
iniconfig @ file:///home/linux1/recipes/ci/iniconfig_1610983019677/work
packaging @ file:///croot/packaging_1720101850331/work
pluggy @ file:///tmp/build/80754af9/pluggy_1648042571233/work
pytest @ file:///croot/pytest_1717793244625/work
pytest-cov==5.0.0
pytest-randomly==3.15.0
pytest-subtests==0.13.1
pytest-xdist==3.6.1
sortedcontainers==2.4.0
tomli @ file:///opt/conda/conda-bld/tomli_1657175507142/work
zipp==3.20.2
-e git+https://github.com/pganssle/zoneinfo.git@0b41c027aac4b69cb5eb9ca599ff78ea5826701c#egg=zoneinfo

name: zoneinfo
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - exceptiongroup=1.2.0=py38h06a4308_0
  - iniconfig=1.1.1=pyhd3eb1b0_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.4.4=h6a678d5_1
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=3.0.16=h5eee18b_0
  - packaging=24.1=py38h06a4308_0
  - pip=24.2=py38h06a4308_0
  - pluggy=1.0.0=py38h06a4308_1
  - pytest=7.4.4=py38h06a4308_0
  - python=3.8.20=he870216_0
  - readline=8.2=h5eee18b_0
  - setuptools=75.1.0=py38h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - tomli=2.0.1=py38h06a4308_0
  - wheel=0.44.0=py38h06a4308_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - attrs==25.3.0
      - coverage==7.6.1
      - execnet==2.1.1
      - hypothesis==6.113.0
      - importlib-metadata==8.5.0
      - pytest-cov==5.0.0
      - pytest-randomly==3.15.0
      - pytest-subtests==0.13.1
      - pytest-xdist==3.6.1
      - sortedcontainers==2.4.0
      - zipp==3.20.2
      - zoneinfo==0.1.0.dev0
prefix: /opt/conda/envs/zoneinfo

tests/test_zoneinfo.py::CZoneInfoTest::test_bad_keys tests/test_zoneinfo.py::CZoneInfoTest::test_bad_keys_paths tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_bad_keys tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoTest::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoTest::test_bad_keys tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_bad_keys tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_bad_keys tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_bad_keys tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoV1Test::test_bad_keys_paths tests/test_zoneinfo.py::ZoneInfoV1Test::test_bad_keys tests/test_zoneinfo.py::CZoneInfoV1Test::test_bad_keys_paths tests/test_zoneinfo.py::CZoneInfoV1Test::test_bad_keys
tests/test_zoneinfo.py::CZoneInfoPickleTest::test_from_file tests/test_zoneinfo.py::CZoneInfoPickleTest::test_cache_hit tests/test_zoneinfo.py::CZoneInfoPickleTest::test_cache_miss tests/test_zoneinfo.py::CZoneInfoPickleTest::test_pickle_after_from_file tests/test_zoneinfo.py::CZoneInfoPickleTest::test_no_cache tests/test_zoneinfo.py::CZoneInfoTest::test_unambiguous tests/test_zoneinfo.py::CZoneInfoTest::test_repr tests/test_zoneinfo.py::CZoneInfoTest::test_fromutc_errors tests/test_zoneinfo.py::CZoneInfoTest::test_str tests/test_zoneinfo.py::CZoneInfoTest::test_folds_and_gaps tests/test_zoneinfo.py::CZoneInfoTest::test_folds_from_utc tests/test_zoneinfo.py::CZoneInfoTest::test_fold_mutate tests/test_zoneinfo.py::CZoneInfoTest::test_bad_zones tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_folds_and_gaps tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_str tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_fold_mutate tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_fromutc_errors tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_repr tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_bad_zones tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_folds_from_utc tests/test_zoneinfo.py::CZoneInfoDatetimeSubclassTest::test_unambiguous tests/test_zoneinfo.py::ZoneInfoTest::test_folds_and_gaps tests/test_zoneinfo.py::ZoneInfoTest::test_folds_from_utc tests/test_zoneinfo.py::ZoneInfoTest::test_bad_zones tests/test_zoneinfo.py::ZoneInfoTest::test_str tests/test_zoneinfo.py::ZoneInfoTest::test_repr tests/test_zoneinfo.py::ZoneInfoTest::test_unambiguous tests/test_zoneinfo.py::ZoneInfoTest::test_fromutc_errors tests/test_zoneinfo.py::ZoneInfoCacheTest::test_strong_refs tests/test_zoneinfo.py::ZoneInfoCacheTest::test_no_cache tests/test_zoneinfo.py::ZoneInfoCacheTest::test_ephemeral_zones tests/test_zoneinfo.py::ZoneInfoCacheTest::test_clear_cache_one_key tests/test_zoneinfo.py::ZoneInfoCacheTest::test_cache_reset_tzpath tests/test_zoneinfo.py::ZoneInfoCacheTest::test_clear_cache_two_keys tests/test_zoneinfo.py::ZoneInfoCacheTest::test_clear_cache_explicit_none tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_repr tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_folds_and_gaps tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_str tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_fromutc_errors tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_folds_from_utc tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_bad_zones tests/test_zoneinfo.py::CZoneInfoTestSubclass::test_unambiguous tests/test_zoneinfo.py::TzPathTest::test_tzpath_attribute tests/test_zoneinfo.py::TzPathTest::test_tzpath_error tests/test_zoneinfo.py::TzPathTest::test_env_variable tests/test_zoneinfo.py::TzPathTest::test_reset_tzpath_kwarg tests/test_zoneinfo.py::CTestModule::test_getattr_error tests/test_zoneinfo.py::CTestModule::test_dir_contains_all tests/test_zoneinfo.py::CTestModule::test_dir_unique tests/test_zoneinfo.py::ZoneInfoPickleTest::test_cache_miss tests/test_zoneinfo.py::ZoneInfoPickleTest::test_pickle_after_from_file tests/test_zoneinfo.py::ZoneInfoPickleTest::test_from_file tests/test_zoneinfo.py::ZoneInfoPickleTest::test_no_cache tests/test_zoneinfo.py::ZoneInfoPickleTest::test_cache_hit tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_subclass_own_cache tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_bad_zones tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_folds_and_gaps tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_repr tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_folds_from_utc tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_fromutc_errors tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_unambiguous tests/test_zoneinfo.py::ZoneInfoTestSubclass::test_str tests/test_zoneinfo.py::WeirdZoneTest::test_one_zone_dst tests/test_zoneinfo.py::WeirdZoneTest::test_zone_very_large_timestamp tests/test_zoneinfo.py::WeirdZoneTest::test_tz_before_only tests/test_zoneinfo.py::WeirdZoneTest::test_no_tz_str tests/test_zoneinfo.py::WeirdZoneTest::test_one_transition tests/test_zoneinfo.py::WeirdZoneTest::test_empty_zone tests/test_zoneinfo.py::TZStrTest::test_tzstr_from_utc tests/test_zoneinfo.py::TZStrTest::test_tzstr_localized tests/test_zoneinfo.py::TZStrTest::test_invalid_tzstr tests/test_zoneinfo.py::TestModule::test_dir_contains_all tests/test_zoneinfo.py::TestModule::test_getattr_error tests/test_zoneinfo.py::TestModule::test_dir_unique tests/test_zoneinfo.py::CTzPathTest::test_env_variable tests/test_zoneinfo.py::CTzPathTest::test_tzpath_attribute tests/test_zoneinfo.py::CTzPathTest::test_tzpath_error tests/test_zoneinfo.py::CTzPathTest::test_reset_tzpath_kwarg tests/test_zoneinfo.py::CTZStrTest::test_invalid_tzstr tests/test_zoneinfo.py::CTZStrTest::test_tzstr_localized tests/test_zoneinfo.py::CTZStrTest::test_tzstr_from_utc tests/test_zoneinfo.py::CZoneInfoCacheTest::test_no_cache tests/test_zoneinfo.py::CZoneInfoCacheTest::test_cache_reset_tzpath tests/test_zoneinfo.py::CZoneInfoCacheTest::test_clear_cache_explicit_none tests/test_zoneinfo.py::CZoneInfoCacheTest::test_ephemeral_zones tests/test_zoneinfo.py::CZoneInfoCacheTest::test_strong_refs tests/test_zoneinfo.py::CZoneInfoCacheTest::test_clear_cache_two_keys tests/test_zoneinfo.py::CZoneInfoCacheTest::test_clear_cache_one_key tests/test_zoneinfo.py::CWeirdZoneTest::test_no_tz_str tests/test_zoneinfo.py::CWeirdZoneTest::test_one_transition tests/test_zoneinfo.py::CWeirdZoneTest::test_zone_very_large_timestamp tests/test_zoneinfo.py::CWeirdZoneTest::test_empty_zone tests/test_zoneinfo.py::CWeirdZoneTest::test_one_zone_dst tests/test_zoneinfo.py::CWeirdZoneTest::test_tz_before_only tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_repr tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_unambiguous tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_bad_zones tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_folds_and_gaps tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_fromutc_errors tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_folds_from_utc tests/test_zoneinfo.py::ZoneInfoDatetimeSubclassTest::test_str tests/test_zoneinfo.py::ZoneInfoV1Test::test_folds_from_utc tests/test_zoneinfo.py::ZoneInfoV1Test::test_bad_zones tests/test_zoneinfo.py::ZoneInfoV1Test::test_folds_and_gaps tests/test_zoneinfo.py::ZoneInfoV1Test::test_str tests/test_zoneinfo.py::ZoneInfoV1Test::test_fromutc_errors tests/test_zoneinfo.py::ZoneInfoV1Test::test_repr tests/test_zoneinfo.py::ZoneInfoV1Test::test_unambiguous tests/test_zoneinfo.py::CZoneInfoV1Test::test_repr tests/test_zoneinfo.py::CZoneInfoV1Test::test_fromutc_errors tests/test_zoneinfo.py::CZoneInfoV1Test::test_bad_zones tests/test_zoneinfo.py::CZoneInfoV1Test::test_unambiguous tests/test_zoneinfo.py::CZoneInfoV1Test::test_folds_and_gaps tests/test_zoneinfo.py::CZoneInfoV1Test::test_str tests/test_zoneinfo.py::CZoneInfoV1Test::test_folds_from_utc
src/zoneinfo/_tzpath.py src/zoneinfo/_common.py src/zoneinfo/__init__.py
src/zoneinfo/_tzpath.py src/zoneinfo/_common.py src/zoneinfo/__init__.py