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.
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
[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
- 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
[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
[BCLY08] Vicente Benjumea, Seung Geol Choi, Javier Lopez, and Moti Yung.
Fair Traceable Multi-Group Signatures. Financial Cryptography 2008.
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
- 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
[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
[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