Fwd: Paul Lou on Sept 25

[Alan Karp]

This talk is part of the regular crypt seminar series.  Talks in this series are much more technical than the lunch talks.

--------------
Alan Karp

---------- Forwarded message ---------
From: Aditi Partap <adit...@stanford.edu>
Date: Fri, Sep 19, 2025 at 11:00 AM
Subject: Paul Lou on Sept 25
To: security...@lists.stanford.edu <security...@lists.stanford.edu>

              Fully Anonymous Secret Sharing

                          Paul Lou

                Thursday, September 25, 2025

                       Talk at 4:00pm

                      CoDA E201 & Zoom

Abstract:

In a secret sharing scheme for a monotone access structure A, a dealer

can share a secret s to n parties such that any authorized subset of

parties can recover s while all other subsets learn nothing about s.  In

this work, we study fully anonymous secret sharing (FASS), which

strengthens standard secret sharing by requiring the following

properties: 1.  Share Anonymity: The shares belonging to any

unauthorized set of parties not only hide the secret, but also all

identifiable information such as party identities and whether or not the

shares were generated together.  In particular, it suffices that such

shares be uniform and independent.  2.  Anonymous Reconstruction: The

reconstruction algorithm does not need to know the reconstructing set of

parties.

Efficient FASS exists for threshold access structures.  For general

access structures, the only known construction relies on a monotone DNF

representation of A and has per-party share size $\Omega(\ell n)$ where

$\ell$ is the number of minterms of A.  This leaves an exponential gap

between standard secret sharing and FASS even for simple access

structures.  Moreover, even in the threshold case, known schemes could

not achieve optimal robust reconstruction when mixing shares of multiple

secrets.

Motivated by a recent work of Eldridge et al.  [USENIX'24], who

demonstrated an application of FASS to stalker detection, we initiate a

systematic study of FASS, obtaining the following main results.  1.

Near-Optimal Information-Theoretic FASS: We obtain strong lower bounds,

showing that the dependence on the DNF size is generally inherent.  In

particular, the share size can be exponential in the number of parties

or even in the minimum CNF size.  This stands in sharp contrast to

standard secret sharing, where no super-polynomial lower bounds are

known, and where the share size is upper bounded by the CNF size.  For

DNF with $\ell$ small minterms, we improve the previous upper bound to

$\tilde O(\ell)$, matching our lower bound up to a polylogarithmic

factor.  2.  Computational FASS: We show that the above negative results

can be circumvented in the computational setting, obtaining FASS schemes

with succinct shares.  Under the learning with errors (LWE) assumption,

we present a general compiler from standard secret sharing to FASS that

preserves the share size of the underlying scheme.  For natural graph

access structures, we directly construct succinct FASS from either

one-way functions or bilinear maps.  3.  Robust FASS: We show that

simple modifications of our computational FASS schemes can allow for

robust reconstruction of a polynomially unbounded number of secrets from

any mixture of their authorized shares.

This is joint work with Allison Bishop, Matthew Green, Yuval Ishai, and

Abhishek Jain.

Bio:

Paul Lou is a postdoctoral researcher at Bocconi University working with

Prof.  Alon Rosen.  He completed his Ph.D.  at UCLA with Prof.  Amit

Sahai and his undergraduate degrees from the University of Pennsylvania

where he was supervised by Prof.  Nadia Heninger.  He is interested

broadly in cryptography and is currently focused on building fundamental

cryptographic primitives, such as public-key encryption, from new

hardness assumptions.

--++**==--++**==--++**==--++**==--++**==--++**==--++**==
security-seminar mailing list
security...@lists.stanford.edu
https://mailman.stanford.edu/mailman/listinfo/security-seminar