Tighter bounds on multi-party coin flipping via augmented weak martingales and differentially private sampling

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

16 اقتباسات (Scopus)

ملخص

In his seminal work, Cleve [STOC '86] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(1/r). This lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for n-party protocols when n < loglogr by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n > loglogr, however, the best bias for n-party coin-flipping protocols remains O(n/√r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ϵ > 0, an rϵ -party r-round coin-flipping protocol can be efficiently biased by Ω(1√r). As far as we know, this is the first improvement of Cleve's bound, and is only n = rϵ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
المحررونMikkel Thorup
ناشرIEEE Computer Society
الصفحات838-849
عدد الصفحات12
رقم المعيار الدولي للكتب (الإلكتروني)9781538642306
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 30 نوفمبر 2018
الحدث59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, فرنسا
المدة: ٧ أكتوبر ٢٠١٨٩ أكتوبر ٢٠١٨

سلسلة المنشورات

الاسمProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
مستوى الصوت2018-October
رقم المعيار الدولي للدوريات (المطبوع)0272-5428

!!Conference

!!Conference59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
الدولة/الإقليمفرنسا
المدينةParis
المدة٧/١٠/١٨٩/١٠/١٨

بصمة

أدرس بدقة موضوعات البحث “Tighter bounds on multi-party coin flipping via augmented weak martingales and differentially private sampling'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا