## Posts Tagged ‘**theory**’

## TPDP 2019

The call for submissions for the latest edition of TPDP (Theory and Practice of Differential Privacy) is out!

https://tpdp.cse.buffalo.edu/2019/

The workshop covers work on differential privacy (of course), and more generally on rigorous modeling of, and attacks on, statistical data privacy. The intention is to be inclusive.

Submissions are due June 21, 2019.

## TCC 2016-B Call For Papers

(Posting this here as a backup, since the main TCC website is temporarily down. The submission server is up and running though.)

The Fourteenth Theory of Cryptography Conference will be held in Beijing, China, sponsored by the International Association for Cryptologic Research (IACR). Papers presenting original research on foundational and theoretical aspects of cryptography are sought. For more information about TCC, see the TCC manifesto.

Submission Deadline | Friday, May 20, 2016, Anywhere on Earth |

Notification of Decision | August 1, 2016 |

Proceedings Version Due | August 23, 2016 |

Conference | November 1-3, 2016 |

The Theory of Cryptography Conference deals with the paradigms, approaches, and techniques used to conceptualize natural cryptographic problems and provide algorithmic solutions to them. More specifically, the scope of the conference includes, but is not limited to the:

- Study of known paradigms, approaches, and techniques, directed towards their better understanding and utilization,
- Discovery of new paradigms, approaches and techniques that overcome limitations of the existing ones,
- Formulation and treatment of new cryptographic problems.
- Study of notions of security and relations among them,
- Modeling and analysis of cryptographic algorithms, and
- Study of the complexity assumptions used in cryptography.

The Theory of Cryptography Conference is dedicated to providing a premier venue for the dissemination of results within its scope. The conference aims to provide a meeting place for researchers and to be instrumental in shaping the identity of the theoretical cryptography community.

**Instructions for Authors**

The submission should begin with a title, followed by the names, affiliations and contact information of all authors, and a short abstract. It should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. Submission must be typeset using the Springer LNCS format with page numbers enabled (\pagestyle{plain}). The main body of the submission, including title page and figures, must not exceed 20 pages. In addition, any amount of clearly marked supplementary material and references are allowed. However, reviewers are not required to read or review any supplementary material and submissions are expected to be intelligible and complete without it.

Submissions must not substantially duplicate work that was published elsewhere, or work that any of the authors has submitted in parallel to any other conference or workshop that has proceedings; see the IACR policy on irregular submissions for more information.

At least one author of each accepted paper is required to present the paper at the conference. Authors are strongly encouraged to post full versions of their submissions in a freely accessible online repository, such as the Cryptology ePrint archive. We encourage the authors to post such a version at the time of submission (in which case the authors should provide a link on the title page of their submission). At the minimum, we expect that authors of accepted papers will post a full version of their papers by the camera-ready deadline. Abstracts of accepted papers will be made public by the PC following the notification.

**Contacting the Authors**

At submission time, authors must provide one or several email addresses for corresponding authors. Throughout the review period, *at least one corresponding author is expected to be available to receive and quickly answer questions (via email) that arise about their submissions*.

**Submission instructions**

Papers must be submitted electronically through the submission web page. The authors are allowed to revise the paper any number of times before the submission deadline, and only the latest submitted version will be seen by the PC. Therefore, the authors are advised not to wait until the last moment for the initial submission.

**Best student paper award**

This prize is for the best paper authored solely by students, where a student is a person that is considered a student by the respective institution at the time of the paper’s submission. Eligibility must be indicated at the time of submission (using a checkbox in the submission form). The program committee may decline to make the award, or may split it among several papers.

**Proceedings**

Proceedings will be published in Springer-Verlag’s Lecture Notes in Computer Science Series and will be available at the conference. Instructions for preparing the final proceedings version will be sent to the authors of accepted papers. The final copies of the accepted papers will be due on the camera-ready deadline listed above. This is a strict deadline, and authors should prepare accordingly.

**Program Committee**

Masayuki Abe (NTT)

Divesh Aggarwal (EPFL)

Andrej Bogdanov (Chinese University of Hong Kong)

Elette Boyle (IDC Herzliya)

Anne Broadbent (uOttawa)

Christina Brzuska (TU Hamburg)

David Cash (Rutgers)

Alessandro Chiesa (UC Berkeley)

Kai-Min Chung (Academia Sinica)

Nico Döttling (UC Berkeley)

Sergey Gorbunov (U. Waterloo)

Martin Hirt (ETH Zurich) — **Co-chair
**Abhishek Jain (Johns Hopkins)

Huijia Lin (UC Santa Barbara)

Hemanta K. Maji (Purdue)

Adam O’Neill (Georgetown)

Rafael Pass (Cornell Tech)

Krzysztof Pietrzak (IST Austria)

Manoj Prabhakaran (U. Illinois, Urbana Champaign)

Renato Renner (ETH Zurich)

Alon Rosen (IDC Herzliya)

abhi shelat (U. Virginia)

Adam Smith (Penn State) —

**Co-chair**

John Steinberger (Tsinghua)

Jonathan Ullman (Northeastern)

Vinod Vaikuntanathan (MIT)

Muthuramakrishnan Venkitasubramaniam (U. Rochester)

Please send questions to tcc2016b.chairs@gmail.com

**Conference Honorary Chair**

Andrew Chi-Chih Yao (IIIS, Tsinghua University, China)

**General Chair**

Dongdai Lin (SKLOIS, Institute of Information Engineering, CAS, China)

**TCC Steering Committee Members**

Mihir Bellare, Ivan Damgård, Shafi Goldwasser, Shai Halevi (**chair**), Russell Impagliazzo, Ueli Maurer, Silvio Micali, Moni Naor, and Tatsuaki Okamoto.

**TCC web site:** http://www.iacr.org/workshops/tcc/

## TCC 2016-B: Deadline May 20

TCC (the Theory of Cryptography Conference) is moving to a late Fall schedule, so this year the conference will occur twice! TCC 2016-A happened already, and TCC 2016-B will happen in November in Beijing.

Deadline is coming up — **May 20, 2016**.

http://tcc2016b.sklois.cn/call_for_papers.html

## Tutorial Videos on and around Differential Privacy

http://dimacs.rutgers.edu/Workshops/DifferentialPrivacy/Slides/slides.html

The tutorial speakers covered connections between DP and a range of areas:

- Moritz Hardt: Differential private algorithms via learning theory
- Gerome Miklau: Query optimization techniques from the DB community
- Benjamin Pierce: Using PL techniques to automate and verify proofs of privacy
- Aaron Roth: Game-theoretic perspectives on privacy

- Slides (with corrections): http://www.cse.psu.edu/~asmith/talks/2012-08-21-crypto-tutorial.pdf
- Video (no corrections!): http://www.youtube.com/watch?v=dbWx62C5Q4o&list=PL3C6A9D61E40300E6&index=26

## DIMACS Workshop on Differential Privacy

Aaron Roth and I are running a 3 day interdisciplinary workshop on differential privacy at DIMACS (Rutgers), on October 24-26. This is immediately following FOCS, which is being held nearby, in downtown New Brunswick. The workshop will begin with a day of tutorials on differential privacy as understood in various communities (theory, databases, programming languages, and game theory), and will continue with two days of research talks and discussion.

Details of the workshop can be found here: http://dimacs.rutgers.edu/Workshops/DifferentialPrivacy/

(n.b.: some extra speakers have confirmed who are not yet on the web page).

As part of the program, we will also have a session of short (5-10 minute) talks from students, postdocs, and other interested parties. We encourage submission of abstracts for short talks. The solicitation is below.

See you all in October!

Aaron and Adam

**DIMACS Workshop on Differential Privacy across Computer Science**

October 24-26, 2012

(immediately after FOCS 2012)

Call for Abstracts — Short Presentations

The upcoming DIMACS workshop on differential privacy will feature invited talks by experts from a range of areas in computer science as well as short talks (5 to 10 minutes) by participants.

Participants interested in giving a short presentation should send an email to asmith+dimacs@psu.edu containing a proposed talk title, abstract, and the speaker’s name and affiliation. We will try to

accommodate as many speakers as possible, but

a) requests received before October 1 will get full consideration

b) priority will be given to junior researchers, so students and postdocs should indicate their status in the email.

More information about the workshop:

The last few years have seen an explosion of results concerning differential privacy across many distinct but overlapping communities in computer science: Theoretical Computer Science, Databases, Programming Languages, Machine Learning, Data Mining, Security, and Cryptography. Each of these different areas has different priorities and techniques, and despite very similar interests, motivations, and choice of problems, it has become difficult to keep track of this large literature across so many different venues. The purpose of this workshop is to bring researchers in differential privacy across all of these communities together under one roof to discuss recent results and synchronize our understanding of the field. The first day of the workshop will include tutorials, representing a broad cross-section of research across fields. The remaining days will be devoted to talks on the exciting recent results in differential privacy across communities, discussion and formation of interesting open problems, and directions for potential inter-community collaborations.

A tentative program and registration information can be found at

http://dimacs.rutgers.edu/Workshops/DifferentialPrivacy/

## ICITS 2012 — playing with the format

I am the program chair for this year’s ICITS, the International Conference on Information-Theoretic Security. (The acronym is admittedly a bit of a mouthful. I like “ickets” as the pronunciation. That way, papers at ICITS are “pickets”, talks there are “tickets”, you get the idea.) ICITS will be held in Montreal right before CRYPTO, August 15-17, 2012.

ICITS occupies an interesting spot at the intersection of a few different fields: crypto, information theory, quantum computing and combinatorics. In the past, ICITS has worked like a normal computer science conference: papers are reviewed carefully, papers cannot have appeared at other conferences or journals, etc. However, because ICITS serves several different communities, the format has sometimes cost it good papers: some are lost to more specific or better-known venues in computer science, others are lost because conference “publication” doesn’t fit well with the culture in other fields, etc.

So to try to broaden participation and make the conference more scientifically useful, we’re shaking up the format this year with a two-track submission process. The “conference” track will operate like a traditional conference with the usual review process and published proceedings. The “workshop” track will operate more like an informal workshop, without published proceedings. Submissions to the former track will follow a traditional page-limited format. Submissions to the latter are much more flexible in format (they can range from full papers or to extended abstracts), and may consist of previously published papers or works in progress. For example, the workshop track would be a great place to come present your Crypto/Eurocrypt, QIP or ISIT paper to the other communities that work on info-theoretic security.

You can see the call for papers if you’re curious about the process. But most importantly, **get your papers ready for submission!** The deadlines are

**March 12**for the regular track and**April 9**for workshop papers.

In addition to the contributed papers we will have a great slate of invited speakers from a broad range of disciplines. And did I mention that the program committee rocks?

Of course, the best part of this is that ICITS will be in Montreal in the summer time. Despite its French character, not all of Montreal goes on vacation in August (in fact, the city does shut down for two weeks, the “construction holidays”, that will be over by the time ICITS hits town). There are festivals, tasty food, nice weather and, for me, lots of friends and family to see.

So submit your papers! And attend!

## Postdocs in data privacy at Penn State

I have been excessively delinquent in posting to this blog for the last little while (ok, two years). But a postdoc announcement is a terrible thing to hide from public view in the current economy.

**Postdoctoral positions in statistical, computational and learning-theoretic aspects of data privacy**

As part of a joint project between Penn State, CMU and Cornell, we are inviting applications for several postdoctoral positions at Penn State University.

The principal investigators at Penn State are:

– Sofya Raskhodnikova,

– Aleksandra Slavkovic and

– Adam Smith.

The other principal investigators on this project are:

– Stephen Fienberg (CMU) and

– John Abowd (Cornell).

We are looking for strong candidates interested in algorithmic, cryptographic, statistical and learning-theoretic aspects of data privacy. Candidates should have a Ph.D. in statistics, computer science or a related field and a strong record of original research. The positions are for one year, extendable to up to three years. The starting date is negotiable.

The project spans a broad range of activities from the exploration of foundational theory to the development of concrete methodology for the social and economic sciences. Postdoctoral fellows may be involved in any of these aspects, depending on their interests and expertise. Extended research visits at CMU and Cornell are possible, though not necessary.

Interested candidates should send a CV and brief research statement, along with the names of three references, to one of the three Penn State investigators (sofya@cse.psu.edu, sesa@stat.psu.edu, asmith@psu.edu). Applications received before February 25, 2012 will receive full consideration. Applications will continue to considered after that date until the position is filled.

**Looking for a different postdoc?**

In case the opportunity above isn’t your cup of tea, here are some public service tips on where to look for postdoc announcements.

- Princeton’s CCI has a decent list of TCS-related jobs
- The IACR has a list of open positions in cryptology [sic]

… and that’s pretty much it. The postdoc market, especially in CS, is ridiculously inefficient. That’s partly because many postdocs (like mine) are project specific, and partly because there’s just no good central repository of relevant jobs.

With that in mind, I will mention the postdoc position in the theory of privacy and economics at the University of Pennsylvania. If you really want to do a postdoc on data privacy, and the Penn State/CMU/Cornell position won’t work for you, then talk to Aaron Roth (or Mike Kearns, Sham Kakade or Mallesh Pai).

## IPAM Workshop Wrap-Up

Last week was the Statistical and Learning-Theoretic Challenges in Data Privacy, which I co-organized with Cynthia Dwork, Steve Fienberg and Sesa Slavkovic. As I explained in my initial post on the workshop, the goal was to tie together work on privacy in statistical databases with the theoretical foundations of learning and statistics.

- Slides for most talks are online
- Blog posts: Arvind N., Jon K. #1, #2 (see also an older post by Ben R.)

The workshop was a success. For one thing, I got a new result out of it and lots of ideas for problems to work on. I even had fun most of the time^{1}.

### — A shift in tone —

More importantly, I felt a different tone in the conversations and talks at this workshop than at a previous ones involving a similar crowd. For the first time, most participants seemed to agree on what the important issues are. I’ve spent lots of time hanging out with statisticians recently, so this feeling may not have been shared by everyone. But one change was objectively clear: the statisticians in the crowd have become much better at describing their problems in computational terms. I distinctly remember encountering fierce resistance, at the original 2005 CS-Stats privacy workshop in Bertinoro, when we reductionist CS types tried to get statisticians to spell out the procedures they use to analyze social science data.

“Analysis requires judgement. It is as much art as science,” they said (which we translated as, “Recursion, shmecursion. We do not know our own programs!”).

“But can’t you try to pin down some common objectives?”, we answered.

This week, there were algorithms and well-defined objectives galore. It helped that we had some polyglots, like Martin Wainwright and Larry Wasserman, around to translate.

### — The “computational lens” at work —

An interesting feature of several talks was the explicit role of “computational” perspective. Both Frank McSherry and Yuval Nardi used techniques from numerical analysis, namely gradient ascent and the Newton-Raphson method, to design protocols which were both more efficient and easier to analyze than previous attempts based on a more global, structural perspective. Frank described a differentially private algorithm for logistic regression, joint with Ollie Williams; Yuval described an efficient SFE protocol for linear regression, joint with Steve Fienberg, Rob Hall, and others.

### — Two under-investigated ideas —

At the wrap-up session (see the notes), I pointed out two directions that I think have been investigated with much less rigor than they deserve:

#### “Cryptanalysis” for database privacy

It would be nice to have a systematic study of, and standard nomenclature for, attacks on privacy/anonymity in statistical databases. Right now it seems every paper ends up defining (or not defining) a model from scratch, yet many papers are doing essentially the same thing in different domains. Even an incomplete taxonomy would be helpful. Here are a few terms I’d like to see becoming standard:

- linkage attack
- reconstruction attack
- composition attack (my personal favorite)

On a related point, it would be nice to see a good categorization of the kinds of side information that gets used. For example, Johannes Gehrke at Cornell and his students have a few papers laying out categories of side information (I have issues with some of the positive results in those papers, but I think the quantification of side information is interesting).

#### Relaxed definitions of privacy with meaningful semantics

This is probably a topic for a much longer post, but briefly: it would be nice to see meaningful definitions of privacy in statistical databases that exploit the adversary’s uncertainty about the data. The normal approach to this is to specify a set of allowable prior distributions on the data (from the adversary’s point of view). However, one has to be careful. The versions I have seen are quite brittle. Some properties to keep in mind when considering new definitions:

- Composition
- Side information: is the class of priors rich enough to incorporate complex side information, such as an anonymization of a related database? [see composition above]
- Convexity and post-processing, as in Dan Kifer’s talk
- Equivalent, “semantic” characterizations [e.g. here, here]

### — Other notes —

- The majority of the talks were completely or partly on differential privacy. Notable exceptions: Brad Malin, Xiaofeng Wang, Ravi Kumar, Jiashun Jin, Yuval Nardi. Our goal was not to have such a preponderance of differential privacy talks, but some of the people we expected to talk about other things (like Jerry Reiter) decided to focus on differential privacy. Tailoring the talk to the crowd?
- The nonspeaker participants were heavily skewed towards CS. In particular, at least [see comments!] four professors (Gerome Miklau, Anupam Gupta, Jonathan Katz, Yevgeniy Dodis) and three postdocs (Katrina Liggett, Anand Sarwate, Arvind Narayanan) from CS departments attended just to listen to the talks; I recognized only one stats postdoc (Saki Kinney). I also recognized lots of UCLA locals there too from CS (Yuval Ishai, Rafi Ostrovsky, Amit Sahai) but none from statistics.
- The rump session + posters combination worked very well (despite my earlier doubts). Rump session slides are online.

^{1} Serious sleep deprivation due to jet-lagged kids and talk prep made the “fun” part occasionally difficult.

## 2010 Sloan Fellows

Once again this year, theorists and their friends were well represented among the Sloan Research Fellows. These are the names I recognize:

- Joel Tropp
- Jonathan Kelner
- Constantinos Daskalakis
- Amin Saberi
- Brent Waters
- Balázs Szegedy

Congratulations to all!

## Differential privacy and the secrecy of the sample

(This post was laid out lazily, using Luca‘s lovely latex2wp.)

** — 1. Differential Privacy — **

Differential privacy is a definition of “privacy” for statistical databases. Roughly, a statistical database is one which is used to provide aggregate, large-scale information about a population, without leaking information specific to individuals. Think, for example, of the data from government surveys (*e.g.* the decennial census or epidemiological studies), or data about a company’s customers that it would like a consultant to analyze.

The idea behind the definition is that *users*–that is, people getting access to aggregate information–should not be able to tell if a given individual’s data has been changed.

More formally, a data set is just a subset of items in a domain . For a given data set , we think of the server holding the data as applying a randomized algorithm , producing a random variable (distributed over vectors, strings, charts, or whatever). We say two data sets are *neighbors* if they differ in one element, that is, .

Definition 1A randomized algorithm is -differentially private if, for all pairs of neighbor data sets , and for all events in the output space of :

This definition has the flavor of *indistinguishability* in cryptography: it states that the random variables and must have similar distributions. The difference with the normal cryptographic setting is that the distance measure is multiplicative rather than additive. This is important for the semantics of differential privacy—see this paper for a discussion.

I hope to write a sequence of posts on differential privacy, mostly discussing aspects that don’t appear in published papers or that I feel escaped attention.

** — 2. Sampling to Amplify Privacy — **

To kick it off, I’ll prove here an “amplification” lemma for differential privacy. It was used implicitly in the design of an efficient, private PAC learner for the PARITY class in a FOCS 2008 paper by Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova and myself. But I think it is of much more general usefulness.

Roughly it states that given a -differentially private algorithm, one can get an -differentially private algorithm at the cost of shrinking the size of the data set by a factor of .

Suppose is a -differentially private algorithm that expects data sets from a domain as input. Consider a new algorithm , which runs on a random subsample of points from its input:

Algorithm 2 (Algorithm )On input and a multi-set

- Construct a set by selecting each element of independently with probability .
- Return .

Lemma 3 (Amplification via sampling)If is -differentially private, then for any , is -differentially private.