Electronic health record (EHR), as the core of the e-healthcare system, is an electronic version of patient medical history, which records personal health-related information. EHR embodies the value of disease monitoring through large-scale sharing via the Cloud service provider (CSP). However, the health data-centric feature makes EHR more preferable to the adversaries compared with other outsourcing data. Moreover, there may even be malicious users who deliberately leak their access privileges for benefits. An e-healthcare system with a black-box traceable and robust data security mechanism is presented for the first time. Specifically, we propose an effective P2HBT, which can perform fine-grained access control on encrypted EHRs, prevent the leakage of privacy contained in access policies, and support tracing of traitors. Under the standard model, the scheme is proved fully secure. Performance analysis demonstrates that P2HBT can achieve the design goals and outperform existing schemes in terms of storage and computation overhead.