© 2017 IEEE. Cloud services are widely used to virtualize themanagement and actuation of the real-world the Internet ofThings (IoT). Due to the increasing privacy concerns regardingquerying untrusted cloud servers, query anonymity has becomea critical issue to all the stakeholders which are related toassessment of the dependability and security of the IoT system. The paper presents our study on the problem of query receiver-anonymityin the cloud-based IoT system, where the trade-offbetween the offered query-anonymity and the incurred communicationis considered. The paper will investigate whether theaccepted worst-case communication cost is sufficient to achieve aspecific query anonymity or not. By way of extensive theoreticalanalysis, it shows that the bounds of worst-case communicationcost is quadratically increased as the offered level of anonymityis increased, and they are quadratic in the network diameter forthe opposite range. Extensive simulation is conducted to verifythe analytical assertions.