This paper was first published in the Communications Security Establishment's Proceedings of the 10th Annual Canadian Information Technology Security Symposium, pages 397-410, where it won the Best 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.

Abstract

Applications are described for blind substring search, where a program to search files for a substring is published without revealing the substring. 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.

Download the complete paper in gzipped Postscript format (46K) or PDF (145K).

Resources

  • NEW - Finding Naked People. From the abstract: "This paper demonstrates an automatic system for telling whether there are naked people present in an image." It flags 43% of nudity and 4% of non-nudity; phenomenally good performance considering the difficulty of the problem, but nowhere near good enough to be useful in censorware.
  • Under the terms of my out-of-court settlement with Microsystems Software Inc. and Mattel Inc., I am no longer distributing the essay The Breaking of Cyber Patrol® 4 and related software, which I co-wrote with Eddy L. O. Jansson and which used to be linked from here. Sorry. I'm also not (and never was) distributing the decrypted Cyber Patrol blocking list. Any "mirror" sites or other copies of that stuff which may exist on the Net, are not authorized by me.
  • ICQ pirates CYBERsitter story from Peacefire (File 4 in the linked document). ICQ99, which includes text-filtering features, apparently is using CYBERsitter's blocking list, obtained by cryptanalysis.
  • Nonlinearity criteria of Boolean functions by Hirose and Ikeda, my reference [2]. Includes a good overview of previous work on the topic.
  • Blind substring searching - some half-formed notes I posted to Usenet.
  • Letter to Brian Milburn (of Solid Oak Software) from J. S. Tyre. (File 2 in the linked document.) My reference [7]; a witty exploration of the limitations of current blocking software security mechanisms.
  • Peacefire and ASFAR - activist organizations that inspired my work.
  • Age discrimination links - part of my own contribution to youth rights activism.
Related pages:

Comments

No comments yet.

New comments are disabled, pending transition to new site code.
Copyright 2017 Matthew Skala
Updates to this site: [RSS syndication file]