An authenticatable device for use with an authentication entity, the authenticatable device comprising: a) a physically-unclonable function, PUF, device having a PUF input and a PUF output and constructed so as to, in response to the input of a specific challenge C, generate an output O that is characteristic to the PUF and the specific challenge C; b) a processor having a processor input that is connected to the PUF output and connectable to the authentication entity and a processor output that is connectable to the authentication entity, the processor configured to: i) in response to the receipt of an output O from the PUF output, generate a commitment value and a helper string that depend upon a private value r, which in turn depends on a random value; and ii) in response to the contemporaneous receipt of an authentication query that includes a nonce and of an output O ' from the PUF output: generate a full block value based on the output O ' , break the full block value into a plurality of subparts and carry out error-correcting code on each of the subparts to reproduce the random value; perform operations as part of an extended Boyko-Peinado-Venkatesan generation on the random value to recover the private value r; and return a zero knowledge proof authentication value that corresponds to the commitment value. a) a physically-unclonable function, PUF, device having a PUF input and a PUF output and constructed so as to, in response to the input of a specific challenge C, generate an output O that is characteristic to the PUF and the specific challenge C; b) a processor having a processor input that is connected to the PUF output and connectable to the authentication entity and a processor output that is connectable to the authentication entity, the processor configured to: i) in response to the receipt of an output O from the PUF output, generate a commitment value and a helper string that depend upon a private value r, which in turn depends on a random value; and ii) in response to the contemporaneous receipt of an authentication query that includes a nonce and of an output O ' from the PUF output: generate a full block value based on the output O ' , break the full block value into a plurality of subparts and carry out error-correcting code on each of the subparts to reproduce the random value; perform operations as part of an extended Boyko-Peinado-Venkatesan generation on the random value to recover the private value r; and return a zero knowledge proof authentication value that corresponds to the commitment value. i) in response to the receipt of an output O from the PUF output, generate a commitment value and a helper string that depend upon a private value r, which in turn depends on a random value; and ii) in response to the contemporaneous receipt of an authentication query that includes a nonce and of an output O ' from the PUF output: generate a full block value based on the output O ' , break the full block value into a plurality of subparts and carry out error-correcting code on each of the subparts to reproduce the random value; perform operations as part of an extended Boyko-Peinado-Venkatesan generation on the random value to recover the private value r; and return a zero knowledge proof authentication value that corresponds to the commitment value. generate a full block value based on the output O ' , break the full block value into a plurality of subparts and carry out error-correcting code on each of the subparts to reproduce the random value; perform operations as part of an extended Boyko-Peinado-Venkatesan generation on the random value to recover the private value r; and return a zero knowledge proof authentication value that corresponds to the commitment value. <EOS>