A method of operating an application search system includes storing application records corresponding respectively to applications. The method includes storing, in a privacy record data store, for each application, a global privacy indicator specific to the application and applicable to all users. The method includes, in response to receiving a first search query from a user device, identifying search results responsive to the first search query from the application records. The method includes, for each search result, selectively determining a privacy indicator based on the privacy record data store. The method includes determining a search sensitivity value based on the privacy indicators and declaring the first search query as private based on the search sensitivity value. The method includes transmitting the search results to the user device. The method includes, in response to the first search query being declared as private, transmitting a search privacy indicator to the user device.