RSA multiple record parametric authentication scheme

We consider the problem of authentication of an arbitrary record of a fixed set without the need to verify the entire data set. A formal model of two-way interaction of the input parties $S$ and $C$ is proposed, in which $S$ stores a set of records and generates authentication parameters; $C$ implements the authentication of individual records based on the provided arguments. A number of algorithms required for authentication are described. As a practical implementation, a parametric RSA authentication scheme for a set of records is demonstrated, which, in contrast to the classical approach with storing hash values, provides a constant authentication time and a fixed size of the data required to authenticate a record. An estimate of the computational complexity of the used algorithms is provided.