Pen-and-paper one-way function for externally-anonymous survey

When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being revealed to the Administrator but not to the Enumerator.

Is there a way to create a one-way function/process using simple (small and cheap) physical objects such as pen and paper that isn't too time-consuming or involves complex math? Inverting the function would be too hard for the Enumerator during, or just after the survey, but the Administrator could do it later. Assume that the Enumerator can do anything quickly to uncover the answer (e.g. "accidentally" open a sealed envelope or claim non-random data is random) so long as the Administrator gets the truthful answer in the end. Assume that this is the only interaction with the survey, so no secret information has been passed among the Administrator and the Respondent. FYI: Previous questions include ones about non-computer/manual full cryptosystems and ciphers, but answers to both involve a long time to execute.

-

There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work.

Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated with answering yes. Here's what we do. We give the respondent an ordinary 6-sided die. We ask the respondent to secretly roll the die (where the enumerator can't see it). If the die comes up 1-4, we ask them to answer honestly; if it comes up 5 or 6, we ask them to reverse their answer (tell us the opposite of their true answer).

This provides plausible deniability for respondents. If they answer "yes", it might be that they have seriously considered suicide; or it might just be that they got a 5 or 6.

It also gives us a way to estimate the fraction of people who have seriously considered suicide. Suppose a fraction $q$ of respondents answer yes. Then we can estimate that about $p=3q-1$ of the population of respondents have seriously considered suicide. We can't identify any specific individual who did or didn't seriously consider suicide, because we only have a noisy view of the truth for any one individual, but we can still compute aggregate statistics.

(Do you see why the formula $p=3q-1$ works? Suppose a fraction $p$ of the population has seriously considered suicide. What fraction of people will answer yes, given this procedure? Well, of the $p$ fraction who have seriously considered suicide, $4/6$ of them will answer yes; of the $1-p$ fraction who have not seriously considered suicide, $2/6$ of them will answer yes; so in total, $4p/6 + 2(1-p)/6$ of the population will answer yes. A bit of simplification shows that this is equal to $(p+1)/3$. Of course, we cannot observe $p$ directly, but we can observe this fraction; this fraction is exactly $q$. So, setting $q=(p+1)/3$ and solving for $p$, we find that $p=3q-1$.)

-
That's a really interesting technique. +1 – Reid Jun 2 '13 at 4:46
Yeah, these are called Randomized response methods. They're useful, though, I was hoping there'd be something more for specific situations. – BeingQuisitive Jun 11 '13 at 2:28

You could probably post the Administrator's public key and some random nonce on the questionnaire. The cipher should be easy enough to compute with a calculator. Does running specialized decryption software count as quick action on the Enumerator's part? If no then the cipher could be really simple.

Another way to go about it is to conceal the identity of the participants from the Enumerator (eg. assign a unique ID to each questionnaire).

-