A cryptographic solution to implement access control in a hierarchy and more.
The need for access control in a hierarchy arises in several different contexts. One such context is managing the information of an organization where the users are divided into different security classes depending on who has access to what. Several cryptographic solutions have been proposed to address this problem --- the solutions are based on generating cryptographic keys for each security class such that the key for a lower level security class depends on the key for the security class that is higher up in the hierarchy. Most solutions use complex cryptographic techniques: integrating these into existing systems may not be trivial. Others have impractical requirement: if a user at a security level wants to access data at lower levels, then all intermediate nodes must be traversed. Moreover, if there is an access control policy that does not conform to the hierarchical structure, such policy cannot be handled by existing solutions. We propose a new solution that overcomes the above mentioned shortcomings. Our solution not only addresses the problem of access control in a hierarchy but also can be used for general cases. It is a scheme similar to the RSA cryptosystem and can be easily incorporated in existing systems.
Figure

1: Enterprise Wide Personnel Hierarchy
2. RELATED WORK
A number of works [1, 2, 6, 9, 12, 14, 18, 23] relating to access
control in a hierarchy have been proposed. In almost all these
works, there is a relationship between the key assigned to a node
and those assigned to its children. The difference between the related
works lie mostly in the different cryptographic techniques
employed for key generation. Some of these techniques [1, 6, 9,
12, 14] are extremely complex. Below we outline a few important
works in this area.
One of the early solutions to the hierarchical access control problem
was proposed by Akl and Taylor [1, 2]. Their solution was
based on the RSA cryptosystem [17]. In this work the authors
choose the exponents in such a way that the key of a child node
can be easily derived from the key of its parent. Mackinnon et
al. [12] gave an optimal algorithm for selecting suitable exponents.
One potential drawback of these schemes is that if a user at a node
wishes to access information stored at a descendant node, he must
traverse all the intermediate nodes between his node and the descendant
node. This may not be very desirable for cases where the
length of the hierarchy is large. Another drawback is that addition
of a new node Ni to the leaf of the hierarchy results in key generation
of all ancestors of Ni.
Sandhu [18] proposed a key generation scheme for a tree hierar-
chy. The solution was based on using different one-way functions
to generate the key for each child node in the hierarchy. The one-way
function was selected based on the name or identity of the
child. When a new child is added, the keys for the ancestors do not
have to be recomputed. This work, however, does not deal for the
case of a general poset. Zheng et al. [23] proposed solutions for
the general poset. The authors present two solutions ? one for indirect
access to nodes (in which to access data at a lower node, the
user has to traverse the intermediate nodes) and the other for direct
access to nodes.
3.

OVERVIEW

OF OUR APPROACH
Our approach is simple. We formulate a new encryption protocol
that is used to encrypt the data stored in a database. The encryption
ensures data integrity as well as data con?dentiality. The data is encrypted
with appropriate keys at the same time it is generated. Different
portions of the database are encrypted with different keys. A
user, who has to retrieve information from the database will attempt
to decrypt the entire database with a decrypting key that is assigned
to him. However, the user is able to decrypt successfully only that
portion(s) of the database for which the user is authorized. The
remaining portion of the database is not decrypted successfully.
Since the access control technology is based on encrypting with
the appropriate key, we ?rst present the theory on which the key
generation is based.
4. THEORY BEHIND THE CRYPTOGRAPHIC
TECHNIQUES
For the following exposition we use the term message to denote
any piece of information that needs to be stored in the database.
De?nition 1. The set of messages M is the set of non negative
integers m that are less than an upper bound N, i.e.
De?nition 2. Given an integer a and a positive integer N,the
following relationship holds,
a qN r where 0 r N and q a N (2)
where x denotes the largest integer less than x.Thevalueqis
referred to as the quotient and r is referred to as the remainder.The
remainder r, denoted a mod N, is referred to as the least positive
residue of a mod N.
De?nition 3. For positive integers a, b and N,wesayais equivalent
to b, modulo N, denoted by a b mod n,ifamod n b mod
n.
De?nition 4. Two integers a, b are said to be relatively prime if
their only common divisor is 1, that is, gcd a b 1.
De?nition 5. The integers n1,n2, ,nkare said to be pairwise
relatively prime,ifgcdni nj 1 for i j.
De?nition 6. The Euler's totient function f N is de?ned as the
number of integers that are less than N and relatively prime to N.
Below we give some properties of totient functions that are of importance

1. f N N1ifNis prime.
2. f N f N1 f N2 fNkif N N1N2 Nkand N1, N2,
,Nkare pairwise relatively prime.
THEOREM 1. Euler's theorem states that for every a and N that
are relatively prime,
a 1modN
PROOF. We omit the proof of Euler's theorem and refer the interested
reader to any book on number theory [13] or cryptography
[20].
COROLLARY 1. If 0 m N and N N1N2 Nkand N1,N2,
,Nk are primes, then mxf
De?nition 7. A key K is de?ned to be the ordered pair e N ,
where N is a product of distinct primes, N M and e is relatively
prime to f N ; e is the exponent and N is the base of the key K.
De?nition 8. The encryption of a message m with the key K THEOREM 3. For any two messages m and m^ , such that m m^
e N , denoted as [m,K], is de?ned as N1 N2,
De?nition 9. The inverse of a key K e N , denoted by
K 1, is an ordered pair d N , satisfying ed 1modfN.
THEOREM 2. For any message m.
where K e N and K 1 d N .
PROOF. We ?rst show that
me mod N K 1 (Def.
me mod N d mod N (Defs. 8,
med mod N (mod arith)
(Defs. 2,
RHS
By symmetry m K 1 K m.
COROLLARY 2. An encryption, m K ,isone-to-one if it satis-
?es the relation
De?nition 10. Two keys K1 e1 N1 and K2 e2 N2
are said to be compatible if e1 e2 and N1 and N2 are relatively
prime.
De?nition 11. If two keys K1 e N1 and K2 e N2
are compatible, then the product key, K1 K2,isde?nedas
eN1N2 .
LEMMA 1. For positive integers a, N1 and N2,
a mod N1N2 a mod N1
PROOF. Let a N1 N2 x are integers.
a mod N1N2 mod N1
N1N2x N1y z N1 N2Nx1N21 y z N1N2 mod N1
N1y z mod N1
z
RHS
a mod N1
N1N2x N1y z mod N1
z
Hence the proof.
where K1 is the key e N1 ,K2is the key e N2 and K1 K2
is the product key e N1 N2 .
PROOF. The proof for (6) is the same as that for (5). We just
consider the proof for (5).
[If part]
Given m m^ we have to prove that
or
me mod N1N2 mod N1 (Def. 8 and Def. 11)
me mod N1 (subs. me for a lemma 1)
R H S m^e mod N1 mod N1
(idempotency of mod op.)
me mod N1 (since m m^,given)
[Only If part]
Given m K1 K2 m^ K1 mod N1,wehavetoprovem m^
me mod N1N2 m^e mod N1 (Defs. 8, 11)
me mod N1 m^e mod N1 mod N1 (lem. 1)
(encryption is one-to-one)
5. KEY GENERATION
Most often in an organization the access requirements match its
hierarchical structure. That is, a person higher up in the hierarchy
will usually have access to the documents that can be accessed by
persons lower in the hierarchy. So we present the key generation
technique for this case ?rst. Later on, we describe how to accomodate
the cases where the access requirement does not follow this
hierarchical pattern.
An organization is usually structured in the form of a hierarchy.
Thus, we de?ne a hierarchy of levels as follows.
De?nition 12. We consider an organization structure that can be
represented as a partially ordered set (poset), L .Lis the set of
levels of the organization and is the dominance relation between
the levels.
1. If Li and Lj are two levels such that Li Lj, then we say that
strictly dominates Li and Li is strictly dominated by Lj.
2. If Li and Lj are two levels such that Li Lj and Lj Li,then
we say that the two levels Li and Lj are equal and denote this
by Li Lj.
3. If levels Li and Lj are such that either Li Lj or Li Lj,
then we say that Li is dominated by Lj or Lj dominates Li
and denote this by Li Lj.
4. Two levels Li and Lj are said to be incomparable if nether
5. We say Ly is a parent of Lx if Lx Ly and there is no element
Lz such that Lx Lz Ly.IfLx Ly,thenLxis said to be a
descendant of Ly and Ly is said to be an ancestor of Lx.
Since the organizational structure is a poset, it can be depicted in
the form of a Hasse diagram [19].
De?nition 13. Each level Li in the organizational hierarchy isassociated with a unique pair of keys, (Ki Ki ) which we term the
default keys for level Li. Ki is the default encryption key of level
Li and Ki 1 is the default decryption key of level Li. If the access
requirements match the hierarchical structure of the organization,
then a person at level Li uses the default encryption key Ki for encrypting
documents and the key K 1 for decrypting the encrypted
documents.
A document encrypted with key Ki possesses the following property

1. it can be decrypted by key K 1 where K 1 is the default
decryption key of level Li,
2. it can be decrypted by key K 1 where K 1 is the default
decryption key of level Lj such that Lj Li.
3. it cannot be decrypted by key K 1 where K 1 is the default
decryption key of level Lk and Lk Li or Lk is incomparable
with Li.
5.1 Determining the Default Encryption Key
and Default Decryption Key
ALGORITHM 1. Default keys generation
Input: (i) L - the set of levels and (ii) - the dominance relation
Output: (i) K - the set containing the default encryption key for
each level and (ii) K 1 - the set containing the default decryption
key for each level.
choose exponent e obeying the requirements in Def. 7
for each Li Ldo
begin
K: K Ki
return K
The default encryption and decryption keys can adequately provide
access control for cases where the access requirements match
the hierarchical structure of the organization.
5.2 Example 1: Student Transcript Informatio

To illustrate our approach we consider an academic organization
? the College of Engineering at some hypothetical university. The
College of Engineering is headed by a Dean. Below the Dean are
the Department Chairpersons who are responsible for managing
the individual departments. Each Faculty (except for cases of joint
appointment) is overseen by the respective Department Chair. The
Students are at the very bottom of this hierarchy. Each student is
advised by one or more faculty members. The organizational hierarchy
is shown in ?gure 2.
Dean
CS Chair ECE Chair
Procedure GenerateDefaultKeys((L,
begin
for each Li Ldo CS Faculty 1 CS Faculty 2 ECE Faculty 1 ECE Faculty 2
while F Ldo
begin
choose a maximal element Li in L F;
for each parent Lj of Li do Student 1 Student 2 Student 3
choose random Ni where gcd Ni factori 1 Figure 2: Access Requirements matching Enterprise Wide Per-
Ni Ni factori sonnel Hierarchy
// Remove factors that have been included multiple times. We need to maintain the information about the transcripts of in-
dividual students. Since this is sensitive information, we need to
while D Ldo protect it. The following are the access requirements.
begin
1. Each student is able to view his or her transcript.
choose a maximal element Li in L D;
for each ancestor Lk of Li do 2. A faculty advising a student is able to see his transcript.
begin
c := no. of distinct paths from Li to Lk 3. The chair of the department in which a student is majoring is
Ni Ni Nk c 1 able to view the student's transcript.
4. The dean is able to view the student's transcript. 3.
For this example, we consider the case for three students, namely,
Student1, Student2, Student3. Each of these students have a faculty
advisor who monitors and advises the student. Student1's advisor
is CS Faculty1. Student2 is co-advised by CS Faculty2 and
ECE Faculty1. Student3's advisor is ECE Faculty2. This is illustrated
in ?gure 2. These are the access requirements for this
example:
4.
1. Student1, CS Faculty1, CS Chair, Dean can view Student1's
transcript.
2. Student2, CS Faculty2, ECE Faculty1, CSChair, ECE Chair,
Dean can view Student2's transcript.
3. Student3, ECE Faculty2, ECE Chair, Dean can view Student3's
transcript.
5.
Note that, in this case the access requirements match the organizational
hierarchical structure. That is, if a person X has access to
some information, then a person Y at a higher level in the hierarchy
will also have access to that information.
5.2.1 Access Control for Example 1
The access control requirement for Example 1 follows the hierarchical
structure of the organization. Thus, using the default encryption
keys the access can be appropriately restricted. Consider 6.
the hierarchy shown in ?gure 2. The keys for the various people
are as follows.
1. The default encryption, decryption keys for Studenti are denoted
respectively by KSi , KSi 1 where 1 i 3.
2. The default encryption, decryption keys for CS Facultyi are
denoted respectively by KCFi , KCF1i where i 1or2.
7.
3. The default encryption, decryption keys for ECE Facultyi
are denoted respectively by KEFi, KEF1i where i 1or2.
4. The default encryption, decryption keys for CS Chair are denoted
respectively by KCChair , KCC1hair .
5. The default encryption, decryption keys for the ECE Chair
are denoted respectively by KEChair , KEC1hair
6. The default encryption, decryption keys for the Dean are de- 8.
noted respectively by KDean, KDe1an.
The key KDean is chosen as per de?nition 7. Once the Dean's
key has been ?xed, the other keys as generated by Algorithm 1 are
as follows:
1. Encryption Key of Dean :
9.
KDean e NDean
Decryption Key of Dean :KDean dDean NDean ,
where e dDean 1modfNDean
2. Default Encryption Key of CS Chair :
KCChair KDean KC ,
Chair
where KC is compatible with KDean
Chair
that is, KCChair e NDean NCChair 10.
Decryption Key of CS Chair :
KCC1hair dCChair NCChair ,
where e dCChair 1modfNChair
Encryption Key of ECE Chair :
KEChair KDean KEChair ,
where KEChair is compatible with KDean
that is, KEChair e NDean NEChair
Decryption Key of ECE Chair :
KEC1hair dEChair NEChair ,
where e dEChair 1modfNEChair
Encryption Key of CS Faculty1 :
KCF1 KCChair KCF1 ,
where KCF1 is compatible with KCChair
that is, KCF1 e NDean NCChair NCF1
Decryption Key of CS Faculty1 :KCF1 dCF1 NCF1 ,
where e dCF1 1modfNCF1
Encryption Key of CS Faculty2 :
KCF2 KCChair KCF2 ,
where KCF2 is compatible with KCChair
that is, KCF2 e NDean NCChair NCF2
Decryption Key of CS Faculty2 :KCF2 dCF2 NCF2 ,
where e dCF2 1modfNCF2
Encryption Key of ECE Faculty1 :
KEF1 KEChair KEF1,
where KEF1 is compatible with KEChair
that is, KEF1 e NDean NEChair NEF1
Decryption Key of ECE Faculty1 :KEF1 dEF1 NEF1 ,
where e dEF1 1modfNEF1
Encryption Key of ECE Faculty2 :
KCF2 KEChair KEF2,
where KEF2 is compatible with KEChair
that is, KCF2 e NDean NEChair KEF2
Decryption Key of ECE Faculty2 :KEF2 dEF2 NEF2 ,
where e dEF2 1modfNEF2
Encryption Key of Student1 :
KS1 KCF1 KS1 , where KS1 is compatible with KCF1
that is, KS1 e NDean NCChair NCF1 NS1
Decryption Key of Student1 :KS1 dS1 NS1 ,
where e dS1 1modfNS1
Encryption Key of Student2 :
KS2 KCF2 KEF1 KS2,
where KS1 is compatible with KCF1 and KEF1
that is, KS2 e NDean NCChair NEChair NCF2 NEF1 NS2
Decryption Key of Student2 :KS2 dS2 NS2 ,
where e dS2 1modfNS2
Encryption Key of Student3 :
KS3 KEF2 KS3,
where KS3 is compatible with KEF2
that is, KS3 e NDean NEChair NEF2N
Decryption Key of Student3 :
KS31 dS3 NS3 ,
where e dS3 1modfNS3
Consider Student1's transcript. If this transcript is encrypted
with key KS1 , then any of the keys KDean, KCChair , KCF1 , KS1 can
be used to decrypt it. Thus all the personnel higher up in the hierarchy
can decrypt this transcript using their own default decryption
key.
5.3 Determining a Customized Encryption Key
As illustrated by Examples 2 and 3, sometimes the access requirement
does not match the organizational structure and then a
different encryption key, which we term customized encryption key,
must be used to protect this information. The decryption key, how-
ever, remains the same.
ALGORITHM 2. Customized encryption key generation
Input: (i) L - the set of levels, (ii) - the dominance relation, (iii)
- the level for which the default encryption key is being gener-
ated, (iv) A - the set of levels that do not dominate Li but who are to
be given access, (v) D - the set of levels that dominate Li and who
are to be denied access, (vi) K - the set of default encryption keys.
Output: Kci - the customized key generated for level Li.
Procedure GenerateCustomEncKey(L, ,Li, D, A, K)
begin
while A allow do
begin
for each Lj A allow that is minimal do
begin
// Deny access to ancestors of Lj
for each parent Lk of Lj do
allow : allow Lj
while D deny do
begin
for each Lj D deny that is minimal do
begin
Give access to ancestors of Lj
for each parent Lk of Lj do
// If Nk has been included multiple times:
for each parent Lk of Lj do
begin
c := no. of paths from Lk to Lj
Kci e Nci
return Kci
Dean
CS Chair ECE Chair
Student 1 Student 1
(CS

Figure

3: Access Requirements for Individual Courses
5.4 Example 2: Individual Course Grade Informatio

The organizational hierarchy in this case is the same as before
(please refer to ?gure 2). We need to maintain information about
the grades each student receives in each of the courses he/she has
taken. The access requirements are complicated in this case:
1. Each student is able to view his or her grades for the courses
he or she has taken.
2. The faculty offering the course is able to see the grades for
all students who have taken the course under the faculty.
3. The chair of the department which has offered the course can
view the grades of the students who have taken that course.
4. A student's advisor is able to see his grades in all the courses.
5. The student's department chair can view the student's grades
for all the courses.
6. The dean is able to view the grades of all students that have
taken a course offered by a department in the college.
Suppose Student1 takes two courses: (i) CS 350 offered by the
Computer Science Department and taught by CS Faculty2 and (ii)
offered by the ECE Department and taught by ECE Faculty1.
This is shown in ?gure 3. Note that ?gure 3 shows only the relevant
portion of the hierarchy given in ?gure 2.
The access requirements are as follows:
1. Student1's CS 350 grade can be viewed by Student1,
CS Faculty1, CS Faculty2, CS Chair, Dean.
2. Student1's ECE 373 grade can be viewed by Student1,
CS Faculty1, ECE Faculty1, ECE Chair, CS Chair, Dean.
Note that, in this case the access requirements do not match
the organizational hierarchy given in ?gure 2. More access is required
than permitted by the organizational hierarchy - for exam-
ple, ECE Faculty1 must be given access to the ECE 373 grades of
Student1.
5.4.1 Access Control for Example 2
In this case the access patterns do not match the organizational
structure. For example, CS Faculty2 must have access to the CS
350 grade of Student1 even though CS Faculty2 is not his advisor.
Thus default keys cannot be used and custom keys are required to
encrypt the grades obtained in the individual courses.
1. Key for encrypting Student1's CS 350 grade:
KcS1 C350 e NDean NCChair NCF1 NCF2 NS1
2. Key for encrypting Student1's ECE 373 grade:
KcS1 E373 e NDean NCChair NEChair NCF1 NEF1 NS1
If key KcS1 C350 is used for encrypting CS 350 grade of Student1,
then the encrypted grade can be decrypted by any of the default decryption
keys of Student1, CS Faculty1,CS Faculty2,CSChair and
the Dean.IfkeyKcS1 E373 is used for encrypting ECE 373 grade of
Student1, then the encrypted grade can be decrypted by any of the
default decryption keys of Student1, CS Faculty1, ECE Faculty1,
CS Chair, ECE Chair and the Dean.
Dean
CS Chair ECE Chair
Student 2
(Sensitive File F)

Figure

4: Access Requirements for a Sensitive Project
5.5 Example 3: Sensitive Project Information
As a part of the curriculum, the students are required to do a
Software Design Project. Some of these projects involve proprietary
data whose disclosure should be kept to a minimum level.
Thus, there is a need for encrypting the ?les associated with the
project. The access requirements are as follows.
1. The faculty members who advise the student on this project
have access to the ?les.
2. The student has access to the ?les.
3. No other person is given access to the ?les.
Student2 is working on a project with faculty membersCS Faculty2
and ECE Faculty1. File F contains sensitive information which
only the student and the project advisors can view. This case is illustrated
in ?gure 4. Note that in ?gure 4 the entire organizational
hierarchy is not shown ? only the part pertinent to the example is
given.
The access requirements are as follows:
1. Sensitive ?le F can be viewed by Student2, CS Faculty2 and
ECE Faculty1.
This is an example where the access requirement does not follow
the organizational hierarchy. People higher up in the hierarchy (the
Dean, the Department Chairperson) is not given the access to these
?les.
5.5.1 Access Control for Example 3
In this case the organizational structure is that given in ?gure 2.
The sensitive ?le F must be protected such that only the faculty
advisors (CS Faculty2, ECE Faculty2 and ECE Faculty1)andthe
student (Student2) have access to this ?le. No other person can have
access. Thus, for protecting the project work the default encryption
key is not adequate. Customized encryption key must be used.
The student encrypts ?le F using the following customized encryption
KcS2. The customized encryption key KcS2 is generated
using Algorithm 2. For this example,
The encrypted ?le F can be decrypted by the default decryption
keys of CS Faculty2, ECE Faculty2, ECE Faculty1 or Student1.
6. SECURITY OF THE PROPOSED MECH-
Our scheme is based on the RSA cryptosystem. Its security is
based on the dif?culty of factoring large prime numbers. We do
need to mention, however, that the low exponent attack on the
RSA cryptosystem [10] does not arise in our case. The low exponent
attack occurs in the following way: suppose the same message
m is encrypted with different keys sharing the same exponent.
Let the exponent e 3 and the different keys are K1 e N1 ,
K2 e N2 , K3 e N3 , etc. By using the Chinese Remainder
Theorem [13] an attacker can get me. Now if he can guess e
correctly, then by extracting the eth root of me, he can obtain m.
To avoid this problem, we choose a large exponent e (e is substantially
larger than the number of levels). Since the complexity of
raising a number to the eth power grows as loge, choosing a large
exponent does not signi?cantly increase the computational com-
plexity. Also in our mechanism, the data is appropriately encrypted
and stored only in one place. Having multiple copies of same data
encrypted with different keys does not arise in our case.
7. ORGANIZATIONAL CHANGES AFFECTING
KEY MANAGEMENT
As outlined in Section 5, the default encryption keys generated
are dependent on the hierarchical structure of the organization. If
restructuring takes place in the organization, the Hasse diagram
representing the personnel hierarchy will be modi?ed resulting in
the change of the default encryption keys. In this section we give
algorithms that result in the modi?cation of default encryption keys
when the organization structure is changed.
Any restructuring can be expressed as modi?cations to the Hasse
Diagram. A Hasse diagram can be modi?ed by using combinations
of the four primitive operations
1. adding an edge between existing nodes ? this corresponds to
the scenario when a new hierarchical relationship is established
between two existing persons in the organization.
2. deleting an edge from an existing node ? this corresponds
to the scenario when an existing hierarchical relationship is
broken.
3. adding a node ? this corresponds to the case when a new
person joins the organization.
4. deleting a node ? this corresponds to the case when a person
leaves the organization.
For each of these operations we give an algorithm stating how the
default encryption key must be changed because of the operation.
The default decryption key, however, remains the same.
ALGORITHM 3. Default enc. key change with edge insertion
Input: (i) L - the set of levels, (ii) - the dominance relation, (iii)
the new directed edge that is to be inserted from level i to
level j, (iv) K - the set of default encryption keys.
Output: K - the set containing the default encryption key for each
level.
Procedure ChangeDefEncKeysEdgeIns(L, ,
begin
for each descendant k of j do
insertion results in a new path from i to k then
for each Li Ldo
begin
return K
ALGORITHM 4. Default enc. key change with edge deletion
Input: (i) L - the set of levels, (ii) - the dominance relation, (iii)
the directed edge from level i to level j that will be removed,
(iv) K - the set of default encryption keys.
Output: K - the set containing the default encryption key for each
level.
Procedure ChangeDefaultEncKeysEdgeDel(L, ,
begin
foreach descendant k of j do
deletion results in no path from i to k then
begin
eliminate access to parents of Li
foreach parent l of i do
if there is a path from l to k after deleting i j do
for each Li Ldo
begin
return K
ALGORITHM 5. Default key generation with node insertion
Input: (i) L - the set of levels, (ii) - the dominance relation, (iii)
- the node that will be added, (iv) K - the set of default encryption
the set of default decryption keys.
Output: (i) K - the set containing the default encryption key for
each level, (ii) K 1 - the set containing the default decryption key
for each level.
Procedure AddDefaultEncKeyNodeIns(L, ,i,K, K 1)
begin
Choose random Ni that is relatively prime to existing Nk
Get the exponent e of any key Kk in K
removal with node deletion
Input: (i) L -thesetoflevels,(i) - the dominance relation, (iii)
- the node that will be added, (iv) K - the set of default encryption
the set of default decryption keys.
Output: (i) K - the set containing the default encryption key for
each level, (ii) K 1 - the set containing the default decryption key
for each level.
Procedure RemoveDefaultKeysNodeDel(L, ,i,K, K 1)
begin
if there are no edges incident on node i then
begin
8. AN ALTERNATE SOLUTION
The problem of access control in a hierarchy can be solved using
an alternative solution1 that can potentially have lesser computational
requirements. Everybody in the organization has a public-private
Suppose an employee wants to share a message m
with his n superiors, denoted by S1, S2, ,Sn. For each superior
Si, the employee encrypts the message m with the public key of superior
Si. Thus, he performs n 1 encryptions (n for his superiors
and one for himself). He stores these n 1 encrypted messages.
Each superior Si can use his private key to retrieve the message.
This alternate solution has a problem: multiple encrypted copies
of data must be stored. Storing multiple copies of encrypted data
can be a source of inconsistency. For example, suppose the employee
decides to change m to m^. After making this change, the
employee is supposed to encrypt m^ with the public keys of his n
superiors. However, the employee forgets to encrypt m^ for superiors
Sj and Sk. In such a case superiors Sj and Sk will be accessing
the previous version of the data which is m. This source of inconsistency
associated with redundant data does not arise in our case
because there is only one copy of the encrypted data. Moreover,
keeping multiple encrypted copies of the same data leads to more
exposure for the data which may not be desirable. This problem
does not arise in our case.
Our solution has another advantage, namely, mutual access awareness
? each person having the encrypted data has the knowledge of
who else can view this data. For any data object we can have the
need-to-know list which speci?es the persons who can access the
document. Anyone having this list can verify that only those persons
in the list and no one else can decrypt the corresponding data
object. This is not possible for the alternate solution.
One might, however, argue that our scheme is more computation
intensive for large hierarchies. This is because the base N of the
1The authors would like to thank the anonymous reviewer for this
alternate solution.
default encryption key increases with the number of levels in the [10]
hierarchy. However there are techniques (for example using Fast
Fourier Transforms) by which the encryption can be done in an [11]
ef?cient manner [5]. These techniques are especially useful if the
base of the keys are large. Details of computational complexity will
be treated in a future work.
9. CONCLUSION AND FUTURE WORK
In this paper we have presented a new encryption technique for
securing information in a database. The implementation that we
propose is completely general; we have shown how the different [13]
access control policies in an organization can be implemented by
our technique. [14]
A lot of work is yet to be done. The ?rst step is to implement the
algorithms that have been proposed; this experience will help us in
detecting subtle ?aws that we may have overlooked. Performance
analysis and scalabilty studies need to be done before our method
can be used in real world scenarios. Finally, we wish to show how
the discretionary and the mandatory access control policies [22] of [15]
an organization can be implemented using the technology that we
proposed.
The need for hierarchical access control arises in other contexts
as well. For example, different kinds of hierarchies, such as, class [16]
composition hierarchy and class inheritance hierarchy arises in object-oriented
database systems [16, 21]. We need to investigate whether
our mechanism can be applied to implement the access control policies
[3, 7, 11] (such as, visibility from above and visiblity from [17]
below policies) desirable in such hierarchies.
10.


--R


The Secure Use of RSA.


In Database Security III

Optimal Algorithm for Assigning Cryptographic Keys to
Access Control in a Hierarchy.

An Introduction to the Theory
of Numbers.

Authentication for Hierarchical Multigroup using the

Advances in Cryptology:


Information Security Policy.

Information Security: An Integrated Collection of Essays
pages 160?
A Model of
Authorization for Next-Generation Database Systems
Transactions on Database Systems
A Method for

Communications of the ACM
Cryptographic Implementation of a Tree
Hierarchy for Access Control.
Mathematics: A Discrete Introduction.
Brooks/Cole

Principles and Practice.
Mandatory Security in




Trusted Computer System Evaluation Criteria (The Orange
New Solutions to the
Problem of Access Control in a Hierarchy.
Preprint 93-2
of Wollongong
http://citeseer.
--TR
An optimal algorithm for assigning cryptographic keys to control access in a hierarchy
Cryptographic implementation of a tree hierarchy for access control
Mandatory security in object-oriented database systems
A cryptographic key generation scheme for multilevel data security
A model of authorization for next-generation database systems
Membership authentication for hierarchical multigroups using the extended Fiat-Shamir scheme
Flexible access control with master keys
Database security
Cryptography and network security (2nd ed.)
Cryptographic solution to a problem of access control in a hierarchy
A method for obtaining digital signatures and public-key cryptosystems
Mathematics
Fundamentals of Database Systems
Access Control in Object-Oriented Database Systems - Some Approaches and Issues

--CTR
H. Ragab Hassen , A. Bouabdallah , H. Bettahar , Y. Challal, Key management for content access control in a hierarchy, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.11, p.3197-3219, August, 2007
Jason Crampton, Applying hierarchical and role-based access control to XML documents, Proceedings of the 2004 workshop on Secure web service, p.37-46, October 29-29, 2004, Fairfax, Virginia
Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, Unconditionally secure key assignment schemes, Discrete Applied Mathematics, v.154 n.2, p.234-252, 1 February 2006
Mikhail J. Atallah , Marina Blanton , Keith B. Frikken, Key management for non-tree access hierarchies, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA
Batrice Finance , Sada Medjdoub , Philippe Pucheral, The case for access control on XML relationships, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Luc Bouganim , Franois Dang Ngoc , Philippe Pucheral, Client-based access control management for XML documents, Proceedings of the Thirtieth international conference on Very large data bases, p.84-95, August 31-September 03, 2004, Toronto, Canada
Mikhail J. Atallah , Keith B. Frikken , Marina Blanton, Dynamic and efficient key management for access hierarchies, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
access control;cryptography;hierarchy