diff --git a/authorization_set.cpp b/authorization_set.cpp
index 9f6810d..4cf070c 100644
--- a/authorization_set.cpp
+++ b/authorization_set.cpp
@@ -179,6 +179,32 @@
     memmove(elems_, elems_ + invalid_count, size() * sizeof(*elems_));
 }
 
+void AuthorizationSet::Union(const keymaster_key_param_set_t& set) {
+    if (set.length == 0)
+        return;
+
+    push_back(set);
+    Deduplicate();
+}
+
+void AuthorizationSet::Difference(const keymaster_key_param_set_t& set) {
+    if (set.length == 0)
+        return;
+
+    Deduplicate();
+
+    for (size_t i = 0; i < set.length; i++) {
+        int index = -1;
+        do {
+            index = find(set.params[i].tag, index);
+            if (index != -1 && keymaster_param_compare(&elems_[index], &set.params[i]) == 0) {
+                erase(index);
+                break;
+            }
+        } while (index != -1);
+    }
+}
+
 void AuthorizationSet::CopyToParamSet(keymaster_key_param_set_t* set) const {
     assert(set);
 
diff --git a/authorization_set_test.cpp b/authorization_set_test.cpp
index ddc7df3..f3f4412 100644
--- a/authorization_set_test.cpp
+++ b/authorization_set_test.cpp
@@ -626,5 +626,120 @@
     // The real test here is that valgrind reports no leak.
 }
 
+TEST(Union, Disjoint) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3)
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD));
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD)
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Union, Overlap) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Union, Empty) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2;
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Difference, Disjoint) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4)
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3)
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD));
+
+    // Elements are the same as set1, but happen to be in a different order
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Difference(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Difference, Overlap) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet empty;
+    set1.Difference(set2);
+    EXPECT_EQ(empty, set1);
+    EXPECT_EQ(0U, set1.size());
+}
+
+TEST(Difference, NullSet) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2;
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Difference(set2);
+    EXPECT_EQ(expected, set1);
+}
+
 }  // namespace test
 }  // namespace keymaster
diff --git a/include/keymaster/authorization_set.h b/include/keymaster/authorization_set.h
index ec68de0..1a7894d 100644
--- a/include/keymaster/authorization_set.h
+++ b/include/keymaster/authorization_set.h
@@ -164,6 +164,17 @@
     void Deduplicate();
 
     /**
+     * Adds all elements from \p set that are not already present in this AuthorizationSet.  As a
+     * side-effect, if \p set is not null this AuthorizationSet will end up sorted.
+     */
+    void Union(const keymaster_key_param_set_t& set);
+
+    /**
+     * Removes all elements in \p set from this AuthorizationSet.
+     */
+    void Difference(const keymaster_key_param_set_t& set);
+
+    /**
      * Returns the data in a keymaster_key_param_set_t, suitable for returning to C code.  For C
      * compatibility, the contents are malloced, not new'ed, and so must be freed with free(), or
      * better yet with keymaster_free_param_set, not delete.  The caller takes ownership.