A Note On White-Box Implementations for PRPs

White-box cryptography (WBC) for secure pseudorandom permutations (block ciphers) is known as an unsolved long-standing open problem in the cryptographic community, with tremendous real world applications. The most fundamental security notion in WBC is unbreakability (UBK), which guarantees hardness in extracting the embedded secret keys from software implementations of cryptographic primitives running in untrusted environments. In this work we build a compiler, taking a secret key for the block cipher as input, and outputting an UBK-secure implementation. Our starting point explores the ways of attaining such implementations from decomposable functional encryption. Our final construction relies solely on representing functions as branching programs and then post-processing them through randomized encodings. We stress that decomposability plays a fundamental role in ensuring that the block cipher can be evaluated in any specific input. The cost associated to decomposability is reflected in a more convoluted security argument. The one proposed herein relies on the presumed hardness of solving systems of multivariate polynomial equations over finite fields (GF(2)). To the best of our knowledge, such a problem is not known to be tackled by any practical or theoretical, classical or quantum adversaries