Paper 2024/236

Public-Key Cryptography through the Lens of Monoid Actions

Hart Montgomery, Linux Foundation
Sikhar Patranabis, IBM Research India
Abstract

We show that key exchange and two-party computation are exactly equivalent to monoid actions with certain structural and hardness properties. To the best of our knowledge, this is the first "natural" characterization of the mathematical structure inherent to any key exchange or two-party computation protocol, and the first explicit proof of the necessity of mathematical structure for public-key cryptography. We then utilize these characterizations to show a new black-box separation result, while also achieving a simpler and more general version of an existing black-box separation result. Concretely, we obtain the following results: - Two-Party Key Exchange. We show that that any two-party noninteractive key exchange protocol is equivalent to the existence of an abelian monoid equipped with a natural hardness property, namely (distributional) unpredictability. More generally, we show that any $k$-round (two-party) key exchange protocol is essentially equivalent to the existence of a (distributional) unpredictable monoid with certain commutator-like properties. We then use a generic version of this primitive to show a simpler and more general version of Rudich's (Crypto '91) black-box separation of $k$-round and $(k+1)$-round key exchange. - Two-Party Computation. We show that any maliciously secure two-party computation protocol is also equivalent to a monoid action with commutator-like properties and certain hardness guarantees. We then use a generic version of this primitive to show a black-box separation between $k$-round semi-honest secure two-party computation and $(k+1)$-round maliciously secure two-party computation. This yields the first black-box separation (to our knowledge) between $k$-round and $(k+1)$-round maliciously secure two-party computation protocols. We believe that modeling cryptographic primitives as mathematical objects (and our approach of using such modeling for black-box separations) may have many other potential applications and uses in understanding what sort of assumptions and mathematical structure are necessary for certain cryptoprimitives.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Foundations of CryptographyMathematical StructureBlack-box SeparationsKey ExchangeTwo-party Computation
Contact author(s)
hart montgomery @ gmail com
sikharpatranabis @ gmail com
History
2024-02-16: approved
2024-02-14: received
See all versions
Short URL
https://ia.cr/2024/236
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/236,
      author = {Hart Montgomery and Sikhar Patranabis},
      title = {Public-Key Cryptography through the Lens of Monoid Actions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/236},
      year = {2024},
      url = {https://eprint.iacr.org/2024/236}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.