A data processing apparatus includes, an input unit to accept information on one or more deletion-target data blocks specified from a plurality of data blocks, a hash generating unit to calculate a hash value of each of the plurality of data blocks, an auxiliary data generating unit to calculate auxiliary data β=gH1(mod N) of a signer based on predetermined values g and N and a product H1 of the hash values of one or more deletion-target data blocks, a digital signature generating unit to calculate intermediate data α=gH2(mod N) based on the predetermined values g and N and a product H2 of the hash values of one or more remaining data blocks to generate a digital signature for a combination of the intermediate data α and position data of one or more deletion-target data blocks with a signing key of a modifier.