Paper 2023/1464

Round-Robin is Optimal: Lower Bounds for Group Action Based Protocols

Daniele Cozzo, IMDEA Software
Emanuele Giunta, IMDEA Software, Universidad Politécnica de Madrid
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2023
Keywords
Generic Action ModelCSIDHRound RobinLower Bounds
Contact author(s)
daniele cozzo @ imdea org
emanuele giunta @ imdea org
History
2023-09-29: revised
2023-09-24: received
See all versions
Short URL
https://ia.cr/2023/1464
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1464,
      author = {Daniele Cozzo and Emanuele Giunta},
      title = {Round-Robin is Optimal: Lower Bounds for Group Action Based Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1464},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1464}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.