Publications

• Jian Zhang and Joan Feigenbaum,
  Finding Highly Correlated Pairs Efficiently with Powerful Pruning,
  to appear in Proceedings of the 2006 ACM Conference on Information and Knowledge Management. [pdf]
• Phillip Porras and Vitaly Shmatikov. 
  "Large-Scale Collection and Sanitization of Network Security Data: Risks and Challenges",
  to appear in New Security Paradigms Workshop 2006.
• T. Roughgarden and  M. Sundararajan,
  ``New Trade-Offs in Cost-Sharing Mechanisms'',
  in 37th Annual ACM Symposium on Theory of Computing (STOC), pages 79--88, 2006.
• T. Roughgarden and  M. Sundararajan,
  ``Approximately Efficient Cost-Sharing Mechanisms'',
  submitted to the 46th Annual Symposium on Foundations of Computer Science (FOCS), 2006.
•  H. Chen, T. Roughgarden, and  G. Valiant,
  ``Sharing Costs to Improve Selfish Network Design'',
  submitted to the 46th Annual Symposium on Foundations of Computer Science (FOCS), 2006.
• T. Roughgarden,
  ``Selfish Routing and the Price of Anarchy'',
  OPTIMA, 2006, to appear.
• G. Valiant and T. Roughgarden,
  ``Braess's Paradox in Large Random Graphs'',
  7th Annual ACM Conference on Electronic Commerce (EC), 2006, to appear.
• R. Cole, Y. Dodis, and T. Roughgarden,
  ``Bottleneck Links, Variable Demand, and the Tragedy of the Commons'',
  17th Annual Symposium on Discrete Algorithms (SODA), pages 668--677, 2006.
• M. Haviv and T. Roughgarden,
  ``The Price of Anarchy: The Case of an Exponential Multi-Server'',
  submitted to Naval Research Logistics, 2006.
•  H. Chen and T. Roughgarden,
  ``Network Design with Weighted Players'',
  18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006, to appear.
• T. Roughgarden,
  ``Potential Functions and the Inefficiency of Equilibria'',
  Proceedings of the International Congress of Mathematicians, 2006, to appear.
• S. Chawla and T. Roughgarden,
  ``Single-Source Stochastic Routing'',
  submitted to the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2006.
• M. Saha, G. Sanchez-Ante, T. Roughgarden, and J.C. Latombe,
  ``Planning Tours of Robotic Arms Among Partitioned Goals'',
  International Journal of Robotics Research, 25(3):207--223, March 1 2006.
• M. Backes, I. Cervesato, A.D. Jaggard, A. Scedrov, and J.-K. Tsay.
  Cryptographically Sound Security Proofs for Basic and Public-Key Kerberos.
  In: D. Gollmann and A. Sabelfeld, eds., "11-th European Symposium On Research In Computer Security (ESORICS 2006)", Hamburg, Germany, September 2006. Springer LNCS, to appear.
• Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira,
  "Incentive-Compatible Interdomain Routing",
  in Proceedings of ACM Conference on Electronic Commerce, Ann Arbor MI, June 2006, pp 130-139. [pdf]
• I. Cervesato, A.D. Jaggard, A. Scedrov, J.-K. Tsay, and C. Walstad. "Breaking and fixing public-key Kerberos". [.pdf]. Revised version in: D. Gollmann and J. Juerjens, eds., International Workshop on Issues in the Theory of Security (WITS '06), Vienna, Austria, March 2006.
• M. Backes, B. Pfitzmann, and A. Scedrov. "Key-dependent Message Security under Active Attacks". Cryptology ePrint Archive: Report 2005/421.
• A. Datta, A. Derek, J.C. Mitchell, A. Ramanathan, and A. Scedrov. "Games and the Impossibility of Realizable Ideal Functionality". In: S. Halevi and T. Rabin, eds., " 3-rd Theory of Cryptography Conference (TCC 2006)", New York, NY, March 2006. Springer LNCS Volume 3876, Springer-Verlag, 2006, pp. 360-379. Revised version in Cryptology ePrint Archive: Report 2005/211.
• J.C. Mitchell, A. Ramanathan, A. Scedrov, and V. Teague. "A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols". Theoretical Computer Science, accepted for publication. [.pdf] [.ps] [.ps.gz]
• Onur Kardes, Raphael S. Ryger and Rebecca N. Wright
  "Implementing Privacy-Preserving Bayesian-Net Discovery for Vertically Partitioned Data",
  to appear in Proceedings of the ICDM Workshop on Privacy and Security Aspects of Data Mining, Houston TX, Nov 2005. [pdf]
• Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
  "Computation in a Distributed Information Market",
  Theoretical Computer Science, 343(2005), pp.114-132. [.pdf]
• Felipe Saint-Jean.
  "Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol".
  Yale University Technical Report YALEU/DCS/TR-1333, July 2005. [.pdf]
• P. Adão, G. Bana, J. Herzog, and A. Scedrov.
  "Soundness of formal encryption in the presence of key-cycles".
  In: S. De Capitani di Vimercati and P. Syverson, eds., "10-th European Symposium on Research in Computer Security (ESORICS 2005)", Milan, Italy, September 2005. Springer LNCS, to appear. [.pdf] [.ps] [.ps.gz]
• P. Adão, G. Bana, and A. Scedrov.
  "Computational and information-theoretic soundness and completeness of formal encryption".
  In: J. Guttman, ed., "18-th IEEE Computer Security Foundations Workshop (CSFW)", Aix-en-Provence, France, June 2005. IEEE Computer Society Press, 2005. [.pdf] [.ps] [.ps.gz]
• I. Cervesato, A. Jaggard, A. Scedrov, and C. Walstad.
  "Specifying Kerberos 5 cross-realm authentication".
  In: C. Meadows, ed., "Proceedings of the 2005 workshop on Issues in the theory of security (WITS'05)", Long Beach, California, January 2005, ACM Digital Library, ACM Press, New York, 2005, pp. 12-26. [.pdf]
• Jian Zhang, Jennifer Rexford, and Joan Feigenbaum,
  "Learning-Based Anomaly Detection in BGP Updates",
  Yale University Technical Report YALEU/DCS/TR-1318, April 2005. [pdf]
• D. Bergemann, T. Eisenbach, J. Feigenbaum, S. Shenker.
  "Flexibility as an Instrument in Digital Rights Management".
  4th Annual Workshop on Economics of Information Security, Cambridge MA, June 2005. [pdf]
• Andrew C. Myers, Andrei Sabelfeld, and Steve Zdancewic.
  "Enforcing Robust Declassification''.
  In Proc. of 17th IEEE Computer Security Foundations Workshop, pages 172-186, Asilomar, CA, June 2004. IEEE Computer Society Press.
• Stephen Tse and Steve Zdancewic.
  "Run-time Principals in Information-flow Type Systems''.
  In IEEE 2004 Symposium on Security and Privacy. IEEE Computer Society Press, May 2004.
• Andrew C. Myers, Andrei Sabelfeld, and Steve Zdancewic.
  Enforcing Robust Declassification and Qualified Robustness.
  Journal of Computer Security, 2006.
• Stephen Tse and Steve Zdancewic.
  Run-time principals in information-flow type systems.
  Transactions on Programming Languages and Systems, 2006. To appear.
• Nikhil Swamy, Michael Hicks, Stephen Tse, and Steve Zdancewic.
  Managing Policy Updates in Security-Typed Languages.
  In Proc. of 19th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, 2006.
• Rajeev Alur, Pavol Cerny, and Steve Zdancewic.
  Preserving Secrecy under Refinement.
  In Proc. of 33rd International Colloquium on Automata, Languages and Programming, 2006.
• Michael Hicks, Stephen Tse, Boniface Hicks, and Steve Zdancewic.
  Dynamic updating of information-flow policies.
  In Proc. of Foundations of Computer Security Workshop, 2005.
• Stephen Tse and Steve Zdancewic.
  Designing a Security-typed Language with Certificate-based Declassification.
  In Proc. of the 14th European Symposium on Programming, 2005.
  
• Peng Li and Steve Zdancewic.
  "Downgrading Policies and Relaxed Noninterference''.
  In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Jan 2005.
• Peng Li and Steve Zdancewic.
  "Practical Information-flow Control in Web-based Information Systems".
  In Proceedings of the 18th IEEE Computer Security Foundation Workshop (CSFW), June 2005.
• Peng Li and Steve Zdancewic.
  "Unifying Confidentiality and Integrity in Downgrading Policies".
  In Proceedings of the LICS'05 Affiliated Workshop on Foundations of Computer Security (FCS), June 2005.
• Peng Li and Steve Zdancewic.
  "Encoding Information Flow In Haskell",
  In Proceedings of the 19th IEEE Computer Security Foundation Workshop (CSFW), July 2006.
  
• Joan Feigenbaum, Benny Pinkas, Raphael Ryger, and Felipe Saint-Jean.
  "Secure Computation of Surveys''.
  EU Workshop on Secure Multiparty Protocols, Amsterdam, The Netherlands, October 2004. [pdf]
• Joseph Y. Halpern and Vanessa Teague,
  "Rational secret sharing and multiparty computation''
  Proceedings of 36th ACM Symposium on Theory of Computing, 2004, pp. 623-632. [pdf]
• Magnus M. Halldorsson, Joseph Y. Halpern, Li Li, and Vahab Mirrokni,
  "On spectrum sharing games''
  In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, 2004, pp. 107-114. [pdf]
• Riccardo Pucella, Vicky Weissman,
  "Reasoning about Dynamic Policies'',
  FOSSACS-04 (Proceedings of the Sixth International Conference on Foundations of Software Science and Computation Structure), 2004, pp. 453-467 [pdf]
• Carl Lagoze, Vicky Weissman,
  "Towards a policy language for humans and computers''
  ECDL-04 (Proceedings of the Eighth European Conference on Digital Libraries), 2004, pp. 513-525 [pdf]