BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/662
DTSTAMP:20230914T125933Z
SUMMARY:Threshold Secret Sharing Requires a Linear Size Alphabet
DESCRIPTION:Speaker: Andrej Bogdanov (The Chinese University of Hong Kong\n
 Shatin\, NT\nHong Kong SAR\nThe Peoples Republic of China)\n\nAbstract: \n
 Abstract: A $t$-out-of-$n$ threshold secret sharing scheme is a protocol f
 or sharing a secret among $n$ parties so that no $t -1$ parties gain any i
 nformation about the secret but any $t$ parties can recover the secret.\n\
 nWe prove that for every $n$ and $1 < t < n$\, any $t$-out-of-$n$ threshol
 d secret sharing scheme for one-bit secrets requires share size $\\log(t +
  1)$ (in bits). Our bound is tight when $t = n - 1$ and $n$ is a prime pow
 er. Together with a result of Kilian and Nisan\, this implies a share size
  lower bound of $\\max\\{\\log(n - t + 2)\, \\log(t + 1)\\} ≥ \\log ((n 
 + 3)/2)$ for every $n$ and $1 < t < n$.\n\nOur proof introduces a new semi
 definite programming framework for proving share size lower bounds for gen
 eral access structures. We show that our analysis for threshold secret sha
 ring is tight in this framework (the talk is based on joint work with Siya
 o Guo and Ilan Komargodski).\n
URL:https://www.tcs.tifr.res.in/web/events/662
DTSTART;TZID=Asia/Kolkata:20160302T160000
DTEND;TZID=Asia/Kolkata:20160302T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR