With the widespread use of Internet, online advertising, as a newly emerged way of delivering advertisements, has become the focus of attention. Compared with traditional ways of advertising, real-time targeted online advertising is much more efficient and profitable, taking the advantage of abundant online users' profiles. Advertisements can be delivered to potential users who are actually interested in the ad content, which improves the accuracy of advertising, and thus potentially increases advertisers' profits. However, targeted advertising makes use of online users' personal profiles, which raises significant privacy concerns since personal profiles may contain sensitive information. It is interesting but challenging to design a privacy-preserving protocol, which allows advertising platform to effectively deliver ads to interested users, while protecting the users' private information. In this paper, we propose a Privacy-pReserving prOtocol for real-time Targeted Advertising (PROTA). We theoretically prove the privacy properties of PROTA, and show that the system requirements are satisfied. Evaluations are also conducted to demonstrate the feasibility of PROTA.