# About numberical comparison in Attribute based encryption

The first CP-ABE scheme in [BSW07] gave an example how to present a numberical comparison (e.g., a<11) to a Boolean access tree. But it seems like this feature is not implemented in Charm.

In the paper, the access policy a<11 is presented as:

("0***" OR ("*0**" AND ("**0*" OR "***0")))


And one attribute a=9 is split to 4 attributes for encryption:

"1***", "*0**", "**0*" and "***1".


My question is:

1. Is it true that the access policy only use "0" bit string? If yes, it is safe enough to encrypt the message with 2 attributes "*0**" and "**0*" (i.e., "1***" and "***1" are not needed)?

2. Do you know a reference that describes how the choice of gates are made?

• Why "no"? since the comparison a < 11 only presented by 0 and *. – Tri Vo Hoang Sep 11 '17 at 11:12

1. Is it true that the access policy only use "0" bit string? If yes, it is safe enough to encrypt the message with 2 attributes *0** and **0* (i.e., 1*** and ***1 are not needed)?

First off, a numerical attribute such as *0** is nothing more than the ASCII string "*0**" which is then hashed.

The following is a user's secret key:

$$\text{SK}=\left(D=g^{\left(\alpha +r\right)/\beta}, \forall j\in S:D_j=g^r\cdot H\left(j\right)^{r_j}, D^{'}_j=g^{r_j}\right)$$

All $r$ and $r_j$ are chosen randomly and independently which means that the attributes ($D_j$ and $D^{'}_j$) of a secret key are not linked together in any way.

A user can or the attribute authority can safely remove multiple attributes without invalidating the whole key. The remaining attributes can still be used to decrypt ciphertexts provided that the remaining attributes satisfy the access policy. This is true for (almost?) all schemes that utilize monotonic access structures as is the case with BSW-ABE.

However, this cannot be true for schemes that utilize non-monotonic access structures. Such access structures can be used to model negation of attributes. In such schemes, all attributes are linked together. If they weren't, then it would be possible for a use to remove a negated attribute and be able to decrypt more ciphertexts.

1*** and ***1 are not needed to satisfy the policy: a<11. However, if the attribute authority removes all attributes containing a 1, then it would limit the expressiveness of the access policy. Furthermore, access policies containing attributes with a 1 can be reduced to improve the policy evaluation performance.

1. Do you know a reference that describes how the choice of gates are made?

This is off-topic. I don't know a natural language description of this, but you can certainly try to deduce the algorithm by looking at the code. cpabe has the original implementation of that in C and JCPABE has an extended implementation of that in Java.