FAdE: Privacy-preserving Targeted Advertising System using Functional Encryption

Abstract

As interest in protecting user privacy began to surge, the online advertising industry, a multi-billion market, is also facing the same challenge. Currently, online ads are delivered through real-time bidding (RTB) and behavioral targeting of users. This is done by tracking users across websites to infer their interests and preferences and then used when selecting ads to present to the user. The user profile sent in the ad request contains data that infringes on user privacy and is delivered to various RTB ecosystem actors, not to mention the data stored by the bidders to increase their performance and profitability. I propose a framework named FAdE to preserve user privacy while enabling behavioral targeting and supporting the current RTB ecosystem by introducing minimal changes in the protocols and data structure. My design leverages the functional encryption (FE) scheme to preserve the user's privacy in behavioral targeted advertising. Specifically, I introduce a trusted third party (TTP) who is the key generator in my FE scheme. The user's profile originally used for behavioral targeting is now encrypted and cannot be decrypted by the participants of the RTB ecosystem. However, the demand-side platforms (DSPs) can submit their functions to the TTP and receive function keys. This function derives a metric, a user score, based on the user profile that can be used in their bidding algorithm. Decrypting the encrypted user profiles with the function keys results in the function's output with the user profile as its input. As a result, the user's privacy is preserved within the RTB ecosystem, while DSPs can still submit their bids through behavioral targeting. My evaluation showed that when using a user profile bit vector of length 2,000, it took less than 20ms to decrypt the encrypted user profile and derive the user score metric through the inner-product function. This is much smaller than my criteria of 50ms, which is based on the typical bidding timeframe (100–1,000ms) used in the ad industry. Moreover, my result is smaller than the state-of-the-art privacy-preserving proposals using homomorphic encryption or multi-party computations. To demonstrate the potential for real-world deployment., I build a prototype implementation of my design that consists of a publisher's website, an ad exchange (ADX), the DSP, and the TTP.

최근 사용자 개인 정보 보호에 대한 관심이 급증하면서 수십억 규모의 시장인 온라인 광고 산업도 같은 문제에 직면해 있다. 현재의 온라인 광고는 Real-time Bidding (RTB)과 사용자 타깃 광고 (targeted advertising)로 대표된다. 이는 웹사이트에서 사용자의 정보를 바탕으로 관심과 선호도를 추정하고 이를 이용해 사용자에게 표시할 적절한 광고를 입찰, 선택하는 방식이다. 광고 요청을 위해 전송되는 user profile에는 사용자의 개인 정보를 침해하는 데이터가 포함되어 있으며, RTB 생태계의 여러 참여자에게 있는 그대로 전달되는 문제점이 있다.

본 연구는 사용자의 개인 정보를 보호하는 동시에 기존의 프로토콜 및 데이터 구조에는 최소한의 변경을 도입함으로써 현재의 RTB 생태계에서 계속해서 타깃 광고가 가능하도록 지원하는 FAdE를 제안한다. 제안하는 디자인은 Functional Encryption (FE)과 그 key 생성자인 Trusted Third Party (TTP)의 도입을 통해 개인정보 보호가 가능한 타깃 광고를 제공한다.

본 디자인에서는, 기존 타깃 광고를 위해 사용되던 user profile을 암호화(encrypt)하여 전달하므로 다른 RTB 환경의 참여자가 해독(decrypt)할 수 없다. Demand Side Platform (DSP)은 광고 요청에 대한 입찰 여부와 입찰가격을 결정하기 위해 암호화된 유저 데이터(encrypted user data, ciphertext)를 사용한다. DSP는 사전에 사용자의 점수를 연산하기 위한 function을 작성하고 이를 TTP에 제출하여 function key를 획득한다. 이 function key를 이용해 암호화된 유저 데이터를 해독(decrypt) 하면 DSP의 내부 입찰 알고리즘에 메트릭(metric)으로 활용할 수 있는 user score를 얻게 되고 이를 입찰 결정에 활용하게 된다. 결과적으로 RTB 환경 내에서 사용자의 개인정보는 보호하면서 DSP는 사용자의 숨겨진 정보를 기반으로 타깃 광고 입찰에 참여할 수 있다.

마지막으로, FAdE 디자인의 실제 활용 가능성에 대한 분석을 진행한다. user profile은 충분한 길이로 확인된 2,000 길이의 0과 1로 이루어진 벡터 (bit vector) 형태로 생성한다. 이 user profile vector를 FE로 암호화(encrypt)한 후, weight vector에 해당하는 임의의 function과 벡터 내적(Inner product) 연산에 소요되는 시간을 측정하였을 때, user score를 도출하는 데 20ms 미만이 소요되는 것을 확인한다. 이는 광고 업계에서 일반적으로 사용되는 입찰 제한 시간(100-1,000ms)을 바탕으로 정의한 본 연구의 자체 기준 50ms 보다 충분히 작은 값에 해당한다. 이 결과는 동형 암호화(Homomorphic Encryption) 또는 Multi-Party Computation(MPC) 등을 사용하는 온라인 광고에서의 다른 개인정보 보호 제안보다 성능 상의 이점을 갖는다. 또한 제안 디자인을 활용해 타깃광고가 실제로 가능함을 확인하기 위해 Publisher 웹사이트, Ad Exchange(ADX), 3개의 DSP 그리고 TTP로 구성된 제안 디자인의 프로토타입 구현을 제시한다.

본 연구에서 제안된 FAdE를 통해 사용자의 개인 정보는 보호하면서 기존과 같은 수준의 타깃 광고가 가능하고, 이를 수용 가능한 수준의 적은 오버헤드로 적용이 가능하였음을 확인하였다. 연구의 결과가 향후 실제 온라인 광고 생태계에서 사용자의 프라이버시 보호에 기여할 수 있을 것으로 기대한다.