28 June 2021 - Martin Albrecht

Speaker

Martin Albrecht

Title

Abstract 

We study when (dual) Vandermonde systems of the form V_T^(ᵀ)·z=s·w admit a solution z over a ring R, where V_T is the Vandermonde matrix defined by a set T and where the “slack” s is a measure of the quality of solutions. To this end, we propose the notion of (s,t)-subtractive sets over a ring R, with the property that if S is (s,t)-subtractive then the above (dual) Vandermonde systems defined by any t-subset T⊆S are solvable over R. The challenge is then to findlarge sets S while minimising (the norm of) s when given a ring R.

By constructing families of (s,t)-subtractive sets S of size n=poly(λ) over cyclotomic rings R=Z[ζp`] for prime p, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation A·x=s·y modq with O(1/n) knowledge error, and s= 1 in case p=poly(λ). Our technique slots naturally into the lattice Bulletproof framework from Crypto’20, producing lattice-based succinct arguments for NP with better parameters.

We then give matching impossibility results constraining n relative to s, which suggest that our Bulletproof-compatible protocols are optimal unless fundamentally new techniques are discovered. Noting that the knowledge error of lattice Bulletproofs is Ω(logk/n) for witnesses in R^k and subtractive set sizen, our result represents a barrier to practically efficient lattice-based succinct arguments in the Bulletproof framework.

Beyond these main results, the concept of (s,t)-subtractive sets bridges group-based threshold cryptography to lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.

Bio

Martin R. Albrecht is a professor in the Information Security Group and the director of the Cryptography Group. His research is focused on all aspects of cryptography from the hard mathematical problems underlying it to the cryptanalysis of deployed cryptographic protocols and implementations. His recent work focuses on lattice-based and post-quantum cryptography, block ciphers for algebraic platforms and attacks on cryptographic protocols. He is also a contributor to the [Sage Mathematics Software](https://www.sagemath.org) and [many](https://github.com/malb) [other](https://bitbucket.org/malb) open-source projects.

Martin studied Computer Science at Universität Bremen in Germany before coming to Royal Holloway to earn his PhD under the supervision of Carlos Cid. After completing his PhD he took a postdoc position at LIP6 in Paris in the POLSYS group of Jean-Charles Faugère and then moved to DTU in Copenhagen to join the team of Lars Knudsen. He came back to Royal Holloway for a postdoc position with Kenny Paterson before becoming a lecturer in the Information Security Group. His Erdős–Bacon number is 6.