How to share a function securely

Abstract

We define the primitive of function sharing, a functional analog of secret sharing, and employ it to construct novel cry ptosy stems. The basic idea of function sharing is to split a hard to compute (trapdoor) function into shadow functions (or share-functions). The intractable function becomes easy to compute at a given point value when given any threshold (at least t out of l) of shadow functions evaluations at that point. Otherwise, the function remains hard. Furthermore, the function must remain intractable even after exposing up to t - 1 shadow functions and exposing values of all shadow functions at polynomially many inputs. The primitive enables the distribution of the power to perform cryptography (signature, decryption, etc.) to agents. This enables the design of various novel cryptosyslems with improved integrity, availability and security properties. Our model should be contrasted with the model of secure function evaluation protocols. We require no channels between agents holding the shadow functions, as the agents act non-interactively on a publicly available input. Our security solely relies on secure memories (and results) as in regular cryptosystems. In secure function evaluation, on the other hand, it is necessary to have private/ secured bilateral channels, interactive protocol, and security of all inputs - in addition to secure memories.