| Title | : | Functional Encryption and Indistinguishability Obfuscation for Turing Machines from (Nearly) Minimal Assumptions |
| Speaker | : | Monosij Maitra (IIT Madras) |
| Details | : | Tue, Jul 17, 2018 3:00 PM, @ Turing Hall |
| Abstract | : | Functional Encryption (FE) is a generalisation of public key encryption (PKE) enabling fine grained access control on encrypted data. Traditional PKE allows issuing only secret keys that enable decryption of a ciphertext CT(m) to retrieve either the encoded message m or nothing else. FE aims to give out secret keys corresponding to functions f from a class of functions F and ciphertexts correspond to messages m from the domain M of f. Given such a function key and a FE ciphertext CT(m), it enables the decryptor to learn f(m) and nothing else. Naturally enough the idea of FE has a lot of applications in todays scenario of cloud computing. Program obfuscation aims to alter a program into an unintelligible one such that its functionality is still preserved. While the most natural idea of program obfuscation, called Virtual Black-box obfuscation, was shown to be impossible for all functions, a weaker version of this notion called Indistinguishability obfuscation (iO) requires that obfuscation of any two functionally equivalent circuits of same size are computationally indistinguishable. Although non-obvious, iO has been shown to be a very powerful notion in the last decade resulting in various practical and theoretical applications in cryptography that were almost out of reach before its advent. FE for circuits has been shown to imply iO with a sub-exponential loss in reduction and iO is also widely believed to be an inherently sub-exponential assumption. Therefore, replacing applications of iO by polynomially secure FE has garnered a lot of interest recently with extensive results. Another interesting direction initiated by Goldwasser et. al. [GKP+13] that has also seen further substantial research efforts is that of modelling functions as Turing machines and Random Access machines instead of circuits. Such a representation leads to direct advantages like supporting unbounded inputs, fixed description size and input specific runtimes. Our results in the above context are as follows: 1. We construct iO for Turing machines with bounded inputs from the same assumptions as required in the circuit model, namely, sub-exponentially secure FE for circuits. The previous best constructions [KLW15, AJS17] require sub-exponentially secure iO for circuits, which in turn requires sub-exponentially secure FE for circuits [AJ15, BV15]. 2. We provide a new construction of single input FE for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact FE for circuits. The previously best known construction by Ananth and Sahai [AS16] relies on iO for circuits, or equivalently, sub-exponentially secure FE for circuits. 3. We provide a new construction of Multi-input FE for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string x_i of unbounded length. We rely on sub-exponentially secure FE for circuits, while the only previous construction [BGJS15] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation (pc-diO). All our results require a mild assumption of decomposability on the underlying circuit FE schemes. Roughly speaking, a decomposable FE scheme asserts a long string to be encrypted bit-by-bit, using shared randomness across bits. This property is already satisfied by almost all existing circuit FE schemes to the best of our knowledge. Our techniques are new and from first principles, and avoid usage of sophisticated iO specific machinery that were used in all relevant prior work. |