Ph.D. University of Toronto 2006, Computer Science
Vladimir Y Kolesnikov
Murray Hill, NJ, USA
Member of Technical Staff
One-line Bio: I received Ph.D. from the Department of Computer Science at the University of Toronto. I am now a researcher at Bell Labs.
My advisors were Ian F. Blake and Charles Rackoff.
My research was (and is) in formal cryptography and systems security. My thesis is titled "Secure Two-Party Computation and Communication."
Brief Bio: Vladimir Kolesnikov is a Member of Technical Staff in Bell Labs in Murray Hill, NJ. He received his Ph.D. in Computer Science from the University of Toronto in 2006. His research interests include key exchange, secure multiparty computation, foundations of cryptography and network security. His work is connected to the practice of cryptography. He has worked on private databases, securing channels in Smart Grid and WiMAX, biometric authentication, digital rights management, and a variety of other subjects.
Vladimir published his work in top cryptographic and security conferences and journals. He has served on program committees of several international cryptography conferences and supervised several summer interns at Bell Labs. He is an editor of the WiMAX "Server Certificate Profile" and "Device Certificate Profile" standards documents. Part of his work was supported by IARPA and Korea’s Gachon Energy Research Institute.
Personal: judo (4.5 yrs), soccer(football) (since age 4), chess (10 yrs).
Honors and Awards
Funding: PI (with Steven Bellovin, Angelos Keromytis and Tal Malkin, all at Columbia University) on IARPA SPAR program.
Project page: BLIND SEER: BLoom INDex SEarch of Encrypted Results.
Award amount $2.23M. Funding Sept 2011 - March 2015.
Update: Phase II funding granted (Apr 2013-March 2014)
Update: Phase II extension funded granted (April 2014-June 2014)
Award win announced on ONR project on secure channels. I am PI, with co-PIs Hugo Krawczyk and Tal Rabin, both at IBM Research.
Award amount $1M. Funding 2013 - 2015.
50% of my time was supported by Smart Grid research, Bell Labs–GERI (Gachon Energy Research Institute, Korea), Sep 2009-Dec 2011.
Service: PC member of
- The 17th IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2014)
- The 2nd ACM Workshop on Information Hiding and Multimedia Security(IH & MMSEC) 2014
- Workshop on Applied Homomorphic Cryptography 2014
- Workshop on Applied Homomorphic Cryptography 2013
- Second International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2012)
- Third IEEE Int'l Conference on Smart Grid Communications (SmartGridComm 2012) (Cyber Security and Privacy Symposium)
- Ninth International Conference on Cryptology And Network Security (CANS 2010)
- 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2010)
- The Eighth International Conference on Cryptology And Network Security (CANS 2009)
- International Conference on Information Security and Cryptology (Inscrypt 2007)
Selected Articles and Publications
Selected Publications -- Cryptography: (Includes both conference and journal articles. Chronological order).
- Ian F. Blake and Vladimir Kolesnikov, Strong Conditional Oblivious Transfer and Computing on Intervals. In proceedings of Advances in Cryptology - ASIACRYPT 2004. (Acceptance rate 17.3%.) Copyright IACR 2004. Presentation slides.
- Vladimir Kolesnikov, Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation. In proceedings of Advances in Cryptology - ASIACRYPT 2005. (Acceptance rate 15.8%.) Copyright IACR 2005. Presentation slides, (with embedded fonts).
- Vladimir Kolesnikov and Charles Rackoff, Key Exchange Using Passwords and Long Keys (preliminary full version). Shorter version appears in Theory of Cryptography Conference (TCC) 2006. Copyright IACR 2006. Presentation slides.
- Ian F. Blake and Vladimir Kolesnikov, Conditional Encrypted Mapping and Comparing Encrypted Numbers. In Financial Cryptography 2006. (Acceptance rate 19.8% for technical papers.) Copyright International Financial Cryptography Association 2006. Presentation slides.
- Vladimir Kolesnikov and Thomas Schneider, A Practical Universal Circuit Construction and Secure Evaluation of Private Functions (preliminary version). In Financial Cryptography 2008. (Acceptance rate 19.1% for technical papers.) Presentation slides. More information, including our implementation in the Fairplay framework is here.
- Vladimir Kolesnikov and Thomas Schneider, Improved Garbled Circuit: Free XOR Gates and Applications. In International Colloquium on Automata, Languages and Programming (ICALP) 2008.
- Vladimir Kolesnikov and Charles Rackoff, Password Mistyping in Two-Factor-Authenticated Key Exchange (Preliminary full version). In International Colloquium on Automata, Languages and Programming (ICALP) 2008. Presentation slides.
- Ian F. Blake and Vladimir Kolesnikov, One-round secure comparison of integers. In Journal of Mathematical Cryptography, Vol 3, Issue 1, May 2009.
- Vladimir Kolesnikov, Advances and impact of secure function evaluation. In Bell Labs Technical Journal (BLTJ), 14(3): 187-192 (2009).
- Juan Garay, Vladimir Kolesnikov and Rae McLellan, MAC Precomputation with Applications to Secure Memory (Preliminary full version). In ISC09 - Information Security Conference 2009. Presentation slides.
- Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi and Thomas Schneider, Secure Evaluation of Private Linear Branching Programs with Medical Applications. (Preliminary full version). In European Symposium on Research in Computer Security (ESORICS) 2009. Presentation slides.
- Vladimir Kolesnikov, Ahmad-Reza Sadeghi and Thomas Schneider, Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima. (Preliminary full version). In Computer and Network Security (CANS) 2009. Presentation slides.
- Shlomi Dolev, Juan Garay, Niv Gilboa and Vladimir Kolesnikov, Swarming Secrets. In In 47th Annual Allerton Conference 2009.
- Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider, Efficient privacy-preserving classification of ECG signals In 1st IEEE International Workshop on Information Forensics and Security (IEEE WIFS), 2009.
- Kimmo Jarvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, Thomas Schneider, Embedded SFE: Offloading Server and Network using Hardware Tokens (Preliminary full version). In 14th International Conference on Financial Cryptography and Data Security (FC'10),.
- Vladimir Kolesnikov, Truly Efficient String Oblivious Transfer Using Resettable Tamper-Proof Tokens (Preliminary full version). In Theory of Cryptography Conference (TCC) 2010. Presentation slides.
- Kimmo Jarvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider, Garbled Circuits for Leakage-Resilience: Hardware Implementation and Evaluation of One-Time Programs (Preliminary full version, also on ePrint). In Workshop on Cryptographic Hardware and Embedded Systems 2010 (CHES 2010). Presentation slides.
- Vladimir Kolesnikov, A Security Enhancement and Proof for Authentication and Key Agreement (AKA) (Preliminary full version, also on ePrint). In 7th Conference on Security and Cryptography for Networks (SCN) 2010. Presentation slides.
- Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov, Brief Announcement: Swarming Secrets. In Twenty-Ninth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) 2010. Presentation slides.
- Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov, Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation. In The Second Symposium on Innovations in Computer Science (ICS 2011). Presentation slides.
- Vladimir Kolesnikov, Ganapathy Sundaram, IBAKE: Identity-Based Authenticated Key Exchange Protocol. In IACR Cryptology ePrint Archive 2011: 612 (2011).
- Vladimir Kolesnikov and Ranjit Kumaresan, Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. In 8th Conference on Security and Cryptography for Networks (SCN), 2012
- Vladimir Kolesnikov, MAC Aggregation with Message Multiplicity. In 8th Conference on Security and Cryptography for Networks (SCN), 2012
- Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis, Secure Two-Party Computation in (Sublinear) Amortized Time. In 19th ACM Conference on Computer and Communications Security (CCS), 2012
- Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov, Yelena Yuditsky. Brief Announcement: Efficient Distributed Private Computation on Unbounded Input Streams. In The 26th International Symposium on DIStributed Computing (DISC) 2012, 2012
- Vladimir Kolesnikov, Ranjit Kumaresan, and Abdullatif Shikfa. Efficient Verification of Input Consistency in Server-Assisted Secure Function Evaluation. In Computer and Network Security (CANS) 2012.
- Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider A systematic approach to practically efficient general two-party secure function evaluation protocols and their modular design. In Journal of Computer Security (JCS), 21(2): 283-315 2012
- Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov and Yelena Yuditsky. Towards Efficient Private Distributed Computation on Unbounded Input Streams. In 11th International Conference on Applied Cryptography and Network Security (ACNS' 13), 2013
- Vladimir Kolesnikov and Ranjit Kumaresan, Improved OT Extension for Transferring Short Secrets. In CRYPTO 2013, 2013
- Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos Keromytis, Steve Bellovin. Blind Seer: A Scalable Private DBMS. To appear in IEEE Symposium on Security and Privacy (Oakland) 2014
Selected Publications -- Security: (Includes both conference and journal articles. Reverse chronological order)
- Young Jin Kim, Vladimir Kolesnikov, Marina Thottan. TSAF: Tamper-resistant and Scalable Mutual Authentication Framework for Plug-in EV Charging. In IEEE SmartGridComm 2013.
- Young Jin Kim, Vladimir Kolesnikov, Marina Thottan. Resilient End-to-End Message Protection for Large-scale Cyber-Physical System Communications. In IEEE SmartGridComm 2012.
- Vladimir Kolesnikov, Abdullatif Shikfa, On the limits of Privacy Provided by Order-Preserving Encryption. In Bell Labs Technical Journal (BLTJ), 2012.
- Vladimir Kolesnikov, Wonsuck Lee, MAC Aggregation Resilient to DoS Attacks. In International Journal of Security and Networks (IJSN), 2012.
- Vladimir Kolesnikov, Wonsuck Lee, and Junhee Hong, MAC Aggregation Resilient to DoS Attacks. In IEEE SmartGridComm 2011, 2011.
- Young-Jin Kim, Vladimir Kolesnikov, Hongseok Kim, and Marina Thottan, SSTP: a Scalable and Secure Transport Protocol for Smart Grid Data Collection. In IEEE SmartGridComm 2011, 2011.
- Vijay Gurbani and Vladimir Kolesnikov, A Survey and Analysis of Media Keying Techniques in the Session Initiation Protocol (SIP). In proceedings of IEEE Communications Surveys and Tutorials. In Second issue 2011.
- Georg Hampel and Vladimir Kolesnikov, Securing Host-based Mobility and Multi-homing Protocols Against on-path Attackers. In Journal of Communications (JCM) Special Issue on Seamless Mobility in Wireless Networks, January 2011.
- Vijay Gurbani and Vladimir Kolesnikov, Work in Progress: A secure and lightweight scheme for media keying in the Session Initiation Protocol (SIP). In proceedings of IPTComm 2010: Principles, Systems and Applications of IP Telecommunications, 2010.
- Young-Jin Kim, Marina Thottan, Vladimir Kolesnikov, Wonsuck Lee, Decentralized and Data-centric Information Infrastructure for Next-Generation Smart Grid. In IEEE Communications Magazine Feature Topic Issue on Green Communications, 2010.
- Ken Budka, Jayant Deshpande, John Hobby, Young-Jin Kim, Vladmir Kolesnikov, Wonsuck Lee, Marina Thottan , Thomas Reddington, Chris A. White, Jung-In. Choi, Junhee Hong, Jinho Kim, Wonsuk Ko, Young-Woo Nam, Sung-Yong Sohn, GERI – Bell Labs Smart Grid Research Focus: Economic Modeling, Networking, and Security and Privacy. In IEEE SmartGridComm 2010, 2010.
- Georg Hampel and Vladimir Kolesnikov, Lightweight Security Solution for Host-Based Mobility & Multi-Homing Protocols. In IEEE Globecom 2010 Workshop on Seamless Wireless Mobility (SWiM 2010), 2010.
Note: some of the above slides use TexPoint. Ph.D. Thesis (official version, June 30, 2006): The thesis contains results reported in the above top four papers.
Official double spaced version: ps pdf. Convenient single spaced version: ps, pdf. M.Sc. Thesis: My M.Sc. thesis deals with heuristic reductions from knapsack problem to the problem of finding short vectors in integer lattices. The latter is efficiently solved by the Lenstra, Lenstra and Lovasz algorithm. A good reduction results in better ways of solving knapsack. Look at the short summary (ps, pdf) (better written), or full thesis (ps) (a bit messier).
The following publications are not available online due to Non-Disclosure Agreements.
Non-refereed publications (Technical Reports, etc.) :
- Biometric Key Binding. Technical report sponsored by Bioscrypt, Inc. and Canadian National Research Council's Industrial Research Assistance Program (NRC-IRAP). With Omid Jahromi, Rene McIver, Colin Soutar and Alex Stoianov, 2005
- Binding Strong Keys to Fingerprints Securely and Privately. Technical Report, Bioscrypt, Inc., 2005
- Distributed Security Architecture For Storage Area Networks (SAN). International patent application, with Dr. Kumar Murty and Daniel Thanos, Kasten Chase, Inc., 2003
- Efficient Storage Security. Technical Report, Kasten Chase, Inc., 2001
- Efficient Broadcast Encryption. Technical Report, Kasten Chase, Inc., 2001
Books and Chapters
- K. Järvinen, V. Kolesnikov, A.-R. Sadeghi, and T. Schneider, Efficient secure two-party computation with untrusted hardware tokens. In Towards Hardware Intrinsic Security: Foundation and Practice (A.-R. Sadeghi, ed.), Information Security & Cryptography, Springer, Heidelberg, Germany, 2010.
10 patents granted, over 30 patents pending. All patents related to cryptography, security and networking.