1
$\begingroup$

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.

Example:

  1. 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)
  2. 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.
  3. 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.

$\endgroup$
  • $\begingroup$ Unless I've gotten something wrong, it would have to be at the minimum O(n). This is simply because you have to read the entire tag to check it. $\endgroup$ – Daffy Jun 25 '17 at 5:21
  • $\begingroup$ I was thinking there might be some efficient tree scheme that might be used to find which tags belong to a certain "student" quickly. Honestly, I'm not sure either, which is why I wanted to ask, but it's entirely possible it must be O(n). $\endgroup$ – Miku Jun 25 '17 at 6:29
  • $\begingroup$ If you loosen your requirement for an insecure channel and allow the teacher and students to exchange a single key securely, then this can easily be done. Store the grades along with the tag and a random "salt" value. Then use a KDF to derive a new key from the original key and the salt (this prevents key reuse). Use this derived key to calculate a MAC (the tag) for the grades. The resulting MACs will look random to all students except the ones relating to their own grades. $\endgroup$ – Daffy Jun 25 '17 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.