diff --git a/java_src/BUILD.bazel b/java_src/BUILD.bazel
index 36cb49e..12d4ebc 100644
--- a/java_src/BUILD.bazel
+++ b/java_src/BUILD.bazel
@@ -155,6 +155,7 @@
         "//src/main/java/com/google/crypto/tink/internal:proto_parameters_serialization",
         "//src/main/java/com/google/crypto/tink/internal:serialization",
         "//src/main/java/com/google/crypto/tink/internal:serialization_registry",
+        "//src/main/java/com/google/crypto/tink/internal:tink_bug_exception",
         "//src/main/java/com/google/crypto/tink/internal:util",
         "//src/main/java/com/google/crypto/tink/jwt:json_util",
         "//src/main/java/com/google/crypto/tink/jwt:jwk_set_converter",
@@ -458,6 +459,7 @@
         "//src/main/java/com/google/crypto/tink/internal:proto_parameters_serialization-android",
         "//src/main/java/com/google/crypto/tink/internal:serialization-android",
         "//src/main/java/com/google/crypto/tink/internal:serialization_registry-android",
+        "//src/main/java/com/google/crypto/tink/internal:tink_bug_exception-android",
         "//src/main/java/com/google/crypto/tink/internal:util-android",
         "//src/main/java/com/google/crypto/tink/jwt:json_util-android",
         "//src/main/java/com/google/crypto/tink/jwt:jwk_set_converter-android",
diff --git a/java_src/src/main/java/com/google/crypto/tink/BUILD.bazel b/java_src/src/main/java/com/google/crypto/tink/BUILD.bazel
index b97c4c7..8175121 100644
--- a/java_src/src/main/java/com/google/crypto/tink/BUILD.bazel
+++ b/java_src/src/main/java/com/google/crypto/tink/BUILD.bazel
@@ -559,6 +559,7 @@
         "//src/main/java/com/google/crypto/tink/internal:mutable_serialization_registry",
         "//src/main/java/com/google/crypto/tink/internal:proto_key_serialization",
         "//src/main/java/com/google/crypto/tink/internal:proto_parameters_serialization",
+        "//src/main/java/com/google/crypto/tink/internal:tink_bug_exception",
         "//src/main/java/com/google/crypto/tink/internal:util",
         "//src/main/java/com/google/crypto/tink/monitoring:monitoring_annotations",
         "//src/main/java/com/google/crypto/tink/tinkkey:key_access",
@@ -598,6 +599,7 @@
         "//src/main/java/com/google/crypto/tink/internal:mutable_serialization_registry-android",
         "//src/main/java/com/google/crypto/tink/internal:proto_key_serialization-android",
         "//src/main/java/com/google/crypto/tink/internal:proto_parameters_serialization-android",
+        "//src/main/java/com/google/crypto/tink/internal:tink_bug_exception-android",
         "//src/main/java/com/google/crypto/tink/internal:util-android",
         "//src/main/java/com/google/crypto/tink/monitoring:monitoring_annotations-android",
         "//src/main/java/com/google/crypto/tink/tinkkey:key_access-android",
diff --git a/java_src/src/main/java/com/google/crypto/tink/KeysetHandle.java b/java_src/src/main/java/com/google/crypto/tink/KeysetHandle.java
index 8733884..e1e1940 100644
--- a/java_src/src/main/java/com/google/crypto/tink/KeysetHandle.java
+++ b/java_src/src/main/java/com/google/crypto/tink/KeysetHandle.java
@@ -23,6 +23,7 @@
 import com.google.crypto.tink.internal.MutableSerializationRegistry;
 import com.google.crypto.tink.internal.ProtoKeySerialization;
 import com.google.crypto.tink.internal.ProtoParametersSerialization;
+import com.google.crypto.tink.internal.TinkBugException;
 import com.google.crypto.tink.monitoring.MonitoringAnnotations;
 import com.google.crypto.tink.proto.EncryptedKeyset;
 import com.google.crypto.tink.proto.KeyData;
@@ -479,7 +480,7 @@
           idRequirement);
     } catch (GeneralSecurityException e) {
       // Cannot happen -- this only happens if the idRequirement doesn't match OutputPrefixType
-      throw new IllegalStateException("Creating a protokey serialization failed", e);
+      throw new TinkBugException("Creating a protokey serialization failed", e);
     }
   }
 
@@ -499,7 +500,7 @@
         return new LegacyProtoKey(protoKeySerialization, InsecureSecretKeyAccess.get());
       } catch (GeneralSecurityException e2) {
         // Cannot happen -- this only throws if we have no access.
-        throw new IllegalStateException("Creating a LegacyProtoKey failed", e2);
+        throw new TinkBugException("Creating a LegacyProtoKey failed", e2);
       }
     }
   }
@@ -530,7 +531,8 @@
       return new KeysetHandle.Entry(
           key, parseStatus(protoKey.getStatus()), id, id == keyset.getPrimaryKeyId());
     } catch (GeneralSecurityException e) {
-      // Cannot happen -- this only happens if protoKey.getStatus() fails.
+      // This may happen if a keyset without status makes it here; we should reject
+      // such keysets earlier instead.
       throw new IllegalStateException("Creating an entry failed", e);
     }
   }
diff --git a/java_src/src/main/java/com/google/crypto/tink/internal/BUILD.bazel b/java_src/src/main/java/com/google/crypto/tink/internal/BUILD.bazel
index d7e62e5..820035a 100644
--- a/java_src/src/main/java/com/google/crypto/tink/internal/BUILD.bazel
+++ b/java_src/src/main/java/com/google/crypto/tink/internal/BUILD.bazel
@@ -450,3 +450,13 @@
         "@maven//:com_google_code_findbugs_jsr305",
     ],
 )
+
+java_library(
+    name = "tink_bug_exception",
+    srcs = ["TinkBugException.java"],
+)
+
+android_library(
+    name = "tink_bug_exception-android",
+    srcs = ["TinkBugException.java"],
+)
diff --git a/java_src/src/main/java/com/google/crypto/tink/internal/TinkBugException.java b/java_src/src/main/java/com/google/crypto/tink/internal/TinkBugException.java
new file mode 100644
index 0000000..1fab855
--- /dev/null
+++ b/java_src/src/main/java/com/google/crypto/tink/internal/TinkBugException.java
@@ -0,0 +1,40 @@
+// Copyright 2022 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+////////////////////////////////////////////////////////////////////////////////
+
+package com.google.crypto.tink.internal;
+
+/**
+ * An exception to be thrown in case there is a bug in Tink.
+ *
+ * <p>This exception is thrown by Tink in cases there is a guaranteed bug in Tink. No non-Tink code
+ * should throw such an exception.
+ */
+public final class TinkBugException extends RuntimeException {
+  /** Constructs a new TinkBugException with the specified detail message. */
+  public TinkBugException(String message) {
+    super(message);
+  }
+
+  /** Constructs a new TinkBugException with the specified detail message and cause. */
+  public TinkBugException(String message, Throwable cause) {
+    super(message, cause);
+  }
+
+  /** Constructs a new TinkBugException as a wrapper on a root cause */
+  public TinkBugException(Throwable cause) {
+    super(cause);
+  }
+}
diff --git a/java_src/src/test/java/com/google/crypto/tink/internal/BUILD.bazel b/java_src/src/test/java/com/google/crypto/tink/internal/BUILD.bazel
index c22eaa9..2a77334 100644
--- a/java_src/src/test/java/com/google/crypto/tink/internal/BUILD.bazel
+++ b/java_src/src/test/java/com/google/crypto/tink/internal/BUILD.bazel
@@ -264,3 +264,13 @@
         "@maven//:junit_junit",
     ],
 )
+
+java_test(
+    name = "TinkBugExceptionTest",
+    size = "small",
+    srcs = ["TinkBugExceptionTest.java"],
+    deps = [
+        "//src/main/java/com/google/crypto/tink/internal:tink_bug_exception",
+        "@maven//:junit_junit",
+    ],
+)
diff --git a/java_src/src/test/java/com/google/crypto/tink/internal/TinkBugExceptionTest.java b/java_src/src/test/java/com/google/crypto/tink/internal/TinkBugExceptionTest.java
new file mode 100644
index 0000000..9fd894f
--- /dev/null
+++ b/java_src/src/test/java/com/google/crypto/tink/internal/TinkBugExceptionTest.java
@@ -0,0 +1,35 @@
+// Copyright 2022 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+////////////////////////////////////////////////////////////////////////////////
+
+package com.google.crypto.tink.internal;
+
+import static org.junit.Assert.assertThrows;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+@RunWith(JUnit4.class)
+public final class TinkBugExceptionTest {
+  private static void throwsTinkBugException() {
+    throw new TinkBugException("I have written a test");
+  }
+
+  @Test
+  public void testException() throws Exception {
+    assertThrows(TinkBugException.class, TinkBugExceptionTest::throwsTinkBugException);
+  }
+}