Alcatel-Lucent > Bell Labs > Enabling Computing Technologies >

Bell Labs
[Vlad Kolesnikov]

Vladimir Kolesnikov

MTS - Cryptography and Security Research
Computing and Software Principles Research
Bell Labs, Alcatel-Lucent
600 Mountain Ave., 2A-404
Murray Hill, NJ 07974, USA
Email: #### at research.bell-labs.com, replacing hashes with kolesnikov


About
Publications
CV
Bio
This page contains only service and publications (mostly with live links). For everything else in detail see CV.

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)

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 supported by Smart Grid research, Bell Labs–GERI (Gachon Energy Research Institute, Korea), Sep 2009-Dec 2011.

Service:

PC member of

Patents:

  • 7 patents granted, over 30 patents pending. All patents related to cryptography, security and networking.

Book Chapters:

  1. 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.

Selected Publications -- Cryptography:

(Includes both conference and journal articles. Chronological order).
  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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.

  6. Vladimir Kolesnikov and Thomas Schneider, Improved Garbled Circuit: Free XOR Gates and Applications. In International Colloquium on Automata, Languages and Programming (ICALP) 2008.

  7. 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.

  8. Ian F. Blake and Vladimir Kolesnikov, One-round secure comparison of integers. In Journal of Mathematical Cryptography, Vol 3, Issue 1, May 2009.

  9. Vladimir Kolesnikov, Advances and impact of secure function evaluation. In Bell Labs Technical Journal (BLTJ), 14(3): 187-192 (2009).

  10. 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.

  11. 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.

  12. 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.

  13. Shlomi Dolev, Juan Garay, Niv Gilboa and Vladimir Kolesnikov, Swarming Secrets. In In 47th Annual Allerton Conference 2009.

  14. 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.

  15. 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),.

  16. Vladimir Kolesnikov, Truly Efficient String Oblivious Transfer Using Resettable Tamper-Proof Tokens (Preliminary full version). In Theory of Cryptography Conference (TCC) 2010. Presentation slides.

  17. 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.

  18. 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.

  19. 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.

  20. 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.

  21. Vladimir Kolesnikov, Ganapathy Sundaram, IBAKE: Identity-Based Authenticated Key Exchange Protocol. In IACR Cryptology ePrint Archive 2011: 612 (2011).

  22. 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

  23. Vladimir Kolesnikov, MAC Aggregation with Message Multiplicity. In 8th Conference on Security and Cryptography for Networks (SCN), 2012

  24. 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

  25. 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

  26. 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.

  27. 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

  28. 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

  29. Vladimir Kolesnikov and Ranjit Kumaresan, Improved OT Extension for Transferring Short Secrets. In CRYPTO 2013, 2013

Selected Publications -- Security:

(Includes both conference and journal articles. Reverse chronological order)
  1. Young Jin Kim, Vladimir Kolesnikov, Marina Thottan. TSAF: Tamper-resistant and Scalable Mutual Authentication Framework for Plug-in EV Charging. To appear in IEEE SmartGridComm 2013.

  2. Young Jin Kim, Vladimir Kolesnikov, Marina Thottan. Resilient End-to-End Message Protection for Large-scale Cyber-Physical System Communications. In IEEE SmartGridComm 2012.

  3. Vladimir Kolesnikov, Abdullatif Shikfa, On the limits of Privacy Provided by Order-Preserving Encryption. In Bell Labs Technical Journal (BLTJ), 2012.

  4. Vladimir Kolesnikov, Wonsuck Lee, MAC Aggregation Resilient to DoS Attacks. In International Journal of Security and Networks (IJSN), 2012.

  5. Vladimir Kolesnikov, Wonsuck Lee, and Junhee Hong, MAC Aggregation Resilient to DoS Attacks. In IEEE SmartGridComm 2011, 2011.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.) :