In order to add authentication features to this CP-ABE scheme, I have tried to combine it with the ABS scheme proposed by Maji et. al.

I want to use the sign() and verify() algorithms of ABS scheme. But the problem is that the two scheme support different access policy structures; CP-ABE uses access trees to define access policy whereas the ABS uses monotone span program (MSP).

What changes are necessary for the two access policy structures to work together? For example, can I translate an MSP access policy to an access tree?


2 Answers 2


Can the access policies defined using different access structures (Monotone Span Program and Access Trees) be used together in CP-ABE scheme?

Yes. As Attribute-based signcryption with hybrid access policy (Yu and Cao, 2015) shows, it is possible to combine an Attribute-based Encryption scheme with an Attribute-based Signature scheme of different access structures and different flavors. This is commonly referred to as Attribute-based Signcryption.

What changes are necessary for the two access policy structures to work together?

That would be a longer answer along with the necessary security game.

For example, can I translate an MSP access policy to an access tree?

Yes, because a monotone access tree has the same expressiveness as a Monotone Span Program. I don't know whether there is an algorithm for this. It is usually done the other way around. For example, access tree to LSSS is described in Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees (Liu, Cao, Wong, 2010).

Note that a Monotone Span Program (MSP) is equivalent to a Linear Secret Sharing Scheme (LSSS). Again, I'm not sure if there is an algorithm of doing the translation out there.

  • $\begingroup$ I will read the paper you suggested and see how they are combining these two schemes? $\endgroup$
    – Aisha
    Feb 14, 2017 at 14:30
  • $\begingroup$ You can always view MSP as LSSS in order to simplify the implementation. The former is in matrix form while the latter is in polynomial form, and they actually work the same. $\endgroup$
    – Tan
    Jan 7, 2020 at 12:01

There are several issues to consider:

  1. ABE and ABS are meant for complex policies, not authenticated encryption (with a simple all-or-nothing policy for confidentiality and integrity). Thus the policies for both confidentiality and integrity should be assumed to be different anyway.
  2. Each scheme has its own process of translating a standard policy definition language compatible policy description into scheme-level components. It doesn't make much sense to create ABS and ABE-schemes with equivalent translation process and access structure representation for this reason only. Rather, you would use different translation process from one common format policy definition first to the ABE scheme and then to the ABS scheme.
  3. If you are still looking for close enough representations of access structures between ABE and ABS, you should look into ABS/FS-schemes that were derived from corresponding encryption schemes. These include Okamoto & Takashima's decentralized ABS (PKC 2013) and ABS from non-monotone predicates (PKC 2011, from the same authors)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.