[FoRK] Congrats to the '04 ACM Dissertation awardees!
khare at alumni.caltech.edu
Fri Mar 11 10:43:41 PST 2005
Very strong work they honored this year. From the looks of it, Barak's
is a classic victory of a new approach that unlocked lots of
consequential results, even if I can't immediately grasp all of its
practical implications. I'm sure that I have friends in crypto who can
do a better job of popularizing his work further. Also, it's pretty
impressive that out of the only two dissertations even the largest CS
departments are limited to nominating, both of MIT's were honored. One
of which already won the department's best dissertation award, in an
area I'm quite intrigued by, markets for networks. I'll have to read it
a lot more carefully before I speculate on its contributions. --Rohit
2004 winner (Springer will publish and $5K)
For his dissertation, Non-Black-Box Techniques in Cryptography,
nominated by the Weizmann Institute of Science.
For his dissertation, Efficiency Loss in Market Mechanisms for Resource
Allocation, nominated by the Massachusetts Institute of Technology.
For his dissertation, Mondriaan Memory Protection, nominated by the
Massachusetts Institute of Technology.
> 2004 ACM Doctoral Dissertation Award
-------------- next part --------------
> Boaz Barak, a postdoctoral researcher at the Institute for Advanced
> Study, conducted his doctoral dissertation work at the Weizmann
> Institute of Science in Israel, from which he received a Ph.D. in
> 2004. He earned his B.Sc. in Mathematics and Computer Science from Tel
> Aviv University. His current research is in foundations of
> cryptography and complexity theory. He will become an assistant
> professor in Princeton University's Computer Science Department this
> Honorable Mention for the ACM Doctoral Dissertation Award went to
> Ramesh Johari of Stanford University for his thesis "Efficiency Loss
> in Market Mechanism for Resource Allocation," and Emmett Witchel of
> the University of Texas, Austin for his thesis "Mondriaan Memory
> Protection." Both nominations were submitted by MIT.
> The Doctoral Dissertation Award is presented annually to the author
> of the best doctoral dissertation in computer science and engineering.
> The amount of the Doctoral Dissertation Award is $5,000. Financial
> support and the publication of the winning dissertation are provided
> by Springer-Verlag.
> ACM will present these and other awards at the annual ACM Awards
> Banquet on June 11, 2005, in San Francisco, CA.
> The American Heritage dictionary defines Black-Box as
> A device or theoretical construct with known or specified
> performance characteristics but unknown or unspecified constituents
> and means of operation.
> In the context of Computer Science, to use a program as a black-box
> means to use only its input/output relation by executing the program
> on chosen inputs, without examining the actual code (i.e.,
> representation as a sequence of symbols) of the program.
> Since learning properties of a program from its code is a notoriously
> hard problem, in most cases both in applied and theoretical computer
> science, only black-box techniques are used. In fact, there are
> specific cases in which it has been either proved (e.g., the Halting
> Problem) or is widely conjectured (e.g., the Satisfiability Problem)
> that there is no advantage for non-black-box techniques over black-box
> In this thesis, we consider several settings in cryptography, and ask
> whether there actually is an advantage in using non-black-box
> techniques over black-box techniques in these settings. Our answer is
> mainly positive. That is, we show that in several contexts in
> cryptography, there is a difference between the power of black-box and
> non-black-box techniques. Using non-black-box techniques we are able
> to solve some problems in cryptography that were previously unsolved.
> In fact, some of these problems were previously proven to be
> unsolvable using black-box techniques.
> The main results of this thesis are the following:
> ? Software Obfuscation: Informally speaking, an obfuscator is a
> compiler that takes a program P as input and produces a new program P'
> that has the same functionality as P, and yet is ``unintelligible'' in
> some sense. Ideally, a software obfuscator should ensure that the only
> information leaked about P from the program P', is information that
> can be derived by using only black-box access to P. Obfuscators, if
> they exist, would have a wide variety of cryptographic and
> complexity-theoretic applications, ranging from software protection to
> homomorphic encryption to complexity-theoretic analogues of Rice's
> In this thesis, we discuss how to formally define obfuscators, and
> whether or not such objects exist. Our main result in this context is
> that even very weak forms of obfuscators do not exist.
> ? Zero-Knowledge: The simulation paradigm, introduced by
> Goldwasser, Micali and Rackoff, has had fundamental impact on
> cryptography. A simulator is an algorithm that tries to simulate the
> interaction of the adversary with an honest party, without knowing the
> private input of this honest party. Loosely speaking, the existence of
> such a simulator demonstrates that the adversary did not gain any
> knowledge about the honest party's input.
> Almost all previously known simulators use the adversary's algorithm
> as a black-box. We present the first constructions of non-black-box
> simulators. Using these new non-black-box techniques we obtain several
> results that were previously shown to be impossible to obtain using
> black-box simulators.
> Specifically, assuming the existence of collision-resistant hash
> functions, we construct a new constant-round zero-knowledge argument
> system for NP that satisfies the following properties:
> ? It remains zero knowledge even when composed concurrently n
> times, where n is the security parameter.
> ? It is an Arthur-Merlin (public coins) protocol.
> ? It has a simulator that runs in strict polynomial time, rather
> than in expected polynomial time.
> It is impossible to obtain a constant-round zero-knowledge protocol
> satisfying either Property (a) or Property (b) using black-box
> simulation (Canetti et al., 2001), (Goldreich and Krawczyk, 1996). We
> show that it is also impossible to obtain a constant-round
> zero-knowledge protocol satisfying Property (c) using black-box
> We use this protocol to obtain other new results in cryptography.
> These include a construction of constant-round zero-knowledge proof of
> knowledge with a strict polynomial-time knowledge extractor, and a
> zero-knowledge resettably sound argument for NP. We show that both
> applications are impossible to obtain when restricted to black-box
> ? Non-Malleability: We construct the first constant round
> non-malleable commitment scheme and the first constant-round
> non-malleable zero-knowledge argument system, as defined by Dolev,
> Dwork and Naor. Previous constructions either used a non-constant
> number of rounds, or were only secure under stronger setup assumptions
> (such as the availability of a public string that was chosen at random
> and published by a trusted third party).
> We obtain this result by using a non-black-box proof of security.
> That is, our proof uses the code of the adversary in the security
> reduction. As an intermediate step we define and construct a
> constant-round non-malleable coin tossing protocol. This coin-tossing
> protocol may be of independent interest.
> To summarize, in this thesis we show that, somewhat unintuitively,
> non-black-box techniques sometimes have a significant advantage over
> black-box techniques in cryptography. From the point of view of
> cryptographers, this result has both negative and positive
> applications. On the one hand, it further stresses the point that it
> is unsafe to rely on the assumption that an adversary attacking our
> schemes will use only black-box techniques. On the other hand, it
> means that when designing and analyzing cryptographic schemes, we can
> use these non-black-box techniques to obtain useful and important
> security goals that cannot be obtained using black-box techniques.
> Submitted to the Feinberg Graduate School of the Weizmann Institute
> of Science, January 2004.
> Ph.D. Thesis
> Efficiency loss in market mechanisms for resource allocation. June
> Massachusetts Institute of Technology, Department of Electrical
> Engineering and Computer Science.
> Supervisor: John N. Tsitsiklis.
> 2004 George M. Sprowls Award for best doctoral dissertation in
> computer science at MIT. Available as PDF.
> Johari, R. and Tsitsiklis, J.N. (2004).? Efficiency loss in a Cournot
> mechanism for network resource allocation.
> ??? Submitted (July 2004).? Available as PDF.
> Johari, R., Mannor, S., and Tsitsiklis, J.N. (2004).? Efficiency loss
> in a network resource allocation game: the case of elastic supply.
> ??? Submitted (June 2004).? Available as PDF.
> ??? LIDS Publication 2605.? Available as PDF.
> Johari, R., and Tsitsiklis, J.N. (2004). Efficiency loss in a network
> resource allocation game.
> ??? First Place in the 2003 INFORMS George E. Nicholson Student Paper
> ??? Mathematics of Operations Research 29 (3): 407-435. Available as
> Johari, R., Mannor, S., and Tsitsiklis, J.N. (2003). A contract-based
> model for directed network formation.
> ??? Submitted (November 2003). Available as PDF.
> Johari, R., and Tsitsiklis, J.N. (2003). Routing and peering in a
> competitive Internet.
> ??? LIDS Publication 2570. Available as PDF.
> Johari, R., and Tan, D. (2001). End-to-end congestion control for the
> Internet: delays and stability.
> ??? IEEE/ACM Transactions on Networking 9 (6): 818-832. Available as
> Johari, R.? Game theoretic methods in networking: a tutorial.
> ??? Presented at SIGCOMM 2004 Workshop on Practice and Theory of
> ??? and Game Theory in Networked Systems (August 2004).? Available as
> This thesis addresses a problem at the nexus of engineering, computer
> science, and economics: in large scale, decentralized systems, how can
> we efficiently allocate scarce resources among competing interests? On
> one hand, constraints are imposed on the system designer by the
> inherent architecture of any large scale system. These constraints are
> counterbalanced by the need to design mechanisms that efficiently
> allocate resources, even when the system is being used by participants
> who have only their own best interests at stake.
> We consider the design of resource allocation mechanisms in such
> environments. The analytic approach we pursue is characterized by four
> salient features. First, the monetary value of resource allocation is
> measured by the aggregate surplus (aggregate utility less aggregate
> cost) achieved at a given allocation. An efficient allocation is one
> which maximizes aggregate surplus. Second, we focus on market-clearing
> mechanisms, which set a single price to ensure demand equals supply.
> Third, all the mechanisms we consider ensure a fully efficient
> allocation if market participants do not anticipate the effects of
> their actions on market-clearing prices. Finally, when market
> participants are price anticipating, full efficiency is generally not
> achieved, and we quantify the efficiency loss.
> We make two main contributions. First, for three economic
> environments, we consider specific market mechanisms and exactly
> quantify the efficiency loss in these environments when market
> participants are price anticipating. The first two environments
> address settings where multiple consumers compete to acquire a share
> of a resource in either fixed or elastic supply; these models are
> motivated by resource allocation in communication networks. The third
> environment addresses competition between multiple producers to
> satisfy an inelastic demand; this model is motivated by market design
> in power systems.
> Our second contribution is to establish that, under reasonable
> conditions, the mechanisms we consider minimize efficiency loss when
> market participants anticipate the effects of their actions on
> market-clearing prices. Formally, we show that in a class of
> market-clearing mechanisms satisfying certain simple mathematical
> assumptions and for which there exist fully efficient competitive
> equilibria, the mechanisms we consider uniquely minimize efficiency
> loss when market participants are price anticipating.
> Mondriaan Memory Protection
> Emmett Witchel (UT Austin) and Krste Asanovic
> The SCALE Group
> Computer Science and Artificial Intelligence Laboratory
> The Stata Center, 32 Vassar Street, Cambridge, MA 02139, USA
> The need for flexible, efficient, fine-grained memory protection and
> sharing has been neglected in modern computing systems. Mondriaan
> memory protection (MMP) is a fine-grained protection scheme that
> allows multiple protection domains to flexibly share memory and export
> protected services. In contrast to earlier page-based systems, MMP
> allows arbitrary permissions control at the granularity of individual
> words. We use a compressed permissions table to reduce space overheads
> and employ two levels of permissions caching to reduce run-time
> We implement the MMP hardware in a simulator and modify a version of
> the Linux 2.4.19 operating system to use it. Linux loads its device
> drivers as kernel module extensions, and MMP enforces the module
> boundaries, only allowing the device drivers access to the memory they
> need to function. The memory isolation provided by MMP increases
> Linux's resistance to programmer error, and exposed two kernel bugs in
> common, heavily-tested drivers. Experiments with several benchmarks
> where MMP was used extensively indicate the space taken by the MMP
> data structures is less than 11% of the memory used by the kernel, and
> the kernel's runtime, according to a simple performance model,
> increases less than 12% (relative to an unmodified kernel).
> "Mondriaan Memory Protection", Emmett Witchel, Ph.D. dissertation,
> Massachusetts Institute of Technology, January, 2004. (PDF paper)
> "Hardware Works, Software Doesn't: Enforcing Modularity with
> Mondriaan Memory Protection", Emmett Witchel and Krste Asanovic, 9th
> Workshop on Hot Topics in Operating Systems (HotOS-IX), Lihue, HI, May
> 2003. (PDF paper, PDF slides, PPT slides)
> "Mondrian Memory Protection", Emmett Witchel, Josh Cates, and Krste
> Asanovic, Tenth International Conference on Architectural Support for
> Programming Languages and Operating Systems (ASPLOS-X) , San Jose,
> CA, October 2002. (PDF paper, PPT slides, PDF slides)
More information about the FoRK