1. A method for embedding a structured watermark into data, defined by a plurality of samples, wherein the data has a format for a frequency domain representation of the data comprising an ordered set of a plurality of frequency domain values, the method comprising: defining, in a memory device, an ordered set of variations to be applied to the frequency domain values, wherein each variation has a value defined by the structured watermark; defining, in a memory device, an irregular mapping from positions in the ordered set of variations to positions in the ordered set of frequency domain values, wherein the irregular mapping is independent of the frequency domain values; and using a processor connected to the memory device, modifying, without overwriting, each frequency domain value by the variation mapped by the irregular mapping to the position of the frequency domain value in the ordered set of frequency domain values.