Bell Labs

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.

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

• 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)

Patents:

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

Selected Publications -- Cryptography:

• 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, Vol 14, Issue 3, p. 187, Fall 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, Ahmad-Reza Sadeghi, and Thomas Schneider, Modular Design of Practically Efficient General Two-Party Secure Function Evaluation Protocols . To appear in Journal of Computer Security (JCS), 2012


• Vladimir Kolesnikov, MAC Aggregation with Message Multiplicity. To appear in 8th Conference on Security and Cryptography for Networks (SCN), 2012


• Vladimir Kolesnikov and Ranjit Kumaresan, Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. To appear 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. To appear 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 . To appear in The 26th International Symposium on DIStributed Computing (DISC) 2012, 2012

Selected Publications -- Security:

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


• Vladimir Kolesnikov, Wonsuck Lee, MAC Aggregation Resilient to DoS Attacks. To appear 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.


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

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

---