Vasilis Pappas, Fernando Krell, Binh Vo, Vlad Kolesnimov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos Keromytis, and Steven M. Bellovin. Blind seer: A scalable private DBMS. In IEEE Symposium on Security and Privacy, May 2014. To appear. [ bib ]

Mariana Raykova, Ang Cui, Binh Vo, Bin Liu, Tal Malkin, Steven M. Bellovin, and Salvatore J. Stolfo. Usable secure private search. IEEE Security & Privacy, 10(5), September-October 2012. [ bib | DOI | .pdf ]

It is a common requirement in real world applications for untrusting parties to be able to share sensitive information securely. We describe a secure anonymous database search scheme (SADS) that provides exact keyword match capability. Using a new primitive, re-routable encryption, and the ideas of Bloom filters and deterministic encryption, SADS allows multiple parties to efficiently execute exact match queries over distributed encrypted database in a controlled manner. We further consider a more general search setting allowing similarity searches, going beyond existing work that considers similarity in terms of error-tolerance and Hamming distance by capturing semantic level similarity in our definition. Building on the cryptographic and privacy preserving guarantees of the SADS primitive, we then describe a general framework for engineering usable private secure search systems.

Mariana Raykova, Hang Zhao, and Steven M. Bellovin. Privacy enhanced access control for outsourced data sharing. In Financial Cryptography and Data Security, March 2012. [ bib | .pdf ]

Traditional access control models often assume that the entity enforcing access control policies is also the owner of data and resources. This assumption no longer holds when data is outsourced to a third-party storage provider, such as the cloud. Existing access control solutions mainly focus on preserving confidentiality of stored data from unauthorized access and the storage provider. However, in this setting, access control policies as well as users' access patterns also become privacy sensitive information that should be protected from the cloud. We propose a two-level access control scheme that combines coarse-grained access control enforced at the cloud, which allows to get acceptable communication overhead and at the same time limits the information that the cloud learns from his partial view of the access rules and the access patterns, and fine-grained cryptographic access control enforced at the user's side, which provides the desired expressiveness of the access control policies. Our solution handles both read and write access control.

Vasilis Pappas, Mariana Raykova, Binh Vo, Steven M. Bellovin, and Tal Malkin. Private search in the real world. In Proceedings of the 2011 Annual Computer Security Applications Conference, December 2011. [ bib | .pdf ]

Encrypted search-performing queries on protected data-has been explored in the past; however, its inherent inefficiency has raised questions of practicality. Here, we focus on improving the performance and extending its functionality enough to make it practical. We do this by optimizing the system, and by stepping back from the goal of achieving maximal privacy guarantees in an encrypted search scenario and consider efficiency and functionality as priorities.

We design and analyze the privacy implications of two practical extensions applicable to any keyword-based private search system. We evaluate their efficiency by building them on top of a private search system, called SADS. Additionally, we improve SADS' performance, privacy guaranties and functionality. The extended SADS system offers improved efficiency parameters that meet practical usability requirements in a relaxed adversarial model. We present the experimental results and evaluate the performance of the system. We also demonstrate analytically that our scheme can meet the basic needs of a major hospital complex's admissions records. Overall, we achieve performance comparable to a simply configured MySQL database system.

Steven M. Bellovin. Frank Miller: Inventor of the one-time pad. Cryptologia, 35(3):203-222, July 2011. An earlier version is available as technical report CUCS-009-11. [ bib | http ]

The invention of the one-time pad is generally credited to Gilbert S. Vernam and Joseph O. Mauborgne. We show that it was invented about 35 years earlier by a Sacramento banker named Frank Miller. We provide a tentative identification of which Frank Miller it was, and speculate on whether or not Mauborgne might have known of Miller's work, especially via his colleague Parker Hitt.

Elli Androulaki, Binh Vo, and Steven M. Bellovin. Privacy-preserving, taxable bank accounts. In Proceedings of the European Symposium on Research in Computer Security (ESORICS), Athens, September 2010. Longer version issued as Tech Report CUCS-005-10. [ bib ]

Current banking systems do not aim to protect user privacy. Purchases made from a single bank account can be linked to each other by many parties. This could be addressed in a straight-forward way by generating unlinkable credentials from a single master credential using Camenisch and Lysyanskaya's algorithm; however, if bank accounts are taxable, some report must be made to the tax authority about each account. Using unlinkable credentials, digital cash, and zero knowledge proofs of kmowledge, we present a solution that prevents anyone, even the tax authority, from knowing which accounts belong to which users, or from being able to link any account to another or to purchases or deposits.

Elli Androulaki and Steven M. Bellovin. A secure and privacy-preserving targeted ad-system. In Proceedings of the 1st Workshop on Real-Life Cryptographic Protocols and Standardization, January 2010. [ bib | .pdf ]

Mariana Raykova, Binh Vo, Tal Malkin, and Steven M. Bellovin. Secure anonymous database search. In Proceedings of the ACM Cloud Computing Security Workshop, November 2009. [ bib | .pdf ]

Elli Androulaki and Steven M. Bellovin. An anonymous credit card system. In Proceedings of 6th International Conference on Trust, Privacy & Security in Digital Business (TrustBus), September 2009. Longer version issued as Tech Report CUCS-010-09. [ bib | .pdf ]

Elli Androulaki and Steven M. Bellovin. Anonymous delivery of physical objects. In Symposium on Privacy-Enhancing Technologies (PET), July 2009. [ bib | .pdf ]

Elli Androulaki, Mariana Raykova, Angelos Stavrou, and Steven M. Bellovin. PAR: Payment for anonymous routing. In Proceedings of the 8th Privacy Enhancing Technologies Symposium, July 2008. [ bib | .pdf ]

Elli Androulaki, Seung Geol Choi, Steven M. Bellovin, and Tal Malkin. Reputation systems for anonymous networks. In Proceedings of the 8th Privacy Enhancing Technologies Symposium, July 2008. [ bib | .pdf ]

Steven M. Bellovin and Eric K. Rescorla. Deploying a new hash algorithm. In Proceedings of NDSS '06, 2006. [ bib | .pdf ]

William Aiello, Steven M. Bellovin, Matt Blaze, Ran Canetti, John Ioannidis, Angelos D. Keromytis, and Omer Reingold. Just fast keying: Key agreement in a hostile Internet. ACM Transactions on Information and System Security (TISSEC), 7(2):1-32, May 2004. [ bib ]

William Aiello, Steven M. Bellovin, Matt Blaze, Ran Canetti, John Ioannidis, Angelos D. Keromytis, and Omer Reingold. Efficient, DoS-resistant, secure key exchange for internet protocols. In Proceedings of the ACM Computer and Communications Security (CCS) Conference, November 2002. [ bib | .ps | .pdf ]

S.M. Bellovin and M.A. Blaze. Cryptographic modes of operation for the Internet. In Second NIST Workshop on Modes of Operation, August 2001. [ bib | .ps | .pdf ]

D. Whiting, B. Schneier, and S. Bellovin. AES key agility issues in high-speed IPsec implementations, 2000. [ bib | .ps | .pdf ]

Steven M. Bellovin. Cryptography and the internet. In Advances in Cryptology: Proceedings of CRYPTO '98, August 1998. [ bib | .ps | .pdf ]

Steven M. Bellovin. Probable plaintext cryptanalysis of the IP security protocols. In Proc. of the Symposium on Network and Distributed System Security, pages 155-160, 1997. [ bib | .ps | .pdf ]

Steven M. Bellovin. Problem areas for the IP security protocols. In Proceedings of the Sixth Usenix Unix Security Symposium, pages 205-214, July 1996. [ bib | .ps | .pdf ]

David A. Wagner and Steven M. Bellovin. A “bump in the stack” encryptor for MS-DOS systems. In Proceedings of the Symposium on Network and Distributed System Security, pages 155-160, San Diego, February 1996. [ bib | .ps | .pdf ]

Uri Blumenthal and Steven M. Bellovin. A better key schedule for DES-like ciphers. In Proceedings of PRAGOCRYPT '96, Prague, 1996. [ bib | .ps | .pdf ]

Matt Blaze and Steven M. Bellovin. Session-layer encryption. In Proc. 5th USENIX UNIX Security Symposium, Salt Lake City, UT, June 1995. [ bib | .ps | .pdf ]

Steven M. Bellovin and Michael Merritt. An attack on the Interlock Protocol when used for authentication. IEEE Transactions on Information Theory, 40(1):273-275, January 1994. [ bib | .ps | .pdf ]

David A. Wagner and Steven M. Bellovin. A programmable plaintext recognizer, 1994. Unpublished. [ bib | .ps | .pdf ]

Steven M. Bellovin and Michael Merritt. Augmented encrypted key exchange. In Proceedings of the First ACM Conference on Computer and Communications Security, pages 244-250, Fairfax, VA, November 1993. [ bib | .ps | .pdf ]

Steven M. Bellovin and Michael Merritt. Encrypted key exchange: Password-based protocols secure against dictionary attacks. In Proc. IEEE Computer Society Symposium on Research in Security and Privacy, pages 72-84, Oakland, CA, May 1992. [ bib | .ps | .pdf ]

Steven M. Bellovin and Michael Merritt. Limitations of the Kerberos authentication system. In USENIX Conference Proceedings, pages 253-267, Dallas, TX, Winter 1991. [ bib | .ps | .pdf ]