printlogo
http://www.ethz.ch/index_EN
International Workshop on Quantum Information Processing
 
print
  

QIP 2010 at

ETH Life

The daily web-journal of ETH Zurich:

"Lifting the big veil"

"Nach dem grossen Schleier lüften"

18.01.2010

QIP 2010 at the

Swiss Radio DRS

Echo der Zeit

from Monday Jan 18, 2010

in German, Link >>

(Real Player recommended)

chocolate


pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

pauliohne


The Swiss National Science Foundation

snflogo


ETH Zurich (Computer Science and Physics Department)

ethlogo


Quantum Science and Technology

qsitmitschrift


CQT Singapore

cqtlogo


QAP European Project

qaplogo3


Sandia National Laboratories

sandia


Institute for Quantum Computing

finaliqc


id Quantique

3rdideequantique

Improved extractors against bounded quantum storage

Thomas Vidick, Berkeley

joint work with Anindya De

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Theta((K-b)/K^g) for any g>0. In contrast, the previous best construction [Ta-Shma, STOC'09] could only extract (K/b)^(1/15) bits.
Our construction follows Trevisan's general reconstruction paradigm, and in fact our proof of security shows that essentially all extractors constructed using this paradigm are secure against quantum storage, with optimal parameters. Our argument is based on bounds for a generalization of quantum random access codes, which we call quantum functional access codes. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in [Ta-Shma, STOC'09] which was the source of the multiplicative overhead. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications.

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2015 ETH Zürich | Imprint | Disclaimer | 5 January 2010
top