CryptoDB
Pratish Datta
NOTE: imports for ToSC and TCHES are no longer functioning.
ORCID: 0000-0002-3938-7594
Publications
Year
Venue
Title
2023
PKC
Decentralized Multi-Authority Attribute-Based Inner-Product FE: Large Universe and Unbounded
Abstract
This paper presents the first decentralized multi-authority attribute-based inner product functional encryption (MA-ABIPFE) schemes supporting vectors of a priori unbounded lengths. The notion of AB-IPFE, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption (ABE) with the possibility of evaluating linear functions on encrypted data. A decentralized MA-ABIPFE defined by Agrawal et al. [TCC 2021] essentially enhances the ABE component of AB-IPFE to the decentralized multi-authority setting where several authorities can independently issue user keys involving attributes under their control. In MA-ABIPFE for unbounded vectors (MA-ABUIPFE), encryptors can encrypt vectors of arbitrary length under access policies of their choice whereas authorities can issue secret keys to users involving attributes under their control and vectors of arbitrary lengths. Decryption works in the same way as for MA-ABIPFE provided the lengths of the vectors within the ciphertext and secret keys match.
We present two MA-ABUIPFE schemes supporting access policies realizable by linear secret sharing schemes (LSSS), in the significantly faster prime-order bilinear groups under decisional assumptions based on the target groups which are known to be weaker compared to their counterparts based in the source groups. The proposed schemes demonstrate different trade-offs between versatility and underlying assumptions. The first scheme allows each authority to control a bounded number of attributes and is proven secure under the well-studied decisional bilinear Diffie-Hellman (DBDH) assumption. On the other hand, the second scheme allows authorities to control exponentially many attributes, that is, supports large attribute universe, and is proven secure under a non-interactive q-type variant of the DBDH assumption called L-DBDH, similar to what was used in prior large-universe multi-authority ABE (MA-ABE) construction.
When compared with the only known MA-ABIPFE scheme due to Agrawal et al. [TCC 2021], our schemes offer significantly higher efficiency while offering greater flexibility and security under weaker assumptions at the same time. Moreover, unlike Agrawal et al., our schemes can support the appearance of the same attributes within an access policy arbitrarily many times. Since efficiency and practicality are the prime focus of this work, we prove the security of our constructions in the random oracle model against static adversaries similar to prior works on MA-ABE with similar motivations and assumptions. On the technical side, we extend the unbounded IPFE techniques of Dufour-Sans and Pointcheval [ACNS 2019] to the context of MA-ABUIPFE by introducing a novel hash-decomposition technique.
2023
EUROCRYPT
Fully Adaptive Decentralized Multi-Authority ABE
Abstract
Decentralized multi-authority attribute-based encryption (MA-ABE) is a distributed generalization of standard (ciphertext-policy) attribute-based encryption where there is no trusted central authority: any party can become an authority and issue private keys, and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters.
We present the first multi-authority attribute-based encryption schemes that are provably fully-adaptively secure. Namely, our construction is secure against an attacker that may corrupt some of the authorities as well as perform key queries adaptively throughout the life-time of the system. Our main construction relies on a prime order bilinear group where the k-linear assumption holds as well as on a random oracle. Along the way, we present a conceptually simpler construction relying on a composite order bilinear group with standard subgroup decision assumptions as well
as on a random oracle.
Prior to this work, there was no construction that could resist adaptive corruptions of authorities, no matter the assumptions used. In fact, we point out that even standard complexity leveraging style arguments do not work in the multi-authority setting.
2023
JOFC
Decentralized Multi-authority ABE for $\textsf{NC}^1$ from BDH
Abstract
Decentralized multi-authority attribute-based encryption ( $$\textsf{MA}$$ MA - $$\textsf{ABE}$$ ABE ) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: Any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first $$\textsf{MA}$$ MA - $$\textsf{ABE}$$ ABE proven secure under the standard search variant of bilinear Diffie–Hellman ( CBDH ) and in the random oracle model. Our scheme supports all access policies captured by $$\textsf{NC}^1$$ NC 1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard q -type assumptions, or subspace decision assumptions over composite-order bilinear groups.
2022
ASIACRYPT
Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH
📺
Abstract
Thispaperpresentsthefirstfunctionalencryption(FE)scheme for the attribute-weighted sum (AWS) functionality that supports the uniform model of computation. In such an FE scheme, encryption takes as input a pair of attributes (x, z) where the attribute x is public while the attribute z is private. A secret key corresponds to some weight function f, and decryption recovers the weighted sum f(x)z. This is an important functionality with a wide range of potential real-life applications, many of which require the attribute lengths to be flexible rather than being fixed at system setup. In the proposed scheme, the public attributes are considered as binary strings while the private attributes are considered as vectors over some finite field, both having arbitrary polynomial lengths that are not fixed at system setup. The weight functions are modelled as Logspace Turing machines.
Prior schemes [Abdalla, Gong, and Wee, CRYPTO 2020 and Datta and Pal, ASIACRYPT 2021] could only support non-uniform Logspace. The proposed scheme is built in asymmetric prime-order bilinear groups and is proven adaptively simulation secure under the well-studied symmetric external Diffie-Hellman (SXDH) assumption against an arbitrary polynomial number of secret key queries both before and after the challenge ciphertext. This is the best possible level of security for FE as noted in the literature. As a special case of the proposed FE scheme, we also obtain the first adaptively simulation secure inner-product FE (IPFE) for vectors of arbitrary length that is not fixed at system setup.
On the technical side, our contributions lie in extending the techniques of Lin and Luo [EUROCRYPT 2020] devised for payload hiding attribute-based encryption (ABE) for uniform Logspace access policies avoiding the so-called “one-use” restriction in the indistinguishability-based security model as well as the “three-slot reduction” technique for simulation- secure attribute-hiding FE for non-uniform Logspace devised by Datta and Pal [ASIACRYPT 2021] to the context of simulation-secure attribute- hiding FE for uniform Logspace.
2021
EUROCRYPT
Decentralized Multi-Authority ABE for DNFs from LWE
📺
Abstract
We construct the first decentralized multi-authority attribute-based
encryption (????????-????????????) scheme for a non-trivial class of access policies
whose security is based (in the random oracle model) solely on the
Learning With Errors (LWE) assumption. The supported access policies
are ones described by ???????????? formulas. All previous constructions of
????????-???????????? schemes supporting any non-trivial class of access policies were
proven secure (in the random oracle model) assuming various assumptions
on bilinear maps.
In our system, any party can become an authority and there is no requirement
for any global coordination other than the creation of an initial
set of common reference parameters. A party can simply act as a standard
ABE authority by creating a public key and issuing private keys to
different users that reflect their attributes. A user can encrypt data in
terms of any ???????????? formulas over attributes issued from any chosen set of
authorities. Finally, our system does not require any central authority.
In terms of efficiency, when instantiating the scheme with a global bound
???? on the size of access policies, the sizes of public keys, secret keys, and
ciphertexts, all grow with ????.
Technically, we develop new tools for building ciphertext-policy ABE
(????????-????????????) schemes using LWE. Along the way, we construct the first
provably secure ????????-???????????? scheme supporting access policies in ????????^1 under
the LWE assumption that avoids the generic universal-circuit-based
key-policy to ciphertext-policy transformation. In particular, our construction
relies on linear secret sharing schemes with new properties and
in some sense is more similar to ????????-???????????? schemes that rely on bilinear
maps. While our ????????-???????????? construction is not more efficient than existing
ones, it is conceptually intriguing and further we show how to extend it
to get the ????????-???????????? scheme described above.
2021
ASIACRYPT
(Compact) Adaptively Secure FE for Attribute-Weighted Sums from k-Lin
📺
Abstract
This paper presents the first adaptively simulation secure functional encryption (FE) schemes for attribute-weighted sums. In such an FE scheme, encryption takes as input N pairs of attribute {(x_i, z_i )}_{i \in [N]} for some N \in \mathbb{N} where the attributes {x_i}_{i \in [N]} are public while the attributes {z_i}_{i \in [N]} are private. The indices i \in [N] are referred to as the slots. A secret key corresponds to some weight function f, and decryption recovers the weighted sum \sum_{i \in [N]} f(x_i)z_i. This is an important functionality with a wide range of potential real life applications. In the proposed FE schemes attributes are viewed as vectors and weight functions are arithmetic branching programs (ABP). We present two schemes with varying parameters and levels of adaptive security.
(a) We first present a one-slot scheme that achieves adaptive security in the simulation-based security model against 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. From the relations between the simulation-based and indistinguishability-based security frameworks for FE, it follows that the proposed FE scheme also achieves indistinguishability- based adaptive security against an a-priori unbounded number of ciphertext queries and an arbitrary polynomial number of secret key queries both before and after the ciphertext queries. Moreover, the scheme enjoys compact ciphertexts that do not grow with the number of appearances of the attributes within the weight functions.
(b) Next, bootstrapping from the one-slot scheme, we present an unbounded-slot scheme that achieves simulation-based adaptive security against a bounded number of ciphertext and pre-ciphertext secret key queries while supporting an a-priori unbounded number of post-ciphertext secret key queries. The scheme achieves public parameters and secret key sizes independent of the number of slots N and a secret key can decrypt a ciphertext for any a-priori unbounded N. Further, just like the one-slot scheme, this scheme also has the ciphertext size independent of the number of appearances of the attributes within the weight functions. However, all the parameters of the scheme, namely, the master public key, ciphertexts, and secret keys scale linearly with the bound on the number of pre-ciphertext secret key queries.
Our schemes are built upon asymmetric bilinear groups of prime order and the security is derived under the standard (bilateral) k-Linear (k-Lin) assumption. Our work resolves an open problem posed by Abdalla, Gong, and Wee in CRYPTO 2020, where they presented an unbounded-slot FE scheme for attribute-weighted sum achieving only semi-adaptive simulation security. At a technical level, our work extends the recent adaptive security framework of Lin and Luo [EUROCRYPT 2020], devised to achieve compact ciphertexts in the context of indistinguishability-based payload-hiding security, into the setting of simulation-based adaptive attribute-hiding security.
2019
PKC
Efficient Attribute-Based Signatures for Unbounded Arithmetic Branching Programs
Abstract
This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP’s, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending and refining the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP’s, which themselves are of unbounded size and input length.
2018
PKC
Full-Hiding (Unbounded) Multi-input Inner Product Functional Encryption from the k-Linear Assumption
Abstract
This paper presents two non-generic and practically efficient private key multi-input functional encryption (MIFE) schemes for the multi-input version of the inner product functionality that are the first to achieve simultaneous message and function privacy, namely, the full-hiding security for a non-trivial multi-input functionality under well-studied cryptographic assumptions. Our MIFE schemes are built in bilinear groups of prime order, and their security is based on the standard k-Linear (k-LIN) assumption (along with the existence of semantically secure symmetric key encryption and pseudorandom functions). Our constructions support polynomial number of encryption slots (inputs) without incurring any super-polynomial loss in the security reduction. While the number of encryption slots in our first scheme is apriori bounded, our second scheme can withstand an arbitrary number of encryption slots. Prior to our work, there was no known MIFE scheme for a non-trivial functionality, even without function privacy, that can support an unbounded number of encryption slots without relying on any heavy-duty building block or little-understood cryptographic assumption.
2018
ASIACRYPT
Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption
Abstract
This paper demonstrates how to achieve simulation-based strong attribute hiding against adaptive adversaries for predicate encryption (PE) schemes supporting expressive predicate families under standard computational assumptions in bilinear groups. Our main result is a simulation-based adaptively strongly partially-hidingPE (PHPE) scheme for predicates computing arithmetic branching programs (ABP) on public attributes, followed by an inner-product predicate on private attributes. This simultaneously generalizes attribute-based encryption (ABE) for boolean formulas and ABP’s as well as strongly attribute-hiding PE schemes for inner products. The proposed scheme is proven secure for any a priori bounded number of ciphertexts and an unbounded (polynomial) number of decryption keys, which is the best possible in the simulation-based adaptive security framework. This directly implies that our construction also achieves indistinguishability-based strongly partially-hiding security against adversaries requesting an unbounded (polynomial) number of ciphertexts and decryption keys. The security of the proposed scheme is derived under (asymmetric version of) the well-studied decisional linear (DLIN) assumption. Our work resolves an open problem posed by Wee in TCC 2017, where his result was limited to the semi-adaptive setting. Moreover, our result advances the current state of the art in both the fields of simulation-based and indistinguishability-based strongly attribute-hiding PE schemes. Our main technical contribution lies in extending the strong attribute hiding methodology of Okamoto and Takashima [EUROCRYPT 2012, ASIACRYPT 2012] to the framework of simulation-based security and beyond inner products.
Program Committees
- Crypto 2024
Coauthors
- Pratish Datta (11)
- Ratna Dutta (2)
- Ilan Komargodski (3)
- Sourav Mukhopadhyay (2)
- Tatsuaki Okamoto (3)
- Tapas Pal (3)
- Katsuyuki Takashima (3)
- Junichi Tomida (1)
- Brent Waters (3)