Transcript A Practical and Efficient Tree-List Structure for Public

Self-Enforcing Private
Inference Control
Yanjiang Yang (I2R, Singapore)
Yingjiu Li (SMU, Singapore)
Jian Weng (Jinan Univ. China)
Jianying Zhou (I2R, Singapore)
Feng Bao
(I2R, Singapore)
RFID Security Seminar 2008
Content
• Introduction
• Self-Enforcing Private Inference Control
– Concept
• Proposed Scheme
• Conclusion
2
Introduction
Project
Summary - why should it be done?
RFID Security Seminar 2008
• Inference problem has been a long
standing issue in database security
– Sensitive information beyond one's
privileges can be inferred from the
unsensitive data to which one is granted
access.
– Access control cannot solve the inference
problem
– The set of queries whose responses lead to
inference is said to form an inference
channel
3
RFID Security Seminar 2008
Introduction – Con.
• Inference Control
– to prevent the formation of inference
channels
– Auditing is a special kind of inference
control technique that audits queries in
order to ensure that a user's current query,
together with his past queries, cannot form
any inference channel
4
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Inference Control
– What forms an inference channel depends
closely on the data to be protected and the
protection objective
– Our concern in this work is the inference
channels that result in identifying the
subjects contained in the database
– An example is a database of medical
records for individuals
• explicit identifying information
• Non-identifying attributes such as age, ZIP
code, DoB are not personally identifiable
5
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Inference Control
– An example is a database of medical
records for individuals
• explicit identifying information
• individual attributes such as age, ZIP code, DoB
are not personally identifiable
• each of them alone usually does not contain
sufficient information to uniquely identify any
individuals, thereby should not be classified as
sensitive.
• However, a combination of some/all of these
non-sensitive attributes may be uniquely
identifiable, thus forming an inference channel.
6
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Inference Control
– Inference control in this context works by
blocking users who access the database
from obtaining responses of the queries
that cover all the attributes necessary to
complete an inference channel.
7
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Query Privacy
– Users who access database also have
privacy concern
• Exposure of what data a user is accessing to
the database server may lead to the
compromise of user privacy
– It is desirable that inference control is
enforced by the server in a way that query
privacy is also preserved
– The two objectives are conflicting to some
extent
8
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Private Inference Control
– Woodruff and Staddon (Private Inference
Control. In: Proc. ACM CCS 04) are the first
to propose private inference control to
attain both objectives
– Unfortunately, practical deployment of
private inference control may encounter an
enormous obstacle
• database server knows nothing about user
queries, so users can easily exploit by issuing
useless queries
9
Introduction
– Con.
Project
Summary - why
should it be done?
RFID Security Seminar 2008
• Private Inference Control
– Unfortunately, practical deployment of
private inference control may encounter an
enormous obstacle
• database server knows nothing about user
queries, so users can easily exploit by issuing
useless queries
• It is a well known fact that inference control
(even without privacy protection) is extremely
computation intensive
• This kind of DoS attacks are expected to be
particularly effective in private inference
control.
10
RFID Security Seminar 2008
Self-Enforcing
Inference
Control
Project
Summary -Private
why should
it be done?
– Concept
• Self-Enforcing Private Inference Control
– The intuition is to force users not to make
queries that form inference channels;
otherwise, penalty will incur on the
querying users
– users are obliged to enforce costly
inference control by themselves before
making queries - Self-Enforcing
11
RFID Security Seminar 2008
Self-Enforcing Private Inference Control – Concept
• Self-Enforcing Private Inference Control
– In our proposed scheme, penalty is
instantiated to be a deprivation of the
access privileges of the violating users.
• If a user makes an inference-enabling query,
then the user's access right is forfeited and he
is rejected to make queries any further
12
RFID Security Seminar 2008
Proposed Scheme
• We incorporate access control into
inference control, and base access
control on one-time access keys
– a user is able to get the access key for
next query only if his current query is
inference-free
– We extend Woodruff and Staddon's
scheme
13
Proposed Scheme – Con.
RFID Security Seminar 2008
• The inference control rule is that for
any record, the user cannot get all its
attributes
– suppose the database has n records, each
record has m attributes
14
Proposed Scheme – Con.
RFID Security Seminar 2008
• User lthQuery Ql = <Hom_Enc(il), Hom_Enc(jl)>
– The server selects a random Kl+1, and generates l
-1 shares, s1, s2, …, sl-1, forming a (l -m+1)-outof-(l -1) sharing of Kl+1 using a secret sharing
scheme
– The server computes e1 = Hom_Enc((i1-il)s1), e2 =
Hom_Enc((i2- il)s2), …, el-1 =Hom_Enc ((il-1 –il)sl-1)
using the user's previous queries.
– The user decrypts e1, e2, …, el-1, if the user's
query sequence thus far does not complete
inference channel, the user can recover at least l –
m + 1 shares, thus reconstructing Kl+1.
15
Proposed Scheme – Con.
RFID Security Seminar 2008
• The remaining steps are largely
Woodruff and Staddon's scheme, with
Kl+1 being the random number in theirs.
• We Discussed Various Issues to
Improve the Above Basic Scheme
– Penalty Lifting
– Allow for Repeat Queries
– Stricter Query Privacy
16
RFID Security Seminar 2008
Conclusion
• DoS Attacks Are Particularly Effective in
Private Inference Control Systems
• We Were Motivated to Propose SelfEnforcing Private Inference Control
• The Intuition is to Force Users to be
Cautious in Making Queries, as Penalty
Will be Inflicted Upon Users Who Make
Inference-Enabling Queries.
• We Presented A Concrete Scheme
17
Q&A
Project
Summary - why should it be done?
THANK YOU!
18
RFID Security Seminar 2008