Is there an efficient algorithm for the tagging and location of information over an insecure channel, where two parties (the tagger and the intended recipient for the tag) can recognize a piece of information has been tagged, but it looks like random data to an outside observer?
Preferably not something linear, maybe O(log n) instead.
- A professor has multiple classes full of students, and would like to publish the set of grades for every piece of homework a student has submitted over the last 10 years. The professor wants the grades to be visible to the public so that analysis can be run on them. (e.g. to show how certain classes might be doing better than others)
- The professor would also like to tag each grade with a code so that each student can recognize which grade is theirs, but could not tell which grade belonged to another person. An attacker should not be able to establish that a set of grades belongs to the same individual through this tag.
- For reasons (and that I can't come up with a better example), the professor and students can only communicate through an insecure channel to establish this tag.
I understand that asymmetric encryption can be used here, but having each "student" run a check on millions/billions of entries to figure out which "grades" are theirs will be too computationally costly.