This paper was first published in the
Establishment's Proceedings of the 10th Annual Canadian Information
Technology Security Symposium, pages 397-410, where it won the
Student Paper award. I'm putting it online here to make it easy for
people to find. I couldn't have written it without similarly web-available
material from others. Comments and questions by
email are welcome.
If you got to this page by following a "youth rights" link and you're wondering what this boring mathematics has to do with youth rights, it's actually pretty simple. There was a fuss a while ago when it was discovered that Cybersitter anti-porn "filter" software used a pathetically weak form of encryption to prevent people from reading the list of sites it blocks. A teenager published that fact, and people used the information to read the list of blocked sites, and they discovered that Cybersitter blocked a number of sites that one would not ordinarily consider to be pornography, and there was an even bigger fuss. That got me thinking. Obviously the makers of Cybersitter should have used stronger encryption if they wanted to keep their hidden agenda hidden... but actually, no ordinary encryption would have been enough because it could be reverse engineered by the same folks who break copy protection. I wondered if there was some kind of technique that Cybersitter could have used that would have been immune to reverse engineering, and this paper is the result. If you think it's unethical of me to give them ideas, look at it this way: someone was bound to think of this problem sooner or later, and wouldn't you rather it be me instead of them? Because I'm the one making this public, nobody can use it in blocking software without looking really silly.
Those of you who came here from an academic direction, please excuse the political digression, but I do hope you'll think about the political implications as well as the math. Hardy was wrong. Mathematics does not exist in a vacuum. It's not at all isolated from the sordid world we live in. But that fact doesn't drag math down. It elevates the world.
Applications are described for
blind substring search, where a
program to search files for a substring is published without revealing the
limited diffusion approach proposed in a previous
article is described. Design criteria for a boolean function to be used in
the limited diffusion algorithm are discussed, and a function meeting the
criteria is proposed. Other factors affecting the security of the algorithm
are discussed. An algorithm for blind substring search is developed, and
results of tests on the algorithm are presented.