How to construct a protocol for a trustless standardized paper test?

So the problem I'm exploring is basically how to run a paper exam (such as the SAT) in such a way that participants can be sure that their exams were graded fairly, meaning the exam hosts can't change the answers or questions of the exam after the exam is conducted without the examinees finding out.

So we have a test which consists of $n$ strings that are questions each of which are multiple choice with $5$ choices.

Currently the protocol I had was the following:

1. Examinees get a test booklet and a scantron. They have a fixed amount of time to fill their scantron and to perform some cryptographic verifications. If they don't finish their exam, finish their verifications, and submit before the time is up then their test is considered void. This might seem unreasonable for people that wait to the list minute to submit but it easier than trying to schedule verification of materials while avoiding cheating/writing answers overtime.

2. The testbooklet contains on one of its pages a string filled with the text for every question concatenated without spaces. Then it features a hash of this string. Then it features a digital signature signed by the test providers private key of this hash. Participants at some point of taking the exam can verify that indeed the text + hash + digital signature is consistent with the public key of the provider using a 3rd party device in the testing room.

3. In order to submit their scantron the examinee provides their scantron to a device which produces a string containing all of the examinees answers concatenated together, then a hash of this string is produced, then a digital signature signed by the private key of the testing provider is produced. Examinees can then verify their scantron was correctly encoded by the same 3rd party device in the examination room. Once they are content they hand over their scantron for grading.

4. Examinees take their testing booklet home.

5. Once the scantrons are graded each examinee receives what the grader claims their answers are, and what the grader claims their questions were. The examinee can contest a particular answer or question by noting they have a signed certificate from the provider asserting their answer was __, or that a particular question was ___ and the examinee can use the providers public key to prove authenticity of their certificates.

So theres a couple issues with this scheme,

1. What if the 3rd party device manufacturer and Testing Provider collude? The only reason that 3rd party device manufacturer enters the picture is because its not reasonable to allow examinees to bring their own smartphones/computers to the room.

2. What if the provider changes their public key after running the exam. Then they can just tell the examinee "oh sorry but that certificate is clearly invalid it doesn't match our new key and we deny that there ever was a different old key".

3. This protocol is logistically kind of challenging. you have people near the end of an exam using a 3rd party machine to verify authenticity.

So I guess I was wondering is there a better way to come up with a physical protocol for how to conduct paper which assumes the minimal amount of trust possible on the testing provider + grader?

This isn't a multi party computation problem. It's a physical security problem. If the exam paper will be published after the fact there's no need for complex multi party computation. Release a signed answer key.

The idea of the test taking organization "changing" their public key after the exam is silly in my opinion. What are they going to do, change all the printed and digital records of that published key? Same thing with the answer key. If they release two different signed answer keys it'll be pretty obvious. If you're concerned they'll do that to one specific person and hire thugs to steal and destroy it, have additional unnafiliated third parties vouch that that answer key is the canonical known answer key. (EG:put it in a blockchain)

4. Examinees take their testing booklet home.

This is doing most of the work. If the test must remain secret, participants take their test to the trusted scantron machine and it spits out a score while verifying the test booklet is valid. Note that questions could be re-ordered or have answers re-ordered. If the machine is trusted, it can perform arbitrary checks on the exam paper after the fact. If participants don't trust the hardware they don't have any record of what happened to show that they were cheated. Any cryptographic data they are given can be garbage since they could just print off an "invalid" test paper they created themselves after the fact. There's no way to tell between such a crazy person and one with a legitimate grievance against the exam proctors.

So given that the booklet is going home with the participant, they can just use their phone as trusted hardware to verify the booklet and get their grade.

Cheating is still a problem. Test takers need to be separated from any electronic devices. Do something like a "coat check" but for phones. Then run participants through a NLJD archway, which is like a metal detector but for electronics, to make sure. Alternately you do the traditional thing with proctors walking around trying to catch participants covertly using electronic devices.

So participants:

• coat check all their electronics
• take the test while unable to use electronic devices to cheat
• get back their device and "grade" their own paper using an open source app.

Just before grading, the proctors publish a signed answer key on the internet somewhere that can be used to verify and grade test papers.

The app can return three possible results:

• valid exam paper:grade=%grade%
• invalid exam paper:the proctors are corrupt!
• this isn't an exam paper at all

Participants could smuggle in a printed invalid exam paper and then raise a fuss. To prevent this, exam papers are marked with a secret string. Participants would have to print this on their smuggled in invalid papers during the test. Anti-counterfeiting technology could be integrated here to make things harder if students can somehow smuggle a laser printer into the exam (EG:tamper seal sticker with secret watermark on all test papers).

The proctors could also use disappearing ink to make an apparently legitimate paper become illegitimate by the end of the test. Anti counterfeit stickers with metallic printed text might then be a good idea even if participants can't smuggle in a laser printer.

Participants would check the secret string when they are given their exam booklet and raise a fuss if there's an error. It can be on a poster or something near where the booklets are handed out.

If there's an invalid paper, other participants can double check. Assuming seating and verification order is verifiably randomized your neighbor is unlikely to be a working with the proctors and it will rapidly be apparent to everyone what's happened.

Making sure the validation secret doesn't leak while also preventing proctors from targeting anyone in particular is a hard problem. Maybe have exam papers laid out beforehand in opaque envelopes that participants are not to touch until the test starts, then hang a banner with the validation secret once the test starts. If participant seating order is verifiably publicly randomized during seating, targeting any one person becomes impractical.