[wtlguzdc] Hiding a circle in a grid

Draw a large circle on a large grid of squares, and note which squares the circle passes through.

Color some of the squares in the grid in an almost uniform random pattern.  The only constraint is squares on the circle path may not be colored.  Next, erase the circle.

How computationally difficult is it to recover the original circle from the pattern of colored and uncolored squares?  What density should the coloring be to maximize difficulty while avoiding lots of spurious solutions?  How does the difficulty change with shapes other than a circle?  Three or more dimensions?

Can this be the basis for a public-key cryptography algorithm (the hidden circle is the private key)?

Yet another inspiration from bathroom tiles.