### RISC Seminars

Archives:**[2019]**[2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004]

**[List of Speakers]**

(To receive information about upcoming seminars, register for the RISC mailing list.)

#### Upcoming Event(s)

[print]

**Special RISC Seminar on the Occasion of Max Fillinger's PhD Defense**

This seminar is on the occasion of Max Fillinger's PhD Defense, which takes place March 19, 10:00h, at Leiden University (Academy Building, Rapenburg 73, 2311 GJ Leiden).

Date: | March 18, 2019 (this is the day before the defense) |

Location: | CWI, room L016 |

Schedule: | |

14:00 - 14:45 h | Max Fillinger (Fox-IT, formerly CWI):Two-Prover Bit-Commitments: Classical, Quantum and Non-Signaling
Abstract: In this talk, I give an overview over the results presented in my PhD
thesis. We examine two-prover bit-commitments, as introduced by Ben-Or,
Goldwasser, Kilian and Wigderson in 1988, where security relies on
assumed communication restrictions between the provers. We introduce new
definitions of the binding property of such commitment schemes and prove
a composition theorem which shows that two commitment schemes can be
composed into a "larger" scheme with the binding parameters adding up.
This composition theorem can be applied to relativistic commitment
schemes. In particular, we show that the relativistic commitment scheme
introduced by Lunghi et al. in 2015 has a much better binding parameter
than the original analysis indicated.
The composition theorem only applies for classical provers. Time
permitting, I will discuss some partial progress towards extending the
result to provers with quantum capabilities.
If one wants to prove a commitment scheme secure on the sole assumption
that provers cannot communicate, one must consider so-called
non-signalling provers: provers whose behavior is correlated in
arbitrary ways, as long as no communication is implied. We show an
impossibility result here: no commitment scheme is both hiding and
binding for such provers. On the other hand, there is a three-prover
scheme that is hiding and binding. |

14:45 h - 15:00 h | Break |

15:00 - 15:45 h | Stacey Jeffery (CWI and QuSoft):On Non-Adaptive Quantum Chosen-Ciphertext Attacks and Learning With Errors
Abstract: Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. This is joint work with Gorjan Alagic, Maris Ozols and Alexander Poremba. |

15:45 h - 16:00 h | Break |

16:00 - 16:45 h | Stefan Wolf (Università della Svizzera italiana):Causality - Consistency - Complexity
Abstract: Quantum theory predicts correlations that question fundamental
space-time causality. Dropping the latter, while still maintaining
logical consistency, has dramatic consequences for the power of
communication and computation. Such reasoning is in the spirit
of Landauer's famous slogan "Information is Physical." A variant of
its paradigmatic rival, Wheeler's "It from Bit," is the Church-Turing
hypothesis: All physical processes can be simulated on a universal
Turing machine. We use the tension between the two viewpoints
to look for a purely intrinsic randomness notion and find one
around the second law of thermodynamics. Quantum correlations,
combined with Kolmogorov complexity as randomness, reveal an
all-or-nothing nature of the Church-Turing hypothesis: Either
non-Turing computations are physically impossible, or they can
be carried out by "devices" as simple as individual photons. |

0.00363s c