Research Topics

Combining Public Key Cryptosystems

It is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an individual user's RSA key pair should only be used for public-key encryption or for digital signatures, and not for both. This principle was only encouraged by the early recognition that the textbook versions of the public-key cryptosystems based on number-theory problems all had the property that we now call malleability, related to their random self-reducibility. From the very beginning, researchers advocated adding redundancy to messages (as Rabin did in one of the founding papers of our field). But a sophisticated understanding of methods to do this, whose security we can properly analyze, is much newer in the research community.

In this work we show that in many cases, the simultaneous use of related keys for two cryptosystems, e.g. for a public-key encryption system and for a public-key signature system, does not compromise the security of either one of the systems. We demonstrate this for a variety of public-key encryption schemes that are secure against chosen-ciphertext attacks, and for a variety of digital signature schemes that are secure against forgery under chosen-message attacks. The precise form of the statement of security that we are able to prove depends on the particular cryptographic schemes in question and on the cryptographic assumptions needed for their proofs of security; but in every case, our proof of security does not require any additional cryptographic assumptions.

Among the cryptosystems that we analyze in this manner are the public-key encryption schemes of Cramer and Shoup, Naor and Yung, and Dolev, Dwork, and Naor, which are all defined in the standard model, while in the random-oracle model we analyze plaintext-aware encryption schemes (as defined by Bellare and Rogaway) and in particular the OAEP+ cryptosystem. Among public-key signature schemes, we analyze those of Cramer and Shoup and of Gennaro, Halevi, and Rabin in the standard model, as well as the random-oracle based variants of the El Gamal and the Schnorr signature schemes.

Efficient Fair Protocols for P2P and Email

This subject refers to two different scalable protocols for ensuring fairness for electronic mail (i.e. implementing certified email) and for peer-to-peer transcations. The main goals in the design of these protocols were scalability, and minimal changes to the exisiting infrastructure (for example, the certified email protocol does not require mail recipients to install any new software). In order to achieve these goals the protocols are based on using a very efficent trusted third party, rather than using ``optimistic'' protocols with an off-line trusted party.

The certified email protocol aims to combine security, scalability, easy implementation, and viable deployment. There are many suggestions for certified email protocols, but most of them do not comply with the exisiting infrastructure, for example by requiring several rounds of interaction between the sender and the receiver, thus preventing the sender from a ``send-and-forget'' approach for sending email. The main advantages of out protocol are the use of a light and stateless on-line trusted third party, a ``send-and-forget'' solution for sending email, an implementation that does not require any special software for the receiver beyond a standard email reader and web browser, and no reliance on a public-key infrastructure. A prototype of this protocol has been implemented.

The motivation for the peer-to-peer escrow service was using economic incentives instead of tamper resistance to motivate users to keep content within a subscription community. The key technical contribution is an integration of a P2P file sharing service with an efficent and state-less escrow service that reliably ``pays'' the party that is serving up the content. The architecture facilitates trust between two unacquainted parties by offloading risk to a trusted third party, which can acquire a revenue stream by assuming this risk. The escrow service is securely implemented using cryptographic techniques, such as encryption, hashing, and error correcting codes. The system motivates users to serve up content of high quality and verifies that users only share legitimate content and not spam, viruses or content that is not part of the subscription. It thereby addresses other important security concerns in P2P systems and problems like the free-rider phenomenon.

Privacy preserving data mining

We introduced the concept of privacy preserving data mining. In our model, two parties owning confidential databases wish to run a data mining algorithm on the union of their databases, without revealing any unnecessary information. This problem has many practical and important applications, such as in medical research with confidential patient records.

Data mining algorithms are usually complex, especially as the size of the input is measured in megabytes, if not gigabytes. A generic secure multi-party computation solution, based on evaluation of a circuit computing the algorithm on the entire input, is therefore of no practical use. We focus on the problem of decision tree learning and use ID3, a popular and widely used algorithm for this problem. We present a solution that is considerably more efficient than generic solutions. It demands very few rounds of communication and reasonable bandwidth. In our solution, each party performs by itself a computation of the same order as computing the ID3 algorithm for its own database. The results are then combined using efficient cryptographic protocols, whose overhead is only logarithmic in the number of transactions in the databases. We feel that our result is a substantial contribution, demonstrating that secure multi-party computation can be made practical, even for complex problems and large inputs.

Privacy preserving auctions

We suggest an architecture for executing protocols for auctions and, more generally, econmoic mechanism design. Our goal is to preserve the privacy of the inputs of the participants (so that no nonessential information about them is divulged, even a posteriori) while maintaining communication and computational efficiency. We achieve this goal by adding another party - the auction issuer - that generates the programs for computing the auctions but does not take an active part in the protocol. The auction issuer is not a trusted party, but is assumed not to collude with the auctioneer. In the case of auctions, barring collusion between the auctioneer and the auction issuer, neither party gains any information about the bids, even after the auction is over. Moreover, bidders can verify that the auction was performed correctly. The bidders in the protocol are only required to send their bid to the auctioneer, and the overall communication and computational efficiency are very reasonable. This architecture can be used to implement any mechanism design where the important factor is the complexity of the decision procedure. We have experimented with a prototype implementation of this protocol, which demonstrates that it can be efficiently implemented for large scale auctions.

Copyright Protection

Suppose that access to some digital content (say an online database or a pay-for-view program) is limited to paying customers who have purchased decryption keys. A pirate might obtain keys from paying customers (``traitors'') and use them to construct pirate decoders which can be sold for less than the official price of a decoder. Upon confiscation of a pirate decoder it is required to identify the traitors who have contributed their keys, so that action can be taken against them. Part of our research (and also the full paper) considerably improved (by factors of a few hundreds!) the efficiency of the best known schemes that achieve this task, and essentially made it practical to use such schemes. This might have a considerable impact on deterring users from revealing their keys to non-paying customers.

We also presented a new method for revoking the keys of users who have been found to be corrupt. This method also combines the revocation with traitor tracing.

Multicast Security

Multicast communication is transmitted from a single source to many receivers (unlike unicast communication, which is between two parties). Although in theory multicast can be simulated by several unicast connections, special protocols to handle multicast communication are essential for the efficiency of data networks and in particular for wide distribution of electronic content. Part of our research concentrates on identifying the special problems of multicast security and on designing efficient solutions for these problems (see also our relevant internet drafts). There are two non-trivial security problems which we identified and targeted: individual authentication, and user revocation. Individual authentication means that only the source of a message can authenticate it. This might be very important even if the content itself is not secret (consider for example the authenticity of transmissions of weather reports which are used by traders for instant decisions on purchases of futures). User revocation is important in order to prevent non-paying customers from accessing the content. Both these problems do not have trivial solutions, but have to be solved in order to enable efficient commercial distribution of digital content. Our work contributes efficient solutions for both problems.

A different paper presented a new and very efficient key revocation schememethod. We also presented a different solution to the user  

DKDC: A Distributed System of Key Distribution Centers

Security in communication networks relies on trust. In networks which use public key cryptography trust is given to Certificate Authorities which certify the public keys of different parties. Networks which rely on private key mechanisms (such as Kerberos) typically use a Key Distribution Center (KDC) which all members trust. Each user has a common key with the KDC, which enables a secure channel between them. When two parties need to communicate securely the KDC generates a key for their usage and sends it to them encrypted, using the secure channels it has to both parties.

The use of a single KDC for all users introduces availability problems whereas replicated KDCs are essentially many points of failure - breaking into any one of them compromises all keys. We introduced a novel concept of a distributed KDC (DKDC). In such a system there are several KDCs and a user should contact any k of them (where k is a parameter) in order to obtain a key. The communication to the k KDCs can be done in parallel. Breaking into any k-1 KDCs does not compromise any key, and furthermore, it is possible to achieve proactive security that keeps the system secure as long as no more than k-1 servers are broken into in say, the same day.

Distributed KDC schemes enable a very natural billing mechanism for accessing the decryption keys of say, a digital TV channel. First, observe that since the system is protected against coalitions of up to k-1 KDCs it is possible to use less trusted parties as KDCs. Suppose that a user should contact k KDCs in order to obtain a key that enables it to view a movie. We can require him to pay each KDC 1/k of the price of the movie, and then there is no need for communication between the KDCs or a need for a central authority that instructs KDCs which users are entitled to receive decryption keys.

Secure and Efficient Metering

We have designed schemes that enable secure, efficient, and accurate measurement of the number of clients that were served by a (web) server. These schemes are essential is order to provide advertisers with reliable data on the popularity of web servers. Other applications for these metering schemes might include secure and efficient accounting of the usage of electronic coupons and secure usage based accounting between data networks. The methods we propose are privacy preserving.

Most of the revenues of internet ventures do not come from purchases or from payments for content but rather from advertising and from connectivity payments. There has been almost no research in securing the mechanisms that decide on the payments for online advertising or for connectivity.

Web servers have a motivation to inflate the number of clients that they claim to have served in order to charge more money for displaying ads. Advertisers on the other hand need reliable usage reports in order to decide on advertisement placing and on advertisement fees. There are numerous companies which offer web measurement services. However, the methods these companies use do not provide secure and efficient measurement of accesses to web pages. In particular it is very hard to accumulate data on most web sites since user survey based web metering does not provide reliable statistics for all but the most popular sites (consequently most internet advertising is displayed on a few dozen popular sites since it is easier to gather information on these sites). Other internet metering schemes  require an audit agency to install a metering module in audited web server, which counts the number of visits by clients. The security of these schemes is based on the tamper resistance of the metering module: if it is broken by the web site then it can start sending false usage reports. Past experience in the software and pay-TV industries has shown that ``tamper resistant'' modules can be broken if there is a large enough financial incentive.

Since web advertising is coming to be a Billion dollar business we believe that it requires secure and efficient schemes for web site popularity metering. We developed such methods. In our proposed schemes each client that approaches a server should send it a short message which depends on a secret information known to that client. The server is able to efficiently consolidate messages which were received from many different clients and generate a short proof for the number of clients that visited it. The length of the proof is much shorter than the number of clients the server had served (one might think of each client as sending the server a one cent coin and then the server somehow converting 10000 such coins into a single $100 note).

Our schemes prevent servers from inflating the count of their reported clients. We are also able to protect servers from clients that send erroneous metering information or that do not wish to send any metering information at all. Furthermore, the schemes protect the privacy of clients: the proofs that servers produce are for the number of clients that visited them and do not disclose the identities of these clients.

A prototype of a Web measurement system based on our schemes was built by  Reuben Sumner .

Our new metering schemes have the potential to considerably mature the internet advertising market by providing reliable and necessary usage data. They provide reliable information about the usage of medium and small size web sites which would facilitate advertising in these sites. In addition the schemes enable to meter the popularity of a site among a targeted group of clients (e.g. medical doctors). This should enable to target internet advertisements more effectively.

Electronic Coupons

Imagine a web server (say that of the Wall St. Journal) which provides its clients with coupons that give them free access to an online service (say for stock quotes) which is run by some service provider. The payment for this usage might be decided according to the number of coupons which were actually used. This scheme realizes a very appealing electronic commerce mechanism. Our metering schemes can be readily used to enable the service provider to construct a compact and undisputed proof for the number of coupons that have been used.

Data networks accounting

Huge amounts of money are being paid for connectivity to data networks (e.g. 50 million web users who each pay $20 a month sum up to $12 Billion annually). Pricing theory anticipates that fixed rate payments for connections would always lead to congestion. However this is the most common method of payments. Part of the reason might be the difficulty in providing efficient and undisputed measurements of the amount of traffic that originated from a source and passed through different networks. This might be a promising application for the secure and efficient metering schemes we proposed which might lead to a reduction in networks congestion.

Visual Cryptography

We designed visual authentication and identification schemes which do not require their users to use any computational device, but rather to rely on their human visual capabilities and on ``low tech'' equipment. Visual authentication schemes can be used for authenticating messages by a human recipient, and visual identification schemes enable a human to be identified to a remote party. We tried to define as accurately as possible the capabilities required from the human participant, and to rigorously reduce the system security to the assumption that humans have these capabilities.

Back to Benny's homepage