From: jim@bilbo.suite.com (Jim Miller)
Date: Wed, 24 Aug 94 13:43:17 PDT
To: shamrock@netcom.com
Subject: Re: Anonymous questionnaires
Message-ID: <9408242034.AA29793@bilbo.suite.com>
MIME-Version: 1.0
Content-Type: text/plain




Lucky Green asks how to:

1. Correlate my answers to the answers of my partner.

2. Verify that I have indeed sent in a filled out questionnaire (and send
   me a check for participating).

3. Allow a supervisory agency, such as the U.S. Department of Health and
   Human Services, to verify that the researchers did not just make up all
   the data - that is to allow an audit.

4. Protect my privacy by making it impossible to correlate my name to the
   answers given.


The following a complicated and impractical solution (but it was a fun  
exercise):

First, assume everybody participating in the study is on the Net and is  
crypto savvy. :-)

Each participant generates a new public-key pair for the study.  


The supervisory agency generates a new public-key pair and gives a copy of  
the public key to each participant.  They do not give a copy to the  
researchers.  


The researchers generate a new public-key pair and give a copy of the  
public key to the supervisory agency and each participant.

Finally, each participant generates a symmetric key, blinds it, and has  
the supervisory agency sign the blinded symmetric key.

Ok, assume Bob and Alice are a couple participating in the study.  Bob and  
Alice each get a copy of the questionaire, the researcher's public key,  
and the supervisory agencies' public key.  They each generate and blind a  
symmetric key and have it signed by the supervisory agency.

Bob fills in his copy of the questionaire and then signs an MD5 hash of  
his completed questionaire.  Alice does the same.  Bob gives his signed  
hash value to Alice and Alice gives her signed hash value to Bob.  Bob  
appends Alice's signed hash value to the end of his completed  
questionaire.  Alice appends Bob's signed hash value to the end of her  
completed questionaire.  Neither sees the other's completed questionaire.

Bob now signs his questionaire with his private key.  Alice signs her  
questionaire with her private key.

Bob encrypts his (now signed) questionaire and his public key with his  
symmetric key.  He next encrypts the signed (and now unblinded) symmetric  
key with the supervisory agencies' public key. Finally, he encrypts those  
items, along with a cleartext copy of the completed and signed  
questionaire, with the researcher's public key and e-mails the result to  
the researchers using a chain of anonymous remailers.  :-)

Alice does the same.

Ok, the researches receive an anonymous e-mail message from somebody (call  
him Ted) that is encrypted with their public key generated specifically  
for this study.  They decrypt the message and get four items:  Ted's  
completed and signed questionaire, Ted's encrypted and signed  
questionaire, Ted's encrypted public key, and Ted's encrypted and signed  
symmetric key. 


Since Ted's public key is encrypted with his symmetric key and the  
symmetric key is encrypted with the agencies' public key, the researchers  
cannot read these items.  Also they cannot verify the signature on the  
cleartext copy of the questionaire.  However, they check that everything  
appears to conform to the requirements of the test, so they credit Ted  
with completing the questionaire and e-mail him (via the encrypted reply  
block) an IOU signed by the researcher's private key.  More on the IOU  
later.

The researchers collect all the anonymous replies and send them as a group  
to the supervisory agency.  The supervisory agency decrypts all the  
encrypted symmetric keys using its private key, validates the signatures  
on those keys, then uses the symmetric keys to decrypt the participants'  
public keys and encrypted questionaires.  Since the symmetric keys were  
blinded when the supervisory agency signed them, the agency does not have  
enough information to be able to determine which participant completed  
which questionaire.  All the agency can do is verify that the  
questionaires were completed by people who had symmetric keys signed by  
the agency.  Since the questionaires where e-mailed to the researchers via  
anonymous remailers, the researchers can't collude with the supervisory  
agency to determine who complete which questionaire.

The agency sends the decrypted public keys and questionaires back to the  
researchers.  The purpose of the signed symmetric keys was to help prove  
to the agency that the researchers did not fabricate the study results.   
This is not perfect, the researchers could have pretended to be all of the  
participants and could have filled out all of the questionaires.  However,  
if they did that, they would be unable to produce any real participants,  
if they were ever challenged.

The researchers use the decrypted public keys and the signed MD5 hashes to  
group the questionaires into related pairs.  The researches can compare  
the decrypted questionaires sent back from the agency with the plaintext  
copies received from the participants to verify that the supervisory  
agency did not substitute any of the real questionaires with bogus ones.

The researchers can now analyze the questionaire data, but they don't know  
which participant filled out which questionaire.  However, the researchers  
do know which questionaire is paired with which other questionaire.


More on the IUO:

How does a participant redeem the IUO without revealing information which  
could allow the researchers or the supervisory agency to pair them up with  
their completed questionaire?

Well, the IUO is really a blinded message sent to the researchers in the  
anonymous message along with the other stuff.  If the researches are  
satisfied with the plaintext questionaire, they will sign the blinded IUO  
and send it back via the encrypted reply block.  The participant unblinds  
the signed IUO.  The participant can now redeem the IOU offline without  
giving anyone any information other than the fact the person was a  
participant in the study.

Of course, if there was real anonymous digital cash, there would be no  
need to use an IOU.


How to prevent a totally fabricated study:

As mentioned above, the researchers could fabricate the entire study by  
pretending to be all of the participants, getting known symmetric keys  
signed and so forth.  How can the supervisory agency determine the  
difference between a real anonymous participant and a bogus anonymous  
participant?

It is at this point that we have to step out of cyberspace and back into  
the real world.  Ideally, the supervisory agency needs to determine two  
things: 


    1) All of the participants were real people.

    2) None of the participants colluded with the researchers.


Requirement 1 can be satisfied by having the supervisory agency redeem the  
IOUs using money they escrowed on behalf of the researchers.  When the  
participant comes in to redeem the IOU (or snail mails it in), the  
supervisory agency can check the ID (driver's license, SS#, whatever) of  
the participant, verify the signature on the IOU, and hand over (or mail)  
the check.  The signed IOU will not give the agency the ability to  
determine which questionaire the participant filled out.

I know of no way to enforce requirement 2 without violating the anonymity  
of the participants.  The researchers could hire a bunch of people to  
redeem bogus (but correctly signed) IOUs, fooling the supervisory agency.   
The only way I can think of to prevent participant/researcher collusion is  
to have independent auditors standing over the participants while they  
fill out the questionaires.  Not what Lucky Green had in mind, I'm sure.

So anyways, there it is, a complex and impractical solution that still  
doesn't solve all the problems.  Oh well.  Time to go back and work at my  
real job.


Jim_Miller@suite.com