Abstract This paper presents the first functional encryption $$(\textsf{FE})$$ ( FE ) scheme for the attribute-weighted sum functionality that supports the uniform model of computation. In such an scheme, encryption takes as input a pair of attributes (x, z) where x is public and z is private. A secret key corresponds to some weight function f, and decryption recovers the weighted sum f(x)z. In our scheme, both the public and private attributes can be of arbitrary polynomial lengths that are not fixed at system setup. The weight functions are modelled as $$\text {Logspace Turing machines}$$ Logspace Turing machines . Prior schemes could only support non-uniform Logspace. The proposed scheme is proven adaptively simulation secure under the well-studied symmetric external Diffie–Hellman assumption against an arbitrary polynomial number of secret key queries both before and after the challenge ciphertext. This is the best possible security notion that could be achieved for . On the technical side, our contributions lie in extending the techniques of Lin and Luo [EUROCRYPT 2020] devised for indistinguishability-based payload hiding attribute-based encryption for uniform Logspace access policies and the “three-slot reduction” technique for simulation-secure attribute-hiding for non-uniform Logspace devised by Datta and Pal [ASIACRYPT 2021] to the context of simulation-secure attribute-hiding for uniform Logspace.

Abstract This paper presents the first attribute-based signature () scheme supporting signing policies representable by Turing machines (), based on well-studied computational assumptions. Our work supports arbitrarys as signing policies in the sense that the s can accept signing attribute strings of unbounded polynomial length and there is no limit on their running time, description size, or space complexity. Moreover, we are able to achieve input-specific running time for the signing algorithm. All other known expressive schemes could at most support signing policies realizable by either arbitrary polynomial-size circuits or s having a pre-determined upper bound on the running time. Consequently, those schemes can only deal with signing attribute strings whose lengths are a priori bounded, as well as suffers from the worst-case running time problem. On a more positive note, for the first time in the literature, the signature size of our scheme only depends on the size of the signed message and is completely independent of the size of the signing policy under which the signature is generated. This is a significant achievement from the point of view of communication efficiency. Our construction makes use of indistinguishability obfuscation () for polynomial-size circuits and certain -compatible cryptographic tools. Note that, all of these building blocks including for polynomial-size circuits are currently known to be realizable under well-studied computational assumptions.

Abstract This paper presents the first adaptively simulation secure functional encryption () schemes for attribute-weighted sums. In the proposed schemes, attributes are viewed as vectors and weight functions are arithmetic branching programs (). We present two schemes with varying parameters and levels of adaptive simulation security. (a) We first present a one-slot scheme supporting a bounded number of ciphertext queries and an arbitrary polynomial number of secret key queries both before and after the ciphertext queries. This is the best possible level of security one can achieve in the adaptive simulation-based framework. The scheme also achieves indistinguishability-based adaptive security against an unbounded number of ciphertext and secret key queries. (b) Next, bootstrapping from the one-slot scheme, we present an unbounded-slot scheme that can support a bounded number of ciphertext and pre-ciphertext secret key queries while supporting an a-priori unbounded number of post-ciphertext secret key queries. Both schemes enjoy ciphertexts that do not grow with the number of appearances of the attributes within the weight functions. The schemes are built upon prime-order asymmetric bilinear groups and the security is derived under the standard (bilateral) k-Linear (k-) assumption. Our work resolves an open problem posed by Abdalla et al (In: CRYPTO, Springer, New York, 2020), where they presented an unbounded-slot scheme for attribute-weighted sum achieving only semi-adaptive simulation security. Technically, we extend the recent adaptive security framework of Lin and Luo (In: EUROCRYPT, Springer, New York, 2020), devised to achieve compact ciphertexts in the context of indistinguishability-based payload-hiding security, to the setting of simulation-based adaptive attribute-hiding security.

This paper demonstrates how to design constrained pseudorandom functions (CPRF) and their various extensions from any public key functional encryption (FE) with standard polynomial security against arbitrary collusions. More precisely, we start by presenting a CPRF construction that supports constraint predicates realizable by arbitrary polynomial-size circuits, based on polynomially-hard public key FE and one way functions. Next, we augment our CPRF construction with the verifiability feature, relying only on a minimal additional assumption, namely, the existence of standard public key encryption (PKE). Finally, we show how to achieve privacy for the issued keys in the context of programable pseudorandom functions (PPRF), which is an enhanced variant of CPRF supporting puncturing constraints, employing polynomially-hard FE and one way functions. All prior works addressing the above problems either work for very restricted settings or rely on highly powerful yet little-understood cryptographic objects such as multilinear maps or indistinguishability obfuscation (IO). Although, there are known transformations from FE to IO, the reductions suffer from an exponential security loss and hence cannot be directly employed to replace IO with FE in cryptographic constructions at the expense of only a polynomial loss. Thus, our results open up a new pathway towards realizing numerous variants of CPRF, which are interesting cryptographic primitives in their own right and, moreover, have already been shown instrumental in a staggering range of applications, both in classical as well as in cutting edge cryptography, based on progressively weaker and well-studied cryptographic building blocks. Our work can also be interpreted as yet another stepping stone towards establishing FE as a substitute for IO in cryptographic applications. In order to achieve our results we build upon the prefix puncturing technique developed by Garg et al. [CRYPTO 2016, EUROCRYPT 2017] [42], [43].