A secure document design has a visible graphical structure that forms part of the aesthetic features on the document and carries encoded message information. A method for generating this design starts with a visible structure used for geometric registration. It then generates a variable auxiliary message comprising message values, and maps the message values to a two dimensional pattern of locations in the visible structure on the document. It repeats the auxiliary message and represents the auxiliary message differently in the two dimensional pattern according to a key. An implementation of this method may be used to create design artwork for printed security documents that is aesthetically pleasing, carries a robust machine readable message, and can be used to authenticate other information on the security document.