DOC PREVIEW
UT CS 380S - CS 380S Homework4

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 380S - Theory and Practice of Secure SystemsFall 2009Homework #4Due: 2pm CST (in class), December 3, 2009NO LATE SUBMISSIONS WILL BE ACCEPTEDYOUR NAME:Collaboration policyNo collaboration is permitted on this assignment. Any cheating (e.g., submitting anotherperson’s work as your own, or permitting your wo r k to be copied) will automatically resultin a failing grade. The Computer Sciences department code of conduct can be found athttp://www.cs.utexas.edu/academics/conduct/1Homework #4 (30 points)Problem 1 (3 points)Let X be some database, and assume that each element x ∈ X is drawn from some proba-bility distribution D over integers between 0 and 100. The databa se is perturbed and thenpublished. Let R be the randomization operator applied to each element of the database topreserve privacy prior to publication. R operates as follows: for each x ∈ X, R(x) = x + ξ,where ξ is an integer which is distributed uniformly at random between −20 and 20. DefineR(X) =Sx∈X{R(x)}.Give an example of a distribution D such that R(X) completely reveals X for any X.Problem 2In this problem, we consider online query monitoring and auditing, i.e., instead of publishinga perturbed database, the database owner interactively receives queries and, for each query,decides whether it is safe to answer it using some auditing or monitoring algorithm.Let X = {x1, . . . , xn} be the database. Each element xiis associated with some integervalue vi. The questioner specifies any subset X′⊆ X. If the query is safe, the response isthe second highest value among those associated with the elements of the requested subset.Unsafe queries are denied.Problem 2a (4 points)Suppose the database owner uses a naive auditing algorithm. Given a query, the naiveauditor denies it if the respo nses to a ll previous queries, taken together with the r esponse tothe current query, would r eveal the value associated with some element of the database X.Give an example of a database X and a sequence of queries that, if processed by thenaive auditor, completely reveals the value associated with some element of X.2Problem 2b (4 points)Suppose the database owner has both a safe query monitor and a simulatable auditor athis disposal. Give an example of a database X and a sequence of queries such that the querymonitor will deny the last query, but a simulatable auditor will allow it.Problem 3 (5 points)A significant percentage o f people living in the US are uniquely identified by the (ZIP code,birthdate, gender) quasi-identifier. If an anonymized dataset conta ins ZIP code, birthdate,and gender attributes, it is possible to determine whether a particular person is present inthe dataset simply by checking if this person’s quasi-identifier occurs in one of the records.Recall that k-anonymity relies on generalizing and suppressing quasi-identifiers until ev-ery quasi-identifier occurs in at least k records in the a nonymized dataset. Therefore, givenany person’s record, it is guaranteed that the same quasi-identifier occurs in the records ofat least k − 1 other people.A common interpretation of this property is t hat k-anonymity hides whether a particularperson is present in the anonymized dataset.Assuming that the attacker knows only people’s quasi-identifiers, is this interpretationaccurate? Explain.3Problem 4 (4 points)Differential privacy is closely related to the concept of function sensitivity. Give examplesof low-sensitivity functions (other than those from the “Differential Privacy” paper) tha tone may wa nt to compute on a database, and give a mathematical explanation of why theirsensitivity is low.Problem 5 (5 points)Consider a deterministic algorithm for generalizing and suppressing quasi-identifiers, such asthose used to achieve k-anonymity, l-diversity, t-closeness, and similar properties.Assuming that the attacker knows only people’s quasi-identifiers, can generalization andsuppression be used to achieve differential privacy? Explain.Problem 6 (5 points)Many privacy policies talk about the “ purpose” for which a sensitive piece of data may ormay not be used. For example, a medical privacy policy may state that a person’s DNAmay be released for the purpo se of making a treatment decision, but not for the purpose ofapproving or denying health-insurance coverage.4Consider a software program operating on sensitive data (you may assume that theyare stored in program variables). Explain how techniques for information-flow control canbe used to express the concept of “purpo se” and to ensure that data are not released forpurposes forbidden by the privacy


View Full Document

UT CS 380S - CS 380S Homework4

Download CS 380S Homework4
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 380S Homework4 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 380S Homework4 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?