# Scheme to select a multiple choice answer on a whiteboard secretly? [closed]

Trying to set up a cute demonstration of cryptography, here's what I'm envisioning so far:

I have a whiteboard, some number of students, and an equal number of different colored markers. On the whiteboard is a survey question, with possible 4 responses. One by one, each student writes something on the whiteboard with their own color to select their response.

But here's the catch:

1. Each student's writing must commit them to one of the four choices.
2. No other student should be able to figure out another student's selection, until...
3. The students can reveal a piece of information that makes deciphering their choice possible.

So after all the students have gone up to the whiteboard, they can reveal their secret and let their choices be known.

What can they write on the board? This is an open-ended question, but I want to optimize for "elegance". I'm having a hard time articulating what I want, but I'll post my own answer and why I don't like my answer if that makes things more clear.

• "Good questions for this site have a limited number of objectively correct answers." Your question as it stands is too broad, as the only criterion you've given for what would set apart an ideal answer from the countless possible schemes is "elegance", a term you don't define. Please try to be more specific in your question, to narrow the scope of possible answers.
– Rubio
Commented Mar 16, 2023 at 2:22
• The trivial (and guaranteed secure) answer is that the student's "piece of information" for step 3 is a one-time pad.
– fljx
Commented Mar 16, 2023 at 9:07
• Must all students use the same scheme (just with different public/private data)? Or can they use completely different ones? Commented Mar 16, 2023 at 9:26
• Could the students write something that gives a different result depending on the secret? E.g could they write "abcd" and have their secret be "2" for an answer of B? Commented Mar 16, 2023 at 9:30

Cryptographically secure approach:

Everyone chooses a long random string beginning with the letter indicating their choice, then writes a cryptographic hash of this string on the board. Since it is unfeasible to find collisions, revealing the unhashed string later proves they chose the string (and therefore the choice) beforehand, but the randomness of the rest of the string makes it unfeasible to guess the hash preimage.

Approach performable in class:

Everyone writes their choice into an unlisted ownerless Pastebin paste, which turns it into an URL with eight unique characters, and writes the last five characters of that URL onto the board. Assuming Pastebin generates URLs randomly, it is unfeasible to generate a collision without submitting several thousand pastes to generate a collision, and it is unfeasible to figure out another student's remaining three characters without checking several thousand pastes.

My own attempt that I don't like too much:

Each student writes a different positive integer underneath all 4 choices.
A student's selection will be the integer whose prime factorization contains the biggest factor. A student can prove their selection by sharing the prime factorizations for each number they wrote on the board.

Things I don't like about my solution:

• Not completely well-defined without tie-breakers, and I can't think of any elegant ones.
• The cryptographic difficulty of the prime factorization might not be realized in my approach? It feels like there might be a shortcut to identify the number with the greatest prime factor without actually factoring them.
• The arithmetic is cumbersome

I'm very out of my depth on understanding cryptography, but I guess I'm looking for a more tangible example of a trapdoor function? If my demo could involve shapes or words instead of arithmetic, that would be nice.

• Why not: Beforehand, give each student a card with something specific on it, distinct from every other student, which they keep secret. This could be a shape or word, as you'd prefer. For each possible response, in order, each student writes their assigned shape/word/whatever under the response if it is the one they are selecting, or a random different shape/word/whatever otherwise. When all annotations are complete and everyone's responses are locked in, the students show their assigned shape/word/whatever card to reveal their selected response. (This works similarly to a pre-shared key.)
– Rubio
Commented Mar 16, 2023 at 2:44
• You should probably update the question to mention trapdoor functions if that is what you want answers to focus on.
– fljx
Commented Mar 16, 2023 at 10:15

Algorithm:

Each student is told a number between $$1$$ and $$6$$. They then write a word that contains $$2$$ or more of the letters ABCD but with the letter representing their choice in the position equivalent to the number they were told. When they reveal the number they were told, you can find their answer to the survey.

Example:

Steve is told the number $$3$$ and his choice is A. He writes the word ‘braid’. Nobody knows his answer until he tells everyone the number he was told. Then, they look at the third letter and see he chose A.

• From the word 'braid' I already now Steve didn't pick C because there is no C in braid. And braid is already a good word. If I get 1, choose A and then write 'apples' everyone knows I picked A without knowing my secret number. Commented Mar 16, 2023 at 13:24
• @quarague The answer states that ‘apples’ is not valid. It has to contain 2 or more of the letters ABCD. Commented Mar 16, 2023 at 13:27