Example with Sample Data

The Utility Demonstrated by this Example

This example is motivated by a problem faced by financial institutions that issue consumer credit. Some fraction of their credit cards and loans are issued to individuals impersonating another individual; in other words, a few customers are committing identity theft. It is important to stop identity theft early to minimize losses and legal problems.

In principle, it should be easy to catch identity thieves who typically open new accounts using information about another party. The legitimate party still has a legitimate account at his or her legal residence. The thief will use a different address so that correspondence regarding the illegitimate accounts is directed away from the victim whose name and financial reputation are being appropriated. The situation can be detected if financial institutions compare their customer lists and addresses. However, in practice there are two barriers to such cooperation. First, the institutions are legally bound not to disclose financial information belonging to their customers and sharing with another institution would represent disclosure. Second, the institutions are actually competitors. Each fears the other will try to steal its customers by contacting them via telephone or mail. Consequently, this obvious operation requires a negotiation about the content of concealed data leading ideally to the exchange of a small controlled amount of information regarding only the suspected, illegal, identity-theft cases.

To illustrate the operation of the negotiated information sharing applied to this example, we introduce the simplification that we simply look for individuals with accounts in two different zip codes. The nine digit postal zip code (ZIP) is a very specific geographic locator and we can use an individual’s social security number (SSN) as the standard identifier for that individual. In more general cases, the broker will need to establish a controlled vocabulary. In this example, however, the format of SSN and ZIP are well known.

Sample Data

In the example there are two institutions A and B with the customer lists shown in Table A and Table B.:

Table A – Credit Card Customers of Bank A

              family     given         zip            ssn

              ------    ------      ------         ------

           Hollander      Dave  20114-4671    214-14-7879

              Kimber     Eliot  26420-9681    155-47-9782

            Magliery       Tom  18603-8576    490-48-8856

               Maler       Eve  13646-5203    615-32-7706

             Maloney    Murray  79123-5517    695-68-3428

              Murata    Makoto  81789-9347    690-95-1189

                Nava      Joel  48742-5578    902-60-6893

           O'Connell   Conleth  37863-9169    736-80-7781

               Paoli      Jean  28667-9364    341-61-9229

              Sharpe     Peter  15576-2097    655-68-6926

    Sperberg-McQueen     C. M.  26667-2936    411-38-1750

               Tigue      John  32122-3390    171-51-9946

Table B – Credit Card Customers of Bank B

              family     given         zip            ssn

              ------    ------      ------         ------

          Angerstein     Paula  86910-9913    506-75-5891

               Bosak       Jon  13858-6727    639-55-6905

                Bray       Tim  59187-3619    623-87-8498

               Clark     James  87635-2887    528-94-3591

            Connolly       Dan  28494-9947    234-75-3246

              DeRose     Steve  77763-2195    435-12-7091

           Hollander      Dave  20114-4671    214-14-7879

              Kimber     Eliot  26420-9681    155-47-9782

            Magliery       Tom  18603-8576    490-48-8856

               Maler       Eve  13646-5203    615-32-7706

             Maloney    Murray  38166-1508    695-68-3428

              Murata    Makoto  81789-9347    690-95-1189

Information to Protect:

1. all Social Security Numbers (SSN) are private information of the customers.
2. Table A contains the names of 6 customers who are not customers of Bank B (Nava, Paoli, Tigue, Sharpe, O'Connell, and Sperberg-McQueen). These names must not be revealed to Bank B.
3. Table B contains the names of 6 customers who are not customers of Bank A (Bosak, Clark, Bray, Angerstein, Connolly, and DeRose). These names must not be revealed to Bank A.

Information to Discover in Tables:

1. Customer Maloney is found in both database but has zip-code 79123-5517 in 38166-1508 Table A. In both tables, the customer claims SSN 695-68-3428.

Method of Discovery

If there were no concerns about revealing private records or about sharing customer data with a competitor, then the two banks would directly exchange data tables. Then either bank could discover the case of suspected identity theft involving their shared customer Mr. Maloney. One possible method would be to place the tables in a relational database having a query language based on SQL. Then the following SQL query directed to the database will return the result:

select a.family, b.family, a.ssn, a.zip, b.zip from table_a as a

   join table_b as b on a.ssn = b.ssn where a.zip <> b.zip

In English the query reads: “Give me names, zip codes and SSN for customers present in the both databases and showing the same social security number but different zip codes.

When the Pygar approach to negotiated information sharing is applied to this example, the data are protected by encryption and then sent to a third party broker who cannot decrypt the data but can discover the desired correlation between records. This example will illustrate that the discovery process followed by the broker for encrypted data is exactly the same as the process that works for unencrypted data. The only consequence of encryption is that the broker sees only an encrypted result – consistent with the plan to prevent the broker for learning the secrets in the data sets.  This will become clear as we look at the data.

Transmittal of the Data to the Broker

All modern business methods rely on standard methods to package data for exchange over the Internet. The method used here is XML because it is the most widely understood and accepted. The data of Table A and Table B can be converted easily and in many cases automatically to XML. Banks A and B are working independently so they need a common format. The broker provides the format. In this example, the broker specifies a small vocabulary of XML tags: <names>, <name>, <family>, <given, <ssn>, and <zip>. For the vocabulary of nouns, the broker does not provide a vocabulary list but simply specifies that names must be written in Latin-1 alphabet, that social security numbers have their canonical form, and that the zip codes should have the precise 9 digit US Post Office format.

The tables are represented as XML in Listing 1 in columns Ex1A and Ex1B:

Listing 1

At this point, the information could be sent to the broker, but then the broker could read it and compromise the data which is private to the customers and proprietary to the bank. Consequently, Bank A and Bank B both encrypt the data before sending. The broker should select one of the banks to originate a one-way encryption key. It does not matter whether Bank A or Bank B selects the key so long as the broker does not learn what the key is. For the example, Bank B selects the key "8jq6r3llnwc9ytraz56d9" and conveys it to Bank A by a channel protected by public key encryption methods. The banks also agree on the one-way encryption algorithm. For this example, they select the algorithm specified in Internet RFC 2104 entitled “HMAC: Keyed-Hashing for Message Authentication”. (For reference see:

http://www.faqs.org/rfcs/rfc2104.html ).

The encryption key and algorithm are applied to each tagged text field in the document but not to the tags themselves.  After encryption we have encrypted documents suitable for transmitting to the broker. These are shown in Listing 2.

Listing 2

Broker’s Discovery of the Basis for Negotiation

The broker receives the pair of encrypted documents shown in Listing 2. From these documents, the broker will discover pairs of XML statements about individuals such that one individual of the pair is on the list provided by Bank A and the other statement is on the list of Bank B. There are many technical implementations of this discovery process but for the example we elect simply to convert the XML documents back to SQL database tables. This conversion is readily accomplished with off-the-shelf software available from Oracle, Microsoft, and others.

Once the data are in tables, the broker simply issues the SQL query shown above to the relational database. The result is a reply that informs the broker that an individual whose last name encrypts to the value “d4ab11188fa3f100f1930c8ae07c0916” and whose social security number encrypts to the value “f1e715fedb1cdebd102257dc77a758ca” is found on the lists from both banks but the zip-code of the billing address provided by the two banks differ and encrypts to “”a30225c1fb0d0bcc645b07173e9f5853” in the list from Bank A and to “7ff0c220b90ac551d6d4969ab68f0229” in the list from Bank B.

The broker now knows that Bank A and Bank B have a matter to discuss that potential involves criminal behavior. The broker notifies the banks about this mutual, shared interest in customer with encrypted social security number “f1e715fedb1cdebd102257dc77a758ca”. This completes the brokers role in the negotiation. From that point forward, the two banks deal directly with each other.

Useful Results of the Negotiation

The brokered negotiation over encrypted documents has lead to a useful start of an investigation.  However, we can also point out that the privacy of all other individuals who are not connected with the investigation has been strictly preserved. Moreover the competitive positions of banks vis-à-vis each other in marketing themselves to customers has been preserved throughout the negotiation because neither bank could inspect the others customer list.

Other advantages accrue in different situations. For example, when we consider national security issues, it is important to remember that investigative units compete with each other for the rewards of a successful investigation. While each unit may have an organizational directive to capture criminals and terrorists, a unit is only rewarded in the present system if the team makes an arrest. Thus, there is a known reluctance on the part of these units to share information pertaining to on-going investigations. When a broker is involved in negotiations, however, the broker can keep a record of the sharing that takes place. The broker cannot read the encrypted basis of negotiation, but either party in the negotiation can use the broker as a reference to establish that it provided essential information to the other party. Thus, a potential benefit of this negotiation process is improved cooperation due to proper assignment of credit for success.