US 8,577,029 B2Granted

Oblivious transfer with hidden access control lists

AssigneeInternational Business Machines Corporation

InventorsJan Leonhard Cameniisch, Maria Dubovitskaya, Gregory Neven, Greg Zaverucha

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method, apparatus, and a computer readable storage medium having computer readable instructions to carry out the steps of the method for anonymous access to a database. Each record of the database has different access control permissions (e.g. attributes, roles, or rights). The method allows users to access the database record while the database does not learn who queries a record. The database does not know which record is being queried: (i) the access control list of that record or (ii) whether a user's attempt to access a record had been successful. The user can only obtain a single record per query and only those records for which he has the correct permissions. The user does not learn any other information about the database structure and the access control lists other than whether he was granted access to the queried record, and if so, the content of the record.

Claims18

Dependent claims

A computer system comprising:

a database server comprising a publisher configured to publish an encrypted form of a database, the database comprising at least one record with an associated index and a list of access-control attributes for each record;
at least one user of the database;
an Issuer configured to provide a credential for each access-control attribute of the database, which is assigned to the at least one user;
wherein said computer system comprises:
a memory storage device,
a processor device;
said processor device associated with said memory storage device and configured to perform a method to encrypt a database, said method
comprising:
generating an encryption key for a record such that the encryption key is derived from at least the index of the record and the access-control attributes and a secret key of the database server, wherein to generate said encryption key, said processor device is configured to use an algorithm comprising:
⁢
g
,
h
⁢
←
$
⁢
G
1
*
;
h
DB
⁢
←
$
⁢
G
2
*
;
H
←
e
⁡
(
g
,
h
DB
)
⁢
x
e
,
x
DB
⁢
←
$
;
y
e
←
g
x
e
;
y
DB
←
g
x
DB
π
setup
=
(
GSProve
⁡
(
CRS
,
y
e
=
g
x
e
,
y
e
,
g
,
x
e
)
,
GSProvePPE
⁡
(
CRS
,
H
,
g
,
h
DB
)
)
For
⁢
⁢
i
=
1
,
…
⁢
,
l
+
1
⁢
⁢
do
x
i
⁢
←
$
;
y
i
←
g
x
i
sk
DB
←
(
h
DB
,
x
e
,
x
DB
,
x
1
,
…
⁢
,
x
l
+
1
)
;
pk
DB
←
(
g
,
H
,
h
,
y
e
,
y
DB
,
y
1
,
…
⁢
,
y
l
+
1
,
π
k
)
encrypting a database record with the encryption key;
encrypting the access-control attributes, which comprises a generator configured to generate a non-interactive zero-knowledge proof that the access-control attributes were correctly encrypted;
wherein the publisher is being responsive to the database encryptor.

185 more elements

A method for anonymously reading records from a database provided by a database server, wherein the database comprises at least one record with an associated index and a list of access-control attributes for each record, and wherein the database server publishes an encrypted form of the database, and wherein at least one user of the database obtains credentials from an Issuer for each access-control attribute which is assigned to the at least one user, and wherein for each record in the encrypted form of the database the following steps are performed:

generating a key that is derived from at least the index of the record and the access-control attributes and a secret key of the database server;
encrypting the record with the key;
encrypting the associated lists of access-control attributes for each record in the encrypted form of the database;
and
generating a non-interactive zero-knowledge proof that the access-control attributes were correctly encrypted, wherein to generate said encryption key, a processor device is configured to use an algorithm comprising:
⁢
g
,
h
⁢
←
$
⁢
G
1
*
;
h
DB
⁢
←
$
⁢
G
2
*
;
H
←
e
⁡
(
g
,
h
DB
)
⁢
x
e
,
x
DB
⁢
←
$
;
y
e
←
g
x
e
;
y
DB
←
g
x
DB
π
setup
=
(
GSProve
⁡
(
CRS
,
y
e
=
g
x
e
,
y
e
,
g
,
x
e
)
,
GSProvePPE
⁡
(
CRS
,
H
,
g
,
h
DB
)
)
⁢
For
⁢
⁢
i
=
1
,
…
⁢
,
⁢
l
+
1
⁢
⁢
do
⁢
x
i
⁢
←
$
;
y
i
←
g
x
i
⁢
sk
DB
←
(
h
DB
,
x
e
,
x
DB
,
x
1
,
…
⁢
,
x
l
+
1
)
;
⁢
pk
DB
←
(
g
,
H
,
h
,
y
e
,
y
DB
,
y
1
,
…
⁢
,
y
l
+
1
,
π
k
)
.

184 more elements

A computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of a method for anonymously reading records from a database provided by a database server, said computer readable storage medium not only a propagating signal, wherein the database comprises at least one record with an associated index and a list of access-control attributes for each record, and wherein the database server publishes an encrypted form of the database, and wherein at least one user of the database obtains credentials from an Issuer for each access-control attribute which is assigned to the at least one user, and wherein for each record in the encrypted form of the database the following steps are performed:

generating a key that is derived from at least the index of the record and the access-control attributes and a secret key of the database server;
encrypting the record with the key;
encrypting the associated lists of access-control attributes for each record in the encrypted form of the database;
and
generating a non-interactive zero-knowledge proof that the access-control attributes were correctly encrypted, wherein to generate said encryption key, a processor device is configured to use an algorithm comprising:
⁢
g
,
h
⁢
←
$
⁢
G
1
*
;
h
DB
⁢
←
$
⁢
G
2
*
;
H
←
e
⁡
(
g
,
h
DB
)
⁢
x
e
,
x
DB
⁢
←
$
;
y
e
←
g
x
e
;
y
DB
←
g
x
DB
π
setup
=
(
GSProve
⁡
(
CRS
,
y
e
=
g
x
e
,
y
e
,
g
,
x
e
)
,
GSProvePPE
⁡
(
CRS
,
H
,
g
,
h
DB
)
)
⁢
For
⁢
⁢
i
=
1
,
…
⁢
⁢
l
+
1
⁢
⁢
do
⁢
x
i
⁢
←
$
;
y
i
←
g
x
i
⁢
sk
DB
←
(
h
DB
,
x
e
,
x
DB
,
x
1
,
…
⁢
,
x
l
+
1
)
;
⁢
pk
DB
←
(
g
,
H
,
h
,
y
e
,
y
DB
,
y
1
,
…
⁢
,
y
l
+
1
,
π
k
)
.

183 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/228,574Filed 9 Sep 2011
Priority: EP 1017612410 Sep 2010
Published: US 2012/0063593 A115 Mar 2012
Granted: 5 Nov 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 21/6227
To a system of files or objects, e.g. local or distributed file system or database: where protection concerns the structure of data, e.g. records,…
H04L 9/0861
Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords: generation of secret information…
H04L 9/3073
Involving algebraic varieties, e.g. elliptic or hyper-elliptic curves: involving pairings, e.g. identity based encryption [IBE], bilinear mappings…
H04L 9/3218
Including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity…: using…