PaperlayerView exact revision on arXiv

Source-linked AI summary

Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications

M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, Farinaz Koushanfar

arXiv:1801.03239v1cs.CRcs.AI

TL;DR

Secure computation frameworks must support efficient privacy-preserving evaluation while handling the differing costs of linear and nonlinear operations. Chameleon combines additive sharing with GMW and garbled circuits, using an offline semi-honest third party for preprocessing. It reports 133x faster execution than CryptoNets and 4.2x faster than MiniONN on a convolutional neural-network evaluation.

  • Problem

    Generic SFE protocols and additive secret-sharing frameworks each have practical efficiency, scalability, or online-participation limitations for private machine learning.

  • Method

    Chameleon is a hybrid framework that assigns linear operations to additive sharing, nonlinear operations to GMW or garbled circuits, and preprocessing to an offline semi-honest third party.

  • Results

    133x faster than Microsoft CryptoNets and 4.2x faster than MiniONN are reported for convolutional-neural-network execution.

  • Takeaways & Limitations

    Chameleon supports signed fixed-point numbers and optimized vector dot products for machine-learning workloads involving heavy matrix multiplications.

  • Takeaways & Limitations

    Floating-point operations are currently performed entirely in garbled circuits, with faster decomposed floating-point protocols left as future work.

Abstract

from arXiv · show

We present Chameleon, a novel hybrid (mixed-protocol) framework for secure function evaluation (SFE) which enables two parties to jointly compute a function without disclosing their private inputs. Chameleon combines the best aspects of generic SFE protocols with the ones that are based upon additive secret sharing. In particular, the framework performs linear operations in the ring $\mathbb{Z}_{2^l}$ using additively secret shared values and nonlinear operations using Yao's Garbled Circuits or the Goldreich-Micali-Wigderson protocol. Chameleon departs from the common assumption of additive or linear secret sharing models where three or more parties need to communicate in the online phase: the framework allows two parties with private inputs to communicate in the online phase under the assumption of a third node generating correlated randomness in an offline phase. Almost all of the heavy cryptographic operations are precomputed in an offline phase which substantially reduces the communication overhead. Chameleon is both scalable and significantly more efficient than the ABY framework (NDSS'15) it is based on. Our framework supports signed fixed-point numbers. In particular, Chameleon's vector dot product of signed fixed-point numbers improves the efficiency of mining and classification of encrypted data for algorithms based upon heavy matrix multiplications. Our evaluation of Chameleon on a 5 layer convolutional deep neural network shows 133x and 4.2x faster executions than Microsoft CryptoNets (ICML'16) and MiniONN (CCS'17), respectively.

1 INTRODUCTION

Chameleon addresses efficiency and scalability limitations in secure computation by combining complementary protocols, offline preprocessing, and support for machine-learning workloads. It reports lower communication than ABY and faster neural-network execution than prior systems.

  • Framework and motivation: Chameleon combines garbled circuits, GMW, and additive secret sharing in a mixed SFE framework based on ABY.The design integrates sequential circuits, fixed-point arithmetic, and STP-based preprocessing.
  • Framework and motivation: Chameleon addresses limitations of generic garbled-circuit and secret-sharing frameworks by supporting sequential circuits and two-party online execution with an offline third party.The STP generates correlated randomness offline, while the online phase involves the two private-input parties.
  • Machine-learning support: The framework supports signed fixed-point numbers and an optimized vector dot product for matrix-heavy machine-learning tasks.The vector dot product targets frequent matrix-multiplication workloads in machine learning and data mining.
  • Performance: 321× and 256× less communication than ABY are reported for generating arithmetic and Boolean multiplication triples, respectively.These reductions come from the framework’s STP-based preprocessing protocols.
  • Performance: 133x faster execution than Microsoft CryptoNets and 4.2x faster execution than MiniONN are reported for deep and convolutional neural networks.The evaluation uses a proof-of-concept implementation on neural-network workloads.

2 PRELIMINARIES

The preliminaries introduce the secret-sharing and generic secure-computation primitives used by Chameleon. Additive sharing makes linear operations local or efficient, while Boolean protocols handle circuit-based nonlinear computation.

  • Generic protocols: Yao’s garbled-circuit protocol evaluates Boolean-circuit representations of functions using wire labels and garbled gates.Its communication depends on the circuit’s AND gates and it executes in a constant number of rounds.
  • Generic protocols: GMW evaluates Boolean circuits on secret-shared wire values, with XOR gates local and AND gates requiring interaction.Beaver-style Boolean multiplication triples support secure AND-gate evaluation and can be generated offline using OTs or a semitrusted third party.
  • Additive secret sharing: Additive secret sharing represents a value as two shares whose sum modulo 2^l reconstructs the secret.Each party holds one share, and reconstruction requires adding the shares in the ring Z2^l.
  • Additive secret sharing: Addition, subtraction, and multiplication by a public constant can be performed locally on additive shares without communication.Multiplication of two shared secrets instead requires one communication round and precomputed multiplication triples.
  • Multiplication triples: Arithmetic multiplication triples are shared values a, b, and c satisfying c = a × b, enabling multiplication of additive shares after preprocessing.The online multiplication procedure reconstructs masked differences before each party computes its output share.

3 THE CHAMELEON FRAMEWORK

Chameleon divides computation between additive sharing, GMW, and garbled circuits, with an STP preparing correlated randomness offline. Protocol selection depends on operation type and circuit structure, while online communication remains between two parties.

  • Execution model: Chameleon has an offline phase for correlated-randomness generation and a two-party online phase for secure computation.The STP supplies randomness and seeds before the parties execute on their private inputs.
  • Offline preprocessing: The offline phase precomputes OTs, arithmetic multiplication triples, Boolean multiplication triples, and vector dot-product shares.These preprocessing tasks support garbled circuits, type conversion, additive multiplication, GMW, and Du-Atallah dot products.
  • Online execution flow: Linear operations and vector dot products use additive sharing, while nonlinear operations use GMW or garbled circuits.The vector dot product of size n comprises n multiplications and n −1 additions.
  • Protocol selection: Garbled circuits are preferred for high latency or deep circuits, whereas GMW is used when its lower-depth communication model is more efficient.Garbled-circuit cost depends on AND-gate count, while GMW requires one communication round per AND-gate layer.
  • Communication: The number of communication rounds depends on protocol switches and GMW circuit depth, not on input-data size.This allows latency overhead to be amortized over high-volume input data.
  • Security model: Chameleon assumes honest-but-curious adversaries and uses an STP that is involved only in offline preprocessing, except for vector-size information in Du-Atallah dot products.The STP does not receive the parties’ inputs or the executed program in the general case.

4 CHAMELEON DESIGN AND IMPLEMENTATION

Chameleon combines additive secret sharing with GC and GMW, shifting most cryptographic work offline while supporting two-party online computation. Its design includes optimized multiplication, vector dot products, signed fixed-point numbers, and multiplication-triple generation.

  • Framework components: Chameleon implements GC, GMW, and additive secret sharing engines, with most cryptographic operations shifted from the online phase to offline preprocessing.The implementation accepts C++ programs and uses .scd and .aby circuit descriptions for GC and GMW.
  • A-SS engine: The Du-Atallah protocol lets two parties holding cleartext operands compute a product with a third party contributing an additive share.The parties exchange masked operands, and the resulting shares sum to the product.
  • A-SS engine: Chameleon moves the Du-Atallah third party’s role to the offline phase, leaving the two computing parties to communicate online.The third party precomputes multiplication material and random shares, while the parties add their new shares to the shared result.
  • A-SS engine: 2x improved online computation and communication, while offline communication improved by 3x for the optimized Du-Atallah protocol versus multiplication triples.The comparison is summarized in Table 1, whose communication values are measured in bits.
  • A-SS engine: The vector dot-product modification aggregates the third party’s shares before distributing them, enabling complete dot products between two parties.The STP generates one l-bit value and corresponding vector dot-product shares, requiring the array size during offline preprocessing.
  • Signed fixed-point numbers: Chameleon supports signed fixed-point numbers across its GC, GMW, additive-sharing, and translation protocols, whereas the current ABY version supports only unsigned integers.An abstraction layer extends ABY to signed fixed-point representation.
  • Signed fixed-point numbers: Chameleon currently performs floating-point operations entirely with GC, while decomposing them into ring and GC/GMW primitives remains future work.The paper does not report separate floating-point experiments because the GC engine is based on TinyGarble.
  • Offline preprocessing: The offline phase precomputes OTs, arithmetic and Boolean multiplication triples, and vector dot-product shares; seed expansion reduces triple communication substantially.Using shared PRG seeds reduces communication from 3 × l × NA-MT to 256 and 256 + l × NA-MT bits for the two parties, respectively.

5 MACHINE LEARNING APPLICATIONS

Chameleon applies mixed secure-computation protocols to private deep-learning and SVM inference, supporting signed fixed-point arithmetic and protocol changes across model layers. Experiments report substantially lower latency and communication than several prior secure-learning frameworks.

  • Chameleon evaluates private DNNs, CNNs, and SVMs, covering deep learning and classification applications.
  • Deep Learning: DNNs and CNNs process layered representations using fully connected, activation, and convolution operations, with CNN inputs represented as pixel matrices or tensors.
  • Deep Learning: Chameleon maps CNN layers to different execution protocols, switching environments as computation proceeds through the network.
  • Deep Learning: 133x faster than CryptoNets for MNIST CNN inference, despite Chameleon using 64-bit numbers versus CryptoNets’ 5-to-10-bit precision.
  • Deep Learning: 4.2x lower latency and 63x less communication than MiniONN are reported for similar MNIST accuracy and network; Chameleon also requires 48x less communication than EzPC.
  • Deep Learning: For MNIST batches of 100, Chameleon reports 0.18 s processing time and 10.5 MB communication per image, reaching up to 20,000 predictions per hour in a LAN.
  • Deep Learning: Chameleon also evaluates a more sophisticated CIFAR-10 CNN with 7 convolution layers, 7 ReLU layers, 2 mean-pooling layers, and one fully connected layer.

6 BENCHMARKS OF ATOMIC OPERATIONS

Chameleon is benchmarked against prior frameworks for atomic operations, conversions, and offline communication. Its precomputation and protocol choices produce major efficiency gains, while benchmark scope excludes input sharing.

  • Benchmark Scope: The atomic-operation benchmarks omit input sharing, so they do not expose improvements for GC-based operations compared with ABY.WAN atomic benchmarks are also omitted because higher latency favors constant-round garbled-circuit evaluation for binary operations.
  • Evaluation Results: Chameleon outperforms all state-of-the-art frameworks in the reported atomic-operation benchmarks.Arithmetic results are reported using additive secret sharing, while remaining atomic operations use Boolean sharing.
  • Conversions and Boolean Operations: Chameleon's Boolean-sharing operations improve over ABY because of efficient Boolean multiplication-triple precomputation.Fast STP-aided oblivious transfers also improve GMW-to-arithmetic, GMW-to-garbled-circuit, and arithmetic-to-garbled-circuit conversions.
  • Comparison with Prior Frameworks: Chameleon's efficiency advantage over Sharemind reflects fewer multiplication-protocol instances and GC/GMW handling of comparisons, equality tests, and multiplexing.Sharemind uses six Du-Atallah instances per multiplication, whereas Chameleon uses two in the general case.
  • Offline Communication: 256× less communication is required for one Boolean multiplication triple to one party than with ABY.The other party receives only constant-size data transmission for generating a single B-MT.
  • Offline Communication: 273×/289×/321× communication reductions are achieved for one arithmetic multiplication triple at 16/32/64-bit lengths, respectively.These reductions apply to communication sent to the other party during offline generation.

7 RELATED WORK

Chameleon extends mixed-protocol secure computation with sequential circuits, signed fixed-point support, and STP-assisted offline preprocessing. Compared with related frameworks, it retains two-party online computation while improving efficiency, but lacks automatic protocol selection.

  • Third-Party-Based Computation: Chameleon uses a semi-honest third party only offline to generate correlated randomness, leaving the STP out of the online phase.The STP precomputes oblivious transfers and multiplication triples used by the two-party computation.
  • Evaluation Scope: The benchmarking methodology inherited from ABY omits input sharing, preventing measurable improvements for GC-based operations.This is a scope limitation of the reported comparison rather than a claim about all Chameleon operations.
  • Secret-Sharing Frameworks: Chameleon uses fewer multiplication-protocol instances than Sharemind and operates modulo 2^l rather than a less efficient prime modulus used by SEPIA.Chameleon needs one instance when one operand is shared and two when both operands are shared, compared with six for Sharemind.
  • Mixed Protocol Frameworks: Unlike TASTY, Chameleon avoids relying on homomorphic encryption and its costly conversion to garbled circuits.TASTY's computational and conversion costs yield only marginal improvement over single-protocol execution.
  • Mixed Protocol Frameworks: Chameleon extends ABY with sequential circuits, signed fixed-point numbers, and more efficient online and offline execution.Sequential circuits improve scalability beyond ABY's combinational-only circuit descriptions, while signed fixed-point numbers target machine-learning applications.
  • Automatic Protocol Selection: Chameleon's current version does not automatically select protocols, although existing heuristic and integer-programming methods could support future partitioning.The cited methods automatically combine secure protocols or insert conversions to reduce total cost.

8 CONCLUSION

Chameleon combines mixed protocols, sequential garbled circuits, optimized vector dot products, and STP-generated preprocessing for secure machine-learning computation. In a convolutional neural network evaluation, it substantially outperformed CryptoNets and MiniONN.

  • Contributions: Chameleon integrates sequential garbled circuits, optimized vector dot products, and STP-generated correlated randomness for preprocessing.The framework uses this hybrid design to support secure matrix multiplications and two-party online computation.
  • Machine-Learning Support: Chameleon supports signed fixed-point numbers, a feature positioned for machine-learning applications including convolutional neural networks.The vector dot product is designed for heavy matrix multiplications in encrypted-data mining and classification.
  • Evaluation: 133x faster execution was achieved than Microsoft CryptoNets, and 4.2x faster execution than MiniONN on the evaluated convolutional neural network.The evaluation processed handwritten digits using the reported neural-network setting.
Loading 1801.03239v1…