Guessing statistics and metrics

• Differentially Private Password Frequency Lists
  (dataset)
  Jeremiah Blocki, Anupam Datta and Joseph Bonneau. NDSS 2016. San Diego, CA, USA.
  Abstract Citation
  

  Given a dataset of user-chosen passwords, the frequency list reveals the frequency of each unique password. We present a novel mechanism for releasing perturbed password frequency lists with rigorous security, efficiency, and distortion guarantees. Specifically, our mechanism is based on a novel algorithm for sampling that enables an efficient implementation of the exponential mechanism for differential privacy (naive sampling is exponential time). It provides the security guarantee that an adversary will not be able to use this perturbed frequency list to learn anything about any individual user's password even if the adversary obtains significant background knowledge about the user. We prove that our mechanism introduces minimal distortion, thus ensuring that the released frequency list if close to the actual list. Further, we empirically demonstrate, using the now-canonical password dataset leaked from RockYou, that the mechanism works well in practice: as the differential privacy parameter epsilon varies from 8 to 0.002 (smaller epsilon implies higher security), the normalized distortion coefficient (representing the distance between the released and actual password frequency list divided by the number of users N) varies from 8.8 x 10^-7 to 1.9 x 10-3. Given this appealing combination of security and distortion guarantees, our mechanism enables organizations to publish perturbed password frequency lists. This can facilitate new research comparing password security between populations and evaluating password improvement approaches. To this end, we have collaborated with Yahoo! to use our differentially private mechanism to publicly release a corpus of 50 password frequency lists representing approximately 70 million Yahoo! users. This dataset is now the largest password frequency corpus available. Using our perturbed dataset we are able to closely replicate the original published analysis of this data.

  @inproceedings{BDB16,
          url="https://www.jbonneau.com/doc/BDB16-NDSS-pw_list_differential_privacy.pdf",
          title="{Differentially Private Password Frequency Lists}",
          author="Jeremiah Blocki and Anupam Datta and Joseph Bonneau",
          location="San Diego, CA, USA",
          booktitle="NDSS '16: The 2016 Network and Distributed System Security Symposium",
          year="2016",
  }
  

• Secrets, Lies, and Account Recovery: Lessons from the Use of Personal Knowledge Questions at Google
  Joseph Bonneau, Elie Bursztein, Ilan Caron, Rob Jackson and Mike Williamson. 25th International World Wide Web Conference (WWW).
  

  Best Student Paper

  Abstract Citation
  

  We examine the first large real-world data set on personal knowledge question's security and memorability from their deployment at Google. Our analysis confirms that secret questions generally offer a security level that is far lower than user-chosen passwords. It turns out to be even lower than proxies such as the real distribution of surnames in the population would indicate. Surprisingly, we found that a significant cause of this insecurity is that users often don't answer truthfully. A user survey we conducted revealed that a significant fraction of users (37%) who admitted to providing fake answers did so in an attempt to make them "harder to guess" although on aggregate this behavior had the opposite effect as people "harden" their answers in a predictable way. On the usability side, we show that secret answers have surprisingly poor memorability despite the assumption that their reliability motivates their continued deployment. From millions of account recovery attempts we observed a significant fraction of users (e.g 40% of our English-speaking US users) were unable to recall their answers when needed. This is lower than the success rate of alternative recovery mechanisms such as SMS reset codes (over 80%). Comparing question strength and memorability reveals that the questions that are potentially the most secure (e.g what is your first phone number) are also the ones with the worst memorability. We conclude that it appears next to impossible to find secret questions that are both secure and memorable. Secret questions continue have some use when combined with other signals, but they should not be used alone and best practice should favor more reliable alternatives.

  @inproceedings{BBCJW15,
          url="https://www.jbonneau.com/doc/BBCJW15-WWW-google_personal_knowledge_questions.pdf",
          author="Joseph Bonneau and Elie Bursztein and Ilan Caron and Rob Jackson and Mike Williamson",
          title="{Secrets, Lies, and Account Recovery: Lessons from the Use of Personal Knowledge Questions at Google}",
          booktitle="25th International World Wide Web Conference (WWW)",
          year="2015",
  }
  

• The Tangled Web of Password Reuse
  Anupam Das, Joseph Bonneau, Matthew Caesar, Nikita Borisov and XiaoFeng Wang. NDSS 2014. San Diego, CA, USA.
  Abstract Citation
  

  Today’s Internet services rely heavily on text-based passwords for user authentication. The pervasiveness of these services coupled with the difficulty of remembering large numbers of secure passwords tempts users to reuse passwords at multiple sites. In this paper, we investigate for the first time how an attacker can leverage a known password from one site to more easily guess that user’s password at other sites. We study several hundred thousand leaked passwords from eleven web sites and conduct a user survey on password reuse; we estimate that 43-51% of users reuse the same password across multiple sites. We further identify a few simple tricks users often employ to transform a basic password between sites which can be used by an attacker to make password guessing vastly easier. We develop the first cross-site password-guessing algorithm, which is able to guess 30% of transformed passwords within 100 attempts compared to just 14% for a standard password-guessing algorithm without cross-site password knowledge.

  @inproceedings{DBCBW14,
          url="https://www.jbonneau.com/doc/DBCBW14-NDSS-tangled_web.pdf",
          author="Anupam Das and Joseph Bonneau and Matthew Caesar and Nikita Borisov and XiaoFeng Wang",
          title="{The Tangled Web of Password Reuse}",
          location="San Diego, CA, USA",
          booktitle="NDSS '14: The 2014 Network and Distributed System Security Symposium",
          year="2014",
  }
  

• The science of guessing: analyzing an anonymized corpus of 70 million passwords
  (source code)
  Joseph Bonneau. Security & Privacy (Oakland) 2012. San Francisco, CA, USA.
  

  NSA Award for Best Scientific Cybersecurity Paper of 2012

  Abstract Citation
  

  We report on the largest corpus of user-chosen passwords ever studied, consisting of anonymized password histograms representing almost 70 million Yahoo! users, mitigating privacy concerns while enabling analysis of dozens of subpopulations based on demographic factors and site usage characteristics. This large data set motivates a thorough statistical treatment of estimating guessing difficulty by sampling from a secret distribution. In place of previously used metrics such as Shannon entropy and guessing entropy, which cannot be estimated with any realistically sized sample, we develop partial guessing metrics including a new variant of guesswork parameterized by an attacker's desired success rate. Our new metric is comparatively easy to approximate and directly relevant for security engineering. By comparing password distributions with a uniform distribution which would provide equivalent security against different forms of guessing attack, we estimate that passwords provide fewer than 10 bits of security against an online, trawling attack, and only about 20 bits of security against an optimal offline dictionary attack. We find surprisingly little variation in guessing difficulty; every identifiable group of users generated a comparably weak password distribution. Security motivations such as the registration of a payment card have no greater impact than demographic factors such as age and nationality. Even pro-active efforts to nudge users towards better password choices with graphical feedback make little difference. More surprisingly, even seemingly distant language communities choose the same weak passwords and an attacker never gains more than a factor of 2 efficiency gain by switching from the globally optimal dictionary to a population-specific lists.

  @inproceedings{B12,
          url="https://www.jbonneau.com/doc/B12-IEEESP-analyzing_70M_anonymized_passwords.pdf",
          author="Joseph Bonneau",
          title="{The science of guessing: analyzing an anonymized corpus of 70 million passwords}",
          location="San Francisco, CA, USA",
          booktitle="2012 IEEE Symposium on Security and Privacy",
          year="2012",
  }
  

• Guessing human-chosen secrets (PhD dissertation)
  (bindable version) (tech report version) (DSpace version) (source code)
  Joseph Bonneau.
  Abstract Citation
  

  Authenticating humans to computers remains a notable weak point in computer security despite decades of effort. Although the security research community has explored dozens of proposals for replacing or strengthening passwords, they appear likely to remain entrenched as the standard mechanism of human-computer authentication on the Internet for years to come. Even in the optimistic scenario of eliminating passwords from most of today's authentication protocols using trusted hardware devices or trusted servers to perform federated authentication, passwords will persist as a means of ``last-mile'' authentication between humans and these trusted single sign-on deputies. This dissertation studies the difficulty of guessing human-chosen secrets, introducing a sound mathematical framework modeling human choice as a skewed probability distribution. We introduce a new metric, alpha-guesswork, which can accurately models the resistance of a distribution against all possible guessing attacks. We also study the statistical challenges of estimating this metric using empirical data sets which can be modeled as a large random sample from the underlying probability distribution. This framework is then used to evaluate several representative data sets from the most important categories of human-chosen secrets to provide reliable estimates of security against guessing attacks. This includes collecting the largest-ever corpus of user-chosen passwords, with nearly 70 million, the largest list of human names ever assembled for research, the largest data sets of real answers to personal knowledge questions and the first data published about human choice of banking PINs. This data provides reliable numbers for designing security systems and highlights universal limitations of human-chosen secrets.

  @phdthesis{B12b,
          url="https://www.jbonneau.com/doc/2012-jbonneau-phd_thesis.pdf",
          author="Joseph Bonneau",
          title="{Guessing human-chosen secrets}",
          school="University of Cambridge",
          year="2012",
  }
  

• Statistical metrics for individual password strength
  Joseph Bonneau. Twentieth International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  We propose several possible metrics for measuring the strength of an individual password or any other secret drawn from a known, skewed distribution. In contrast to previous ad hoc approaches which rely on textual properties of passwords, we consider the problem without any knowledge of password structure. This enables rating the strength of a password given a large sample distribution without assuming anything about password semantics. We compare the results of our generic metrics against those of the NIST metrics and other previous ``entropy-based'' metrics for a large password dataset, which suggest over-fitting in previous metrics.

  @inproceedings{B12a,
          url="https://www.jbonneau.com/doc/B12-SPW-statistical_password_strength_metrics.pdf",
          author="Joseph Bonneau",
          title="{Statistical metrics for individual password strength}",
          location="Cambridge, UK",
          booktitle="SPW '12: 20\textsuperscript{th} International Workshop on Security Protocols",
          year="2012",
  }
  

• Linguistic properties of multi-word passphrases
  Joseph Bonneau and Ekaterina Shutova. USEC '12: Workshop on Usable Security. Kralendijk, Bonaire, Netherlands.
  Abstract Citation
  

  We examine patterns of human choice in a passphrase-based authentication system deployed by Amazon, a large online merchant. We tested the availability of a large corpus of over 100,000 possible phrases at Amazon's registration page, which prohibits using any phrase already registered by another user. A number of large, readily-available lists such as movie and book titles prove effective in guessing attacks, suggesting that passphrases are vulnerable to dictionary attacks like all schemes involving human choice. Extending our analysis with natural language phrases extracted from linguistic corpora, we find that phrase selection is far from random, with users strongly preferring simple noun bigrams which are common in natural language. The distribution of chosen passphrases is less skewed than the distribution of bigrams in English text, indicating that some users have attempted to choose phrases randomly. Still, the distribution of bigrams in natural language is not nearly random enough to resist offline guessing, nor are longer three- or four-word phrases for which we see rapidly diminishing returns.

  @inproceedings{BS12,
          url="https://www.jbonneau.com/doc/BS12-USEC-passphrase_linguistics.pdf",
          author="Joseph Bonneau and Ekaterina Shutova",
          title="{Linguistic properties of multi-word passphrases}",
          location="Kralendijk, Bonaire, Netherlands",
          booktitle="USEC '12: Workshop on Usable Security",
          year="2012",
  }
  

• A birthday present every eleven wallets? The security of customer-chosen banking PINs
  (RockYou PIN plot) (iPhone PIN plot)
  Joseph Bonneau, Sören Preibusch and Ross Anderson. FC '12: The 16th International Conference on Financial Cryptography. Kralendijk, Bonaire, Netherlands.
  Abstract Citation
  

  We provide the first published estimates of the difficulty of guessing a human-chosen 4-digit PIN. We begin with two large sets of 4-digit sequences chosen outside banking for online passwords and smartphone unlock-codes. We use a regression model to identify a small number of dominant factors influencing user choice. Using this model and a survey of over 1,100 banking customers, we estimate the distribution of banking PINs as well as the frequency of security-relevant behaviour such as sharing and reusing PINs. We find that guessing PINs based on the victims' birthday, which nearly all users carry documentation of, will enable a competent thief to gain use of an ATM card once for every 11-18 stolen wallets, depending on whether banks prohibit weak PINs such as 1234. The lesson for cardholders is to never use one's date of birth as a PIN. The lesson for card-issuing banks is to implement a denied PIN list, which several large banks still fail to do. However, blacklists cannot effectively mitigate guessing given a known birth date, suggesting banks should move away from customer-chosen banking PINs in the long term.

  @inproceedings{BPA12,
          url="https://www.jbonneau.com/doc/BPA12-FC-banking_pin_security.pdf",
          author="Joseph Bonneau and S{\"{o}}ren Preibusch and Ross Anderson",
          title="{A birthday present every eleven wallets? The security of customer-chosen banking PINs}",
          location="Kralendijk, Bonaire, Netherlands",
          booktitle="FC '12: Proceedings of the the 16\textsuperscript{th} International Conference on Financial Cryptography",
          year="2012",
  }
  

• What's in a Name? Evaluating Statistical Attacks on Personal Knowledge Questions
  (dataset)
  Joseph Bonneau, Mike Just and Greg Matthews. FC '10: The 14th International Conference on Financial Cryptography. Tenerife, Spain.
  Abstract Citation
  

  We study the efficiency of statistical attacks on human authentication systems relying on personal knowledge questions. We adapt techniques from guessing theory to measure security against a trawling attacker attempting to compromise a large number of strangers' accounts. We then examine a diverse corpus of real-world statistical distributions for likely answer categories such as the names of people, pets, and places and find that personal knowledge questions are significantly less secure than graphical or textual passwords. We also demonstrate that statistics can be used to increase security by proactively shaping the answer distribution to lower the prevalence of common responses.

  @inproceedings{BJM10,
          url="https://www.jbonneau.com/doc/BJM10-FC-name_guessing_statistics.pdf",
          author="Joseph Bonneau and Mike Just and Greg Matthews",
          title="{What's in a Name? Evaluating Statistical Attacks on Personal Knowledge Questions}",
          location="Tenerife, Spain",
          booktitle="FC '10: Proceedings of the the 14\textsuperscript{th} International Conference on Financial Cryptography",
          year="2010",
  }
  

Web authentication in practice

• Passwords and the Evolution of Imperfect Authentication
  Joseph Bonneau, Cormac Herley, Paul C. van Oorschot and Frank Stajano. Communications of the ACM.
  Abstract Citation
  

  Theory on passwords has lagged behind practice, where large providers use back-end smarts to survive with imperfect technology. Simplistic models of user and attacker behaviors have led the research community to emphasize the wrong threats. Authentication is a classification problem amenable to machine learning, with many signals in addition to the password available to large Web services. Passwords will continue as a useful signal for the foreseeable future, where the goal is not impregnable security but reducing harm at acceptable cost.

  @article{BHOS15,
          author="Joseph Bonneau and Cormac Herley and Paul C. {van Oorschot} and Frank Stajano",
          vol="58",
          no="7",
          title="{Passwords and the Evolution of Imperfect Authentication}",
          url="https://www.jbonneau.com/doc/BHOS15-CACM-imperfect_authentication.pdf",
          journal="Communications of the ACM",
          year="2015",
  }
  

• Cracking-Resistant Password Vaults using Natural Language Encoders
  Rahul Chatterjee, Joseph Bonneau, Ari Juels and Thomas Ristenpart. Security & Privacy (Oakland) 2015. San Francisco, CA, USA.
  Abstract Citation
  

  Password vaults are increasingly popular applications that store multiple passwords encrypted under a single master password that the user memorizes. A password vault can greatly reduce the burden on a user of remembering passwords, but introduces a single point of failure. An attacker that obtains a user's encrypted vault can mount offline brute-force attacks and, if successful, compromise all of the passwords in the vault. In this paper, we investigate the construction of encrypted vaults that resist such offline cracking attacks and force attackers instead to mount online attacks. Our contributions are as follows. We present an attack and supporting analysis showing that a previous design for cracking-resistant vaults—the only one of which we are aware—actually degrades security relative to conventional password-based approaches. We then introduce a new type of secure encoding scheme that we call a natural language encoder (NLE). An NLE permits the construction of vaults which, when decrypted with the wrong master password, produce plausible-looking decoy passwords. We show how to build NLEs using existing tools from natural language processing, such as $n$-gram models and probabilistic context-free grammars, and evaluate their ability to generate plausible decoys. Finally, we present, implement, and evaluate a full, NLE-based cracking-resistant vault system called NoCrack.

  @inproceedings{CBJR15,
          url="https://www.jbonneau.com/doc/CBJR15-IEEESP-cracking_resistant_password_vaults.pdf",
          author="Rahul Chatterjee and Joseph Bonneau and Ari Juels and Thomas Ristenpart",
          title="{Cracking-Resistant Password Vaults using Natural Language Encoders}",
          location="San Francisco, CA, USA",
          booktitle="IEEE Symposium on Security and Privacy",
          year="2015",
  }
  

• Of contraseñas, סיסמאות, and 密码: Character encoding issues for web passwords
  Joseph Bonneau and Rubin Xu. Web 2.0 Security & Privacy. San Francisco, CA, USA.
  Abstract Citation
  

  Password authentication remains ubiquitous on the web, primarily because of its low cost and compatibility with any device which allows a user to input text. Yet text is not universal. Computers must use a character encoding system to convert human-comprehensible writing into bits. We examine for the first time the lingering effects of character encoding on the password ecosystem. We report a number of bugs at large websites which reveal that non-ASCII passwords are often poorly supported, even by websites otherwise correctly supporting the recommended Unicode/UTF-8 character encoding system. We also study user behaviour through several leaked data sets of passwords chosen by English, Chinese, Hebrew and Spanish speakers as case studies. Our findings suggest that most users still actively avoid using characters outside of the original ASCII character set even when allowed to. Coping strategies include transliterating non-ASCII passwords using ASCII, changing keyboard mappings to produce nonsense ASCII passwords, and using passwords consisting entirely of numbers or of a geometric pattern on the keyboard. These last two strategies may reduce resistance to guessing attacks for passwords chosen by non-English speakers.

  @inproceedings{BX12,
          url="https://www.jbonneau.com/doc/BX12-W2SP-passwords_character_encoding.pdf",
          author="Joseph Bonneau and Rubin Xu",
          title="{Of contrase{\~{n}}as, sysmawt, and m\`{i}m\v{a}: Character encoding issues for web passwords}",
          location="San Francisco, CA, USA",
          booktitle="W2SP '12: Workshop on Web 2.0 Security {\&} Privacy",
          year="2012",
  }
  

• The Quest to Replace Passwords: A Framework for Comparative Evaluation of Web Authentication Schemes
  (full-length technical report)
  Joseph Bonneau, Cormac Herley, Paul C. van Oorschot and Frank Stajano. Security & Privacy (Oakland) 2012. San Francisco, CA, USA.
  Abstract Citation
  

  We evaluate two decades of proposals to replace text passwords for general-purpose user authentication on the web using a broad set of twenty-five usability, deployability and security benefits that an ideal scheme might provide. The scope of proposals we survey is also extensive, including password management software, federated login protocols, graphical password schemes, cognitive authentication schemes, one-time passwords, hardware tokens, phone-aided schemes and biometrics. Our comprehensive approach leads to key insights about the difficulty of replacing passwords. Not only does no known scheme come close to providing all desired benefits: none even retains the full set of benefits that legacy passwords already provide. In particular, there is a wide range from schemes offering minor security benefits beyond legacy passwords, to those offering significant security benefits in return for being more costly to deploy or more difficult to use. We conclude that many academic proposals have failed to gain traction because researchers rarely consider a sufficiently wide range of real-world constraints. Beyond our analysis of current schemes, our framework provides an evaluation methodology and benchmark for future web authentication proposals.

  @inproceedings{BHOS12,
          url="https://www.jbonneau.com/doc/BHOS12-IEEESP-quest_to_replace_passwords.pdf",
          author="Joseph Bonneau and Cormac Herley and Paul C. {van Oorschot} and Frank Stajano",
          title="{The Quest to Replace Passwords: A Framework for Comparative Evaluation of Web Authentication Schemes}",
          location="San Francisco, CA, USA",
          booktitle="2012 IEEE Symposium on Security and Privacy",
          year="2012",
  }
  

• Getting web authentication right: a best-case protocol for the remaining life of passwords
  Joseph Bonneau. 19th International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  We outline an end-to-end password authentication protocol for the web designed to be stateless and as secure as possible given legacy limitations of the web browser and performance constraints of commercial web servers. Our scheme is secure against very strong but passive attackers able to observe both network traffic and the server's database state. At the same time, our scheme is simple for web servers to implement and requires no changes to modern, HTML5-compliant browsers. We assume TLS is available for initial login and no other public-key cryptographic operations, but successfully defend against cookie-stealing and cookie-forging attackers and provide strong resistance to password guessing attacks.

  @inproceedings{B11,
          url="https://www.jbonneau.com/doc/B11-SPW-web_auth_right.pdf",
          author="Joseph Bonneau",
          title="{Getting web authentication right: a best-case protocol for the remaining life of passwords}",
          location="Cambridge, UK",
          booktitle="SPW '11: 19\textsuperscript{th} International Workshop on Security Protocols",
          year="2011",
  }
  

• The Password Game: negative externalities from weak password practices
  Sören Preibusch and Joseph Bonneau. GameSec 2010: Conference on Decision and Game Theory for Security. Berlin, Germany.
  Abstract Citation
  

  The combination of username and password is widely used as a human authentication mechanism on the Web. Despite this universal adoption and despite their long tradition, password schemes exhibit a high number of security flaws which jeopardise the confidentiality and integrity of personal information. As Web users tend to reuse the same password for several sites, security negligence at any one site introduces a negative externality into the entire password ecosystem. We analyse this market inefficiency as the equilibrium between password deployment strategies at security-concerned Web sites and indifferent Web sites. The game-theoretic prediction is challenged by an empirical analysis. By a manual inspection of 150 public Web sites that offer free yet password-protected sign-up, complemented by an automated sampling of 2184 Web sites, we demonstrate that observed password practices follow the theory: Web sites that have little incentive to invest in security are indeed found to have weaker password schemes, thereby facilitating the compromise of other sites. We use the theoretical model to explore which technical and regulatory approaches could eliminate the empirically detected inefficiency in the market for password protection.

  @inproceedings{PB10,
          url="https://www.jbonneau.com/doc/PB09-GS-password_game.pdf",
          author="S{\"{o}}ren Preibusch and Joseph Bonneau",
          title="{The Password Game: negative externalities from weak password practices}",
          location="Berlin, Germany",
          booktitle="GameSec 2010: Conference on Decision and Game Theory for Security",
          year="2010",
  }
  

• The password thicket: technical and market failures in human authentication on the web
  Joseph Bonneau and Sören Preibusch. WEIS '10: The 9th Workshop on the Economics of Information Security. Boston, MA, USA.
  Abstract Citation
  

  We report the results of the first large-scale empirical analysis of password implementations deployed on the Internet. Our study included 150 websites which offer free user accounts for a variety of purposes, including the most popular destinations on the web and a random sample of e-commerce, news, and communication websites. Although all sites evaluated relied on user-chosen textual passwords for authentication, we found many subtle but important technical variations in implementation with important security implications. Many poor practices were commonplace, such as a lack of encryption to protect transmitted passwords, storage of cleartext passwords in server databases, and little protection of passwords from brute force attacks. While a spectrum of implementation quality exists with a general correlation between implementation choices within more-secure and less-secure websites, we find a surprising number of inconsistent choices within individual sites, suggesting that the lack of a standards is harming security. We observe numerous ways in which the technical failures of lower-security sites can compromise higher-security sites due to the well-established tendency of users to re-use passwords. Our data confirms that the worst security practices are indeed found at sites with few security incentives, such as newspaper websites, while sites storing more sensitive information such as payment details or user communication implement more password security. From an economic viewpoint, password insecurity is a negative externality that the market has been unable to correct, undermining the viability of password-based authentication. We also speculate that some sites deploying passwords do so primarily for psychological reasons, both as a justification for collecting marketing data and as a way to build trusted relationships with customers. This theory suggests that efforts to replace passwords with more-secure protocols or federated identity systems may fail because they don't recreate the entrenched ritual of password authentication.

  @inproceedings{BP10,
          url="https://www.jbonneau.com/doc/BP10-WEIS-password_thicket.pdf",
          author="Joseph Bonneau and S{\"{o}}ren Preibusch",
          title="{The password thicket: technical and market failures in human authentication on the web}",
          location="Boston, MA, USA",
          booktitle="WEIS '10: Proceedings of the 9\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2010",
  }
  

Security and privacy in the social web

• “I was told to buy a software or lose my computer. I ignored it”: A study of ransomware
  Camelia Simoiu, Christopher Gates, Joseph Bonneau and Sharad Goel. SOUPS 2019: The 15th Symposium On Usable Privacy and Security. Santa Clara, CA, USA.
  Abstract Citation
  

  Ransomware has received considerable news coverage in recent years, in part due to several attacks against high-profile corporate targets. Little is known, however, about the prevalence and characteristics of ransomware attacks on the general population, what proportion of users pay, or how users perceive risks and respond to attacks. Using a detailed survey of a representative sample of 1,180 American adults, we estimate that 2%–3% of respondents were affected over a 1-year period between 2016 and 2017. The average payment amount demanded was $530 and only a small fraction of affected users (about 4% of those affected) reported paying. Perhaps surprisingly, cryptocurrencies were typically only one of several payment options, suggesting that they may not be a primary driver of ransomware attacks. We conclude our analysis by developing a simple proof-of-concept method for risk-assessment based on self-reported security habits.

  @inproceedings{SGBG19,
          url="https://www.usenix.org/system/files/soups2019-simoiu.pdf",
          author="Camelia Simoiu and Christopher Gates and Joseph Bonneau and Sharad Goel",
          title="{``I was told to buy a software or lose my computer. I ignored it'': A study of ransomware}",
          location="Santa Clara, CA, USA",
          booktitle="SOUPS '19: The 15\textsuperscript{th} Symposium On Usable Privacy and Security",
          year="2019",
  }
  

• Cognitive Disconnect: Understanding Facebook Connect Login Permissions
  (abridged version)
  Nicky Robinson and Joseph Bonneau. COSN '14: ACM Conference on Online Social Networks. Dublin, Ireland.
  Abstract Citation
  

  We study Facebook Connect's permissions system using crawling, experimentation, and user surveys. We find several areas in which it it works differently than many users and developers expect. More permissions can be granted than developers intend. In particular, permissions that allow a site to post to the user's profile are granted on an all-or-nothing basis. While users generally understand what data sites can read from their profile, they generally do not understand the full extent of what sites can post. In the case of write permissions, we show that user expectations are influenced by the identity of the requesting site although this has no impact on what is actually enforced. We also find that users generally do not understand the way Facebook Connect permissions interact with Facebook's privacy settings. Our results suggest that users understand detailed, granular messages better than those that are broad and vague.

  @inproceedings{RB14,
          author="Nicky Robinson and Joseph Bonneau",
          title="{Cognitive Disconnect: Understanding Facebook Connect Login Permissions}",
          url="https://www.jbonneau.com/doc/RB14-COSN-understanding_facebook_login_permissions.pdf",
          location="Dublin, Ireland",
          booktitle="COSN '14: ACM Conference on Online Social Networks",
          year="2014",
  }
  

• Clarity of Facebook Connect login permissions (poster)
  Nicky Robinson and Joseph Bonneau. SOUPS 2014: The 10th Symposium On Usable Privacy and Security. Menlo Park, CA, USA.
  Abstract Citation
  

  Single Sign-On (SSO) systems allow users to log in to websites using their username and password from a third-party identity provider. This means fewer passwords for users to remember which theoretically means they can create more complicated and therefore more secure passwords. Facebook Connect, based off of OAuth, is perhaps the most common SSO system. It does more than just allow a user to sign in: sites can request access to parts of the user’s Facebook profile. When the developer integrates the login system with their website, they request various permissions from Facebook to read information from the user’s profile or publish content to their profile. Users logging in with Facebook Connect place a lot of trust in Facebook to only share information that the user authorizes. This relies both on Facebook granting only the permissions presented in the authorization messages and users correctly interpreting these messages. We explored user understanding of authorization messages via an online survey conducted over Amazon Mechanical Turk presenting users with Facebook permissions dialogues and asking them to identify which permissions would be granted if they approved the applications. We identified a number of areas where user understanding is inconsistent with the mechanics of Facebook Connect. In general, users believe that Facebook Connect authorizes far less information to be shared than it actually authorizes.

  @inproceedings{RB14a,
          url="https://www.jbonneau.com/doc/RB14-SOUPS-facebook_login_permissions_poster_abstract.pdf",
          author="Nicky Robinson and Joseph Bonneau",
          title="{Clarity of Facebook Connect login permissions (poster)}",
          location="Menlo Park, CA, USA",
          booktitle="SOUPS 2014: The 10\textsuperscript{th} Symposium On Usable Privacy and Security",
          year="2014",
  }
  

• Privacy concerns of implicit secondary factors for web authentication
  Joseph Bonneau, Edward W. Felten, Prateek Mittal and Arvind Narayanan. WAY 2014: Who are you?! Adventures in Authentication Workshop. Menlo Park, CA, USA.
  Citation
  

  @inproceedings{BFMN14,
          url="https://www.jbonneau.com/doc/BFMN14-WAY-privacy_issues_implicit_web_authentication.pdf",
          author="Joseph Bonneau and Edward W. Felten and Prateek Mittal and Arvind Narayanan",
          title="{Privacy concerns of implicit secondary factors for web authentication}",
          location="Menlo Park, CA, USA",
          booktitle="WAY 2014: Who are you?! Adventures in Authentication Workshop",
          year="2014",
  }
  

• The privacy landscape: product differentiation on data collection
  Sören Preibusch and Joseph Bonneau. WEIS '11: The 10th Workshop on the Economics of Information Security. Washington, DC, USA.
  Abstract Citation
  

  Whilst the majority of online consumers do not seem to take the privacy characteristics of goods and services into account with their consumption choices, a sizeable proportion consider differences in data collection and processing amongst alternative suppliers when deciding where to buy. Meeting their heterogeneous privacy preferences would require varied privacy regimes between different suppliers. Based on an empirical evaluation of 140 Web sites across five industries, we consider two questions: (1) can privacy-conscious consumers find a privacy-friendly seller/provider? (2) is this alternative associated with higher prices? We interpret the empirical evidence using the economic model of horizontal differentiation. As an overarching conclusion, differentiation on privacy is more prevalent in markets where consumption is priced—an observation that confirms the prediction from theory. Surprisingly, sellers that collect less data charge lower prices, with high significance. Implications for regulation and for further study are discussed.

  @inproceedings{PB11,
          url="https://www.jbonneau.com/doc/PB11-WEIS-privacy_landscape.pdf",
          author="S{\"{o}}ren Preibusch and Joseph Bonneau",
          title="{The privacy landscape: product differentiation on data collection}",
          location="Washington, DC, USA",
          booktitle="WEIS '11: Proceedings of the 10\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2011",
  }
  

• Don't Tread on Me: Moderating Access to OSN Data with SpikeStrip
  Christo Wilson, Alessandra Sala, Joseph Bonneau, Robert Zablit and Ben Zhao. WOSN 2010: The 3rd Workshop on Online Social Networks. Boston, Massachussets.
  Abstract Citation
  

  Online social networks rely on their valuable data stores to attract users and produce income. Their survival depends on the ability to protect users’ profiles and disseminate it to other users through controlled channels. Given the sparse user adoption of privacy policies, however, there is increasing incentive and opportunity for malicious parties to extract these datasets for profit using automated “crawlers” and “screen-scrapers.” With the arrival of distributed botnets and low-cost hosted VMs, attackers can perform fast, distributed crawls that evade traditional detectors and rate limiters. We propose SpikeStrip, a server add-on that uses light-weight link encryption to isolate and rate limit crawlers. We experiment with real OSN data, and show that SpikeStrip successfully curtails sophisticated, distributed crawlers while imposing minimal server throughput overhead and inconvenience to end-users.

  @inproceedings{WSBZZ09,
          url="https://www.cs.ucsb.edu/~ravenben/publications/pdf/spikestrip-wosn10.pdf",
          author="Christo Wilson and Alessandra Sala and Joseph Bonneau and Robert Zablit and Ben Zhao",
          title="{Don't Tread on Me: Moderating Access to OSN Data with SpikeStrip }",
          location="Boston, Massachussets",
          booktitle="WOSN 2010: The 3\textsuperscript{rd} Workshop on Online Social Networks",
          year="2010",
  }
  

• Privacy-Enhanced Public View for Social Graphs
  Hyoungshick Kim and Joseph Bonneau. SWSM '09: The 2nd Workshop on Social Web Search and Mining. Hong Kong, China.
  Abstract Citation
  

  We consider the problem of releasing a limited public view of a sensitive graph which reveals at least k edges per node. We are motivated by Facebook’s public search listings, which ex- pose user profiles to search engines along with a fixed number of each user’s friends. If this public view is produced by uniform random sampling, an adversary can accurately approximate many sensitive features of the original graph, including the degree of individual nodes. We propose several schemes to produce public views which hide degree informa- tion. We demonstrate the practicality of our schemes using real data and show that it is possible to mitigate inference of degree while still providing useful public views.

  @inproceedings{KB09,
          url="https://www.jbonneau.com/doc/KB09-SWSM-privacy_public_view.pdf",
          author="Hyoungshick Kim and Joseph Bonneau",
          title="{Privacy-Enhanced Public View for Social Graphs}",
          location="Hong Kong, China",
          booktitle="SWSM '09: The 2\textsuperscript{nd} Workshop on Social Web Search and Mining",
          year="2009",
  }
  

• Privacy Preserving Social Networking Over Untrusted Networks
  Jonathan Anderson, Claudia Diaz, Joseph Bonneau and Frank Stajano. WOSN 2009: The 2nd ACM SIGCOMM Workshop on Online Social Networks. Barcelona, Spain.
  Abstract Citation
  

  Current social networks require users to place absolute faith in their operators, and the inability of operators to protect users from malicious agents has led to sensitive private in formation being made public. We propose an architecture for social networking that protects users’ social information from both the operator and other network users. This archi tecture builds a social network out of smart clients and an untrusted central server in a way that removes the need for faith in network operators and gives users control of their privacy.

  @inproceedings{ADBS09,
          url="https://www.jbonneau.com/doc/ADBS09-WOSN-privacy_enabling_sns.pdf",
          author="Jonathan Anderson and Claudia Diaz and Joseph Bonneau and Frank Stajano",
          title="{Privacy Preserving Social Networking Over Untrusted Networks}",
          location="Barcelona, Spain",
          booktitle="WOSN 2009: The 2\textsuperscript{nd} ACM SIGCOMM Workshop on Online Social Networks",
          year="2009",
  }
  

• Prying Data out of a Social Network
  Joseph Bonneau, Jonathan Anderson and George Danezis. ASONAM 09: The 1st International Conference on Advances in Social Networks Analysis and Mining. Athens, Greece.
  Abstract Citation
  

  Preventing adversaries from compiling significant amounts of user data is a major challenge for social network operators. We examine the difficulty of collecting profile and graph information from the popular social networking website Facebook and report two major findings. First, we describe several novel ways in which data can be extracted by third parties. Second, we demonstrate the efficiency of these methods on crawled data. Our findings highlight how the current pro tection of personal data is inconsistent with users’ expectations of privacy.

  @inproceedings{BAD09,
          url="https://www.jbonneau.com/doc/BAS09-ASONAM-prying_sns_data.pdf",
          author="Joseph Bonneau and Jonathan Anderson and George Danezis",
          title="{Prying Data out of a Social Network}",
          location="Athens, Greece",
          booktitle="ASONAM 09: The 1\textsuperscript{st} International Conference on Advances in Social Networks Analysis and Mining",
          year="2009",
  }
  

• Privacy Stories: Confidence in Privacy Behaviors through End User Programming (poster)
  (abstract)
  Luke Church, Jonathan Anderson, Joseph Bonneau and Frank Stajano. SOUPS 2009: The 5th Symposium On Usable Privacy and Security. Mountain View, CA, USA.
  Abstract Citation
  

  In [2] we argued that, in the search to give users meaningful control over their information, we should consider End User Programming techniques as a possible replacement for either opaque, expert determined choices or the endless proliferation of options that arises from a simplistic application of direct manipulation principles. We describe a work in progress to study the viability of this approach for improving the usability of social network privacy configuration. As suggested in [2] we make use of analytical usability techniques to discuss the usability challenges of the current Facebook interface and to inform the design of our proposed alternative. We then report on a very small (two­ user) pilot study and look at challenges that we will address in future design iterations.

  @inproceedings{CABS09,
          url="https://www.jbonneau.com/doc/CABS09-SOUPS-poster-privacy_stories.pdf",
          author="Luke Church and Jonathan Anderson and Joseph Bonneau and Frank Stajano",
          title="{Privacy Stories: Confidence in Privacy Behaviors through End User Programming (poster)}",
          location="Mountain View, CA, USA",
          booktitle="SOUPS 2009: The 5\textsuperscript{th} Symposium On Usable Privacy and Security",
          year="2009",
  }
  

• Privacy Suites: Shared Privacy for Social Networks (poster)
  (abstract)
  Joseph Bonneau, Jonathan Anderson and Luke Church. SOUPS 2009: The 5th Symposium On Usable Privacy and Security. Mountain View, CA, USA.
  Abstract Citation
  

  Creating privacy controls for social networks that are both expressive and usable is a major challenge. Lack of user understanding of privacy settings can lead to unwanted disclosure of private information and, in some cases, to material harm. We propose a new paradigm which allows users to easily choose “suites” of privacy settings which have been specified by friends or trusted experts, only modifying them if they wish. Given that most users currently stick with their default, operator-chosen settings, such a system could dramatically increase the privacy protection that most users experience with minimal time investment.

  @inproceedings{BAC09d,
          url="https://www.jbonneau.com/doc/ADBS09-WOSN-privacy_enabling_sns.pdf",
          journal="SOUPS '09: Symposium on Usable Privacy and Security",
          author="Joseph Bonneau and Jonathan Anderson and Luke Church",
          title="{Privacy Suites: Shared Privacy for Social Networks (poster)}",
          location="Mountain View, CA, USA",
          booktitle="SOUPS 2009: The 5\textsuperscript{th} Symposium On Usable Privacy and Security",
          year="2009",
  }
  

• Security APIs for Online Applications
  Jonathan Anderson, Joseph Bonneau and Frank Stajano. 3rd International Workshop on Analysis of Security APIs. Port Jefferson, NY, USA.
  Abstract Citation
  

  Online social networks, in their current form, require users to place a vast amount of trust in the operators of both the core network and the third-party applications they use. Since both of these actors have shown themselves to be untrustworthy in the past [1], [2], [3], [4], [5], we have proposed a model for social networks in which client software runs on the user’s computer, encrypted blocks are stored on a “dumb” server and third-party applications are sandboxed to avoid the leakage of personal information [6]. In this scheme, the interface between applications and the core client software resembles a system call API in which a kernel offers applications the means to perform privileged operations. We have begun exploring this API to determine its functional requirements and desired security properties, but we welcome comments from and engagement with the security API community in order to provide the users of social networks with meaningful promises of personal privacy.

  @inproceedings{ABS09,
          url="https://www.jbonneau.com/doc/ABS09-ASA-security_apis_online_apps.pdf",
          author="Jonathan Anderson and Joseph Bonneau and Frank Stajano",
          title="{Security APIs for Online Applications}",
          location="Port Jefferson, NY, USA",
          booktitle="3\textsuperscript{rd} International Workshop on Analysis of Security APIs",
          year="2009",
  }
  

• The Privacy Jungle: On the Market for Privacy in Social Networks
  (abridged paper)
  Joseph Bonneau and Sören Preibusch. WEIS '09: The 8th Workshop on the Economics of Information Security. London, UK.
  Abstract Citation
  

  We have conducted the first thorough analysis of the market for privacy practices and policies in online social networks. From an evaluation of 45 social networking sites using 260 criteria we find that many popular assumptions regarding privacy and social networking need to be revisited when considering the entire ecosystem instead of only a handful of well-known sites. Contrary to the common perception of an oligopolistic market, we find evidence of vigorous competition for new users. Despite observing many poor security practices, there is evidence that social network providers are making efforts to implement privacy enhancing technologies with substantial diversity in the amount of privacy control offered. However, privacy is rarely used as a selling point, even then only as auxiliary, non-decisive feature. Sites also failed to promote their existing privacy controls within the site. We similarly found great diversity in the length and content of formal privacy policies, but found an opposite promotional trend: though almost all policies are not accessible to ordinary users due to obfuscating legal jargon, they conspicuously vaunt the sites’ privacy practices. We conclude that the market for privacy in social networks is dysfunctional in that there is significant variation in sites’ privacy controls, data collection requirements, and legal privacy policies, but this is not effectively conveyed to users. Our empirical findings motivate us to introduce the novel model of a privacy communication game, where the economically rational choice for a site operator is to make privacy control available to evade criticism from privacy fundamentalists, while hiding the privacy control interface and privacy policy to maximise sign-up numbers and encourage data sharing from the pragmatic majority of users.

  @inproceedings{BP09,
          url="https://www.jbonneau.com/doc/BP09-WEIS-privacy_jungle.pdf",
          author="Joseph Bonneau and S{\"{o}}ren Preibusch",
          title="{The Privacy Jungle: On the Market for Privacy in Social Networks}",
          location="London, UK",
          booktitle="WEIS '09: Proceedings of the 8\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2009",
  }
  

• Eight Friends Are Enough: Social Graph Approximation via Public Listings
  Joseph Bonneau, Jonathan Anderson, Frank Stajano and Ross Anderson. SNS '09: The 2nd ACM Workshop on Social Network Systems. Nuremberg, Germany.
  Abstract Citation
  

  The popular social networking website Facebook exposes a “public view” of user profiles to search engines which includes eight of the user’s friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.

  @inproceedings{BASA09,
          url="https://www.jbonneau.com/doc/BASA09-SNS-eight_friends.pdf",
          author="Joseph Bonneau and Jonathan Anderson and Frank Stajano and Ross Anderson",
          title="{Eight Friends Are Enough: Social Graph Approximation via Public Listings}",
          location="Nuremberg, Germany",
          booktitle="SNS '09: Proceedings of the 2\textsuperscript{nd} ACM Workshop on Social Network Systems",
          year="2009",
  }
  

Side channel cryptanalysis

• Robust Final-Round Cache-Trace Attacks Against AES
  Joseph Bonneau.
  Abstract Citation
  

  This paper describes an algorithm to attack AES using side-channel information from the final round cache lookups performed by the encryption, specifically whether each access hits or misses in the cache, building off of previous work by Aciicmez and Koc. It is assumed that an attacker could gain such a trace through power consumption analysis or electromagnetic analysis. This information has already been shown to lead to an effective attack. This paper interprets cache trace data available as binary constraints on pairs of key bytes then reduces key search to a constraint-satisfaction problem. In this way, an attacker is guaranteed to perform as little search as is possible given a set of cache traces, leading to a natural tradeoff between online collection and offline processing. This paper also differs from previous work in assuming a partially pre-loaded cache, proving that cache trace attacks are still effective in this scenario with the number of samples required being inversely related to the percentage of cache which is pre-loaded.

  @techreport{B06,
          url="https://www.jbonneau.com/doc/B06-eprint-aes_cache_trace.pdf",
          institution="Cryptology ePrint Archive",
          number="2006/374",
          author="Joseph Bonneau",
          title="{Robust Final-Round Cache-Trace Attacks Against AES}",
          year="2006",
  }
  

• Cache Collision Timing Attacks Against AES
  (source code)
  Joseph Bonneau and Ilya Mironov. CHES '06: Workshop on Cryptographic Hardware and Embedded Systems. Boston, MA, USA.
  Abstract Citation
  

  This paper describes several novel timing attacks against the common table-driven software implementation of the AES cipher. We define a general attack strategy using a simplified model of the cache to predict timing variation due to cache-collisions in the sequence of lookups performed by the encryption. The attacks presented should be applicable to most high-speed software AES implementations and computing platforms, we have implemented them against OpenSSL v. 0.9.8.(a) running on Pentium III, Pentium IV Xeon, and UltraSPARC III+ machines. The most powerful attack has been shown under optimal conditions to reliably recover a full 128-bit AES key with 2^13 timing samples, an improvement of almost four orders of magnitude over the best previously published attacks of this type [Ber05]. While the task of defending AES against all timing attacks is challenging, a small patch can significantly reduce the vulnerability to these specific attacks with no performance penalty.

  @inproceedings{BM06,
          url="https://www.jbonneau.com/doc/BM06-CHES-aes_cache_timing.pdf",
          author="Joseph Bonneau and Ilya Mironov",
          title="{Cache Collision Timing Attacks Against AES}",
          location="Boston, MA, USA",
          booktitle="CHES '06: Proceedings of 2006 Workshop on Cryptographic Hardware and Embedded Systems",
          year="2006",
  }
  

Secure messaging

• NOTRY: Deniable messaging with retroactive avowal
  Faxing Wang, Shaanan Cohney, Riad Wahby and Joseph Bonneau. PETS 2024. Bristol, England, UK.
  Abstract Citation
  

  Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke the deniability of a conversation and avow its contents after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated verifier proofs (ADV proofs) which may be of independent interest. Our implementation of the protocol incurs an 8× communication and computation performance overhead over the basic Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as key exchanges (the source of the overhead) still complete in just over 1ms.

  @inproceedings{WCWB24,
          url="https://eprint.iacr.org/2023/1926",
          institution="",
          author="Faxing Wang and Shaanan Cohney and Riad Wahby and Joseph Bonneau",
          title="{NOTRY: Deniable messaging with retroactive avowal}",
          location="Bristol, England, UK",
          booktitle="PETS '24: The 18\textsuperscript{th} Privacy Enhancing Technologies Symposium",
          year="2024",
  }
  

• VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries
  Nirvan Tyagi, Ben Fisch, Andrew Zitek, Joseph Bonneau and Stefano Tessaro. ACM CCS 2022. Los Angeles, CA, USA.
  Abstract Citation
  

  Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server. Applications include distribution of public keys, routing information or software binaries. Existing proposals for verifiable registries rely on global invariants being audited whenever the registry is updated. Clients typically rely on trusted third-party auditors, as large registries become expensive to audit. We propose several new protocols for client-auditable registries that enable efficient verification of many updates to the registry, removing the need for third-party auditors. Our solutions use incrementally-verifiable computation (IVC) and/or RSA accumulators. Our evaluation shows that our constructions meet practical throughput requirements (60 updates / second), which is 100x faster than naive solutions using IVC. Clients save 100-10^4x bandwidth and computation costs over prior solutions requiring auditing every update.

  @inproceedings{TFZBT22,
          url="https://eprint.iacr.org/2021/627.pdf",
          author="Nirvan Tyagi and Ben Fisch and Andrew Zitek and Joseph Bonneau and Stefano Tessaro",
          title="{VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries}",
          location="Los Angeles, CA, USA",
          booktitle="CCS '22: Proceedings of the 29\textsuperscript{th} ACM Conference on Computer and Communications Security",
          year="2022",
  }
  

• Obstacles to the Adoption of Secure Communication Tools
  Ruba Abu-Salma, M. Angela Sasse, Joseph Bonneau, Anastasia Danilova, Alena Naiakshina and Matthew Smith. IEEE Security & Privacy (Oakland) 2017. San Francisco, CA, USA.
  Abstract Citation
  

  The computer security community has advocated widespread adoption of secure communication tools to counter mass surveillance. Several popular personal communication tools (e.g., WhatsApp, iMessage) have adopted end-to-end encryption, and many new tools (e.g., Signal, Telegram) have been launched with security as a key selling point. However it remains unclear if users understand what protection these tools offer, and if they value that protection. In this study, we interviewed 60 partici- pants about their experience with different communication tools and their perceptions of the tools’ security properties. We found that the adoption of secure communication tools is hindered by fragmented user bases and incompatible tools. Furthermore, the vast majority of participants did not understand the essential concept of end-to-end encryption, limiting their motivation to adopt secure tools. We identified a number of incorrect mental models that underpinned these beliefs.

  @inproceedings{ASBDNS17,
          url="https://www.jbonneau.com/doc/ASBDNS17-IEEESP-secure_messaging_obstacles.pdf",
          author="Ruba Abu-Salma and M. Angela Sasse and Joseph Bonneau and Anastasia Danilova and Alena Naiakshina and Matthew Smith",
          title="{Obstacles to the Adoption of Secure Communication Tools}",
          location="San Francisco, CA, USA",
          booktitle="IEEE Symposium on Security and Privacy",
          year="2017",
  }
  

• Can Unicorns Help Users Compare Crypto Key Fingerprints?
  (supporting material)
  Joshua Tan, Lujo Bauer, Joseph Bonneau, Lorrie Faith Cranor, Jeremy Thomas and Blase Ur. CHI 2017. Denver, CO, USA.
  Abstract Citation
  

  Many authentication schemes ask users to manually compare compact representations of cryptographic keys, known as fingerprints. If the fingerprints do not match, that may signal a man-in-the-middle attack. An adversary performing an attack may use a fingerprint that is similar to the target fingerprint, but not an exact match, to try to fool inattentive users. Fingerprint representations should thus be both usable and secure. We tested the usability and security of eight fingerprint representations under different configurations. In a 661-participant between-subjects experiment, participants compared fingerprints under realistic conditions and were subjected to a simulated attack. The best configuration allowed attacks to succeed 6% of the time; the worst 72%. We find the seemingly effective compare-and-select approach performs poorly for key fingerprints and that graphical fingerprint representations, while intuitive and fast, vary in performance. We identify some fingerprint representations as particularly promising.

  @inproceedings{TBBCTU17,
          url="https://joshktan.com/papers/chi17.pdf",
          author="Joshua Tan and Lujo Bauer and Joseph Bonneau and Lorrie Faith Cranor and Jeremy Thomas and Blase Ur",
          title="{Can Unicorns Help Users Compare Crypto Key Fingerprints?}",
          location="Denver, CO, USA",
          booktitle="CHI '17: The ACM CHI Conference on Human Factors in Computing Systems",
          year="2017",
  }
  

• Secure Chat for the Masses? User-centered Security to the Rescue (poster)
  Ruba Abu-Salma, M. Angela Sasse and Joseph Bonneau. ACM CCS 2015. Denver, CO, USA.
  Abstract Citation
  

  In light of recent revelations of mass state surveillance of phone and Internet communications, many solutions now claim to provide secure messaging. This includes both a broad range of new projects and several widely adopted applications that have added security features. However, despite the demand for better solutions, there is no clear winner in the race for widespread development and deployment of messaging tools. Recently, the Electronic Frontier Foundation (EFF) Secure Messaging Scorecard has evaluated dozens of messaging tools based on security best practices [14]. Motivated by this work, our goal is to expand the scorecard by evaluating messaging tools on a range of usefulness (usability and utility) attributes. We believe this work can uncover many interesting challenges for the research community.

  @inproceedings{ASB15,
          author="Ruba Abu-Salma and M. Angela Sasse and Joseph Bonneau",
          title="{Secure Chat for the Masses? User-centered Security to the Rescue (poster)}",
          location="Denver, CO, USA",
          booktitle="CCS '15: Proceedings of the 22\textsuperscript{nd} ACM Conference on Computer and Communications Security",
          year="2015",
  }
  

• CONIKS: Bringing Key Transparency to End Users
  Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Michael J. Freedman and Edward W. Felten. USENIX Security 2015. Washington, DC, USA.
  

  2017 PET Award

  Abstract Citation
  

  We present CONIKS, an end-user key verification service capable of integration in end-to-end encrypted communication systems. CONIKS builds on transparency log proposals for web server certificates but solves several new challenges specific to key verification for end users. CONIKS obviates the need for global third-party monitors and enables users to efficiently monitor their own key bindings for consistency, downloading less than 20 kB per day to do so even for a provider with billions of users. CONIKS users and providers can collectively audit providers for non-equivocation, and this requires downloading a constant 2.5 kB per provider per day. Additionally, CONIKS preserves the level of privacy offered by today's major communication services, hiding the list of usernames present and even allowing providers to conceal the total number of users in the system.

  @inproceedings{MBBFF15,
          url="https://www.jbonneau.com/doc/MBBFF15-coniks.pdf",
          author="Marcela S. Melara and Aaron Blankstein and Joseph Bonneau and Michael J. Freedman and Edward W. Felten",
          title="{CONIKS: Bringing Key Transparency to End Users}",
          location="Washington, DC, USA",
          booktitle="Proceedings of the 24th USENIX Security Symposium",
          year="2015",
  }
  

• SoK: Secure Messaging
  (abridged paper)
  Nik Unger, Sergej Dechand, Joseph Bonneau, Sascha Fahl, Henning Perl, Ian Goldberg and Matthew Smith. Security & Privacy (Oakland) 2015. San Francisco, CA, USA.
  Abstract Citation
  

  Motivated by recent revelations of widespread state surveillance of personal communication, many solutions now claim to offer secure and private messaging. This includes both a large number of new projects and many widely adopted tools that have added security features. The intense pressure in the past two years to deliver solutions quickly has resulted in varying threat models, incomplete objectives, dubious security claims, and a lack of broad perspective on the existing cryptographic literature on secure communication. In this paper, we evaluate and systematize current secure messaging solutions and propose an evaluation framework for their security, usability, and ease-of-adoption properties. We consider solutions from academia, but also identify innovative and promising approaches used "in-the-wild" that are not considered by the academic literature. We identify three key challenges and map the design landscape for each: trust establishment, conversation security, and transport privacy. Trust establishment approaches offering strong security and privacy features perform poorly from a usability and adoption perspective, whereas some hybrid approaches that have not been well studied in the academic literature might provide better trade-offs in practice. In contrast, once trust is established, conversation security can be achieved without any user involvement in most two-party conversations, though conversations between larger groups still lack a good solution. Finally, transport privacy appears to be the most difficult problem to solve without paying significant performance penalties.

  @inproceedings{UDBFPGS15,
          url="https://www.jbonneau.com/doc/UDBFPGS15-IEEESP-secure_messaging_sok.pdf",
          author="Nik Unger and Sergej Dechand and Joseph Bonneau and Sascha Fahl and Henning Perl and Ian Goldberg and Matthew Smith",
          title="{SoK: Secure Messaging}",
          location="San Francisco, CA, USA",
          booktitle="IEEE Symposium on Security and Privacy",
          year="2015",
  }
  

• Finite State Security Analysis of OTR Version 2
  Joseph Bonneau and Andrew Morrison.
  Abstract Citation
  

  Off-the-Record messaging is a protocol for enabling secure, authenticated, deniable messaging with perfect forward secrecy, specifically over instant messaging networks. In this paper we describe the results of a finite-state security analysis of the OTR protocol. In addition to finding several security issues in the process of modeling the protocol, our model has discovered security problems in both the authenticated key exchange and data exchange phases of the protocol. The security problem during data exchange leads to an attack where by an active attacker can modify a message without detection by either party or disruption of the protocol. In addition to describing the attacks found, we describe possible solutions where appropriate.

  @unpublished{BM06a,
          url="https://www.jbonneau.com/doc/BM06-OTR_v2_analysis.pdf",
          author="Joseph Bonneau and Andrew Morrison",
          title="{Finite State Security Analysis of OTR Version 2}",
          year="2006",
  }
  

Miscellaneous

• Scrambling for lightweight censorship resistance
  Joseph Bonneau and Rubin Xu. 19th International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  In this paper we propose scrambling as a lightweight method of censorship resistance, in place of the traditional use of encryption. We consider a censor which can only block banned content by scanning it while in transit (for example using deep-packet inspection), instead of attacking the communication endpoints (for example using address filtering or taking servers offline). Our goal is to greatly increase the workload of the censor by scrambling all data during communication, while maintaining reasonable workloads for the endpoints of the communication network. In particular, our goal is to make it impossible for the censor to effectively accelerate the de-scrambling procedure over what may be achieved by commodity PCs or mobile phones at the endpoints, a goal which we term \emph{high-inertia} scrambling. We also aim to achieve this using the standard JavaScript runtime environment of modern browsers, requiring no distribution or installation of censorship-resistance software.

  @inproceedings{BX11,
          url="https://www.jbonneau.com/doc/BX11-SPW-scrambling_censorship.pdf",
          author="Joseph Bonneau and Rubin Xu",
          title="{Scrambling for lightweight censorship resistance}",
          location="Cambridge, UK",
          booktitle="SPW '11: 19\textsuperscript{th} International Workshop on Security Protocols",
          year="2011",
  }
  

• Inglourious Installers: Security in the Application Marketplace
  Jonathan Anderson, Joseph Bonneau and Frank Stajano. WEIS '10: The 9th Workshop on the Economics of Information Security. Boston, MA, USA.
  Abstract Citation
  

  From mobile phones to social networks, installing and running third-party applications can be risky. Installing applications often requires running unverified, untrustworthy code with the privilege of a system administrator, allowing it to compromise the security of user data and the operating system. Once installed, applications on most platforms can access anything that a user can: a web browser can read users’ e-mail and an e-mail client can access browsing history. Computer scientists have been developing systems for decades which follow the “principle of least authority,” yet few consumer computing platforms adopt their techniques. In this paper, we examine the application markets for ten computing platforms, including personal computers, mobile phones, social networks and web browsers. We identify economic causes for the wide variation in their installation and sandboxing techniques, and we propose measures to align the incentives of market actors such that providing better application security guarantees is in everyone’s interest.

  @inproceedings{ABS10,
          url="https://www.cl.cam.ac.uk/~jra40/publications/2010-WEIS-application-markets.pdf",
          author="Jonathan Anderson and Joseph Bonneau and Frank Stajano",
          title="{Inglourious Installers: Security in the Application Marketplace}",
          location="Boston, MA, USA",
          booktitle="WEIS '10: Proceedings of the 9\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2010",
  }
  

• Digital immolation: new directions in online protest
  Joseph Bonneau. 18th International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  The current literature and experience of online activism assumes two basic uses of the Internet for social movements: straightforward extensions of offline organising and fund-raising using online media to improve efficiency and reach, or “hacktivism” using technical knowledge to illegally deface or disrupt access to online resources. We propose a third model which is non-violent yet proves commitment to a cause by enabling a group of activists to temporarily or permanently sacrifice valuable online identities such as email accounts, social networking profiles, or gaming avatars. We describe a basic cryptographic framework for enabling such a protest, which provides an additional property of binding solidarity which is not normally possible offline.

  @inproceedings{B10,
          url="https://www.jbonneau.com/doc/B10-SPW-online_protest.pdf",
          author="Joseph Bonneau",
          title="{Digital immolation: new directions in online protest}",
          location="Cambridge, UK",
          booktitle="SPW '10: 18\textsuperscript{th} International Workshop on Security Protocols",
          year="2010",
  }
  

• Alice and Bob's life stories: Cryptographic communication using shared experiences
  Joseph Bonneau. 17th International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  We propose a protocol for confidential one-way communication between two parties who know each other well using only pre-existing knowledge from their shared life experience. This could enable, for example, lovers or close friends to communicate without prior key exchange. Our system uses a flexible secret-sharing mechanism to accommodate personal knowledge of variable guessing resistance and memorability with reasonable overhead in terms of computation and storage.

  @inproceedings{B09,
          url="https://www.jbonneau.com/doc/B09-SPW-experience_encryption.pdf",
          author="Joseph Bonneau",
          title="{Alice and Bob's life stories: Cryptographic communication using shared experiences}",
          location="Cambridge, UK",
          booktitle="SPW '09: 17\textsuperscript{th} International Workshop on Security Protocols",
          year="2009",
  }
  

HTTPS

• Certificate Transparency with Privacy
  (arXiv entry)
  Saba Eskandarian, Eran Messeri, Joseph Bonneau and Dan Boneh. PETS 2017. Minneapolis, MN, USA.
  Abstract Citation
  

  Certificate transparency (CT) is an elegant mechanism designed to detect when a certificate authority (CA) has issued a certificate incorrectly. Many CAs now support CT and it is being actively deployed in browsers. However, a number of privacy-related challenges remain. In this paper we propose practical solutions to two issues. First, we develop a mechanism that enables web browsers to audit a CT log without violating user privacy. Second, we extend CT to support non-public subdomains.

  @inproceedings{EMBB17,
          url="https://arxiv.org/pdf/1703.02209.pdf",
          author="Saba Eskandarian and Eran Messeri and Joseph Bonneau and Dan Boneh",
          title="{Certificate Transparency with Privacy}",
          location="Minneapolis, MN, USA",
          booktitle="PETS '17: The 17\textsuperscript{th} Privacy Enhancing Technologies Symposium",
          year="2017",
  }
  

• Upgrading HTTPS in Mid-Air: An Empirical Study of Strict Transport Security and Key Pinning
  Michael Kranch and Joseph Bonneau. NDSS 2015. San Diego, CA, USA.
  Abstract Citation
  

  We have conducted the first in-depth empirical study of two important new web security features: strict transport security (HSTS) and public-key pinning. Both have been added to the web platform to harden HTTPS, the prevailing standard for secure web browsing. While HSTS is further along, both features still have very limited deployment at a few large websites and a long tail of small, security-conscious sites. We find evidence that many developers do not completely understand these features, with a substantial portion using them in invalid or illogical ways. The majority of sites we observed trying to set an HSTS header did so with basic errors that significantly undermine the security this feature is meant to provide. We also identify several subtle but important new pitfalls in deploying these features in practice. For example, the majority of pinned domains undermined the security benefits by loading non-pinned resources with the ability to hijack the page. A substantial portion of HSTS domains and nearly all pinned domains leaked cookie values, including login cookies, due to the poorly-understood interaction between HTTP cookies and the same-origin policy. Our findings highlight that the web platform, as well as modern web sites, are large and complicated enough to make even conceptually simple security upgrades challenging to deploy in practice.

  @inproceedings{KB15,
          url="https://www.jbonneau.com/doc/KB15-NDSS-hsts_pinning_survey.pdf",
          author="Michael Kranch and Joseph Bonneau",
          title="{Upgrading HTTPS in Mid-Air: An Empirical Study of Strict Transport Security and Key Pinning}",
          location="San Diego, CA, USA",
          booktitle="NDSS '15: The 2015 Network and Distributed System Security Symposium",
          year="2015",
  }
  

• S-links: Why distributed security policy requires secure introduction
  Joseph Bonneau. Web 2.0 Security & Privacy. San Francisco, CA, USA.
  Abstract Citation
  

  In this paper we argue that secure introduction via hyperlinks will be essential for distributing security policies on the web. The "strict transport security" policy, which makes HTTPS mandatory for a given domain, can already be expressed by links with an https URL. We propose s-links, a set of lightweight HTML extensions to express more complex security policies in links such as key pinning. This is the simplest and most efficient way to secure connections to new domains before persistent security policy can be negotiated directly, requiring no changes to the user experience and aligning trust decisions with the user's mental model. We show how s-links can benefit a variety of proposed protocols and discuss implications for the browser's same-origin policy.

  @inproceedings{B13,
          url="https://www.jbonneau.com/doc/B13-W2SP-slinks.pdf",
          author="Joseph Bonneau",
          title="{S-links: Why distributed security policy requires secure introduction}",
          location="San Francisco, CA, USA",
          booktitle="W2SP '13: Workshop on Web 2.0 Security {\&} Privacy",
          year="2013",
  }
  

Blockchains and cryptocurrencies

• SoK: Trusted setups for powers-of-tau strings (to appear)
  Faxing Wang, Shanaan Cohney and Joseph Bonneau. FC 2025. Miyakojima, Japan.
  Citation
  

  @inproceedings{WCB25,
          url="",
          institution="",
          author="Faxing Wang and Shanaan Cohney and Joseph Bonneau",
          title="{SoK: Trusted setups for powers-of-tau strings}",
          location="Miyakojima, Japan",
          booktitle="FC '25: Proceedings of the 29\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2025",
  }
  

• How Much Public Randomness Do Modern Consensus Protocols Need? (working draft)
  Joseph Bonneau, Benedikt Bünz, Miranda Christ and Yuval Efron.
  Abstract Citation
  

  Modern blockchain-based consensus protocols aim for efficiency (i.e., low communication and round complexity) while maintaining security against adaptive adversaries. These goals are usually achieved using a public randomness beacon to select roles for each participant. We examine to what extent this randomness is necessary. Specifically, we provide tight bounds on the amount of entropy a Byzantine Agreement protocol must consume from a beacon in order to enjoy efficiency and adaptive security. We first establish that no consensus protocol can simultaneously be efficient, be adaptively secure, and use O(log n) bits of beacon entropy. We then show this bound is tight and, in fact, a trilemma by presenting three consensus protocols that achieve any two of these three properties.

  @inproceedings{BBCE24b,
          url="https://eprint.iacr.org/2024/1794",
          institution="",
          author="Joseph Bonneau and Benedikt B{\"{u}}nz and Miranda Christ and Yuval Efron",
          title="{How Much Public Randomness Do Modern Consensus Protocols Need?}",
          year="2024",
  }
  

• Atomic and Fair Data Exchange via Blockchain
  Ertem Nusret Tas, István András Seres, Yinou Zhang, Márk Melczer, Mahimna Kelkar, Joseph Bonneau and Valeria Nikolaenko. ACM CCS 2024. Salt Lake City, UT, USA.
  

  Distinguished Paper Award

  Abstract Citation
  

  We introduce a blockchain Fair Data Exchange (FDE) protocol, enabling a storage server to transfer a data file to a client atomically: the client receives the file if and only if the server receives an agreed-upon payment. We put forth a new definition for a cryptographic scheme that we name verifiable encryption under committed key (VECK), and we propose two instantiations for this scheme. Our protocol relies on a blockchain to enforce the atomicity of the exchange and uses VECK to ensure that the client receives the correct data (matching an agreed-upon commitment) before releasing the payment for the decrypting key. Our protocol is trust-minimized and requires only constant-sized on-chain communication, concretely 3 signatures, 1 verification key, and 1 secret key, with most of the data stored and communicated off-chain. It also supports exchanging only a subset of the data, can amortize the server's work across multiple clients, and offers a general framework to design alternative FDE protocols using different commitment schemes. A prominent application of our protocol is the Danksharding data availability scheme on Ethereum, which commits to data via KZG polynomial commitments. We also provide an open-source implementation for our protocol with both instantiations for VECK, demonstrating our protocol's efficiency and practicality on Ethereum.

  @inproceedings{TKZSNB24,
          url="https://eprint.iacr.org/2024/418",
          author="Ertem Nusret Tas and István András Seres and Yinou Zhang and Márk Melczer and Mahimna Kelkar and Joseph Bonneau and Valeria Nikolaenko",
          title="{Atomic and Fair Data Exchange via Blockchain}",
          location="Salt Lake City, UT, USA",
          booktitle="CCS '24: The 31\textsuperscript{st} ACM Conference on Computer and Communications Security",
          year="2024",
  }
  

• Cornucopia: Distributed randomness beacons at scale
  Miranda Christ, Kevin Choi and Joseph Bonneau. AFT 2024. Vienna, Austria.
  Abstract Citation
  

  We propose Cornucopia, a distributed randomness beacon protocol combining accumulators and verifiable delay functions. Cornucopia extends the Unicorn protocol of Lenstra and Wesolowski, utilizing an accumulator to enable efficient verification by each participant that their randomness contribution has been included in the beacon output. The security of this construction reduces to a novel property of accumulators, insertion security. We first show that not all accumulators are insertion-secure. We then prove that common constructions (Merkle trees and RSA accumulators) are naturally insertion-secure. Finally, we give a generic transformation from any universal accumulator (supporting nonmembership proofs) to an insertion-secure accumulator, albeit with an efficiency loss proportional to the security parameter.

  @inproceedings{CCB23,
          url="https://eprint.iacr.org/2023/1554.pdf",
          author="Miranda Christ and Kevin Choi and Joseph Bonneau",
          title="{Cornucopia: Distributed randomness beacons at scale}",
          location="Vienna, Austria",
          booktitle="AFT '24: Proceedings of the 6\textsuperscript{th} International Conference on Advances in Financial Technologies",
          year="2024",
  }
  

• Accountable Secret Leader Election
  Walter McKelvie, Miranda Christ, Kevin Choi, Tal Malkin and Joseph Bonneau. AFT 2024. Vienna, Austria.
  Abstract Citation
  

  We consider the problem of secret leader election with accountability. Secret leader election protocols counter adaptive adversaries by keeping the identities of elected leaders secret until they choose to reveal themselves, but in existing protocols this means it is impossible to determine who was elected leader if they fail to act. This opens the door to undetectable withholding attacks, where leaders fail to act in order to slow the protocol or bias future elections in their favor. We formally define accountability (in weak and strong variants) for secret leader election protocols. We present three paradigms for adding accountability, using delay-based cryptography, enforced key revelation, or threshold committees, all of which ensure that after some time delay the result of the election becomes public. The paradigm can be chosen to balance trust assumptions, protocol efficiency, and the length of the delay before leaders are revealed. Along the way, we introduce several new cryptographic tools including re-randomizable timed commitments and timed VRFs.

  @inproceedings{MCCMB23,
          url="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.1",
          author="Walter McKelvie and Miranda Christ and Kevin Choi and Tal Malkin and Joseph Bonneau",
          title="{Accountable Secret Leader Election}",
          location="Vienna, Austria",
          booktitle="AFT '24: Proceedings of the 6\textsuperscript{th} International Conference on Advances in Financial Technologies",
          year="2024",
  }
  

• Powers-of-Tau to the People: Decentralizing Setup Ceremonies
  Valeria Nikolaenko, Sam Ragsdale, Joseph Bonneau and Dan Boneh. ACNS 2023. Abu Dhabi, UAE.
  Abstract Citation
  

  We introduce the first decentralized trusted setup protocols for constructing a powers-of-tau structured reference string. Facilitated by a blockchain platform, our protocols can run in a permissionless manner, with anybody able to participate in exchange for paying requisite transaction fees. The result is secure as long as any single party participates honestly. We introduce several protocols optimized for different sized powers-of-tau setups and using an on-chain or off-chain data availability model to store the resulting string. We implement our most efficient protocol on top of Ethereum, demonstrating practical concrete performance numbers.

  @inproceedings{NRBB22,
          url="https://eprint.iacr.org/2022/1592",
          institution="Cryptology ePrint Archive",
          author="Valeria Nikolaenko and Sam Ragsdale and Joseph Bonneau and Dan Boneh",
          title="{Powers-of-Tau to the People: Decentralizing Setup Ceremonies}",
          location="Abu Dhabi, UAE",
          booktitle="ACNS '24: he 22\textsuperscript{nd} International Conference on Applied Cryptography and Network Security (ACNS)",
          year="2024",
  }
  

• Naysayer proofs
  István András Seres, Noemi Glaeser and Joseph Bonneau. FC 2024. Willemstad, Curaçao.
  Abstract Citation
  

  This work introduces the notion of naysayer proofs. We observe that in numerous (zero-knowledge) proof systems, it is significantly more efficient for the verifier to be convinced by a so-called naysayer that a false proof is invalid than it is to check that a genuine proof is valid. We show that every NP language has constant-size and constant-time naysayer proofs. We also show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles. Naysayer proofs enable an interesting new optimistic verification mode potentially suitable for resource-constrained verifiers, such as smart contracts.

  @inproceedings{SGB24,
          url="https://eprint.iacr.org/2023/1472.pdf",
          institution="",
          author="István András Seres and Noemi Glaeser and Joseph Bonneau",
          title="{Naysayer proofs}",
          location="Willemstad, Curaçao",
          booktitle="FC '24: Proceedings of the 28\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2024",
  }
  

• Riggs: Decentralized Sealed-Bid Auctions
  Nirvan Tyagi, Arasu Arun, Cody Freitag, Riad Wahby, Joseph Bonneau and David Mazières. ACM CCS 2023. Copenhagen, Denmark.
  Abstract Citation
  

  We introduce the first practical protocols for fully decentralized sealed-bid auctions using timed commitments. Timed commitments ensure that the auction is finalized fairly even if all participants drop out after posting bids or if n − 1 bidders collude to try to learn the $n^{th}$ bidder’s bid value. Our protocols rely on a novel non-malleable timed commitment scheme which efficiently supports range proofs to establish that bidders have sufficient funds to cover a hidden bid value. Our protocols are concretely efficient and we have implemented them in an Ethereum-compatible smart contract which automatically enforces payment and delivery of an auctioned digital good.

  @inproceedings{TAFWBM23,
          url="https://eprint.iacr.org/2023/1336",
          author="Nirvan Tyagi and Arasu Arun and Cody Freitag and Riad Wahby and Joseph Bonneau and David Mazières",
          title="{Riggs: Decentralized Sealed-Bid Auctions}",
          location="Copenhagen, Denmark",
          booktitle="CCS '23: The 30\textsuperscript{th} ACM Conference on Computer and Communications Security",
          year="2023",
  }
  

• Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles (working draft)
  Noemi Glaeser, István András Seres, Michael Zhu and Joseph Bonneau.
  Abstract Citation
  

  Auction and voting schemes play a crucial role in the Web3 ecosystem. Yet currently deployed implementations either lack privacy or require at least two rounds, hindering usability and security. We introduce Cicada, a general framework for using linearly homomorphic time-lock puzzles (HTLPs) to enable provably secure, non-interactive private auction and voting protocols. We instantiate our framework with an efficient new HTLP construction and novel packing techniques that enable succinct ballot correctness proofs independent of the number of candidates. We demonstrate the practicality of our approach by implementing our protocols for the Ethereum Virtual Machine (EVM).

  @inproceedings{GSZB23,
          url="https://eprint.iacr.org/2023/1473.pdf",
          institution="",
          author="Noemi Glaeser and István András Seres and Michael Zhu and Joseph Bonneau",
          title="{Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles}",
          year="2023",
  }
  

• High Performance, Low Energy, and Trustworthy Blockchains Using Satellites
  Dennis Shasha, Taegyun Kim, Joseph Bonneau, Yan Michalevsky,, Gil Shotan and Yonatan Winetraub. Foundations and Trends in Networking.
  Abstract Citation
  

  Blockchains are meant to provide an append-only sequence (ledger) of transactions. Security commonly relies on a consensus protocol in which forks in the sequence are either prevented completely or are exponentially unlikely to last more than a few blocks. This monograph proposes the design of algorithms and a system to achieve high performance (a few seconds from the time of initiation for transactions to enter the blockchain), the absence of forks, and a very low energy cost (a per transaction cost that is a factor of a billion or more less than bitcoin). This monograph will discuss the overall architecture and algorithms of such a system, the assumptions it makes, and the guarantees it gives.

  @article{SKBMSW23,
          url="https://www.nowpublishers.com/article/Details/NET-070",
          author="Dennis Shasha and Taegyun Kim and Joseph Bonneau and Yan Michalevsky, and Gil Shotan and Yonatan Winetraub",
          title="{High Performance, Low Energy, and Trustworthy Blockchains Using Satellites}",
          volume="13",
          number="4",
          publisher="Now Publishers",
          journal="Foundations and Trends in Networking",
          year="2023",
  }
  

• Proof of Necessary Work: Succinct State Verification with Fairness Guarantees
  Assimakis Kattis and Joseph Bonneau. FC 2023. Bol, Brač, Croatia.
  Abstract Citation
  

  Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. In almost all of today’s implementations, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). We propose a new distributed payment system which uses Incrementally Verifiable Computation (IVC) to enable constant-time verification. Since generating the succinct proofs needed to verify correctness is more expensive, we introduce the notion of Proof of Necessary Work (PoNW), in which proof generation is an integral part of the proof-of-work used in Nakamoto consensus, effectively producing proofs using energy that would otherwise be wasted. We implement and benchmark a prototype of our system using recent recursive SNARK-based constructions, enabling stateless “light” clients to efficiently verify the entire blockchain history in about 40 milliseconds.

  @inproceedings{KB23,
          url="https://eprint.iacr.org/2020/190.pdf",
          author="Assimakis Kattis and Joseph Bonneau",
          title="{Proof of Necessary Work: Succinct State Verification with Fairness Guarantees}",
          location="Bol, Brač, Croatia",
          booktitle="FC '23: Proceedings of the 27\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2023",
  }
  

• Limits on revocable proof systems, with applications to stateless blockchains
  Miranda Christ and Joseph Bonneau. FC 2023. Bol, Brač, Croatia.
  Abstract Citation
  

  Motivated by the goal of building a cryptocurrency with succinct global state, we introduce the abstract notion of a revocable proof system. We prove an information-theoretic result on the relation between global state size and the required number of local proof updates as statements are revoked (e.g., coins are spent). We apply our result to conclude that there is no useful trade-off point when building a stateless cryptocurrency: the system must either have a linear-sized global state (in the number of accounts in the system) or require a near-linear rate of local proof updates. The notion of a revocable proof system is quite general and also provides new lower bounds for set commitments, vector commitments and authenticated dictionaries.

  @inproceedings{CB23,
          url="https://eprint.iacr.org/2022/1478",
          author="Miranda Christ and Joseph Bonneau",
          title="{Limits on revocable proof systems, with applications to stateless blockchains}",
          location="Bol, Brač, Croatia",
          booktitle="FC '23: Proceedings of the 27\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2023",
  }
  

• Mina: Decentralized Cryptocurrency at Scale
  Joseph Bonneau, Izaak Meckler, Vanishree Rao and Evan Shapiro.
  Abstract Citation
  

  We introduce the notion of a succinct blockchain, a replicated state machine in which each state transition (block) can be efficiently verified in constant time regardless of the number of prior transitions in the system. Traditional blockchains require verification time linear in the number of transitions. We show how to construct a succinct blockchain using recursively composed succinct non-interactive arguments of knowledge (SNARKs). Finally, we instantiate this construction to implement Coda, a payment system (cryptocurrency) using a succinct blockchain. Coda offers payment functionality similar to Bitcoin, with a dramatically faster verification time of 200ms making it practical for lightweight clients and mobile devices to perform full verification of the system’s history.

  @techreport{VMRS20,
          url="https://minaprotocol.com/wp-content/uploads/technicalWhitepaper.pdf",
          institution="Cryptology ePrint Archive",
          number="2020/352",
          author="Joseph Bonneau and Izaak Meckler and Vanishree Rao and Evan Shapiro",
          title="{Mina: Decentralized Cryptocurrency at Scale}",
          year="2020",
  }
  

• Scaling Proof-of-Replication for Filecoin Mining
  Ben Fisch, Joseph Bonneau, Nicola Greco and Juan Benet.
  Abstract Citation
  

  A proof-of-replication (PoRep) is a proof system that a server can use to demonstrate to a network in a publicly verifiable way that it is dedicating unique resources to storing one or more replicas of a data file. While it is not possible for PoReps to guarantee cryptographically that the prover’s storage format is redundant, PoReps do guarantee that: (a) The prover must be using as much space to produce the proof as replicas it claims to store (it is a proof of space) (b) The prover can retrieve a committed data file (it is a proof of retrievability) (c) The prover can use the space to store this file without any overhead In this sense a PoRep is a useful proof of space. It is uniquely suited to replace proof-ofwork in Nakamoto consensus as a Sybil resistance mechanism, while simultaneously incentivizing and subsidizing the cost of file storage.

  @techreport{FBGB19,
          url="https://research.protocol.ai/publications/scaling-proof-of-replication-for-filecoin-mining/fisch2018.pdf",
          institution="Stanford University",
          author="Ben Fisch and Joseph Bonneau and Nicola Greco and Juan Benet",
          title="{Scaling Proof-of-Replication for Filecoin Mining}",
          year="2019",
  }
  

• Hostile blockchain takeovers
  Joseph Bonneau. BITCOIN 2018. Curaçao.
  Abstract Citation
  

  Most research modelling Bitcoin-style decentralised consensus protocols has assumed profit-motivated participants. Complementary to this analysis, we revisit the notion of attackers with an extrinsic motivation to disrupt the consensus process (Goldfinger attacks). We outline several routes for obtaining a majority of decision-making power in the consensus protocol (a hostile takeover). Our analysis suggests several fundamental differences between proof-of-work and proof-of-stake systems in the face of such an adversary.

  @inproceedings{B18,
          url="https://www.jbonneau.com/doc/B18a-BITCOIN-why_buy_when_you_can_rent.pdf",
          author="Joseph Bonneau",
          title="{Hostile blockchain takeovers}",
          location="Curaçao",
          booktitle="BITCOIN '18: IFCA Workshop on Bitcoin and Blockchain Research",
          year="2018",
  }
  

• Proofs-of-delay and randomness beacons in Ethereum
  Benedikt Bünz, Steven Goldfeder and Joseph Bonneau. S&B '17: IEEE Security & Privacy on the Blockchain. Paris, France.
  Abstract Citation
  

  Blockchains generated using a proof-of-work consensus protocol, such as Bitcoin or Ethereum, are promising sources of public random-ness. However, the randomness is subject to manipulation by the miners generating the blockchain. A general defense is to apply a delay function, preventing malicious miners from computing the random output until it is too late to manipulate it. Ideally, this delay function can provide a short proof-of-delay that is efficient enough to be verified within a smart contract, enabling the randomness source to be directly by smart contracts. In this paper we describe the challenges of solving this problem given the extremely limited computational capacity available in Ethereum, the most popular general-purpose smart contract framework to date. We introduce a novel multi-round protocol for verifying delay functions using a refereed delegation model. We provide a prototype Ethereum implementation to analyze performance and find that it is feasible in terms of gas costs, costing roughly 180000 gas (US$ 0.11 1 ) to post a beacon and 720000 gas (US$ 0.98) to resolve a dispute. We also discuss the incentive challenges raised by providing a secure randomness beacon as a public good.

  @inproceedings{BGB17,
          url="https://www.jbonneau.com/doc/BGB17-IEEESB-proof_of_delay_ethereum.pdf",
          author="Benedikt B{\"{u}}nz and Steven Goldfeder and Joseph Bonneau",
          title="{Proofs-of-delay and randomness beacons in Ethereum}",
          location="Paris, France",
          booktitle="S{\&}B '17: Proceedings of the 1\textsuperscript{st} IEEE Security {\&} Privacy on the Blockchain Workshop",
          year="2017",
  }
  

• Escrow protocols for cryptocurrencies: How to buy physical goods using Bitcoin
  Steven Goldfeder, Joseph Bonneau, Rosario Gennaro and Arvind Narayanan. FC '17: The 21st International Conference on Financial Cryptography. Silema, Malta.
  Abstract Citation
  

  We consider the problem of buying physical goods with cryptocurrencies. There is an inherent circular dependency: should be the buyer trust the seller and pay before receiving the goods or should the seller trust the buyer and ship the goods before receiving payment? This dilemma is addressed in practice using a third party escrow service. However, we show that naive escrow protocols introduce both privacy and security issues. We formalize the escrow problem and present a suite of schemes with improved security and privacy properties.

  @inproceedings{GBGN17,
          url="https://www.jbonneau.com/doc/GBGN17-FC-physical_escrow.pdf",
          author="Steven Goldfeder and Joseph Bonneau and Rosario Gennaro and Arvind Narayanan",
          title="{Escrow protocols for cryptocurrencies: How to buy physical goods using Bitcoin}",
          location="Silema, Malta",
          booktitle="FC '17: Proceedings of the the 21\textsuperscript{st} International Conference on Financial Cryptography",
          year="2017",
  }
  

• Bitcoin and Cryptocurrency Technologies
  Arvind Narayanan, Joseph Bonneau, Edward W. Felten, Andrew Miller and Steven Goldfeder.
  Citation
  

  @book{NBFMG16,
          url="https://bitcoinbook.cs.princeton.edu/",
          author="Arvind Narayanan and Joseph Bonneau and Edward W. Felten and Andrew Miller and Steven Goldfeder",
          title="{Bitcoin and Cryptocurrency Technologies}",
          publisher="Princeton University Press",
          year="2016",
  }
  

• Why buy when you can rent? Bribery attacks on Bitcoin consensus
  Joseph Bonneau. BITCOIN '16: 3rd Workshop on Bitcoin and Blockchain Research. Barbados.
  Abstract Citation
  

  The Bitcoin cryptocurrency introduced a novel distributed consensus mechanism relying on economic incentives. While a coalition controlling a majority of computational power may undermine the system, for example by double-spending funds, it is often assumed it would be incentivized not to attack to protect its long-term stake in the health of the currency. We show how an attacker might purchase mining power (perhaps at a cost premium) for a short duration via bribery. Indeed, bribery can even be performed in-band with the system itself enforcing the bribe. A bribing attacker would not have the same concerns about the long-term health of the system, as their majority control is inherently short-lived. New modeling assumptions are needed to explain why such attacks have not been observed in practice. The need for all miners to avoid short-term profits by accepting bribes further suggests a potential tragedy of the commons which has not yet been analyzed.

  @inproceedings{B16a,
          url="https://www.jbonneau.com/doc/B16a-BITCOIN-why_buy_when_you_can_rent.pdf",
          author="Joseph Bonneau",
          title="{Why buy when you can rent? Bribery attacks on Bitcoin consensus}",
          location="Barbados",
          booktitle="BITCOIN '16: Proceedings of the 3\textsuperscript{rd} Workshop on Bitcoin and Blockchain Research",
          year="2016",
  }
  

• EthIKS: Using Ethereum to audit a CONIKS key transparency log
  Joseph Bonneau. BITCOIN '16: 3rd Workshop on Bitcoin and Blockchain Research. Barbados.
  Abstract Citation
  

  CONIKS is a proposed key transparency system which enables a centralized service provider to maintain an auditable yet privacy-preserving directory of users' public keys. In the original CONIKS design, users must monitor that their data is correctly included in every published snapshot of the directory, necessitating either slow updates or trust in an unspecified third-party to audit that the data structure has stayed consistent. We demonstrate that the data structures for CONIKS are very similar to those used in Ethereum, a consensus computation platform with a Turing-complete programming environment. We can take advantage of this to embed the core CONIKS data structures into an Ethereum contract with only minor modifications. Users may then trust the Ethereum network to audit the data structure for consistency and non-equivocation. Users who do not trust (or are unaware of) Ethereum can self-audit the CONIKS data structure as before. We have implemented a prototype contract for our hybrid EthIKS scheme, demonstrating that it adds only modest bandwidth overhead to CONIKS proofs and costs hundredths of pennies per key update in fees at today's rates.

  @inproceedings{B16b,
          url="https://www.jbonneau.com/doc/B16b-BITCOIN-ethiks.pdf",
          title="{EthIKS: Using Ethereum to audit a CONIKS key transparency log}",
          author="Joseph Bonneau",
          location="Barbados",
          booktitle="BITCOIN '16: Proceedings of the 3\textsuperscript{rd} Workshop on Bitcoin and Blockchain Research",
          year="2016",
  }
  

• Incentive Compatibility of Bitcoin Mining Pool Reward Functions
  Okke Schrijvers, Joseph Bonneau, Dan Boneh and Tim Roughgarden. FC '16: The 20th International Conference on Financial Cryptography. Barbados.
  Abstract Citation
  

  In this paper we introduce a game-theoretic model for reward functions in Bitcoin mining pools. Our model consists only of an unordered history of reported shares and gives participating miners the strategy choices of either reporting or delaying when they discover a share or full solution. We defined a precise condition for incentive compatibility to ensure miners strategy choices optimize the welfare of the pool as a whole. With this definition we show that proportional mining rewards are not incentive compatible in this model. We introduce and analyze a novel reward function which is incentive compatible in this model. Finally we show that the popular reward function pay-per-last-N-shares is also incentive compatible in a more general model.

  @inproceedings{SBBR16,
          url="https://www.jbonneau.com/doc/SBBR16-FC-mining_pool_reward_incentive_compatibility.pdf",
          title="{Incentive Compatibility of Bitcoin Mining Pool Reward Functions}",
          author="Okke Schrijvers and Joseph Bonneau and Dan Boneh and Tim Roughgarden",
          location="Barbados",
          booktitle="FC '16: Proceedings of the the 20\textsuperscript{th} International Conference on Financial Cryptography",
          year="2016",
  }
  

• The Bitcoin Brain Drain: Examining the Use and Abuse of Bitcoin Brain Wallets
  Marie Vasek, Joseph Bonneau, Ryan Castellucci, Cameron Keith and Tyler Moore. FC '16: The 20th International Conference on Financial Cryptography. Barbados.
  Abstract Citation
  

  In the cryptocurrency Bitcoin, users can deterministically derive the private keys used for transmitting money from a password. Such "brain wallets" are appealing because they free users from storing their private keys on untrusted computers. Unfortunately, they also enable attackers to conduct unlimited offline password guessing. In this paper, we report on the first large-scale measurement of the use of brain wallets in Bitcoin. Using a wide range of word lists, we evaluated around 300 billion passwords. Surprisingly, after excluding activities by researchers, we identified just 884 brain wallets worth around \$100K in use from September 2011 to August 2015. We find that all but 21 wallets were drained, usually within 24 hours but often within minutes. We find that around a dozen "drainers" are competing to liquidate brain wallets as soon as they are funded. We find no evidence that users of brain wallets loaded with more bitcoin select stronger passwords, but we do find that brain wallets with weaker passwords are cracked more quickly.

  @inproceedings{VBCKM16,
          url="https://www.jbonneau.com/doc/VBCKM16-FC-bitcoin_brain_wallets.pdf",
          title="{The Bitcoin Brain Drain: Examining the Use and Abuse of Bitcoin Brain Wallets}",
          author="Marie Vasek and Joseph Bonneau and Ryan Castellucci and Cameron Keith and Tyler Moore",
          location="Barbados",
          booktitle="FC '16: Proceedings of the the 20\textsuperscript{th} International Conference on Financial Cryptography",
          year="2016",
  }
  

• On Bitcoin as a public randomness source
  Joseph Bonneau, Jeremy Clark and Steven Goldfeder .
  Abstract Citation
  

  We formalize the use of Bitcoin as a source of publicly-verifiable randomness. As a side-effect of Bitcoin's proof-of-work-based consensus system, random values are broadcast every time new blocks are mined. We can derive strong lower bounds on the computational min-entropy in each block: currently, at least 68 bits of min-entropy are produced every 10 minutes, from which one can derive over 32 near-uniform bits using standard extractor techniques. We show that any attack on this beacon would form an attack on Bitcoin itself and hence have a monetary cost that we can bound, unlike any other construction for a public randomness beacon in the literature. In our simplest construction, we show that a lottery producing a single unbiased bit is manipulation-resistant against an attacker with a stake of less than 50 bitcoins in the output, or about US\$12,000 today. Finally, we propose making the beacon output available to smart contracts and demonstrate that this simple tool enables a number of interesting applications.

  @techreport{BCG15,
          url="https://eprint.iacr.org/2015/1015.pdf",
          institution="Cryptology ePrint Archive",
          number="2015/1015",
          author="Joseph Bonneau and Jeremy Clark and Steven Goldfeder ",
          title="{On Bitcoin as a public randomness source}",
          year="2015",
  }
  

• Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges
  (ePrint entry)
  Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark and Dan Boneh. ACM CCS 2015. Denver, CO, USA.
  Abstract Citation
  

  Bitcoin exchanges function like banks, securely holding their customers' bitcoins on their behalf. Several exchanges have suffered catastrophic losses with customers permanently losing their savings. A proof of solvency demonstrates that the exchange controls sufficient reserves to settle each customer's account. We introduce Provisions, a privacy-preserving proof of solvency whereby an exchange does not have to disclose its Bitcoin addresses; total holdings or liabilities; or any information about its customers. We also propose an extension which prevents exchanges from colluding to cover for each other's losses. We have implemented Provisions and show that it offers practical computation times and proof sizes even for a large Bitcoin exchange with millions of customers.

  @inproceedings{DBBCB15,
          url="https://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf",
          author="Gaby G. Dagher and Benedikt B{\"{u}}nz and Joseph Bonneau and Jeremy Clark and Dan Boneh",
          title="{Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges}",
          location="Denver, CO, USA",
          booktitle="CCS '15: Proceedings of the 22\textsuperscript{nd} ACM Conference on Computer and Communications Security",
          year="2015",
  }
  

• An empirical study of Namecoin and lessons for decentralized namespace design
  Harry Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau and Arvind Narayanan. WEIS '15: The 14th Workshop on the Economics of Information Security. Delft, Netherlands.
  Abstract Citation
  

  Secure decentralized namespaces have recently become possible due to cryptocurrency technology. They enable a censorship-resistant domain-name system outside the control of any single entity, among other applications. Namecoin, a fork of Bitcoin, is the most prominent example. We initiate the study of decentralized namespaces and the market for names in such systems. Our extensive empirical analysis of Namecoin reveals a system in disrepair. Indeed, our methodology for detecting "squatted" and otherwise inactive domains reveals that among Namecoin’s roughly 120,000 registered domain names, a mere 28 are not squatted and have nontrivial content. Further, we develop techniques for detecting transfers of domains in the Namecoin Blockchains and provide evidence that the market for domains is thin-to-nonexistent. We argue that the state of the art in mechanism design for decentralized namespace markets is lacking. We propose a model of utility of different names to different participants, and articulate desiderata of a decentralized namespace in terms of this utility function. We use this model to explore the design space of mechanisms and analyze the trade-offs.

  @article{KCEBN15,
          url="https://www.cs.princeton.edu/~arvindn/publications/namespaces.pdf",
          author="Harry Kalodner and Miles Carlsten and Paul Ellenbogen and Joseph Bonneau and Arvind Narayanan",
          title="{An empirical study of Namecoin and lessons for decentralized namespace design}",
          location="Delft, Netherlands",
          journal="WEIS '15: Proceedings of the 14\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2015",
  }
  

• Research Perspectives and Challenges for Bitcoin and Cryptocurrencies
  Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll and Edward W. Felten. Security & Privacy (Oakland) 2015. San Francisco, CA, USA.
  Abstract Citation
  

  Bitcoin has emerged as the most successful cryptographic currency in history. Within two years of its quiet launch in 2009, Bitcoin grew to comprise billions of dollars of economic value despite only cursory analysis of the system's design. Since then a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promising alternatives, and singled out difficult future challenges. Meanwhile a large and vibrant open-source community has proposed and deployed numerous modifications and extensions. We provide the first systematic exposition Bitcoin and the many related cryptocurrencies or `altcoins.' Drawing from a scattered body of knowledge, we identify three key components of Bitcoin's design that can be decoupled. This enables a more insightful analysis of Bitcoin's properties and future stability. We map the design space for numerous proposed modifications, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We survey anonymity issues in Bitcoin and provide an evaluation framework for analyzing a variety of privacy-enhancing proposals. Finally we provide new insights on what we term disintermediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disintermediation strategies and provide a detailed comparison.

  @inproceedings{BMCNKF15,
          url="https://www.jbonneau.com/doc/BMCNKF15-IEEESP-bitcoin.pdf",
          author="Joseph Bonneau and Andrew Miller and Jeremy Clark and Arvind Narayanan and Joshua A. Kroll and Edward W. Felten",
          title="{Research Perspectives and Challenges for Bitcoin and Cryptocurrencies}",
          location="San Francisco, CA, USA",
          booktitle="IEEE Symposium on Security and Privacy",
          year="2015",
  }
  

• On Decentralizing Prediction Markets and Order Books
  Jeremy Clark, Joseph Bonneau, Edward W. Felten, Joshua A. Kroll, Andrew Miller and Arvind Narayanan. WEIS '14: The 13th Workshop on the Economics of Information Security. State College, PA, USA.
  Abstract Citation
  

  We propose techniques for decentralizing prediction markets and order books, utilizing Bitcoin’s security model and consensus mechanism. Decentralization of prediction markets offers several key advantages over a centralized market: no single entity governs over the market, all transactions are transparent in the block chain, and anybody can participate pseudonymously to either open a new market or place bets in an existing one. We provide trust agility: each market has its own specified arbiter and users can choose to interact in markets that rely on the arbiters they trust. We also provide a transparent, decentralized order book that enables order execution on the block chain in the presence of potentially malicious miners.

  @inproceedings{CBFKMN14,
          author="Jeremy Clark and Joseph Bonneau and Edward W. Felten and Joshua A. Kroll and Andrew Miller and Arvind Narayanan",
          title="{On Decentralizing Prediction Markets and Order Books}",
          url="https://www.jbonneau.com/doc/CBEKMN14-WEIS-decentralizing_prediction_markets.pdf",
          location="State College, PA, USA",
          booktitle="WEIS '14: Proceedings of the 10\textsuperscript{th} Workshop on the Economics of Information Security",
          year="2014",
  }
  

• Fawkescoin: A cryptocurrency without public-key cryptography
  Joseph Bonneau and Andrew Miller. 22nd International Workshop on Security Protocols. Cambridge, UK.
  Abstract Citation
  

  We present, Fawkescoin, a simple cryptocurrency using no public-key cryptography. Our proposal utilizes the distributed consensus mechanism of Bitcoin but for transactions replaces Bitcoin's ECDSA signatures with hash-based Guy Fawkes signatures. While this introduces a number of complexities, it demonstrates that a distributed cryptocurrency is in fact possible with only symmetric operations with no dramatic loss of efficiency overall and several efficiency gains.

  @inproceedings{BM14,
          url="https://www.jbonneau.com/doc/BM14-SPW-fawkescoin.pdf",
          author="Joseph Bonneau and Andrew Miller",
          title="{Fawkescoin: A cryptocurrency without public-key cryptography}",
          location="Cambridge, UK",
          booktitle="SPW '14: The 22\textsuperscript{nd} International Workshop on Security Protocols",
          year="2014",
  }
  

• Mixcoin: Anonymity for Bitcoin with accountable mixes
  (abridged version) (ePrint entry)
  Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua A. Kroll and Edward W. Felten. FC '14: The 18th International Conference on Financial Cryptography. Barbados.
  Abstract Citation
  

  We propose Mixcoin, a protocol to facilitate anonymous payments in Bitcoin and similar cryptocurrencies. We build on the emergent phenomenon of currency mixes, adding an accountability mechanism to expose theft. We demonstrate that incentives of mixes and clients can be aligned to ensure that rational mixes will not steal. Our scheme is efficient and fully compatible with Bitcoin. Against a passive attacker, our scheme provides an anonymity set of all other users mixing coins contemporaneously. This is an interesting new property with no clear analog in better-studied communication mixes. Against active attackers our scheme offers similar anonymity to traditional communication mixes.

  @inproceedings{BNMCKF14,
          url="https://www.jbonneau.com/doc/BNMCKF14-FC-mixcoin_full.pdf",
          author="Joseph Bonneau and Arvind Narayanan and Andrew Miller and Jeremy Clark and Joshua A. Kroll and Edward W. Felten",
          title="{Mixcoin: Anonymity for Bitcoin with accountable mixes}",
          location="Barbados",
          booktitle="FC '14: Proceedings of the the 18\textsuperscript{th} International Conference on Financial Cryptography",
          year="2014",
  }
  

Improving password security

• Learning Assigned Secrets for Unlocking Mobile Devices
  Stuart Schechter and Joseph Bonneau. SOUPS '15: The 11th Symposium On Usable Privacy and Security. Ottawa, Canada.
  Abstract Citation
  

  Nearly all smartphones and tablets support unlocking with a short user-chosen secret: e.g., a numeric PIN or a pattern. To address users' tendency to choose guessable PINs and patterns, we compare two approaches for helping users learn assigned random secrets. In one approach, built on our prior work, we assign users a second numeric PIN and, during each login, we require them to enter it after their chosen PIN. In a new approach, we re-arrange the digits on the keypad so that the user's chosen PIN appears on an assigned random sequence of key positions. We performed experiments with over a thousand participants to compare these two repetition-learning approaches to simple user-chosen PINs and assigned PINs that users are required to learn immediately at account set-up time. Almost all of the participants using either repetition-learning approach learned their assigned secrets quickly and could recall them three days after the study. Those using the new mapping approach were less likely to write down their secret. Surprisingly, the learning process was less time consuming for those required to enter an extra PIN.

  @article{SB15,
          url="https://www.jbonneau.com/doc/SB15-SOUPS-learning_assigned_secrets_mobile.pdf",
          author="Stuart Schechter and Joseph Bonneau",
          title="{Learning Assigned Secrets for Unlocking Mobile Devices}",
          location="Ottawa, Canada",
          journal="SOUPS '15: Proceedings of the 11\textsuperscript{th} Symposium On Usable Privacy and Security",
          year="2015",
  }
  

• Towards reliable storage of 56-bit secrets in human memory
  (abridged version)
  Joseph Bonneau and Stuart Schechter. USENIX Security 2014. San Diego, CA, USA.
  Abstract Citation
  

  Challenging the conventional wisdom that users cannot remember cryptographically-strong secrets, we test the hypothesis that users can learn randomly-assigned 56-bit codes (encoded as either 6 words or 12 characters) through spaced repetition. We asked remote research participants to perform a distractor task that required logging into a website 90 times, over up to two weeks, with a password of their choosing. After they entered their chosen password correctly we displayed a short code (4 letters or 2 words, 18.8 bits) that we required them to type. For subsequent logins we added an increasing delay prior to displaying the code, which participants could avoid by typing the code from memory. As participants learned, we added two more codes to comprise a 56.4-bit secret. Overall, 94% of participants eventually typed their entire secret from memory, learning it after a median of 36 logins. The learning component of our system added a median delay of just 6.9 s per login and a total of less than 12 minutes over an average of ten days. 88% were able to recall their codes exactly when asked at least three days later, with only 21% reporting having written their secret down. As one participant wrote with surprise, “the words are branded into my brain.”

  @inproceedings{BS14,
          author="Joseph Bonneau and Stuart Schechter",
          title="{Towards reliable storage of 56-bit secrets in human memory}",
          url="https://www.jbonneau.com/doc/BS14-USENIX-towards_memorizing_random_passwords.pdf",
          location="San Diego, CA, USA",
          booktitle="Proceedings of the 23rd USENIX Security Symposium",
          year="2014",
  }
  

Time-based cryptography and verifiable lotteries

• Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions (working draft)
  Joseph Bonneau, Benedikt Bünz, Miranda Christ and Yuval Efron.
  Abstract Citation
  

  We reconsider Cleve's famous 1986 impossibility result on coin-flipping without an honest majority. Recently proposed constructions have circumvented this limit by using cryptographic delay functions. We show that this is necessary: a (weak) notion of delay functions is in fact implied by the existence of a protocol circumventing Cleve's impossibility. However, such delay functions are weaker than those used in existing constructions. We complete our result by showing an equivalence, that these weaker delay functions are also sufficient to construct not just fair dishonest-majority coin-flipping protocols, but also the stronger notion of a distributed randomness beacon. We also show that this is possible in a weaker communication model than previously considered, without the assumption of reliable broadcast or a public bulletin board.

  @inproceedings{BBCE24a,
          url="https://eprint.iacr.org/2024/1711",
          institution="",
          author="Joseph Bonneau and Benedikt B{\"{u}}nz and Miranda Christ and Yuval Efron",
          title="{Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions}",
          year="2024",
  }
  

• Cornucopia: Distributed randomness beacons at scale
  Miranda Christ, Kevin Choi and Joseph Bonneau. AFT 2024. Vienna, Austria.
  Abstract Citation
  

  We propose Cornucopia, a distributed randomness beacon protocol combining accumulators and verifiable delay functions. Cornucopia extends the Unicorn protocol of Lenstra and Wesolowski, utilizing an accumulator to enable efficient verification by each participant that their randomness contribution has been included in the beacon output. The security of this construction reduces to a novel property of accumulators, insertion security. We first show that not all accumulators are insertion-secure. We then prove that common constructions (Merkle trees and RSA accumulators) are naturally insertion-secure. Finally, we give a generic transformation from any universal accumulator (supporting nonmembership proofs) to an insertion-secure accumulator, albeit with an efficiency loss proportional to the security parameter.

  @inproceedings{CCB23,
          url="https://eprint.iacr.org/2023/1554.pdf",
          author="Miranda Christ and Kevin Choi and Joseph Bonneau",
          title="{Cornucopia: Distributed randomness beacons at scale}",
          location="Vienna, Austria",
          booktitle="AFT '24: Proceedings of the 6\textsuperscript{th} International Conference on Advances in Financial Technologies",
          year="2024",
  }
  

• Accountable Secret Leader Election
  Walter McKelvie, Miranda Christ, Kevin Choi, Tal Malkin and Joseph Bonneau. AFT 2024. Vienna, Austria.
  Abstract Citation
  

  We consider the problem of secret leader election with accountability. Secret leader election protocols counter adaptive adversaries by keeping the identities of elected leaders secret until they choose to reveal themselves, but in existing protocols this means it is impossible to determine who was elected leader if they fail to act. This opens the door to undetectable withholding attacks, where leaders fail to act in order to slow the protocol or bias future elections in their favor. We formally define accountability (in weak and strong variants) for secret leader election protocols. We present three paradigms for adding accountability, using delay-based cryptography, enforced key revelation, or threshold committees, all of which ensure that after some time delay the result of the election becomes public. The paradigm can be chosen to balance trust assumptions, protocol efficiency, and the length of the delay before leaders are revealed. Along the way, we introduce several new cryptographic tools including re-randomizable timed commitments and timed VRFs.

  @inproceedings{MCCMB23,
          url="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.1",
          author="Walter McKelvie and Miranda Christ and Kevin Choi and Tal Malkin and Joseph Bonneau",
          title="{Accountable Secret Leader Election}",
          location="Vienna, Austria",
          booktitle="AFT '24: Proceedings of the 6\textsuperscript{th} International Conference on Advances in Financial Technologies",
          year="2024",
  }
  

• Riggs: Decentralized Sealed-Bid Auctions
  Nirvan Tyagi, Arasu Arun, Cody Freitag, Riad Wahby, Joseph Bonneau and David Mazières. ACM CCS 2023. Copenhagen, Denmark.
  Abstract Citation
  

  We introduce the first practical protocols for fully decentralized sealed-bid auctions using timed commitments. Timed commitments ensure that the auction is finalized fairly even if all participants drop out after posting bids or if n − 1 bidders collude to try to learn the $n^{th}$ bidder’s bid value. Our protocols rely on a novel non-malleable timed commitment scheme which efficiently supports range proofs to establish that bidders have sufficient funds to cover a hidden bid value. Our protocols are concretely efficient and we have implemented them in an Ethereum-compatible smart contract which automatically enforces payment and delivery of an auctioned digital good.

  @inproceedings{TAFWBM23,
          url="https://eprint.iacr.org/2023/1336",
          author="Nirvan Tyagi and Arasu Arun and Cody Freitag and Riad Wahby and Joseph Bonneau and David Mazières",
          title="{Riggs: Decentralized Sealed-Bid Auctions}",
          location="Copenhagen, Denmark",
          booktitle="CCS '23: The 30\textsuperscript{th} ACM Conference on Computer and Communications Security",
          year="2023",
  }
  

• Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles (working draft)
  Noemi Glaeser, István András Seres, Michael Zhu and Joseph Bonneau.
  Abstract Citation
  

  Auction and voting schemes play a crucial role in the Web3 ecosystem. Yet currently deployed implementations either lack privacy or require at least two rounds, hindering usability and security. We introduce Cicada, a general framework for using linearly homomorphic time-lock puzzles (HTLPs) to enable provably secure, non-interactive private auction and voting protocols. We instantiate our framework with an efficient new HTLP construction and novel packing techniques that enable succinct ballot correctness proofs independent of the number of candidates. We demonstrate the practicality of our approach by implementing our protocols for the Ethereum Virtual Machine (EVM).

  @inproceedings{GSZB23,
          url="https://eprint.iacr.org/2023/1473.pdf",
          institution="",
          author="Noemi Glaeser and István András Seres and Michael Zhu and Joseph Bonneau",
          title="{Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles}",
          year="2023",
  }
  

• SoK: Distributed Randomness Beacons
  Kevin Choi, Aathira Manoj and Joseph Bonneau. IEEE Security & Privacy (Oakland) 2023. San Francisco, CA, USA.
  Abstract Citation
  

  Motivated and inspired by the emergence of blockchains, many new protocols have recently been proposed for generating publicly verifiable randomness in a distributed yet secure fashion. These protocols work under different setups and assumptions, use various cryptographic tools, and entail unique trade-offs and characteristics. In this paper, we systematize the design of distributed randomness beacons (DRBs) as well as the cryptographic building blocks they rely on. We evaluate protocols on two key security properties, unbiasability and liveness and discuss common attack vectors for predicting or biasing the beacon output and the countermeasures employed by protocols. We also compare protocols by communication and computational efficiency. Finally, we provide insights on the applicability of different protocols in various deployment scenarios and highlight possible directions for further research.

  @inproceedings{CMB23,
          url="https://eprint.iacr.org/2023/728.pdf",
          institution="",
          author="Kevin Choi and Aathira Manoj and Joseph Bonneau",
          title="{SoK: Distributed Randomness Beacons}",
          location="San Francisco, CA, USA",
          booktitle="IEEE Symposium on Security and Privacy",
          year="2023",
  }
  

• Bicorn: An optimistically efficient distributed randomness beacon
  Kevin Choi, Arasu Arun, Nirvan Tyagi and Joseph Bonneau. FC 2023. Bol, Brač, Croatia.
  Abstract Citation
  

  We introduce Bicorn, an optimistically efficient distributed randomness protocol with strong robustness properties under a dishonest majority. Bicorn is a "commit-reveal-recover" protocol. Each participant contributes a commitment to a random value, which are then opened and combined to produce a random output. If any participants fail to open, recovery is possible via a single time-lock puzzle which can be solved by any party. In the optimistic case, Bicorn is an extremely simple and efficient two-round protocol with no time-lock puzzle. In either case, Bicorn supports open, flexible participation and reconfiguration, requires only a public bulletin board and no group-specific setup or PKI, and is guaranteed to produce unpredictable output assuming any single participant is honest. All communication and computation costs are (at most) linear in the number of participants with very low concrete overhead.

  @inproceedings{CATB23,
          url="https://eprint.iacr.org/2023/221.pdf",
          author="Kevin Choi and Arasu Arun and Nirvan Tyagi and Joseph Bonneau",
          title="{Bicorn: An optimistically efficient distributed randomness beacon}",
          location="Bol, Brač, Croatia",
          booktitle="FC '23: Proceedings of the 27\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2023",
  }
  

• Short-lived zero-knowledge proofs and signatures
  Arasu Arun, Joseph Bonneau and Jeremy Clark. Asiacrypt 2022. Taipei, Taiwan.
  Abstract Citation
  

  We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens "naturally" without further involvement from the prover or any third party. We propose formal definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. Our work also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest.

  @inproceedings{ABC22,
          url="https://eprint.iacr.org/2022/190.pdf",
          author="Arasu Arun and Joseph Bonneau and Jeremy Clark",
          title="{Short-lived zero-knowledge proofs and signatures}",
          location="Taipei, Taiwan",
          booktitle="Asiacrypt '22: Annual International Conference on the Theory and Application of Cryptology and Information Security",
          year="2022",
  }
  

• Verifiable Delay Functions
  Dan Boneh, Joseph Bonneau, Benedikt Bünz and Ben Fisch. CRYPTO 2018. Santa Barbara, CA, USA.
  Abstract Citation
  

  We study the problem of building a verifiable delay function (VDF). A VDF requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

  @inproceedings{BBBF18,
          url="https://eprint.iacr.org/2018/601.pdf",
          author="Dan Boneh and Joseph Bonneau and Benedikt B{\"{u}}nz and Ben Fisch",
          title="{Verifiable Delay Functions}",
          location="Santa Barbara, CA, USA",
          booktitle="CRYPTO '18: The 2018 IACR International Cryptology Conference",
          year="2018",
  }
  

• Proofs-of-delay and randomness beacons in Ethereum
  Benedikt Bünz, Steven Goldfeder and Joseph Bonneau. S&B '17: IEEE Security & Privacy on the Blockchain. Paris, France.
  Abstract Citation
  

  Blockchains generated using a proof-of-work consensus protocol, such as Bitcoin or Ethereum, are promising sources of public random-ness. However, the randomness is subject to manipulation by the miners generating the blockchain. A general defense is to apply a delay function, preventing malicious miners from computing the random output until it is too late to manipulate it. Ideally, this delay function can provide a short proof-of-delay that is efficient enough to be verified within a smart contract, enabling the randomness source to be directly by smart contracts. In this paper we describe the challenges of solving this problem given the extremely limited computational capacity available in Ethereum, the most popular general-purpose smart contract framework to date. We introduce a novel multi-round protocol for verifying delay functions using a refereed delegation model. We provide a prototype Ethereum implementation to analyze performance and find that it is feasible in terms of gas costs, costing roughly 180000 gas (US$ 0.11 1 ) to post a beacon and 720000 gas (US$ 0.98) to resolve a dispute. We also discuss the incentive challenges raised by providing a secure randomness beacon as a public good.

  @inproceedings{BGB17,
          url="https://www.jbonneau.com/doc/BGB17-IEEESB-proof_of_delay_ethereum.pdf",
          author="Benedikt B{\"{u}}nz and Steven Goldfeder and Joseph Bonneau",
          title="{Proofs-of-delay and randomness beacons in Ethereum}",
          location="Paris, France",
          booktitle="S{\&}B '17: Proceedings of the 1\textsuperscript{st} IEEE Security {\&} Privacy on the Blockchain Workshop",
          year="2017",
  }
  

• On Bitcoin as a public randomness source
  Joseph Bonneau, Jeremy Clark and Steven Goldfeder .
  Abstract Citation
  

  We formalize the use of Bitcoin as a source of publicly-verifiable randomness. As a side-effect of Bitcoin's proof-of-work-based consensus system, random values are broadcast every time new blocks are mined. We can derive strong lower bounds on the computational min-entropy in each block: currently, at least 68 bits of min-entropy are produced every 10 minutes, from which one can derive over 32 near-uniform bits using standard extractor techniques. We show that any attack on this beacon would form an attack on Bitcoin itself and hence have a monetary cost that we can bound, unlike any other construction for a public randomness beacon in the literature. In our simplest construction, we show that a lottery producing a single unbiased bit is manipulation-resistant against an attacker with a stake of less than 50 bitcoins in the output, or about US\$12,000 today. Finally, we propose making the beacon output available to smart contracts and demonstrate that this simple tool enables a number of interesting applications.

  @techreport{BCG15,
          url="https://eprint.iacr.org/2015/1015.pdf",
          institution="Cryptology ePrint Archive",
          number="2015/1015",
          author="Joseph Bonneau and Jeremy Clark and Steven Goldfeder ",
          title="{On Bitcoin as a public randomness source}",
          year="2015",
  }
  

Zero-knowledge proofs

• NOPE: Strengthening domain authentication with zero-knowledge proofs
  Zachary DeStefano, Jeff J. Ma, Joseph Bonneau and Michael Walfish. SOSP 2024. Austin, TX, USA.
  Abstract Citation
  

  Server authentication assures users that they are communicating with a server that genuinely represents a claimed domain. Today, server authentication relies on certification authorities (CAs), third parties who sign statements binding public keys to domains. CAs remain a weak spot in Internet security, as any faulty CA can issue a certificate for any domain. This paper describes the design, implementation, and experimental evaluation of NOPE, a new mechanism for server authentication that uses succinct proofs (for example, zero-knowledge proofs) to prove that a DNSSEC chain exists that links a public key to a specified domain. The use of DNSSEC dramatically reduces reliance on CAs, and the small size of the proofs enables compatibility with legacy infrastructure, including TLS servers, certificate formats, and certificate transparency. NOPE proofs add minimal performance overhead to clients, increasing the size of a typical certificate chain by about 10x. NOPE's core technical contributions (which generalize beyond NOPE) include efficient techniques for representing parsing and cryptographic operations within succinct proofs, which reduce proof generation time and memory requirements by nearly an order of magnitude.

  @inproceedings{DMBW,
          url="https://nope-tools.org/nope.pdf",
          author="Zachary DeStefano and Jeff J. Ma and Joseph Bonneau and Michael Walfish",
          title="{NOPE: Strengthening domain authentication with zero-knowledge proofs}",
          location="Austin, TX, USA",
          booktitle="SOSP '24: The 30\textsuperscript{th} Symposium on Operating Systems Principles",
          year="2024",
  }
  

• NOTRY: Deniable messaging with retroactive avowal
  Faxing Wang, Shaanan Cohney, Riad Wahby and Joseph Bonneau. PETS 2024. Bristol, England, UK.
  Abstract Citation
  

  Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke the deniability of a conversation and avow its contents after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated verifier proofs (ADV proofs) which may be of independent interest. Our implementation of the protocol incurs an 8× communication and computation performance overhead over the basic Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as key exchanges (the source of the overhead) still complete in just over 1ms.

  @inproceedings{WCWB24,
          url="https://eprint.iacr.org/2023/1926",
          institution="",
          author="Faxing Wang and Shaanan Cohney and Riad Wahby and Joseph Bonneau",
          title="{NOTRY: Deniable messaging with retroactive avowal}",
          location="Bristol, England, UK",
          booktitle="PETS '24: The 18\textsuperscript{th} Privacy Enhancing Technologies Symposium",
          year="2024",
  }
  

• Zombie: Middleboxes that Don’t Snoop
  Collin Zhang, Zachary DeStefano, Arasu Arun, Joseph Bonneau, Paul Grubbs and Michael Walfish. NSDI 2024. Santa Clara, CA, USA.
  Abstract Citation
  

  Zero-knowledge middleboxes (ZKMBs) are a recent paradigm in which clients get privacy while middleboxes enforce policy: clients prove in zero knowledge that the plaintext underlying their encrypted traffic complies with network policies, such as DNS filtering. However, prior work had impractically poor performance and was limited in functionality. This work presents Zombie, the first system built using the ZKMB paradigm. Zombie introduces techniques that push ZKMBs to the verge of practicality: preprocessing (to move the bulk of proof generation to idle times between requests), asynchrony (to remove proving and verifying costs from the critical path), and batching (to amortize some of the verification work). Zombie’s choices, together with these techniques, provide a factor of 3.5x speedup in total computation done by client and middlebox, lowering the critical path overhead for a DNS filtering application to less than 300ms (on commodity hardware) or (in the asynchronous configuration) to 0. As an additional contribution that is likely of independent interest, Zombie introduces a portfolio of techniques to efficiently encode regular expressions in probabilistic (and zero knowledge) proofs; these techniques offer significant asymptotic and constant factor improvements in performance over a standard baseline. Zombie builds on this portfolio to support policies based on regular expressions, such as data loss prevention.

  @inproceedings{ZDAGBW24,
          url="https://eprint.iacr.org/2023/1022.pdf",
          author="Collin Zhang and Zachary DeStefano and Arasu Arun and Joseph Bonneau and Paul Grubbs and Michael Walfish",
          title="{Zombie: Middleboxes that Don't Snoop}",
          location="Santa Clara, CA, USA",
          booktitle="NSDI '24: The 21\textsuperscript{st} USENIX Symposium on Networked Systems Design and Implementation (NSDI)",
          year="2024",
  }
  

• Powers-of-Tau to the People: Decentralizing Setup Ceremonies
  Valeria Nikolaenko, Sam Ragsdale, Joseph Bonneau and Dan Boneh. ACNS 2023. Abu Dhabi, UAE.
  Abstract Citation
  

  We introduce the first decentralized trusted setup protocols for constructing a powers-of-tau structured reference string. Facilitated by a blockchain platform, our protocols can run in a permissionless manner, with anybody able to participate in exchange for paying requisite transaction fees. The result is secure as long as any single party participates honestly. We introduce several protocols optimized for different sized powers-of-tau setups and using an on-chain or off-chain data availability model to store the resulting string. We implement our most efficient protocol on top of Ethereum, demonstrating practical concrete performance numbers.

  @inproceedings{NRBB22,
          url="https://eprint.iacr.org/2022/1592",
          institution="Cryptology ePrint Archive",
          author="Valeria Nikolaenko and Sam Ragsdale and Joseph Bonneau and Dan Boneh",
          title="{Powers-of-Tau to the People: Decentralizing Setup Ceremonies}",
          location="Abu Dhabi, UAE",
          booktitle="ACNS '24: he 22\textsuperscript{nd} International Conference on Applied Cryptography and Network Security (ACNS)",
          year="2024",
  }
  

• Naysayer proofs
  István András Seres, Noemi Glaeser and Joseph Bonneau. FC 2024. Willemstad, Curaçao.
  Abstract Citation
  

  This work introduces the notion of naysayer proofs. We observe that in numerous (zero-knowledge) proof systems, it is significantly more efficient for the verifier to be convinced by a so-called naysayer that a false proof is invalid than it is to check that a genuine proof is valid. We show that every NP language has constant-size and constant-time naysayer proofs. We also show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles. Naysayer proofs enable an interesting new optimistic verification mode potentially suitable for resource-constrained verifiers, such as smart contracts.

  @inproceedings{SGB24,
          url="https://eprint.iacr.org/2023/1472.pdf",
          institution="",
          author="István András Seres and Noemi Glaeser and Joseph Bonneau",
          title="{Naysayer proofs}",
          location="Willemstad, Curaçao",
          booktitle="FC '24: Proceedings of the 28\textsuperscript{th} International Conference on Financial Cryptography and Data Security",
          year="2024",
  }
  

• Riggs: Decentralized Sealed-Bid Auctions
  Nirvan Tyagi, Arasu Arun, Cody Freitag, Riad Wahby, Joseph Bonneau and David Mazières. ACM CCS 2023. Copenhagen, Denmark.
  Abstract Citation
  

  We introduce the first practical protocols for fully decentralized sealed-bid auctions using timed commitments. Timed commitments ensure that the auction is finalized fairly even if all participants drop out after posting bids or if n − 1 bidders collude to try to learn the $n^{th}$ bidder’s bid value. Our protocols rely on a novel non-malleable timed commitment scheme which efficiently supports range proofs to establish that bidders have sufficient funds to cover a hidden bid value. Our protocols are concretely efficient and we have implemented them in an Ethereum-compatible smart contract which automatically enforces payment and delivery of an auctioned digital good.

  @inproceedings{TAFWBM23,
          url="https://eprint.iacr.org/2023/1336",
          author="Nirvan Tyagi and Arasu Arun and Cody Freitag and Riad Wahby and Joseph Bonneau and David Mazières",
          title="{Riggs: Decentralized Sealed-Bid Auctions}",
          location="Copenhagen, Denmark",
          booktitle="CCS '23: The 30\textsuperscript{th} ACM Conference on Computer and Communications Security",
          year="2023",
  }
  

• Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles (working draft)
  Noemi Glaeser, István András Seres, Michael Zhu and Joseph Bonneau.
  Abstract Citation
  

  Auction and voting schemes play a crucial role in the Web3 ecosystem. Yet currently deployed implementations either lack privacy or require at least two rounds, hindering usability and security. We introduce Cicada, a general framework for using linearly homomorphic time-lock puzzles (HTLPs) to enable provably secure, non-interactive private auction and voting protocols. We instantiate our framework with an efficient new HTLP construction and novel packing techniques that enable succinct ballot correctness proofs independent of the number of candidates. We demonstrate the practicality of our approach by implementing our protocols for the Ethereum Virtual Machine (EVM).

  @inproceedings{GSZB23,
          url="https://eprint.iacr.org/2023/1473.pdf",
          institution="",
          author="Noemi Glaeser and István András Seres and Michael Zhu and Joseph Bonneau",
          title="{Cicada: Efficient tally-private elections and sealed-bid auctions from homomorphic time-lock puzzles}",
          year="2023",
  }
  

• Short-lived zero-knowledge proofs and signatures
  Arasu Arun, Joseph Bonneau and Jeremy Clark. Asiacrypt 2022. Taipei, Taiwan.
  Abstract Citation
  

  We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens "naturally" without further involvement from the prover or any third party. We propose formal definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. Our work also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest.

  @inproceedings{ABC22,
          url="https://eprint.iacr.org/2022/190.pdf",
          author="Arasu Arun and Joseph Bonneau and Jeremy Clark",
          title="{Short-lived zero-knowledge proofs and signatures}",
          location="Taipei, Taiwan",
          booktitle="Asiacrypt '22: Annual International Conference on the Theory and Application of Cryptology and Information Security",
          year="2022",
  }
  

• Zero-Knowledge Middleboxes
  Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau and Michael Walfish. USENIX Security 2022. Boston, MA, USA.
  Abstract Citation
  

  This paper initiates research on zero-knowledge middleboxes (ZKMBs). A ZKMB is a network middlebox that enforces network usage policies on encrypted traffic. Clients send the middlebox zero-knowledge proofs that their traffic is policy-compliant; these proofs reveal nothing about the client’s communication except that it complies with the policy. We show how to make ZKMBs work with unmodified encrypted-communication protocols (specifically TLS 1.3), making ZKMBs invisible to servers. As a contribution of independent interest, we design zero-knowledge proofs for TLS 1.3 session keys. We apply the ZKMB paradigm to several case studies, including filtering for encrypted DNS protocols. Experimental results suggest that performance, while not yet practical, is promising. The middlebox’s overhead is only 2–5ms of running time per verified proof. Clients must store hundreds of MBs to participate in the protocol, and added latency ranges from tens of seconds (to set up a connection) to several seconds (for each successive packet requiring proof). Our optimized TLS 1.3 proofs improve the client’s costs 6× over an unoptimized baseline.

  @inproceedings{GAZBW22,
          url="https://eprint.iacr.org/2021/1022.pdf",
          author="Paul Grubbs and Arasu Arun and Ye Zhang and Joseph Bonneau and Michael Walfish",
          title="{Zero-Knowledge Middleboxes}",
          location="Boston, MA, USA",
          booktitle="Proceedings of the 31st USENIX Security Symposium",
          year="2022",
  }
  

News provenance

• Transparency, Trust, and Security Needs for the Design of Digital News Authentication Tools
  Bernat Ivancsics, Eve Washington, Errol Francis II, Ayana Monroe, Emily Sidnam-Mauch, Joseph Bonneau, Kelly Caine and Susan E. McGregor. CSCW 2023.
  Abstract Citation
  

  Americans' trust in news is declining, and authenticity and transparency challenges in digital publishing contexts pose unique challenges to the ability to effectively gratify their information-seeking needs via online media. Cryptographic technologies and web-based provenance indicators have the potential to enhance the trustworthiness and transparency of digital communication, but better understandings of news consumers practices and needs are required to develop practical tools. Through a representative online survey of 400 digital news consumers and 19 follow-up interviews, we investigate how users authenticate and assign trust to news content, and identify specific needs pertaining to news transparency and authentication that could be met by digital news authentication tools. While many users currently rely on political ideology to assess news trustworthiness, we find that users of all political orientations see value in independent provenance and authentication tools for digital news.

  @inproceedings{IWFMSBCM23,
          url="https://dl.acm.org/doi/10.1145/3579534",
          author="Bernat Ivancsics and Eve Washington and Errol Francis II and Ayana Monroe and Emily Sidnam-Mauch and Joseph Bonneau and Kelly Caine and Susan E. McGregor",
          title="{Transparency, Trust, and Security Needs for the Design of Digital News Authentication Tools}",
          booktitle="CSCW '23: 26\textsuperscript{th} ACM Conference On Computer-Supported Cooperative Work And Social Computing",
          year="2023",
  }
  

• Usable Cryptographic Provenance Systems to Proactively Mitigate Misinformation Creation and Spread
  Emily Sidnam-Mauch, Bernat Ivancsics, Ayana Monroe, Eve Washington, Errol Francis II, Kelly Caine, Joseph Bonneau and Susan E. McGregor. MEDIATE.
  Abstract Citation
  

  This paper describes how cryptographic provenance can serve as a proactive, partial solution for mitigating misinformation. Drawing on literature from human-centered computing and usable security, journalism, and cryptography, we discuss the advantages and limitations of both content-based and technical approaches to the problem of online misinformation. We argue cryptographic provenance systems designed for usability can reduce the spread of misinformation by surfacing provenance information and making this information salient and acceptable to information consumers. We highlight challenges and open research areas related to designing usable cryptographic provenance systems, specifically concerning two key stakeholder groups: journalists and news consumers.

  @inproceedings{SIMWBCM22,
          url="https://workshop-proceedings.icwsm.org/pdf/2022_55.pdf",
          author="Emily Sidnam-Mauch and Bernat Ivancsics and Ayana Monroe and Eve Washington and Errol Francis II and Kelly Caine and Joseph Bonneau and Susan E. McGregor",
          title="{Usable Cryptographic Provenance Systems to Proactively Mitigate Misinformation Creation and Spread}",
          booktitle="MEDIATE Workshop",
          year="2022",
  }
  

• The Invisible Infrastructures of Online Visibility: An Analysis of the Platform-Facing Markup Used by U.S.-Based Digital News Organizations
  Bernat Ivancsics, Eve Washington, Errol Francis II, Ayana Monroe, Emily Sidnam-Mauch, Joseph Bonneau, Kelly Caine and Susan E. McGregor. Digital Journalism 2022.
  Abstract Citation
  

  This study analyzes and compares how the digital semantic infrastructure of U.S. based digital news varies according to certain characteristics of the media outlet, including the community it serves, the content management system (CMS) it uses, and its institutional affiliation (or lack thereof). Through a multi-stage analysis of the actual markup found on news outlets’ online text articles, we reveal how multiple factors may be limiting the discoverability and reach of online media organizations focused on serving specific communities. Conceptually, we identify markup and metadata as aspects of the semantic infrastructure underpinning platforms’ mechanisms of distributing online news. Given the significant role that these platforms play in shaping the broader visibility of news content, we further contend that this markup therefore constitutes a kind of infrastructure of visibility by which news sources and voices are rendered accessible—or, conversely—invisible in the wider platform economy of journalism. We accomplish our analysis by first identifying key forms of digital markup whose structured data is designed to make online news articles more readily discoverable by search engines and social media platforms. We then analyze 2,226 digital news stories gathered from the main pages of 742 national, local, Black, and other identity-based news organizations in mid-2021, and analyze each for the presence of specific tags reflecting the Schema.org, OpenGraph, and Twitter metadata structures. We then evaluate the relationship between audience focus and the robustness of this digital semantic infrastructure. While we find only a weak relationship between the markup and the community served, additional analysis revealed a much stronger association between these metadata tags and content management system (CMS), in which 80% of the attributes appearing on an article were the same for a given CMS, regardless of publisher, market, or audience focus. Based on this finding, we identify the organizational characteristics that may influence the specific CMS used for digital publishing, and, therefore, the robustness of the digital semantic infrastructure deployed by the organization. Finally, we reflect on the potential implications of the highly disparate tag use we observe, particularly with respect to the broader visibility of online news designed to serve particular US communities.

  @inproceedings{IWFMSBCM22,
          url="https://par.nsf.gov/servlets/purl/10470469",
          number="2021/627",
          author="Bernat Ivancsics and Eve Washington and Errol Francis II and Ayana Monroe and Emily Sidnam-Mauch and Joseph Bonneau and Kelly Caine and Susan E. McGregor",
          title="{The Invisible Infrastructures of Online Visibility: An Analysis of the Platform-Facing Markup Used by U.S.-Based Digital News Organizations}",
          booktitle="Digital Journalism: The Platformization of News",
          year="2022",
  }