26838 research outputs found
Sort by
Post-quantum privacy for traceable receipt-free encryption
Get PDFTraceable Receipt-free Encryption (TREnc) has recently been introduced as a verifiable public-key encryption primitive endowed with a unique security model. In a nutshell, TREnc allows randomizing ciphertexts in transit in order to remove any subliminal information up to a public trace that ensures the non-malleability of the underlying plaintext. A remarkable property of TREnc is the indistinguishability of the randomization of chosen ciphertexts against traceable chosen-ciphertext attacks (TCCA). The main application lies in voting systems by allowing voters to encrypt their votes, tracing whether a published ballot takes their choices into account, and preventing them from proving how they
voted. While being a very promising primitive, the few existing TREnc mechanisms solely rely on discrete-logarithm related assumptions making them vulnerable to the well-known record-now/decrypt-later attack in the wait of quantum computers.
We address this limitation by building the first TREnc whose privacy withstands the advent of quantum adversaries in the future. To design our construction, we first generalize the original TREnc primitive that is too restrictive to be easily compatible with built-in lattice-based semantically-secure encryption. Our more flexible model keeps all the ingredients generically implying receipt-free voting. Our instantiation relies on Ring Learning With Errors (RLWE) with pairing-based statistical zero-knowledge simulation sound proofs from Groth-Sahai, and further enjoys a public-coin common reference string removing the need of a trusted setup
Invited talk: "De Wiskunde van de Ergernis: Slimme algoritmen om wachttijden te verminderen"
No full text
Moment-sos and spectral hierarchies for polynomial optimization on the sphere and quantum de Finetti theorems
Get PDFWe revisit the convergence analysis of two approximation hierarchies for polynomial optimization on the unit sphere. The first one is based on the moment-sos approach and gives semidefinite bounds for which Fang and Fawzi (2021) showed an analysis in O(1/r2) for the r-th level bound, using the polynomial kernel method. The second hierarchy was recently proposed by Lovitz and Johnston (2023) and gives spectral bounds for which they show a convergence rate in O(1/r), using a quantum de Finetti theorem of Christandl et al. (2007) that applies to complex Hermitian matrices with a "double" symmetry. We investigate links between these approaches, in particular, via duality of moments and sums of squares. We also propose another proof for the analysis of the spectral bounds, via a "banded" real de Finetti theorem, and show that the spectral bounds cannot have a convergence rate better than O(1/r2). In addition, we show how to use the polynomial kernel method to obtain a de Finetti type result for real maximally symmetric matrices, improving an earlier result of Doherty and Wehner (2012)
Random restrictions of high-rank tensors and polynomial maps
Get PDFMotivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, for a broad class of rank functions called natural rank functions, random coordinate restriction to a dense set will typically reduce the rank by at most a constant factor
A peek inside art objects: New algorithm makes CT scan more accessible
No full textAn X-ray scanner, some small metal balls, and a newly developed algorithm. That is all you need to make a 3D model that enables you to look inside art objects without dismantling them. Thanks to the research of Francien Bossema (Centrum Wiskunde & Informatica and Leiden Institute of Advanced Computer Science), museums can now use existing X-ray equipment as CT scanners, without having to buy such a costly and complicated device. Bossema graduated on 23 May
Fusing 3D imaging modalities for the internal and external investigation of multi-material museum objects
No full textGrothendieck inequalities characterize converses to the polynomial method
Get PDFA surprising ‘converse to the polynomial method’ of Aaronson et al. (CCC’16)
shows that any bounded quadratic polynomial can be computed exactly in expec-
tation by a 1-query algorithm up to a universal multiplicative factor related to the
famousGrothendieckconstant. Hereweshowthatsucharesultdoesnotgeneralize
to quartic polynomials and 2-query algorithms, even when we allow for additive
approximations. We also show that the additive approximation implied by their
result is tight for bounded bilinear forms, which gives a new characterization of the
Grothendieck constant in terms of 1-query quantum algorithms. Along the way
we provide reformulations of the completely bounded norm of a form, and its dual
norm