Structural Testing with Homomorphic Encryption

This paper introduces a novel theoretical framework to enhance black-box testing through structural guarantees. We define a structural specification for a program as a set of permissible algebraic operations, and the program under test must be equivalent to one constructed solely from these operations. We design a protocol that facilitates validation of structural specifications in black-box setting. To achieve this, we leverage a model of homomorphic encryption, which encompasses cryptographic schemes based on algebraic isomorphisms. Furthermore, we show that our protocol can potentially invalidate upper-bounds on polynomial degrees in a single query, representing a significant improvement over methods that rely on input-output pairs of a program. This work showcases a novel application of homomorphic encryption and makes a case for the development of encryption schemes for arbitrary algebras.