From: rpw3@rigden.wpd.sgi.com (Rob Warnock)
Newsgroups: sci.crypt
Subject: Re: Random-dot stereograms
Date: 8 Apr 92 04:58:20 GMT
Article-I.D.: sgi.j98fm2s
Organization: Silicon Graphics, Inc.  Mountain View, CA

+---------------
| richard@aiai.ed.ac.uk (Richard Tobin) writes:
| > The recipient would be provided in advance with one half of the
| > stereogram, and the other half would be constructed when needed.  
+---------------

Cute! I like it!

graham@sees.bangor.ac.uk (The Land of Confusion) writes:
+---------------
| As the information in a random dot stereogram is stored in the disparities
| between corresponding dots in the pair of images, isn't it necessary to
| have the plain text in advance of constructing *both* images? This seems
| to indicate that the `key' half is not in fact independent of the information 
| to be securely transmitted and could therefore not be provided `in advance'.
+---------------

No, not at all. The "key" image *can* be pre-computed, and indeed can be
used as the "key" for several coded images. [Hey, this is neat!]

You're thinking of a *particular* implementation which, given two copies
of the random background, initially identical, encodes the stereogram by
displacing dots from each copy in opposite directions, filling in "exposed"
area with "new" random dots. That is, take pixel {x,y} and move it to {x+d,y}
in the left picture and {x-d,y} in the right, replacing {x,y} in each picture
with a new random pixel, *different* in each picture [provided, of course,
that {x,y} is not also part of the "elevated" portion of the picture]. This
is indeed the easiest way to think of the process, and the simplest to code.

But consider another way of doing it. Again, start with two identical copies
of a background image, but initialize the background to the "key" image. As
we proceed, only one of the images will be changed, and the other will remain
constant. Let's assume the "key" is the left image. To code the "text", copy
the pixel {x+d,y} from the left picture into {x-d,y} in the right picture, and
substitute a new random pixel for {x,y} in the right picture only [again, only
if {x,y} is not also part of the elevated portion]. A correct *implementation*
of the second method may be a little trickier, but the results are the same.

(In both methods, you have to be a little careful not to add the "new"
random pixels to "exposed" background until you have done all the moving
you're going to do, and then don't step on one of the moved pixels. Small
matter of bookeeping.)

I claim that both methods give identical results in terms of the resulting
correlations between the images *and* in the statistics of the isolated
images. That is, the images of the "key+text" pair are individually "just
as random" as the images of the "text_LEFT/text_RIGHT" pair.

And this is *only* true because the "key" image is truly random. It doesn't
matter whether the {x-d,y} pixel in the "text_RIGHT" is a copy of {x,y} in
some common initial "text_BOTH" background or was copied from "key" {x+d,y}.
It's "just as random" either way.


-Rob

-----
Rob Warnock, MS-9U/510		rpw3@sgi.com
Silicon Graphics, Inc.		(415)335-1673
2011 N. Shoreline Blvd.
Mountain View, CA  94039-7311