BEGIN:VCALENDAR
CALSCALE:GREGORIAN
VERSION:2.0
X-WR-TIMEZONE:Europe/Paris
METHOD:PUBLISH
PRODID:-//LIP6//www.lip6.fr//FR
X-WR-CALNAME;VALUE=TEXT:Séminaire LIP6
X-LIC-LOCATION:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
DTSTART:19810329T020000
TZNAME:GMT+02:00
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
DTSTART:19961027T030000
TZNAME:GMT+01:00
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Lower and Upper Bounds on the Randomness Complexity of Private Com
putations of AND
ORGANIZER;CN=Damien Vergnaud:MAILTO:damien.vergnaud@lip6.fr
ATTENDEE;CN=Damien Vergnaud;CUTYPE=INDIVIDUAL;PARTSTAT=ACCEPTED
DESCRIPTION:(joint work with Eyal Kushilevitz\, Rafail Ostrovsky\, Emmanue
l Prouff\, Adi Rosen & Adrian Thillard)
We consider multi-party informat
ion-theoretic private protocols\, and specifically their randomness comple
xity. The randomness complexity of private protocols is of interest both b
ecause random bits are considered a scarce resource\, and because of the r
elation between that complexity measure and other complexity measures of B
oolean functions such as the circuit size or the sensitivity of the functi
on being computed. More concretely\, we consider the randomness complexity
of the basic Boolean function and\, that serves as a building block in th
e design of many private protocols. We show that and cannot be privately c
omputed using a single random bit\, thus giving the first non-trivial lowe
r bound on the 1-private randomness complexity of an explicit Boolean func
tion. We further show that the function and\, on any number of inputs n (o
ne input bit per player)\, can be privately computed using 8 random bits.
Together with our lower bound\, we thus approach the exact determination o
f the randomness complexity of and. To the best of our knowledge\, the exa
ct randomness complexity of private computation is not known for any expli
cit function (except for xor\, which is trivially 1-random\, and for sever
al degenerate functions).
DTSTAMP:20200526T232209Z
DTSTART;TZID=Europe/Paris:20191107T143000
DURATION:PT2H
URL;VALUE=URI:https://www.lip6.fr/liens/organise-fiche.php?ident=O1025
UID:LIP6/SEM/O1025
LOCATION:Campus Jussieu\, salle Jean-Louis Laurière (24-25/309)\, 4 plac
e Jussieu\, 75005 Paris
GEO:48.846954;2.354357
END:VEVENT
END:VCALENDAR