Vitaly Shmatikov

Research interests: computer security and privacy, formal methods for analysis of secure systems and network protocols

Teaching   -   Students   -   Papers   -   Fly!   -   Pictures   -   Contact

---

Teaching

• CS 380S - Theory and Practice of Secure Systems (Fall '09,'08,'06,'05)
• CS 378 - Network Security and Privacy (Spring '09, Fall '07, Spring '07, '06, '05)
• CS 178H - Introduction to CS Research-Honors (Spring '09)
• CS 345 - Programming Languages (Spring '08)
• CS 395T - Design and Analysis of Security Protocols (Fall '04)
• Security Analysis of Network Protocols (Stanford, Winter '04)

---

Students

• Arvind Narayanan (PhD, May 2009)
  Thesis: Database Privacy: the Non-Interactive Setting
• Justin Brickell (PhD, May 2009)
  Thesis: Privacy-Preserving Computation for Data Mining

---

Research papers   (see in reverse chronological order)

Network security

• E. Wong, V. Shmatikov. Get Off My Prefix! Using Gerontocratic Policies to Improve the Security and Stability of Internet Routing. UT Austin TR-09-15.   [abstract]
• R. Chang, G. Jiang, F. Ivančić, S. Sankaranarayanan, V. Shmatikov. Inputs of Coma: Static Detection of Denial-of-Service Vulnerabilities. CSF 2009.   [abstract]
• V. Shmatikov, M-H. Wang. Secure Verification of Location Claims with Simultaneous Distance Modification. ASIAN 2007.   [abstract, PDF, PS]
• V. Shmatikov, M-H. Wang. Security Against Probe-Response Attacks in Collaborative Intrusion Detection. LSAD 2007.   [abstract, PDF, PS]
• E. Wong, P. Balasubramanian, L. Alvisi, M. Gouda, V. Shmatikov. Truth in Advertising: Lightweight Verification of Route Integrity. PODC 2007.   [abstract]
• P. Gupta, V. Shmatikov. Security Analysis of Voice-over-IP Protocols. CSF 2007.   [abstract, PDF, PS]
• A. Mahimkar, J. Dange, V. Shmatikov, H. Vin, Y. Zhang. dFence: Transparent Network-based Denial of Service Mitigation. NSDI 2007.   [abstract, PDF, PS]

Privacy

• A. Narayanan, V. Shmatikov. De-anonymizing Social Networks (full version). S&P 2009.   [abstract, PDF, PS]
  
  • FAQ about this paper.
  • Media: BBC, Technology Review, New Scientist, InformationWeek, PC World (via IDG News), Austin Business Journal.
  • Blogs, etc.: Slashdot, Ars Technica, Schneier, Online Media Daily, Behavioral Insider, BizReport.
  • Foreign media: De Telegraaf, 20 Minuten, Die Presse, ma.hu, OSnews.pl, Gryziemy.net, Вебпланета, RBC Daily.
• J. Brickell, V. Shmatikov. Privacy-Preserving Classifier Learning. Financial Crypto 2009.   [abstract]
• J. Brickell, V. Shmatikov. The Cost of Privacy: Destruction of Data-Mining Utility in Anonymized Data Publishing. KDD 2008.   [abstract]
• A. Narayanan, V. Shmatikov. Robust De-anonymization of Large Sparse Datasets (How to Break Anonymity of the Netflix Prize Dataset). S&P 2008.   [abstract, PDF, PS]
  
  • FAQ about this paper.
  • Winner of the 2008 PET Award (press release).
  • Media: Slashdot, Wired, SecurityFocus, Spiegel, New Scientist.
• S. Jha, L. Kruger, and V. Shmatikov. Towards Practical Privacy for Genomic Computation. S&P 2008.   [abstract, PDF, PS]
• J. Brickell, D. Porter, V. Shmatikov, E. Witchel. Privacy-Preserving Remote Diagnostics. CCS 2007.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Efficient Two-Party Secure Computation on Committed Inputs. EUROCRYPT 2007.   [abstract]
• J. Brickell, V. Shmatikov. Efficient Anonymity-Preserving Data Collection. KDD 2006.   [abstract]
• P. Porras, V. Shmatikov. Large-Scale Collection and Sanitization of Network Security Data: Risks and Challenges. NSPW 2006.   [abstract, PDF, PS]
• A. Narayanan, V. Shmatikov. Obfuscated Databases and Group Privacy. CCS 2005.   [abstract, PDF, PS]
• J. Brickell, V. Shmatikov. Privacy-Preserving Graph Algorithms in the Semi-Honest Model. ASIACRYPT 2005.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Probabilistic Escrow of Financial Transactions with Cumulative Threshold Disclosure. Financial Crypto 2005.   [abstract, PDF, PS]
• P. Lincoln, P. Porras, V. Shmatikov. Privacy-Preserving Sharing and Correlation of Security Alerts. USENIX Security 2004.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Handcuffing Big Brother: an Abuse-Resilient Transaction Escrow Scheme. EUROCRYPT 2004.   [abstract, PDF, PS]
• D. Hughes, V. Shmatikov. Information Hiding, Anonymity and Privacy: A Modular Approach. J. Computer Security, 2004.   [abstract, PDF, PS]
  This paper was also presented at MFPS 2003 and supercedes:
  • V. Shmatikov, D. Hughes. Defining Anonymity and Privacy. WITS 2002.
• S. Jarecki, P. Lincoln, V. Shmatikov. Negotiated Privacy. ISSS 2002.   [abstract, PDF, PS]

      Mix networks:

• V. Shmatikov, M-H. Wang. Measuring Relationship Anonymity in Mix Networks. WPES 2006.   [abstract, PDF, PS]
• V. Shmatikov, M-H. Wang. Timing Analysis in Low-Latency Mix Networks: Attacks and Defenses. ESORICS 2006.   [abstract, PDF, PS]
• R. Dingledine, V. Shmatikov, P. Syverson. Synchronous Batching: From Cascades to Free Routes. PET 2004.   [abstract, PDF, PS]

Password cracking

• A. Narayanan, V. Shmatikov. Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff. CCS 2005.   [abstract, PDF, PS]

Formal methods for security protocols
    case studies:

• R. Chang, V. Shmatikov. Formal Analysis of Authentication in Bluetooth Device Pairing. FCS-ARSPA 2007.   [abstract]

    computationally sound:

• P. Gupta, V. Shmatikov. Key Confirmation and Adaptive Corruptions in the Protocol Security Logic. FCS-ARSPA 2006.   [abstract, PDF, PS, full version]
• P. Gupta, V. Shmatikov. Towards Computationally Sound Symbolic Analysis of Key Exchange Protocols. FMSE 2005.   [abstract, PDF, PS, full version with proofs]
• A. Datta, A. Derek, J.C. Mitchell, V. Shmatikov, M. Turuani. Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. ICALP 2005.   [abstract, PDF, PS]
• A. Datta, R. Küsters, J.C. Mitchell, A. Ramanathan, V. Shmatikov. Unifying Equivalence-Based Definitions of Protocol Security. WITS 2004.   [abstract, PDF, PS]

    probabilistic:

• G. Norman, V. Shmatikov. Analysis of Probabilistic Contract Signing. J. Computer Security, 2006.   [abstract, PDF, PS]
  This paper supercedes:
  • G. Norman, V. Shmatikov. Analysis of Probabilistic Contract Signing. FASec 2002.
• V. Shmatikov. Probabilistic Model Checking of an Anonymity System. J. Computer Security, 2004.   [abstract, PDF, PS]
  This paper supercedes:
  • V. Shmatikov. Probabilistic Analysis of Anonymity. CSFW 2002.

    game-based:

• A. Mahimkar, V. Shmatikov. Game-Based Analysis of Denial-of-Service Prevention Protocols. CSFW 2005.   [abstract, PDF, PS]
  The paper in the CSFW proceedings contains a bug in the verification conditions. This is the corrected version.
• R. Chadha, J.C. Mitchell, A. Scedrov, V. Shmatikov. Contract Signing, Optimism, and Advantage. CONCUR 2003.   [abstract, PDF, PS]
  Revised journal version containing all proofs:
  • R. Chadha, J.C. Mitchell, A. Scedrov, V. Shmatikov. Contract Signing, Optimism, and Advantage (with proofs). J. Logic and Algebraic Programming, 2005.

    decidable infinite-state:

• J. Millen, V. Shmatikov. Symbolic Protocol Analysis with an Abelian Group Operator or Diffie-Hellman Exponentiation. J. Computer Security, 2005.   [abstract, PDF, PS]  
  Warning: Contains serious bugs in the proofs; corrections coming eventually.
  This paper supercedes:
  • J. Millen, V. Shmatikov. Symbolic Protocol Analysis with Products and Diffie-Hellman Exponentiation. CSFW 2003.
• V. Shmatikov. Decidable Analysis of Cryptographic Protocols with Products and Modular Exponentiation. ESOP 2004.   [abstract, PDF, PS]
• H. Comon-Lundh, V. Shmatikov. Intruder Deductions, Constraint Solving and Insecurity Decision in Presence of Exclusive or. LICS 2003.   [abstract, PDF, PS]
• H. Comon, V. Shmatikov. Is It Possible to Decide Whether a Cryptographic Protocol Is Secure Or Not?. J. Telecommunications and Information Technology, 2002.   [abstract, PDF, PS]
• J. Millen, V. Shmatikov. Constraint Solving for Bounded-Process Cryptographic Protocol Analysis. CCS 2001.   [abstract, PDF, PS]

    finite-state:

• V. Shmatikov, J.C. Mitchell. Finite-State Analysis of Two Contract Signing Protocols. Theoretical Computer Science, 2002.   [abstract, PDF, PS]
  This paper supercedes the following three papers:
  • V. Shmatikov, J.C. Mitchell. Analysis of Abuse-Free Contract Signing. Financial Crypto 2000.
  • V. Shmatikov, J.C. Mitchell. Analysis of a Fair Exchange Protocol. NDSS 2000.
  • V. Shmatikov, J.C. Mitchell. Analysis of a Fair Exchange Protocol. FLOC Workshop on Formal Methods and Security Protocols, 1999.
• V. Shmatikov, U. Stern. Efficient Finite-State Analysis for Large Security Protocols. CSFW 1998.   [abstract, PDF, PS]
• J.C. Mitchell, V. Shmatikov, U. Stern. Finite-State Analysis of SSL 3.0. USENIX Security 1998.   [abstract, PDF, PS]
  This paper supercedes:
  • J.C. Mitchell, V. Shmatikov, U. Stern. Finite-State Analysis of SSL 3.0 and Related Protocols. DIMACS Workshop on Design and Formal Verification of Security Protocols, 1997.

Trust management

• V. Shmatikov, C. Talcott. Reputation-Based Trust Management. J. Computer Security, 2005.   [abstract, PDF, PS]
  This paper supercedes:
  • V. Shmatikov, C. Talcott. Reputation-Based Trust Management. WITS 2003.

Foundations of programming languages

• V. Bono, A. Patel, V. Shmatikov. A Core Calculus of Classes and Mixins. ECOOP 1999.   [abstract, PDF, PS]
  
• V. Bono, A. Patel, V. Shmatikov, J.C. Mitchell. A Core Calculus of Classes and Objects. MFPS 1999.   [abstract, PDF, PS]
  

---

Contact information

Department of Computer Science
The University of Texas at Austin
1 University Station C0500
Austin, TX   78712   U.S.A.

email: first five letters of last name AT cs.utexas.edu
phone: +1-512-471-9530
office: TAY 4.115C

---

The face was drawn, the eyes haggard, the general appearance that of one who has searched for the leak in life's gaspipe with a lighted candle.
      -- P.G.Wodehouse, "The Old Reliable"