MEG: Memory and Energy Efficient Garbled Circuit Evaluation on Smartphones


Garbled circuits are a general tool that allows two parties to compute any function without disclosing their respective inputs. Applications of this technique vary from distributed privacy-preserving machine learning tasks, to secure outsourced authentication. Unfortunately, the energy cost of garbled circuit evaluation protocols is substantial. This limits the applicability of garbled circuits in scenarios that involve battery-operated devices, such as Internet of things (IoT) devices and smartphones. In this paper, we propose MEG, a Memory- and Energy- efficient Garbled circuit evaluation mechanism. MEG utilizes batch data transmission and multi-threading to reduce memory and energy consumption. We implement MEG on an Android smartphone, and compare its performance and energy consumption to state-of-the-art techniques using two garbled circuits of widely different sizes (AES-128, and 256-bit edit distance). Our results show that, compared to “plain” garbled circuit evaluation, MEG decreases memory consumption by more than 90%. When compared with current pipelined garbled circuit evaluation techniques, MEG’s energy usage was 42% lower for AES-128, and 23% lower for EDT-256. Further, our multi-thread implementation of MEG decreased circuit evaluation time by up to 56.7% for AES-128, and by up to 13.5% for EDT-256, compared to state-of-the-art pipelining techniques.

Transactions on Information Forensics and Security (T-IFS)