Linsy's 2-ng blog

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

Last update:
Publish date:
Reading time: 5 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:

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:

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:

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 × SessionID 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 [ 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 × 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.