How to prove that you finished your homework before due, but forgot to submit?

Last update: 2023-12-20

Tags: writings

Reading time: 9 minutes

This was an interesting question I though of when I was getting huge (1 pts) deduction for my late homework. I finished my homework before due but forgot to submit. I was thinking that whether it is possible to prove that I finished my homework before due.

There is a trivial and working solution:

A simple solution

We can create a GitHub public repository and upload the encrypted homework before due. Later when we want to verify, we can show the secret to others and easily recover the original homework. As long as you trust GitHub and the encryption algorithm, you should believe that the homework is done before due.

You may also replace GitHub with any big social media, like Twitter or Instagram.

In this example, Github acts as an authority that both students and teachers trust.

However, there are some problems:

What if I don’t want others know that I was publishing those documents? I want to do this anonymously!
What if I don’t want any form of my documents being stored on the server? (including hash)

→ Problem Description

Here is the problem:

Problem Description

The Late Homework Problem. John is a student (Prover) and Peter is John’s teacher (Verifier). Peter has many students and John is only one of them. Peter released some homework but he needed to leave campus for a while so he cannot grade students’ homework. Peter wants his students to finish homework before due (during his leave) and when he came back, all students can prove to Peter that they finished their homework before due. However, there are some restrictions regarding how students can prove their homework finishing time:

Homework is individual, no communication is allowed between students
Students cannot communicate with Peter during his leave

John soon realized that it was impossible to prove without an external authority. He discussed with Peter and Peter allowed students to use an authority on the Internet provided by you. However, the authority must follow some rules:

Students cannot send anything to the authority, except for sending some GET requests anonymously. The get requests headers cannot contain any information except a session id the server returns
The server (authority) HTTP session policy: generate a unique session id to every time the user requests, and expire it in a few minutes (e.g. 5 minutes)
When the server expires a session, all data generated by this session will be deleted
In any session, a user cannot send requests more than $C$ times ( $C$ is a pre-decided small constant, e.g. 8, this is used to prevent you from encoding message into binary)
When sending the request, the authority can respond any data (e.g. return a program that can be run on student’s computer)
Peter can only communicate with the authority after he came back
There might be other people accessing the authority
The lag between the client and the authority is stable and small (two requests need almost same time to reach the authority)

We need to design the authority server and give it to Peter. How can we design it so that John could prove that he did his homework before due and Peter could verify his statement (with low P value)?

Hint

At first glance, it seems impossible to get a certificate for John that could work after a lot of days because the things you know in the future completely contain what you know in the past.

For example, if you get some data $I$ from the authority before due, then through some calculation you get $f (I, m)$ where $m$ is your homework, then after a few days you can still calculate $f (I, m^{'})$ where $m^{'}$ is a modified homework, if $f$ doesn’t bring any side-effects.

Therefore we can bring some side-effects to $f$ .

Solution

The authority has a secret bijection between server time (in milliseconds) with session ID and some encrypted text:

f_{s} : Time \times SessionID \to String

g_{s} = f_{s}^{- 1}

The authority provides $g_{s}$ as a black box program to the verifiers.

When the user sends a GET request, the server starts a session with the user and only allow $C$ requests in this session.

Moreover, in this session, the user can only send one request in 33 seconds (otherwise simply returns 404).

On receiving a GET request in session $s$ , the server immediately returns $t$ and $f_{s} (t, s)$ where $t$ is current server time.

Let Peter prepares a public hash function $h (m, s)$ that hashes message $m$ with salt $s$ to an integer $x \in [0, 2^{15}]$ .

When John finished his homework $w$ before due, he first sent a GET request to the authority at time $l_{0}$ (local time) to get a server time $t_{1}$ and a string $r_{1}$ .

Then he immediately calculated $c_{1} = h (w, r_{1})$ and sent a GET request at $l_{0} + 33000 + c_{1}$ time. He got a server time $t_{2}$ and a string $r_{2}$ .

Similarly, he immediately calculated $c_{2} = h (w, r_{2})$ and sent a GET request at $l_{0} + 33000 \times 2 + c_{2}$ time. Repeatedly, he can finally calculate $c_{7}$ in the 8-th request.

John can use all $c_{i}$ s, $t_{i}$ s and $r_{i}$ s along with his session ID $s$ as certificates.

To verify the certificate $(C, T, R, s)$ matches the homework $w$ , simply run $g_{s}$ on all $r_{i}$ s and check if $c_{i}$ s and $t_{i}$ s are correct.

Vulnerability

Assume that John didn’t complete his homework before due and tries to use an alternative homework $w^{'}$ . Now let’s estimate how difficult it is to generate a correct certificate for $w^{'}$ .

The only way to crack this method is to send requests at random time and try to create a hash conflict.

He need to run approximately $(2^{15})^{7} = 2^{105}$ tests to find a conflict and it’s very unlikely to happen in a short time.