Alin Tomescu
ABSTRACT
Transparency logs allow users to audit a potentially malicious service, paving the way towards a more accountable Internet. For example, Certificate Transparency (CT) enables domain owners to audit Certificate Authorities (CAs) and detect impersonation attacks. Yet, to achieve their full potential, transparency logs must be bandwidth-efficient when queried by users. Specifically, everyone should be able to efficientlylook up log entries by their keyand efficiently verify that the log remainsappend-only. Unfortunately, without additional trust assumptions, current transparency logs cannot provide both small-sizedlookup proofs and small-sizedappend-only proofs. In fact, one of the proofs always requires bandwidth linear in the size of the log, making it expensive for everyone to query the log. In this paper, we address this gap with a new primitive called anappend-only authenticated dictionary (AAD). Our construction is the first to achieve (poly)logarithmic size for both proof types and helps reduce bandwidth consumption in transparency logs. This comes at the cost of increased append times and high memory usage, both of which remain to be improved to make practical deployment possible.
Supplemental Material
- Heather Adkins. 2011. An update on attempted man-in-the-middle attacks. http://googleonlinesecurity.blogspot.com/2011/08/update-on-attempted-man-in-middle.html. Accessed: 2015-08--22.Google Scholar
- Mustafa Al-Bassam and Sarah Meiklejohn. 2018. Contour: A Practical System for Binary Transparency. In Data Privacy Management, Cryptocurrencies and Blockchain Technology.Google Scholar
- Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. 2016. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In ASIACRYPT'16.Google Scholar
- Muneeb Ali, Jude Nelson, Ryan Shea, and Michael J. Freedman. 2016. Blockstack: A Global Naming and Storage System Secured by Blockchains. In USENIX ATC'16.Google Scholar
- Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. 2017. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In ACM CCS'17.Google ScholarDigital Library
- Aris Anagnostopoulos, Michael T. Goodrich, and Roberto Tamassia. 2001. Persistent Authenticated Dictionaries and Their Applications. In Information Security.Google Scholar
- Paulo S. L. M. Barreto and Michael Naehrig. 2006. Pairing-Friendly Elliptic Curves of Prime Order. In Selected Areas in Cryptography.Google Scholar
- David Basin, Cas Cremers, Tiffany Hyun-Jin Kim, Adrian Perrig, Ralf Sasse, and Pawel Szalachowski. 2014. ARPKI: Attack Resilient Public-Key Infrastructure. In ACM CCS'14.Google ScholarDigital Library
- Mihir Bellare and Adriana Palacio. 2004. The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. In CRYPTO'04.Google ScholarCross Ref
- Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046. https://eprint.iacr.org/2018/046.Google Scholar
- Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent Succinct Arguments for R1CS. In EUROCRYPT'19.Google ScholarDigital Library
- Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2017. Scalable Zero Knowledge Via Cycles of Elliptic Curves. Algorithmica, Vol. 79, 4 (01 Dec 2017).Google ScholarDigital Library
- Josh Benaloh and Michael de Mare. 1994. One-Way Accumulators: A Decentralized Alternative to Digital Signatures. In EUROCRYPT'93.Google ScholarCross Ref
- Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive Composition and Bootstrapping for SNARKS and Proof-carrying Data. In STOC'13.Google Scholar
- Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. 2014. On the Existence of Extractable One-way Functions. In STOC'14.Google Scholar
- Dan Boneh and Xavier Boyen. 2008. Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology, Vol. 21, 2 (2008).Google ScholarCross Ref
- Dan Boneh, Benedikt Bünz, and Ben Fisch. 2018. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains. Cryptology ePrint Archive, Report 2018/1188. https://eprint.iacr.org/2018/1188.Google Scholar
- Joseph Bonneau. 2016. EthIKS: Using Ethereum to audit a CONIKS key transparency log. BITCOIN'16.Google ScholarCross Ref
- Sean Bowe. 2017. Switch from BN254 to BLS12--381. https://github.com/zcash/zcash/issues/2502. Accessed: 2019-02-03.Google Scholar
- Sean Bowe, Ariel Gabizon, and Matthew D. Green. 2019. A Multi-party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK. In Financial Cryptography '19.Google Scholar
- Sean Bowe, Ariel Gabizon, and Ian Miers. 2017. Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model. Cryptology ePrint Archive, Report 2017/1050. https://eprint.iacr.org/2017/1050.Google Scholar
- Elette Boyle and Rafael Pass. 2015. Limits of Extractability Assumptions with Distributional Auxiliary Input. In ASIACRYPT'15.Google Scholar
- Ahto Buldas, Peeter Laud, and Helger Lipmaa. 2000. Accountable Certificate Management using Undeniable Attestations. In ACM CCS'00.Google ScholarDigital Library
- Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. 2018. Bulletproofs: Short Proofs for Confidential Transactions and More. In IEEE S&P'18.Google Scholar
- M. Castro and B. Liskov. 2002. Practical Byzantine Fault Tolerance and Proactive Recovery. TOCS, Vol. 20, 4 (2002).Google Scholar
- Melissa Chase, Apoorvaa Deshpande, and Esha Ghosh. 2018. Privacy Preserving Verifiable Key Directories. Cryptology ePrint Archive, Report 2018/607. https://eprint.iacr.org/2018/607.Google Scholar
- Melissa Chase and Sarah Meiklejohn. 2016. Transparency Overlays and Applications. In ACM CCS'16.Google Scholar
- Laurent Chuat, Pawel Szalachowski, Adrian Perrig, Ben Laurie, and Eran Messeri. 2015. Efficient gossip protocols for verifying the consistency of Certificate logs. In IEEE CNS'15.Google ScholarCross Ref
- Scott A. Crosby and Dan S. Wallach. 2009. Efficient Data Structures for Tamper-evident Logging. In USENIX Security '09.Google Scholar
- Scott A. Crosby and Dan S. Wallach. 2011. Authenticated Dictionaries: Real-World Costs and Trade-Offs. ACM Transactions on Information and System Security, Vol. 14, 2, Article 17 (Sept. 2011).Google ScholarDigital Library
- Rasmus Dahlberg and Tobias Pulls. 2018. Verifiable Light-Weight Monitoring for Certificate Transparency Logs. In NordSec 2018: Secure IT Systems.Google Scholar
- Rasmus Dahlberg, Tobias Pulls, Jonathan Vestin, Toke Høiland-Jørgensen, and Andreas Kassler. 2018. Aggregation-Based Gossip for Certificate Transparency. CoRR, Vol. abs/1806.08817 (2018). arxiv: 1806.08817 http://arxiv.org/abs/1806.08817Google Scholar
- Ivan Damgård and Nikos Triandopoulos. 2008. Supporting Non-membership Proofs with Bilinear-map Accumulators. Cryptology ePrint Archive, Report 2008/538. http://eprint.iacr.org/2008/538.Google Scholar
- Benjamin Dowling, Felix Gü nther, Udyani Herath, and Douglas Stebila. 2016. Secure Logging Schemes and Certificate Transparency. In ESORICS'16.Google Scholar
- Graham Edgecombe. 2016. Compressing X.509 certificates. https://www.grahamedgecombe.com/blog/2016/12/22/compressing-x509-certificates. Accessed: 2018-04--12.Google Scholar
- Adam Eijdenberg, Ben Laurie, and Al Cutter. 2016. Verifiable Data Structures. https://github.com/google/trillian/blob/master/docs/papers/VerifiableDataStructures.pdf. Accessed: 2018-04--12.Google Scholar
- Saba Eskandarian, Eran Messeri, Joseph Bonneau, and Dan Boneh. 2017. Certificate Transparency with Privacy. PoPETs, Vol. 2017, 4 (2017).Google ScholarCross Ref
- Sascha Fahl, Sergej Dechand, Henning Perl, Felix Fischer, Jaromir Smrcek, and Matthew Smith. 2014. Hey, NSA: Stay Away from My Market! Future Proofing App Markets Against Powerful Attackers. In ACM CCS'14.Google ScholarDigital Library
- Ariel J. Feldman, Aaron Blankstein, Michael J. Freedman, and Edward W. Felten. 2012. Social Networking with Frientegrity: Privacy and Integrity with an Untrusted Provider. In USENIX Security '12.Google Scholar
- Ariel J. Feldman, William P. Zeller, Michael J. Freedman, and Edward W. Felten. 2010. SPORC: Group Collaboration Using Untrusted Cloud Resources. In OSDI'10.Google ScholarDigital Library
- Tore Kasper Frederiksen, Yehuda Lindell, Valery Osheter, and Benny Pinkas. 2018. Fast Distributed RSA Key Generation for Semi-honest and Malicious Adversaries. In CRYPTO'18.Google Scholar
- Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. 2013. Quadratic Span Programs and Succinct NIZKs without PCPs. In EUROCRYPT'13.Google ScholarCross Ref
- Craig Gentry and Daniel Wichs. 2011. Separating Succinct Non-interactive Arguments from All Falsifiable Assumptions. In STOC'11.Google ScholarDigital Library
- Google. 2016a. HTTPS encryption on the web: Certificate transparency. https://transparencyreport.google.com/https/certificates. Accessed: 2018-04--12.Google Scholar
- Google. 2016b. Trillian: General Transparency. https://github.com/google/trillian. Accessed: 2018-04--12.Google Scholar
- Vipul Goyal. 2007. Reducing Trust in the PKG in Identity Based Cryptosystems. In CRYPTO'07.Google Scholar
- Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT'10.Google Scholar
- Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In EUROCRYPT'16.Google Scholar
- Benjamin Hof and Georg Carle. 2017. Software Distribution Transparency and Auditability. CoRR, Vol. abs/1711.07278 (2017). arxiv: 1711.07278 http://arxiv.org/abs/1711.07278Google Scholar
- Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. 2015. Zcash Protocol Specification. https://github.com/zcash/zips/blob/master/protocol/protocol.pdf. Accessed: 2017--11--17.Google Scholar
- Antoine Joux. 2000. A One Round Protocol for Tripartite Diffie--Hellman. In Algorithmic Number Theory.Google Scholar
- Nikolaos Karapanos, Alexandros Filios, Raluca Ada Popa, and Srdjan Capkun. 2016. Verena: End-to-End Integrity Protection for Web Applications. In IEEE S&P'16.Google Scholar
- Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. 2010. Constant-Size Commitments to Polynomials and Their Applications. In ASIACRYPT'10.Google ScholarCross Ref
- Aggelos Kiayias, Ozgur Oksuz, and Qiang Tang. 2015. Distributed Parameter Generation for Bilinear Diffie Hellman Exponentiation and Applications. In Information Security.Google Scholar
- Tiffany Hyun-Jin Kim, Lin-Shung Huang, Adrian Perring, Collin Jackson, and Virgil Gligor. 2013. Accountable Key Infrastructure (AKI): A Proposal for a Public-key Validation Infrastructure. In WWW'13.Google Scholar
- Paul C. Kocher. 1998. On certificate revocation and validation. In Financial Cryptography '98.Google ScholarCross Ref
- Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., Vol. 4, 3 (1982), 20.Google ScholarDigital Library
- Ben Laurie. 2015. Revocation Transparency. https://www.links.org/files/RevocationTransparency.pdf. Accessed: 2018-07--31.Google Scholar
- Ben Laurie, Adam Langley, and Emilia Kasper. 2013. RFC: Certificate Transparency. http://tools.ietf.org/html/rfc6962. Accessed: 2015--5--13.Google Scholar
- Jinyuan Li, Maxwell Krohn, David Mazières, and Dennis Shasha. 2004. Secure Untrusted Data Repository (SUNDR). In OSDI'04.Google Scholar
- Jinyuan Li and David Maziéres. 2007. Beyond One-third Faulty Replicas in Byzantine Fault Tolerant Systems. In NSDI'07.Google Scholar
- Vincent Lynch. 2018. Scaling CT Logs: Temporal Sharding. https://www.digicert.com/blog/scaling-certificate-transparency-logs-temporal-sharding/. Accessed: 2019-02-03.Google Scholar
- Ravi Mandalia. 2012. Security breach in CA networks - Comodo, DigiNotar, GlobalSign. http://blog.isc2.org/isc2_blog/2012/04/test.html. Accessed: 2015-08--22.Google Scholar
- Petros Maniatis and Mary Baker. 2003. Authenticated Append-only Skip Lists. CoRR, Vol. cs.CR/0302010 (2003). http://arxiv.org/abs/cs.CR/0302010Google Scholar
- Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Edward W. Felten, and Michael J. Freedman. 2015. Bringing Deployable Key Transparency to End Users. In USENIX Security '15.Google Scholar
- Alfred Menezes, Palash Sarkar, and Shashank Singh. 2017. Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-Based Cryptography. In Mycrypt'16.Google Scholar
- Alfred Menezes, Scott Vanstone, and Tatsuaki Okamoto. 1991. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. In STOC'91.Google ScholarDigital Library
- Ralph C. Merkle. 1982. Method of providing digital signatures.Google Scholar
- Silvio Micali. 2000. Computationally Sound Proofs. SIAM J. Comput., Vol. 30, 4 (2000).Google ScholarDigital Library
- Silvio Micali, Michael Rabin, and Joe Kilian. 2003. Zero-Knowledge Sets. In FOCS'03.Google Scholar
- Silvio Micali, Salil Vadhan, and Michael Rabin. 1999. Verifiable Random Functions. In FOCS'99.Google Scholar
- Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf. Accessed: 2017-03-08.Google Scholar
- Namecoin. 2011. Namecoin. https://namecoin.info/. Accessed: 2015-08--23.Google Scholar
- Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In CRYPTO'03.Google Scholar
- Moni Naor and Kobbi Nissim. 1998. Certificate Revocation and Certificate Update. In USENIX Security '98.Google Scholar
- Lan Nguyen. 2005. Accumulators from Bilinear Pairings and Applications. In CT-RSA'05.Google Scholar
- André Niemann and Jacqueline Brendel. 2014. A Survey on CA Compromises.Google Scholar
- Kirill Nikitin, Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Linus Gasser, Ismail Khoffi, Justin Cappos, and Bryan Ford. 2017. CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds. In USENIX Security '17.Google Scholar
- Alina Oprea and Kevin D. Bowers. 2009. Authentic Time-Stamps for Archival Storage. In ESORICS'09.Google Scholar
- Mark H. Overmars. 1987. Design of Dynamic Data Structures.Google Scholar
- Mark H. Overmars and Jan van Leeuwen. 1981. Worst-case optimal insertion and deletion methods for decomposable searching problems. Inform. Process. Lett., Vol. 12, 4 (1981).Google ScholarCross Ref
- Charalampos Papamanthou and Roberto Tamassia. 2007. Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures. In Information and Communications Security.Google Scholar
- Roel Peeters and Tobias Pulls. 2016. Insynd: Improved Privacy-Preserving Transparency Logging. In ESORICS'16.Google Scholar
- Raluca Ada Popa, Emily Stark, Jonas Helfer, Steven Valdez, Nickolai Zeldovich, M. Frans Kaashoek, and Hari Balakrishnan. 2014. Building Web Applications on Top of Encrypted Data Using Mylar. In NSDI'14.Google Scholar
- Franco P. Preparata and Dilip V. Sarwate. 1977. Computational Fourier Transforms Complexity of Over Finite Fields. Math. Comp., Vol. 31, 139 (1977).Google Scholar
- Tobias Pulls and Roel Peeters. 2015. Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure. In ESORICS'15.Google Scholar
- Leonid Reyzin and Sophia Yakoubov. 2016. Efficient Asynchronous Accumulators for Distributed PKI. In Security and Cryptography for Networks.Google Scholar
- Mark D. Ryan. 2014. Enhanced certificate transparency and end-to-end encrypted mail. In NDSS'14.Google ScholarCross Ref
- Tomas Sander, Amnon Ta-Shma, and Moti Yung. 2001. Blind, Auditable Membership Proofs. In Financial Cryptography '01.Google Scholar
- SCIPR Lab. 2016. libff. https://github.com/scipr-lab/libff. Accessed: 2018-07--28.Google Scholar
- SCIPR Lab. 2016. libfqfft. https://github.com/scipr-lab/libfqfft. Accessed: 2018-07--28.Google Scholar
- Victor Shoup. 2016. libntl. https://www.shoup.net/ntl/. Accessed: 2018-07--28.Google Scholar
- Ryan Sleevi. 2017. Certificate Transparency in Chrome - Change to Enforcement Date. https://groups.google.com/a/chromium.org/forum/#!msg/ct-policy/sz_3W_xKBNY/6jq2ghJXBAAJ. Accessed: 2018-04--20.Google Scholar
- E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, P. Jovanovic, L. Gasser, N. Gailly, I. Khoffi, and B. Ford. 2016. Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning. In IEEE S&P'16.Google Scholar
- Pawel Szalachowski, Stephanos Matsumoto, and Adrian Perrig. 2014. PoliCert: Secure and Flexible TLS Certificate Management. In ACM CCS'14.Google ScholarDigital Library
- Alin Tomescu and Srinivas Devadas. 2017. Catena: Efficient Non-equivocation via Bitcoin. In IEEE S&P'17.Google Scholar
- Jelle van den Hooff, M Frans Kaashoek, and Nickolai Zeldovich. 2014. VerSum: Verifiable Computations over Large Public Logs. In ACM CCS'14.Google ScholarDigital Library
- Joachim von zur Gathen and Jurgen Gerhard. 2013. Fast Euclidean Algorithm. In Modern Computer Algebra 3rd ed.). Cambridge University Press, New York, NY, USA, Chapter 11, 313--333.Google Scholar
- Joachim von zur Gathen and Jurgen Gerhard. 2013. Fast Multiplication. In Modern Computer Algebra 3rd ed.). Cambridge University Press, New York, NY, USA, Chapter 8, 221--254.Google Scholar
- Joachim von zur Gathen and Jurgen Gerhard. 2013. Fast polynomial evaluation and interpolation. In Modern Computer Algebra 3rd ed.). Cambridge University Press, New York, NY, USA, Chapter 10, 295--310.Google Scholar
- Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. 2018. Doubly-Efficient zkSNARKs Without Trusted Setup. In IEEE S&P'18.Google Scholar
- Gavin Wood. 2015. Ethereum: A Secure Decentralised Generalised Transaction Ledger. http://gavwood.com/paper.pdf. Accessed: 2016-05--15.Google Scholar
- Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. DIZK: A Distributed Zero Knowledge Proof System. In USENIX Security '18.Google Scholar
- Jiangshan Yu, Vincent Cheval, and Mark Ryan. 2016. DTKI: A New Formalized PKI with Verifiable Trusted Parties. Comput. J., Vol. 59, 11 (2016).Google Scholar
- Zcash. 2017. What is Jubjub. https://z.cash/technology/jubjub/. Accessed: 2019-02-03.Google Scholar
Index Terms
- Transparency Logs via Append-Only Authenticated Dictionaries
Recommendations
Authenticated Dictionaries: Real-World Costs and Trade-Offs
Authenticated dictionaries are a widely discussed paradigm to enable verifiable integrity for data storage on untrusted servers, such as today’s widely used “cloud computing” resources, allowing a server to provide a “proof,” typically in the form of a ...
Optimal trade-off for Merkle tree traversal
In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle ...
Convertible multi-authenticated encryption scheme
A convertible authenticated encryption (CAE) scheme allows the signer to generate a valid authenticated ciphertext on his chosen message such that only the designated recipient can retrieve the message. Further, the recipient has the ability to convert ...
Comments