My research interests are in cryptography and security, with my main research focusing on the development of privacy-enhancing mechanisms. I am also interested in foundational questions in cryptography such as general feasibility results and relationships between cryptographic primitives. In the future, while remaining open to new opportunities, I expect to continue working on privacy-enhancing mechanisms; in particular, I find privacy issues related to cloud computing quite interesting.


Privacy-Enhancing Mechanisms
On the Internet, a huge number of privacy-sensitive transactions are being performed, e.g., financial transactions, medical transactions, and email transactions. Needless to say, the disclosure of these private pieces of information may inflict critical damage on the owners, and therefore it is imperative to develop mechanisms that guarantee privacy in various contexts. I have worked on privacy-enhancing mechanisms in various contexts, described next.

• Secure Multi-party Computation: secure MPC enables any number of parties to jointly evaluate an arbitrary function of their inputs while preserving security properties such as privacy and correctness. Its practical deployment has the potential to revolutionize fields from science (e.g., data mining without divulging personal information) to business (e.g., secure distributed auctions) to law enforcement (finding criminals without compromising privacy laws). Yet, until recently, secure MPC was of only theoretical interest as known protocols were prohibitively expensive. In the past few years, however, due to both theoretical progress and increased capability of modern computers, several generic solutions have been implemented which are applicable in some restricted scenarios. In my research, I have explored both practical and theoretical aspects of secure MPC.
  
  
  
  • MPC Implementation. In recent work, I showed the first implementation of a generic MPC protocol for boolean circuits, and the first to tolerate an arbitrary number of semi-honest corrupted parties. In addition, we applied our solution to the design of a distributed, privacy-preserving marketplace, which matches customers with providers in a way that optimizes some value under a certain set of constraints.
    
    [CHK+12] Seung Geol Choi, Kyung-Wook Hwang, Jonathan Katz, Tal Malkin, and Dan Rubenstein. Secure Multi-Party Computation of Boolean Circuits with Applications to Privacy in On-Line Marketplaces CT-RSA 2012. source code
    
    
  • Security Analysis of Practical MPC Technique. Kolesnikov and Schneider introduced the free-XOR approach for two-party computation which allows XOR gates in the underlying circuit to be evaluated for free, resulting in roughly a 40% efficiency improvement. I pinned down the appropriate security notion in the standard model, by showing that security holds if the underlying hash function satisfies what we call "circular correlation robustness".
    
    [CKKZ12] Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, and Hong-Sheng Zhou On the Security of the Free-XOR Technique. TCC 2012
    
    
  • I also explored various topics of MPC, including achieving UC security from tamper-proof hardware, efficient UC-secure constructions, and adaptively secure protocols.
  
  
• Private Database
  I am currently working on a research project to enhance privacy of database systems; the server should not know what the client's queries are, and the client should not know what the database records are except the ones from query results. What is interesting is that we aim at developing a solution with practical efficiency (with only 10 multiplicative factor performance degradation) and scalability (with 108records and 10 Terabytes).This immediately stops us from naively applying secure two-party computation protocols; it is too inefficient. Instead, we divide a search task into small problems (as in a binary search), and apply secure two-party computation to them. This way, we can obtain a reasonable level of privacy, though not perfect, and practical efficiency and scalability as well.
  
  
  
• Anonymity and Reputation
  
  
  • Reputation Systems. Anonymity is a desirable attribute for users who participate in peer-to-peer system. A peer, representing himself via a pseudonym, is free from the burden of revealing his real identity when carrying out transactions with others. Complete anonymity, however, is not desirable for the good of the whole community: otherwise, an honest peer has no choice but to suffer from repeated misbehaviors (e.g., sending an infected file to others) by a malicious peer, which lead to no consequences in a perfectly pseudonymous world. Reputation systems can be regarded as a reasonable solution to the above problem. I formalized a security notion for reputation systems in the above setting, and also gave a secure construction. The main advantage of our scheme is that the reputation is bound not to pseudonyms but to the actual identity of a user. Therefore, our scheme allows an honest user to switch to a new pseudonym while keeping his good reputation, while preventing a malicious user from erasing his trail of misdeeds with a new pseudonym.
    
    
    
    [ACBM08] Elli Androulaki, Seung Geol Choi, Steven M. Bellovin, and Tal Malkin. Reputation Systems for Anonymous Networks. PETS 2008.
    
    
  • I also showed constructions for anonymous certificates and presented a framework that extends to PKI (X.509) and supports these certificates.
    
    [BCLY08] Vicente Benjumea, Seung Geol Choi, Javier Lopez, and Moti Yung. Fair Traceable Multi-Group Signatures. Financial Cryptography 2008.
    GNU Project for FTMGS
    [BCLY07] Vicente Benjumea, Seung Geol Choi, Javier Lopez, and Moti Yung. Anonymity 2.0 -- X.509 Extensions Supporting Privacy-Friendly Authentication. CANS 2007
    [CPY06] Seung Geol Choi, Kunsoo Park, and Moti Yung. Short Traceable Signatures Based on Bilinear Pairings IWSEC 2006.
    
    
  
  
• Outsourcing computation
  Cloud computing can provide computing and data-storage resources for end users with limited means. However, utilizing the benefits of the cloud service to the fullest extent requires several security properties to be ensured. Clients would like to verify that the computation of the cloud is correct. Moreover, it is critical that privacy of the data be maintained during the computation. Needless to say, verifiability and privacy should be achieved along with efficiency on the client side so as not to defeat the purpose of using the cloud service in the first place.
  
  
  
  Until now, researchers have focused on the single client case. There are, however, scenarios in which it would be desirable to extend this functionality to the multi-client setting, e.g., networks made up of several resource-constrained nodes (sensors) that collectively gather data to be used jointly as input to some computation. I showed a non-interactive multi-client outsourcing scheme.
  
  [CKKC13] Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, and Carlos Cid Multi-Client Non-Interactive Verifiable Computation 10th Theory of Cryptography Conference (TCC) 2013.

Foundations in Cryptography

• Black-box Constructions
  A non-malleable encryption scheme prevents an adversary from modifying an encrypted value in a predictable way. To see the usefulness of the primitive, imagine a sealed-bid auction where Company A places a bid of $100,000 by publishing an encryption c = E(100,000). If it is feasible to generate E(100,001) only from c, then Company B could make a big exactly $1 higher without every learning the bid of Company A. I showed the first black-box construction of a non-malleable encryption scheme from any standard encryption scheme. Black-box constructions are important because they are typically orders of magnitude more efficient than nonblack-box constructions. Indeed, most cryptographic constructions are black-box, and a large body of work has sought to understand the power and limitations of black-box techniques.
  
  [CDMW08]Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee. Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One. TCC 2008
  
  
• Round Efficiency and Adaptive Security in MPC
  Round complexity of a protocol is a critical measure of efficiency. In some of my early work [CEJ+07, CEMY09], I showed how single-round protocols for two-party and multi-party computation could be achieved in a setting where encryptions of inputs are published in advance. In another line of work [CDSM09a, CDMW09b] I considered a stronger (and more realistic) adversary that can adaptively determine who to corrupt during the course of the protocol. In that work we constructed an efficient MPC protocol with adaptive security, given the secure cryptographic primitives of commitment and semi-honest oblivious transfer.
  
  [CEJ+07] Seung Geol Choi, Ariel Elbaz, Ari Juels, Tal Malkin, and Moti Yung. Two-Party Computing with Encrypted Data Asiacrypt 2007
  [CEMY09] Seung Geol Choi, Ariel Elbaz, Tal Malkin and Moti Yung. Secure Multi-party Computation Minimizing Online Rounds Asiacrypt 2009
  [CDMW09a] Seung Geol Choi, Dana Dachman-Soled, Tal Malkin and Hoeteck Wee. Improved Non-Committing Encryption with Applications to Adaptively Secure Protocols Asiacrypt 2009
  [CDMW09b] Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee. Simple, Black-Box Constructions of Adaptively Secure Protocols. TCC 2009