Towards Building Efficient SCALES Protocols

Anasuya Acharya; Carmit Hazay; Vladimir Kolesnikov; Manoj Prabhakaran

Paper 2025/1487

Towards Building Efficient SCALES Protocols

Anasuya Acharya

, Aarhus University

Carmit Hazay

, Bar-Ilan University

Vladimir Kolesnikov

, Georgia Institute of Technology

Manoj Prabhakaran, Indian Institute of Technology Bombay

Abstract

SCALES (Small Clients And Larger Ephemeral Servers) (Acharya et al., TCC 2022, CRYPTO 2024) is a recently proposed model for MPC with several attractive features, including resilience to adaptive corruption. Known SCALES constructions, while offering reasonable asymptotics for large-scale MPC, incur high concrete costs both in computation and communication. As our primary contribution, we dramatically improve both asymptotic and concrete costs of SCALES for permutation branching programs (PBP), a well-motivated practical model of computation. We achieve linear cost in program length, input size, and the security parameter. Our instantiations of the building blocks may be of independent interest. Further, we present generic transformations to extend any semi-honestly secure SCALES protocol to achieve (1) guaranteed output delivery in the presence of mixed adversaries (that corrupt servers maliciously and clients semi-honestly) in the all-but-one corruption setting; and (2) protocols for computing general functionalities where each server's computation scales sub-linearly in the function~size.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in ASIACRYPT 2025
Keywords: SCALES MPC with Ephemeral Servers Semi-Honest Security Guaranteed Output Delivery Rerandomizable Garbled Circuits
Contact author(s): acharya @ cs au dk
carmit hazay @ biu ac il
kolesnikov @ gatech edu
mp @ cse iitb ac in
History: 2025-08-20: approved; 2025-08-17: received; See all versions
Short URL: https://ia.cr/2025/1487
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1487,
      author = {Anasuya Acharya and Carmit Hazay and Vladimir Kolesnikov and Manoj Prabhakaran},
      title = {Towards Building Efficient {SCALES} Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1487},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1487}
}