diff --git a/java/com/google/gerrit/server/account/AccountResolver.java b/java/com/google/gerrit/server/account/AccountResolver.java
index 632f0c8..2670e52 100644
--- a/java/com/google/gerrit/server/account/AccountResolver.java
+++ b/java/com/google/gerrit/server/account/AccountResolver.java
@@ -704,6 +704,18 @@
         input, searchers, self.get(), this::allVisiblePredicate, AccountResolver::isActive);
   }
 
+  public Result resolveAsUserIgnoreVisibility(CurrentUser asUser, String input)
+      throws ConfigInvalidException, IOException {
+    return resolveAsUserIgnoreVisibility(asUser, input, AccountResolver::isActive);
+  }
+
+  public Result resolveAsUserIgnoreVisibility(
+      CurrentUser asUser, String input, Predicate<AccountState> accountActivityPredicate)
+      throws ConfigInvalidException, IOException {
+    return searchImpl(
+        input, searchers, asUser, this::allVisiblePredicate, accountActivityPredicate);
+  }
+
   /**
    * Resolves all accounts matching the input string by name or email.
    *
diff --git a/java/com/google/gerrit/server/query/change/ChangeQueryBuilder.java b/java/com/google/gerrit/server/query/change/ChangeQueryBuilder.java
index f6fc8db..56a0bbd 100644
--- a/java/com/google/gerrit/server/query/change/ChangeQueryBuilder.java
+++ b/java/com/google/gerrit/server/query/change/ChangeQueryBuilder.java
@@ -24,6 +24,7 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Enums;
 import com.google.common.base.Splitter;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
@@ -230,6 +231,7 @@
   public static final Account.Id OWNER_ACCOUNT_ID = Account.id(0);
   public static final Account.Id NON_UPLOADER_ACCOUNT_ID = Account.id(-1);
   public static final Account.Id NON_CONTRIBUTOR_ACCOUNT_ID = Account.id(-2);
+  public static final Account.Id NON_EXISTING_ACCOUNT_ID = Account.id(-1000);
 
   public static final String OPERATOR_MERGED_BEFORE = "mergedbefore";
   public static final String OPERATOR_MERGED_AFTER = "mergedafter";
@@ -1043,7 +1045,7 @@
           } else if (value.equals(ARG_ID_NON_CONTRIBUTOR)) {
             accounts = Collections.singleton(NON_CONTRIBUTOR_ACCOUNT_ID);
           } else {
-            accounts = parseAccount(value);
+            accounts = parseAccountIgnoreVisibility(value);
           }
         } else if (key.equalsIgnoreCase(ARG_ID_GROUP)) {
           group = parseGroup(value).getUUID();
@@ -1071,17 +1073,17 @@
         if (accounts != null || group != null) {
           throw new QueryParseException("more than one user/group specified (" + value + ")");
         }
-        try {
-          if (value.equals(ARG_ID_OWNER)) {
-            accounts = Collections.singleton(OWNER_ACCOUNT_ID);
-          } else if (value.equals(ARG_ID_NON_UPLOADER)) {
-            accounts = Collections.singleton(NON_UPLOADER_ACCOUNT_ID);
-          } else if (value.equals(ARG_ID_NON_CONTRIBUTOR)) {
-            accounts = Collections.singleton(NON_CONTRIBUTOR_ACCOUNT_ID);
-          } else {
-            accounts = parseAccount(value);
-          }
-        } catch (QueryParseException qpex) {
+        if (value.equals(ARG_ID_OWNER)) {
+          accounts = Collections.singleton(OWNER_ACCOUNT_ID);
+        } else if (value.equals(ARG_ID_NON_UPLOADER)) {
+          accounts = Collections.singleton(NON_UPLOADER_ACCOUNT_ID);
+        } else if (value.equals(ARG_ID_NON_CONTRIBUTOR)) {
+          accounts = Collections.singleton(NON_CONTRIBUTOR_ACCOUNT_ID);
+        } else {
+          accounts = parseAccountIgnoreVisibility(value);
+        }
+
+        if (accounts.contains(NON_EXISTING_ACCOUNT_ID)) {
           // If it doesn't match an account, see if it matches a group
           // (accounts get precedence)
           try {
@@ -1227,7 +1229,7 @@
   @Operator
   public Predicate<ChangeData> owner(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
-    return owner(parseAccount(who, (AccountState s) -> true));
+    return owner(parseAccountIgnoreVisibility(who, (AccountState s) -> true));
   }
 
   private Predicate<ChangeData> owner(Set<Account.Id> who) {
@@ -1240,7 +1242,7 @@
 
   private Predicate<ChangeData> ownerDefaultField(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
-    Set<Account.Id> accounts = parseAccount(who);
+    Set<Account.Id> accounts = parseAccountIgnoreVisibility(who);
     if (accounts.size() > MAX_ACCOUNTS_PER_DEFAULT_FIELD) {
       return Predicate.any();
     }
@@ -1251,7 +1253,7 @@
   public Predicate<ChangeData> uploader(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
     checkOperatorAvailable(ChangeField.UPLOADER_SPEC, "uploader");
-    return uploader(parseAccount(who, (AccountState s) -> true));
+    return uploader(parseAccountIgnoreVisibility(who, (AccountState s) -> true));
   }
 
   private Predicate<ChangeData> uploader(Set<Account.Id> who) {
@@ -1266,7 +1268,7 @@
   public Predicate<ChangeData> attention(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
     checkOperatorAvailable(ChangeField.ATTENTION_SET_USERS, "attention");
-    return attention(parseAccount(who, (AccountState s) -> true));
+    return attention(parseAccountIgnoreVisibility(who, (AccountState s) -> true));
   }
 
   private Predicate<ChangeData> attention(Set<Account.Id> who) {
@@ -1403,7 +1405,7 @@
   @Operator
   public Predicate<ChangeData> commentby(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
-    return commentby(parseAccount(who));
+    return commentby(parseAccountIgnoreVisibility(who));
   }
 
   private Predicate<ChangeData> commentby(Set<Account.Id> who) {
@@ -1417,7 +1419,7 @@
   @Operator
   public Predicate<ChangeData> from(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
-    Set<Account.Id> ownerIds = parseAccount(who);
+    Set<Account.Id> ownerIds = parseAccountIgnoreVisibility(who);
     return Predicate.or(owner(ownerIds), commentby(ownerIds));
   }
 
@@ -1469,7 +1471,7 @@
   @Operator
   public Predicate<ChangeData> reviewedby(String who)
       throws QueryParseException, IOException, ConfigInvalidException {
-    return ChangePredicates.reviewedBy(parseAccount(who));
+    return ChangePredicates.reviewedBy(parseAccountIgnoreVisibility(who));
   }
 
   @Operator
@@ -1722,18 +1724,42 @@
     }
   }
 
-  private Set<Account.Id> parseAccount(
-      String who, java.util.function.Predicate<AccountState> activityFilter)
-      throws QueryParseException, IOException, ConfigInvalidException {
+  private Set<Account.Id> parseAccountIgnoreVisibility(String who)
+      throws QueryRequiresAuthException, IOException, ConfigInvalidException {
     try {
       return args.accountResolver
-          .resolveAsUser(args.getUser(), who, activityFilter)
+          .resolveAsUserIgnoreVisibility(args.getUser(), who)
           .asNonEmptyIdSet();
     } catch (UnresolvableAccountException e) {
       if (e.isSelf()) {
         throw new QueryRequiresAuthException(e.getMessage(), e);
       }
-      throw new QueryParseException(e.getMessage(), e);
+      return ImmutableSet.of(NON_EXISTING_ACCOUNT_ID);
+    }
+  }
+
+  private Set<Account.Id> parseAccountIgnoreVisibility(
+      String who, java.util.function.Predicate<AccountState> activityFilter)
+      throws QueryRequiresAuthException, IOException, ConfigInvalidException {
+    try {
+      return args.accountResolver
+          .resolveAsUserIgnoreVisibility(args.getUser(), who, activityFilter)
+          .asNonEmptyIdSet();
+    } catch (UnresolvableAccountException e) {
+      // Thrown if no account was found.
+
+      // Users can always see their own account. This means if self was being resolved and there was
+      // no match the user wasn't logged it and the request was done anonymously.
+      if (e.isSelf()) {
+        throw new QueryRequiresAuthException(e.getMessage(), e);
+      }
+
+      // If no account is found, we don't want to fail with an error as this would allow users to
+      // probe the existence of accounts (error -> account doesn't exist, empty result -> account
+      // exists but didn't take part in any visible changes). Hence, we return a special account ID
+      // (NON_EXISTING_ACCOUNT_ID) that doesn't match any account so the query can be normally
+      // executed
+      return ImmutableSet.of(NON_EXISTING_ACCOUNT_ID);
     }
   }
 
@@ -1790,7 +1816,7 @@
 
     Predicate<ChangeData> reviewerPredicate = null;
     try {
-      Set<Account.Id> accounts = parseAccount(who);
+      Set<Account.Id> accounts = parseAccountIgnoreVisibility(who);
       if (!forDefaultField || accounts.size() <= MAX_ACCOUNTS_PER_DEFAULT_FIELD) {
         reviewerPredicate =
             Predicate.or(
diff --git a/javatests/com/google/gerrit/acceptance/api/change/QueryChangesIT.java b/javatests/com/google/gerrit/acceptance/api/change/QueryChangesIT.java
index 3220615..43c8684 100644
--- a/javatests/com/google/gerrit/acceptance/api/change/QueryChangesIT.java
+++ b/javatests/com/google/gerrit/acceptance/api/change/QueryChangesIT.java
@@ -372,8 +372,132 @@
     assertThat(result3).hasSize(1);
   }
 
+  /**
+   * This test verifies that querying by a non-visible account doesn't fail.
+   *
+   * <p>Change queries only return changes that are visible to the calling user. If a non-visible
+   * account participated in such a change the existence of this account is known to everyone who
+   * can see the change. Hence it's OK to that the account visibility check is skipped when querying
+   * changes by non-visible accounts. If the account is visible through any visible change these
+   * changes are returned, otherwise the result is empty (see
+   * emptyResultWhenQueryingByNonVisibleAccountAndMatchingChangesAreNotVisible()), same as for
+   * non-existing accounts (see test emptyResultWhenQueryingByNonExistingAccount()).
+   */
   @Test
-  public void accountNotFoundWhenQueryingByNonVisibleSecondaryEmail() throws Exception {
+  @GerritConfig(name = "accounts.visibility", value = "NONE")
+  public void changesCanBeQueriesByNonVisibleAccounts() throws Exception {
+    String ownerEmail = "owner@example.com";
+    Account.Id nonVisibleOwner = accountOperations.newAccount().preferredEmail(ownerEmail).create();
+
+    String reviewerEmail = "reviewer@example.com";
+    Account.Id nonVisibleReviewer =
+        accountOperations.newAccount().preferredEmail(reviewerEmail).create();
+
+    // Create the change.
+    Change.Id changeId = changeOperations.newChange().owner(nonVisibleOwner).create();
+
+    // Add a review.
+    requestScopeOperations.setApiUser(nonVisibleReviewer);
+    gApi.changes().id(changeId.get()).current().review(ReviewInput.recommend());
+
+    requestScopeOperations.setApiUser(user.id());
+
+    // Verify that user can see the change.
+    assertThat(gApi.changes().query("change:" + changeId).get())
+        .comparingElementsUsing(hasChangeId())
+        .containsExactly(changeId);
+
+    // Verify that user cannot see the other accounts.
+    assertThrows(
+        ResourceNotFoundException.class, () -> gApi.accounts().id(nonVisibleOwner.get()).get());
+    assertThrows(
+        ResourceNotFoundException.class, () -> gApi.accounts().id(nonVisibleReviewer.get()).get());
+
+    // Verify that the change is also found if user queries for changes owned/uploaded by
+    // nonVisibleOwner.
+    assertThat(gApi.changes().query("owner:" + ownerEmail).get())
+        .comparingElementsUsing(hasChangeId())
+        .containsExactly(changeId);
+    assertThat(gApi.changes().query("uploader:" + ownerEmail).get())
+        .comparingElementsUsing(hasChangeId())
+        .containsExactly(changeId);
+
+    // Verify that the change is also found if user queries for changes reviewed by
+    // nonVisibleReviewer.
+    assertThat(gApi.changes().query("reviewer:" + reviewerEmail).get())
+        .comparingElementsUsing(hasChangeId())
+        .containsExactly(changeId);
+    assertThat(gApi.changes().query("label:Code-Review+1,user=" + reviewerEmail).get())
+        .comparingElementsUsing(hasChangeId())
+        .containsExactly(changeId);
+  }
+
+  /**
+   * This test verifies that an empty result is returned for a query by a non-existing account.
+   *
+   * <p>Such queries must not return an error so that users cannot probe whether an account exists.
+   * Since we return an empty result for non-visible accounts if there are no matched changes or non
+   * of the matched changes is visible, users could conclude the existence of a account if we would
+   * return an error for non-existing accounts.
+   */
+  @Test
+  public void emptyResultWhenQueryingByNonExistingAccount() throws Exception {
+    assertThat(gApi.changes().query("owner:non-existing@example.com").get()).isEmpty();
+    assertThat(gApi.changes().query("uploader:non-existing@example.com").get()).isEmpty();
+    assertThat(gApi.changes().query("reviewer:non-existing@example.com").get()).isEmpty();
+    assertThat(gApi.changes().query("label:Code-Review+1,user=non-existing@example.com").get())
+        .isEmpty();
+  }
+
+  @Test
+  @GerritConfig(name = "accounts.visibility", value = "NONE")
+  public void emptyResultWhenQueryingByNonVisibleAccountAndMatchingChangesAreNotVisible()
+      throws Exception {
+    String ownerEmail = "owner@example.com";
+    Account.Id nonVisibleOwner = accountOperations.newAccount().preferredEmail(ownerEmail).create();
+
+    String reviewerEmail = "reviewer@example.com";
+    Account.Id nonVisibleReviewer =
+        accountOperations.newAccount().preferredEmail(reviewerEmail).create();
+
+    // Create the change.
+    Change.Id changeId = changeOperations.newChange().owner(nonVisibleOwner).create();
+
+    // Add a review.
+    requestScopeOperations.setApiUser(nonVisibleReviewer);
+    gApi.changes().id(changeId.get()).current().review(ReviewInput.recommend());
+
+    // Block read permission so that the change is not visible.
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(block(Permission.READ).ref("refs/heads/master").group(REGISTERED_USERS))
+        .update();
+
+    requestScopeOperations.setApiUser(user.id());
+
+    // Verify that user cannot see the change.
+    assertThat(gApi.changes().query("change:" + changeId).get()).isEmpty();
+
+    // Verify that user cannot see the other accounts.
+    assertThrows(
+        ResourceNotFoundException.class, () -> gApi.accounts().id(nonVisibleOwner.get()).get());
+    assertThrows(
+        ResourceNotFoundException.class, () -> gApi.accounts().id(nonVisibleReviewer.get()).get());
+
+    // Verify that the change is also found if user queries for changes owned/uploaded by
+    // nonVisibleOwner.
+    assertThat(gApi.changes().query("owner:" + ownerEmail).get()).isEmpty();
+    assertThat(gApi.changes().query("uploader:" + ownerEmail).get()).isEmpty();
+
+    // Verify that the change is also found if user queries for changes reviewed by
+    // nonVisibleReviewer.
+    assertThat(gApi.changes().query("reviewer:" + reviewerEmail).get()).isEmpty();
+    assertThat(gApi.changes().query("label:Code-Review+1,user=" + reviewerEmail).get()).isEmpty();
+  }
+
+  @Test
+  public void emptyResultWhenQueryingByNonVisibleSecondaryEmail() throws Exception {
     String secondaryOwnerEmail = "owner-secondary@example.com";
     Account.Id owner =
         accountOperations
@@ -410,38 +534,16 @@
     assertThrows(
         ResourceNotFoundException.class, () -> gApi.accounts().id(secondaryReviewerEmail).get());
 
-    // Verify that querying for changes owned/uploaded by the secondary email of the owner that is
-    // not visible to user fails.
-    assertThat(
-            assertThrows(
-                BadRequestException.class,
-                () -> gApi.changes().query("owner:" + secondaryOwnerEmail).get()))
-        .hasMessageThat()
-        .isEqualTo(String.format("Account '%s' not found", secondaryOwnerEmail));
-    assertThat(
-            assertThrows(
-                BadRequestException.class,
-                () -> gApi.changes().query("uploader:" + secondaryOwnerEmail).get()))
-        .hasMessageThat()
-        .isEqualTo(String.format("Account '%s' not found", secondaryOwnerEmail));
+    // Verify that the change is not found if user queries for changes owned/uploaded by the
+    // secondary email of the owner that is not visible to user.
+    assertThat(gApi.changes().query("owner:" + secondaryOwnerEmail).get()).isEmpty();
+    assertThat(gApi.changes().query("uploader:" + secondaryOwnerEmail).get()).isEmpty();
 
-    // Verify that querying for changes reviewed by the secondary email of the reviewer doesn't
-    // match the change. Note this is not failing if the specified account doesn't exist or is not
-    // visible because it falls back to searching with the reviewerByEmailPredicate in this case
-    // which is for matching reviewers by email that have no account.
+    // Verify that the change is not found if user queries for changes reviewed by the secondary
+    // email of the reviewer that is not visible to user.
     assertThat(gApi.changes().query("reviewer:" + secondaryReviewerEmail).get()).isEmpty();
-
-    // Verify that querying for changes by label + user with the secondary email of the reviewer
-    // that is not visible to user fails.
-    assertThat(
-            assertThrows(
-                BadRequestException.class,
-                () ->
-                    gApi.changes()
-                        .query("label:Code-Review+1,user=" + secondaryReviewerEmail)
-                        .get()))
-        .hasMessageThat()
-        .isEqualTo(String.format("Account '%s' not found", secondaryReviewerEmail));
+    assertThat(gApi.changes().query("label:Code-Review+1,user=" + secondaryReviewerEmail).get())
+        .isEmpty();
   }
 
   @Test
diff --git a/javatests/com/google/gerrit/acceptance/server/project/ProjectWatchIT.java b/javatests/com/google/gerrit/acceptance/server/project/ProjectWatchIT.java
index cf1eee0..432a6c6 100644
--- a/javatests/com/google/gerrit/acceptance/server/project/ProjectWatchIT.java
+++ b/javatests/com/google/gerrit/acceptance/server/project/ProjectWatchIT.java
@@ -450,8 +450,18 @@
             .to("refs/for/master");
     r.assertOkStatus();
 
-    // assert no email notifications for user
-    assertThat(sender.getMessages()).isEmpty();
+    // Assert email notification for user.
+    // The non-visible account participated in a change that is visible to user, hence through this
+    // change user can see the non-visible account.
+    // Even if watching by the non-visible account was not possible, user could just watch all
+    // changes that are visible to them and then filter them by the non-visible account locally.
+    List<Message> messages = sender.getMessages();
+    assertThat(messages).hasSize(1);
+    Message m = messages.get(0);
+    assertThat(m.rcpt()).containsExactly(user.getNameEmail());
+    assertThat(m.body()).contains("Change subject: subject\n");
+    assertThat(m.body()).contains("Gerrit-PatchSet: 1\n");
+    sender.clear();
   }
 
   @Test