In this project we design efficient secure algorithms for various multi-party protocol tasks. The protocols must be provably secure based on well-understood cryptographic assumptions, they need to satisfy requirements imposed by the real-world applications of these protocols, and they need to be efficient enough to be usable in practice.
Among the protocol tasks we address are private authentication schemes, aggregate signature schemes, dynamic group key agreement schemes, and proactive cryptosystems. The challenge in designing such protocols is to achieve efficiency without making assumptions that would impede the adoption of these protocols in practice. For example, protocols that rely on a public key infrastructure cannot assume universally trusted authorities, and they should remain efficient if protocol participants hold certificates from multiple sources. Moreover, to be truly useful a multi-party protocol must remain efficient in realistic communication conditions, e.g. if the participating nodes do not have synchronized clocks, or if the communication mechanism between any two protocol participants can be disrupted.
Development of efficient secure multi-party protocols which meet these efficiency goals and operational requirements relies on construction of public key primitives with novel security properties, and on finding new approaches to fundamental questions related to multi-party protocols, e.g. fairness, limitations imposed by trust assumptions, and security under protocol composition.
This project can also have an immediate impact on a variety of computer systems, improving their reliability, security, and privacy properties. Examples of prospective applications of our protocols are provision of fault-tolerant security services, and enabling of group-wide security mechanisms in ad-hoc and mobile networks.
The project on Secure Multi-Party Protocols generated outcomes of two types: First, it generated protocols that offer secure and practical solutions to several important tasks, with potentially far-reaching consequences to internet security. Secondly, it generated several cryptographic tools of general applicability in secure protocol design. Within the domain of practical secure solutions to specific protocol tasks, the most important outcomes of this project are Searchable Encryption, Password-Protected Secret-Sharing, and Private and Covert Authentication: Searchable Encryption allows outsourcing data in an encrypted form, and yet the server which keeps the encrypted data can efficiently find and retrieve the ciphertexts that match the data owner's query (or another party which the data owner allowed to query its data). Such protocol could allow, for example, for all email held by mail services like gmail or yahoo, to reside on these services in encrypted form, and yet if the user wants to retrieve all emails containing certain keyword, and/or a text that includes a specified substring, and/or a date which falls within some specified time range, then an efficient protocol allows the user to retrieve all (and only) those ciphertexts that match the user's query. Password-Protected Secret-Sharing allows for distribution of some secret information, e.g. keys used for authentication or message decryption, among several computing nodes (e.g. servers, or general data-capable devices, like smart phones, smart watches, etc), in such a way that the secret reconstruction succeeds only if the user supplies his/her password in the reconstruction protocol. Crucially, even n-1 out of n nodes together do not hold any useful information about either the shared secret or the password necessary for its reconstruction. Such schemes can greatly improve the security of internet authentication, because they avoid storing users' authentication secrets (e.g. passwords or password hashes) in a single location (e.g. an internet authentication server), from which such information can be stolen. Private and Covert Authentication allows two parties who hold matching certificaticates, e.g. two members of the same organization, to authenticate each other in a way that to outside parties, e.g. to entities that do not hold a valid membership certificate in this organization, looks indistinguishable from random noise. Such protocols can be used for establishing secure communication between two mutually authenticated parties without revealing that such communication is taking place to any third party. Within the second domain, perhaps the most important and widely applicable cryptographic tools whose development was supported by this project, are OPRFs, COTs, and CCTs: OPRF, an oblivious pseudorandom function computation protocol, enables party A to compute an encipherment of his/her message m under the private key held by party B in a way that does not leak any (useful) information to party B about A's message m. (Likewise, the protocol also does not leak any other useful information about B's key to party A, except for the encryption of A's message m under this key.) OPRFs turn out to be extremely useful for various secure protocol tasks, including Searchable Encryption and Password-Protected Distributed Cryptosystems discussed above. COT, a Conditional Oblivious Transfer, enables party A to send a message to party B conditioned upon some statement x held by A to be true and upon B holding a witness w to this statement. An example is that A wants to send a message only to a holder of a valid certificate issued under some key which A recognizes (e.g. certifying that the certificate holder is a member of some organization, or is otherwise authorized by some authority to receive certain type of documents), in which case a witness that proves this statement true would be a valid signature under such certificate, which party B presumably holds. The point is that rather than B authenticating itself to A and proving that whatever A requires to give B access to message m is true, a COT can shortcut this process by A sending m in such a way that it can be decoded only if B holds appropriate certificates. Moreover, a COT can hide the statement x "under which" the message m is sent, to any parties that does not hold a valid witness for x, and that property of COTs is an essential enabler for Private Authentication protocols discussed above. CCT, a Conditional Covert Transfer (CCT), is a COT protocol with an added feature: If party B does not hold a valid witness for sender A's statement x, then B not only cannot learn anything about either x or m, but it also cannot distinguish communicating with A from receiving random bits. Likewise party A cannot tell communicating with B from receiving random bits. CCTs are essential enablers of Covert Authentication protocols discussed above.
