A digital watermark extracting apparatus that extract a watermark hidden in host data is provided. A location information generator generates a plurality of candidate watermark locations according to a secret key. An extractor extracts from each of the candidate watermark locations a watermark which has been embedded in a watermarked host signal and detects a soft decision value on the extracted watermark. A decision value evaluator evaluates a sum of the absolute values of the components of the each soft value. A selector determines a true watermark location according to the soft decision value evaluated by the decision value evaluator. The selector provides to an ECC decoder the soft decision value on the watermark extracted from the true watermark location. The ECC decoder error-correction decodes the soft decision value on the extracted watermark and outputs watermark information.