# Oddly Shaped Pegs

An inquiry into the Nature and Causes of Stuff

## Archive for the ‘Uncategorized’ Category

Vitaly Feldman, Aaditya Ramdas, Aaron Roth and I are organizing the second annual (?) workshop on adaptive data analysis and post-selection inference, to be held December 9, 2016 in Barcelona (as part of NIPS).

We have a great slate of invited speakers, and are now calling for papers to be presented there (as posters and, for a subset, as short talks).

Send us your papers! CFP follows below the fold. Latest deadline is October 25 (or September 23 if you want an answer in time for early registration).

August 24, 2016 at 9:54 am

Posted in Uncategorized

## 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)
Christina Brzuska (TU Hamburg)
David Cash (Rutgers)
Alessandro Chiesa (UC Berkeley)
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)
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)

### 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/

May 2, 2016 at 9:02 am

Posted in Conferences, Uncategorized

Tagged with , ,

## 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

(Backup posted on this blog.)
“Theory of cryptography” is broad, and should really be interpreted as “mathematical aspects of information security”. That includes everything from mainstream cryptographic topics (encryption, zero-knowledge and, more recently, obfuscation) to data privacy, information theoretic secrecy, relevant combinatorics and number theory, logic and programming language theory. Experimental work is also welcome to the extent it is driven by and informs our mathematical understanding of a problem.

April 27, 2016 at 9:06 am

Posted in Conferences, Uncategorized

Tagged with , ,

## 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
• Amin Saberi
• Brent Waters
• Balázs Szegedy

Congratulations to all!

February 17, 2010 at 11:00 pm

Posted in Uncategorized

Tagged with , ,

## Military security

with one comment

Two interesting reads this morning on military security.

First, Matt Blaze blogs about physical and procedural security measures at a decommissioned nuclear ICBM silo. Startling pictures and lots of food for thought. The cultural and game theoretic aspects of our current conflicts are pretty different from those of the cold war; I was surprised to find myself looking back with something like nostalgia at the bright ideological lines of my childhood.

“MAD [Mutually Assured Destruction] may well be the most perfectly evocative acronym in the English language, but for 40 years, it actually seemed to work. Leaders on both sides evidently knew a Nash equilibrium when they saw one. […]

A few hundred of the successors to the Titans, the “Minuteman III” missiles, remain active in silos throughout the northern US. […] Looking up from the bottom of the silo at the little crack of sunlight 150 feet above, an obvious fact hit home for me. I realized at that moment that these things are actually aimed somewhere, somewhere not at all abstract.”

*****

On an unrelated (?) topic, the Washington Post (discussed by Harry Lewis) reports that US drones have been transmitting video in the clear, and that militants in Iraq and Afghanistan have been watching avidly.

“The U.S. government has known about the flaw since the U.S. campaign in Bosnia in the 1990s… But the Pentagon assumed local adversaries wouldn’t know how to exploit it, [current and former] officials said.”

That explains it. But surely, in 15+ years, someone would have had time to patch the hole.

“Fixing the security gap would have caused delays, according to current and former military officials. It would have added to the Predator’s price.”

Huh? Software encryption is cheap! All right, maybe dedicated hardware costs more. Maybe even thousands of dollars. Ok, now I get it.

“Today, the Air Force is buying hundreds of Reaper drones, a newer model, whose video feeds could be intercepted in much the same way as with the Predators, according to people familiar with the matter. A Reaper costs between $10 million and$12 million…”

Never mind.

PS: Of course, the security of video transmissions may be the least of the problems that the extensive use of drones in Pakistan and Afghanistan raises. Reading the Post article this morning reminded me of this Fresh Air interview from a few months ago on the use of robotic weapons in general.

December 18, 2009 at 3:15 pm

Posted in Uncategorized

## Locational Privacy

with one comment

Leo Reyzin pointed out the following EFF article on locational privacy. The article does a reasonable job of explaining the role that new technology can have in both violating and protecting privacy.

I can’t count how many times I’ve had a similar conversation (ok, monologue) with government folks and non-technical friends. Maybe next time I can spare myself the trouble and email them the link.

August 6, 2009 at 10:27 am

Posted in Uncategorized

Michaels Nielsen and Mitzenmacher pointed out a recent post by Harvard’s Stuart Shieber about the “don’t ask, don’t tell” policy that is the implicit norm in scholarly publications, at least in computer science.

“Publishers officially forbid online distribution, authors do it anyway without telling the publishers, and publishers don’t ask them to stop even though it violates contractual obligations. What happens when you refuse to play that game?”

I recommend reading the whole thing. Shieber does post his papers online and, unlike many authors, he makes sure to attach an addendum to any copyright agreements with publishers to ensure that he is not in breach of contract. Publishers almost never complain, he says.

“In retrospect, this may make sense.  Since the contractual modification applies only to a single article by a single author, it is unlikely that anyone looking for copyright clearance would even know that all copyright hadn’t been assigned to the publisher.  And in any case publishers must realize that authors act as if they have a noncommercial distribution license…”

I will consider using the Science Commons addenda for future copyright agreements with publishers. But just to share my own story: When we submitted the final version of the fuzzy extractors paper to SICOMP (SIAM Journal on Computing), Leo Reyzin suggested we explicitly modify SIAM’s copyright agreement to make it a “publication agreement” that confers only non-exclusive publication rights to SIAM. The revised agreement let us retain all other publications rights, including free online distribution via sites of our choice. For my readers’ entertainment, here is our modified agreement with SIAM, which SIAM accepted without comment.

Finally, David Eppstein points out that free online journals make all the hassle so last century.

P.S.: For a great radio show about what people usually mean by “don’t ask, don’t tell”, listen to the June 16 episode of NPR’s Fresh Air, in which Terry Gross interviews Nathaniel Frank, author of Unfriendly Fire.

July 7, 2009 at 4:36 pm

## FOCS ’09 crypto accepts

The FOCS 2009 accepted papers are posted, with abstracts. See the chair’s comments here, and other topic-specific discussions here, here and here. Despite some excellent submissions not making it in, there are still some (few!) crypto papers, all of which look interesting. In no particular order:

• Steven Myers and abhi shelat. One bit encryption is complete
• Yi Deng, Vipul Goyal and Amit Sahai. Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. Extracting Correlations
• Yael Tauman Kalai, Xin Li and Anup Rao. 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness

Quantum crypto papers:

Not exactly crypto, but highly relevant:

• Iftach Haitner. A Parallel Repetition Theorem for Any Interactive Argument
• Falk Unger. A Probabilistic Inequality with Applications to Threshold Direct Product Theorems

Scanning over the FOCS abstracts is hard because of information overload. I will try to read all of the papers on the list above (maybe I’ll even attend the conference) but for now two stand out because they resolve problems I have thought about:

First, Steve and abhi’s surprising paper (not yet available online), which gives a black-box construction of many-bit CCA-secure encryption from 1-bit CCA-secure encryption. This question is tied to very basic notions of authenticity and secrecy in cryptography. For CPA-secure encryption (that is, encryption secure against passive attacks), increasing the message length is straightforward: Goldwasser and Micali showed that encrypting each bit separately works (a classic example of a “hybrid” argument). However, for schemes that must resist active attacks, such as chosen-ciphertext attacks (CCA), bit-by-bit encryption fails miserably. Prior to this paper, there existed (limited) impossibility results, but no evidence that a black-box construction was possible.

Second, André and Iordanis’ paper on optimal strong quantum coin flipping. Information-theoretically secure quantum coin flipping was proved to be impossible in the late 90’s by Mayers and Lo and Chau, using the same techniques that rule out information-theoretically secure oblivious transfer and bit commitment. That result only rules out protocols that produce a very good biased coin (with bias 1/2+o(1)). However, protocols were constantly being proposed (and occasionally broken) which  produced weakly biased coins. This new paper gives a protocol matching Kitaev’s lower bound of $1/\sqrt{2}\approx 0.707$ on the minimal bias. This is not of critical importance in practice, but it does elucidate one of the key phenomena which distinguish quantum from classical cryptographic protocols.

July 2, 2009 at 9:33 pm

Posted in Uncategorized

## Crypto and politics

While the interactions between cryptography and politics are usually far from the public eye, the crackdown in Iran has given anonymization and covert communication technologies (ironically!) a chance to shine. For a layman’s introduction, see this Irish Times article and this Washington Post one (via Michael M.). I’d appreciate people using the comments to post links to articles with more technical analysis of what is currently going.

The geek in me is curious to see how the conflict between surveillers and surveillance evaders will play out in Iran; but most of me is just plain angry. This blog is now green…

June 26, 2009 at 2:15 am

Posted in Uncategorized