skip to main content
research-article

Verifiable auctions for online ad exchanges

Published: 27 August 2013 Publication History

Abstract

This paper treats a critical component of the Web ecosystem that has so far received little attention in our community: ad exchanges. Ad exchanges run auctions to sell publishers' inventory-space on Web pages-to advertisers who want to display ads in those spaces. Unfortunately, under the status quo, the parties to an auction cannot check that the auction was carried out correctly, which raises the following more general question: how can we create verifiability in low-latency, high-frequency auctions where the parties do not know each other? We address this question with the design, prototype implementation, and experimental evaluation of VEX. VEX introduces a technique for efficient, privacy-preserving integer comparisons; couples these with careful protocol design; and adds little latency and tolerable overhead.

References

[1]
Cookie Matching. http://developers.google.com/ad-exchange/rtb/cookie-guide, Apr. 2013.
[2]
DoubleClick Ad Exchange Real-Time Bidding Protocol. https://developers.google.com/ad-exchange/rtb/downloads.
[3]
DoubleClick Bid Request Message. https://developers.google.com/ad-exchange/rtb/downloads/realtime-bidding-proto.txt.
[4]
DoubleClick Ad Exchange. http://google.com/doubleclick/advertisers/ad_exchange.html.
[5]
Google Display Network. http://google.com/ads/displaynetwork.
[6]
Fast SHA-256 implementations on Intel architecture processors. http://download.intel.com/embedded/processor/whitepaper/327457.pdf.
[7]
Microsoft Media Network. http://advertising.microsoft.com/advertise/microsoft-media-network.
[8]
OpenX. http://www.openx.com.
[9]
PAPI. http://icl.cs.utk.edu/papi/index.html.
[10]
Rightmedia. http://www.rightmedia.com.
[11]
Source lines of code counter. https://github.com/bytbox/sloc.
[12]
Yahoo! Advertising Solutions. http://advertising.yahoo.com.
[13]
Y. Aumann and Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. Journal of Cryptology, 23(2):281--343, 2010.
[14]
H. Beales. The value of behavioral targeting. http://www.networkadvertising.org/pdfs/Beales_NAI_Study.pdf, 2010.
[15]
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM CCS, Nov. 1993.
[16]
P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach, and T. Toft. Secure multiparty computation goes live. In Financial Cryptography and Data Security, Feb. 2009.
[17]
F. Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT, May 2000.
[18]
F. Brandt. How to obtain full privacy in auctions. International Journal of Information Security, 5(4):201--216, Oct. 2006.
[19]
E. Brickell, D. Chaum, I. Damgård, and J. V. de Graaf. Gradual and verifiable release of a secret. In CRYPTO, Aug. 1987.
[20]
J. Camenisch, R. Chaabouni, and a. shelat. Efficient protocols for set membership and range proofs. In ASIACRYPT, Dec. 2008.
[21]
R. Chaabouni, H. Lipmaa, and B. Zhang. A non-interactive range proof with constant communication. In Financial Cryptography and Data Security, Feb. 2012.
[22]
V. Dave, S. Guha, and Y. Zhang. Measuring and fingerprinting clickspam in online ad networks. In ACM SIGCOMM, Aug. 2012.
[23]
DoubleClick. Search before the purchase: Understanding buyer search activity as it builds to online purchase. http://google.com/doubleclick/research/index.html, Feb. 2005.
[24]
DoubleClick. Profiting from non-guaranteed advertising: The value of dynamic allocation and auction pricing for online publishers. http://www.google.com/doubleclick/pdfs/DC_Ad_Exchange_WP_100713.pdf, 2010.
[25]
DoubleClick. Google white paper: The arrival of real-time bidding and what it means for media buyers. http://google.com/doubleclick/research/index.html, July 2011.
[26]
E. Elkind and H. Lipmaa. Interleaving cryptography and mechanism design: The case of online auctions. In Financial Cryptography, Feb. 2004.
[27]
P. Fauzi, H. Lipmaa, and B. Zhang. New non-interactive zero-knowledge subset sum, decision knapsack and range arguments. Cryptology ePrint Archive, Report 2012/548, Feb. 2013.
[28]
A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In CRYPTO, Nov. 1986.
[29]
M. K. Franklin and M. K. Reiter. The design and implementation of a secure auction service. In IEEE Symposium on Security and Privacy, May 1995.
[30]
S. Guha, B. Cheng, and P. Francis. Privad: Practical privacy in online advertising. In NSDI, Mar. 2011.
[31]
H. Haddadi. Fighting online click-fraud using bluff ads. ACM SIGCOMM CCR, 40(2):22--25, Apr. 2010.
[32]
A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In SOSP, Oct. 2007.
[33]
M. Harkavy, J. D. Tygar, and H. Kikuchi. Electronic auctions with private bids. In USENIX Workshop on Electronic Commerce, Aug. 1998.
[34]
A. Juels. Targeted advertising... and privacy too. In RSA Security Conference, The Cryptographers' Track, Apr. 2001.
[35]
L. Lamport. Password authentication with insecure communication. Communications of the ACM, 24(11):770--772, 1981.
[36]
H. Lipmaa, N. Asokan, and V. Niemi. Secure Vickrey auctions without threshold trust. In Financial Cryptography, Mar. 2002.
[37]
S. Meiklejohn, C. C. Erway, A. Küpçü, T. Hinkle, and A. Lysyanskaya. ZKPDL: A language-based system for efficient zero-knowledge proofs and electronic cash. In USENIX Security Symposium, Aug. 2010.
[38]
S. Muthukrishnan. Ad exchanges: Research issues. In Workshop on Internet and Network Economics. Dec. 2009.
[39]
M. Naor, B. Pinkas, and R. Summer. Privacy preserving auctions and mechanism design. In ACM Conference on Electronic Commerce, Nov. 1999.
[40]
K. Q. Nguyen, Y. Mu, and V. Varadharajan. Digital coins based on hash chain. In National Information Systems Security Conference, Oct. 1997.
[41]
T. Okamoto and J. Stern. Almost uniform density of power residues and the provable security of ESIGN. In ASIACRYPT, Nov. 2003.
[42]
OpenX. Openx handles more than one trillion ad requests in 2011. http://www.openx.com/content/openx-handles-more-one-trillion-ad-requests-2011, 2011.
[43]
D. C. Parkes, M. O. Rabin, S. M. Shieber, and C. A. Thorpe. Practical secrecy-preserving, verifiably correct and trustworthy auctions. In International Conference on Electronic Commerce, Aug. 2006.
[44]
M. O. Rabin, Y. Mansour, S. Muthukrishnan, and M. Yung. Strictly-black-box zero-knowledge and efficient validation of financial transactions. In International Colloquium on Automata, Languages and Programming, July 2012.
[45]
M. O. Rabin, R. A. Servedio, and C. A. Thorpe. Highly efficient secrecy-preserving proofs of correctness of computations and applications. In IEEE Symposium on Logic in Computer Science, July 2007.
[46]
A. Reznichenko, S. Guha, and P. Francis. Auctions in do-not-track compliant internet advertising. In ACM CCS, Oct. 2011.
[47]
N. Singer. Your online attention, bought in an instant. http://www.nytimes.com/2012/11/18/technology/your-online-attention-bought-in-an-instant-by-advertisers.html, Nov. 2012. The New York Times.
[48]
B. Stone-Gross, R. Stevens, R. Kemmerer, C. Kruegel, G. Vigna, and A. Zarras. Understanding fraudulent activities in online ad exchanges. In IMC, Nov. 2011.
[49]
K. Suzuki, K. Kobayashi, and H. Morita. Efficient sealed-bid auction using hash chain. In Information Security and Cryptology, Dec. 2000.
[50]
V. Toubiana, A. Narayanan, D. Boneh, H. Nissenbaum, and S. Barocas. Adnostic: Privacy preserving targeted advertising. In NDSS, Feb. 2010.
[51]
J. Trevathan and W. Read. Undesirable and fraudulent behavior in online auctions. In SECRYPT, Aug. 2006.
[52]
V. Vaidya. Cookie synching. http://www.admonsters.com/blog/cookie-synching, Apr. 2010.
[53]
N. Vratonjic, J. Freudiger, and J.-P. Hubaux. Integrity of the web content: The case of online advertisement. In Workshop on Collaborative Methods for Security and Privacy, Aug. 2010.
[54]
N. Vratonjic, J. Freudiger, J.-P. Hubaux, and M. Felegyhazi. Securing online advertising. Technical Report LCA-REPORT-2008-017, Laboratory for Computer Communications and Applications, École Polytechnique Fédérale de Lausanne, July 2008.
[55]
N. Vratonjic, J.-P. Hubaux, M. Raya, and D. C. Parkes. Security games in online advertising: Can ads help secure the web? In Workshop on Economics of Information Security, June 2010.
[56]
K. Weide. Real-time bidding in the United States and Western Europe, 2010--2015. http://info.pubmatic.com/rs/pubmatic/images/IDC_Real-Time%20Bidding_US_Western%20Europe_Oct2011.pdf, Oct.2011.
[57]
B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In OSDI, Dec. 2002.
[58]
A. C.-C. Yao. How to generate and exchange secrets. In FOCS, Oct. 1986.
[59]
ZenithOptimedia. Quadrennial events to help ad market grow in 2012 despite economic troubles. http://www.zenithoptimedia.com/about-us/press-releases/zenithoptimedia-adspend-forecast-update-dec-2011, Dec. 2011.
[60]
M. Zhao, W. Zhou, A. J. Gurney, A. Haeberlen, M. Sherr, and B. T. Loo. Private and verifiable interdomain routing decisions. In ACM SIGCOMM, Aug. 2012.

Cited By

View all
  • (2022)Digital audio and programmatic ad buying: status and prospects in the post-pandemic contextEl Profesional de la información10.3145/epi.2022.sep.11Online publication date: 29-Sep-2022
  • (2021)CloudExProceedings of the Workshop on Hot Topics in Operating Systems10.1145/3458336.3465278(96-103)Online publication date: 1-Jun-2021
  • (2020)Verifiable state machinesACM SIGOPS Operating Systems Review10.1145/3421473.342147954:1(40-46)Online publication date: 31-Aug-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review
ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
October 2013
595 pages
ISSN:0146-4833
DOI:10.1145/2534169
Issue’s Table of Contents
  • cover image ACM Conferences
    SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
    August 2013
    580 pages
    ISBN:9781450320566
    DOI:10.1145/2486001
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2013
Published in SIGCOMM-CCR Volume 43, Issue 4

Check for updates

Author Tags

  1. ad exchanges
  2. online advertising
  3. verifiable auctions

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)138
  • Downloads (Last 6 weeks)20
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Digital audio and programmatic ad buying: status and prospects in the post-pandemic contextEl Profesional de la información10.3145/epi.2022.sep.11Online publication date: 29-Sep-2022
  • (2021)CloudExProceedings of the Workshop on Hot Topics in Operating Systems10.1145/3458336.3465278(96-103)Online publication date: 1-Jun-2021
  • (2020)Verifiable state machinesACM SIGOPS Operating Systems Review10.1145/3421473.342147954:1(40-46)Online publication date: 31-Aug-2020
  • (2017)ERA: Towards privacy preservation and verifiability for online ad exchangesJournal of Network and Computer Applications10.1016/j.jnca.2017.08.01298(1-10)Online publication date: Nov-2017
  • (2016)In-Depth Survey of Digital Advertising TechnologiesIEEE Communications Surveys & Tutorials10.1109/COMST.2016.251991218:3(2124-2148)Online publication date: Nov-2017
  • (2015)An Efficient, Privacy-Preserving, and Verifiable Online Auction Mechanism for Ad Exchanges2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2015.7417743(1-6)Online publication date: Dec-2015
  • (2015)Incentivizing advertiser networks to submit multiple bidsInternational Journal of Game Theory10.1007/s00182-015-0501-y45:4(1031-1052)Online publication date: 23-Sep-2015
  • (2014)ChoiceNetACM SIGCOMM Computer Communication Review10.1145/2656877.265688644:3(58-65)Online publication date: 28-Jul-2014
  • (2014)POLA: A privacy-preserving protocol for location-based real-time advertising2014 IEEE 33rd International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2014.7017108(1-8)Online publication date: Dec-2014
  • (2023)Verifiable and Privacy-Preserving Ad Exchange for Smart Targeted Advertising2023 20th Annual International Conference on Privacy, Security and Trust (PST)10.1109/PST58708.2023.10320165(1-9)Online publication date: 21-Aug-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media