Welcome to the resource topic for 2023/1464
Title:
Round-Robin is Optimal: Lower Bounds for Group Action Based Protocols
Authors: Daniele Cozzo, Emanuele Giunta
Abstract:An hard homogeneous space (HHS) is a finite group acting on a set with
the group action being hard to invert and the set lacking any algebraic
structure.
As such HHS could potentially replace finite groups where the discrete logarithm is hard for building cryptographic primitives and protocols in a post-quantum world.
Threshold HHS-based primitives typically require parties to compute the group action of a secret-shared input on a public set element.
On one hand this could be done through generic MPC techniques, although they incur in prohibitive costs due to the high complexity of circuits evaluating group actions known to date.
On the other hand round-robin protocols only require black box usage of the HHS.
However these are highly sequential procedures, taking as many rounds as parties involved.
The high round complexity appears to be inherent due the lack of homomorphic properties in HHS, yet no lower bounds were known so far.
In this work we formally show that round-robin protocols are optimal.
In other words, any at least passively secure distributed computation of a group action making black-box use of an HHS must take a number of rounds greater or equal to the threshold parameter.
We furthermore study fair protocols in which all users receive the output in the same round (unlike plain round-robin), and prove communication and computation lower bounds of \Omega(n \log_2 n) for n parties.
Our results are proven in Shoup’s Generic Action Model (GAM), and hold regardless of the underlying computational assumptions.
ePrint: https://eprint.iacr.org/2023/1464
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .