Схема параметрической аутентификации RSA множества записей

Рассматривается задача аутентификации произвольной записи фиксированного множества без необходимости верификации всего набора данных. Предлагается формальная модель взаимодействия сторон $S$ и $C$, в которой $S$ осуществляет хранение множества записей и генерацию аутентификационных параметров; $C$ реализует проверку подлинности отдельных записей на основе предоставляемых данных. Описывается ряд алгоритмов, необходимых для аутентификации. В качестве практической реализации демонстрируется схема параметрической аутентификации RSA множества записей, обеспечивающая, в отличие от классического подхода с хранением хеш-значений, константное время проверки подлинности и фиксированный размер данных, необходимых для аутентификации записи. Приводится оценка вычислительной сложности используемых алгоритмов.