PaperlayerView exact revision on arXiv

Source-linked AI summary

SIRNN: A Math Library for Secure RNN Inference

Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, Aseem Rastogi

arXiv:2105.04236v1cs.CRcs.LGcs.MS

TL;DR

Secure inference for RNNs is hindered by high-communication generic 2PC implementations of math functions. The paper introduces precise lookup-table and mixed-bitwidth protocols and implements them in SIRNN, which reports up to 423× lower communication for math functions and three orders of magnitude better end-to-end performance than a state-of-the-art baseline.

  • Problem

    Existing secure inference supports CNNs more readily than RNN-based models because exponentiation, sigmoid, tanh, and reciprocal square root rely on high-communication generic 2PC protocols.

  • Method

    The paper develops lookup-table-based, numerically precise math functionalities and specialized 2PC protocols for mixed-bitwidth operations, then integrates them into the SIRNN inference library.

  • Results

    SIRNN provides secure inference for RNNs on speech and sensor data and CNN-RNN head detection, with up to 423× lower math-protocol communication and three orders of magnitude lower end-to-end latency and communication than prior or baseline systems.

  • Takeaways & Limitations

    Precise mixed-bitwidth protocols extend practical secure inference to RNN and hybrid CNN-RNN workloads while preserving cleartext model accuracy.

Abstract

from arXiv · show

Complex machine learning (ML) inference algorithms like recurrent neural networks (RNNs) use standard functions from math libraries like exponentiation, sigmoid, tanh, and reciprocal of square root. Although prior work on secure 2-party inference provides specialized protocols for convolutional neural networks (CNNs), existing secure implementations of these math operators rely on generic 2-party computation (2PC) protocols that suffer from high communication. We provide new specialized 2PC protocols for math functions that crucially rely on lookup-tables and mixed-bitwidths to address this performance overhead; our protocols for math functions communicate up to 423x less data than prior work. Some of the mixed bitwidth operations used by our math implementations are (zero and signed) extensions, different forms of truncations, multiplication of operands of mixed-bitwidths, and digit decomposition (a generalization of bit decomposition to larger digits). For each of these primitive operations, we construct specialized 2PC protocols that are more communication efficient than generic 2PC, and can be of independent interest. Furthermore, our math implementations are numerically precise, which ensures that the secure implementations preserve model accuracy of cleartext. We build on top of our novel protocols to build SIRNN, a library for end-to-end secure 2-party DNN inference, that provides the first secure implementations of an RNN operating on time series sensor data, an RNN operating on speech data, and a state-of-the-art ML architecture that combines CNNs and RNNs for identifying all heads present in images. Our evaluation shows that SIRNN achieves up to three orders of magnitude of performance improvement when compared to inference of these models using an existing state-of-the-art 2PC framework.

I. INTRODUCTION

Secure inference systems support CNNs well but lack efficient support for RNN math functions, motivating specialized precise protocols with mixed bitwidths. SIRNN applies these protocols to end-to-end RNN and hybrid models, achieving substantially lower communication and latency while preserving accuracy.

  • Motivation: RNNs and CNN-RNN architectures rely extensively on exponentiation, reciprocal square root, sigmoid, and tanh, unlike CNNs using mainly ReLU and Maxpool.These functions are important for sequential and time-series applications such as speech and sensor data.
  • Approach: SIRNN uses provably precise math functionalities and novel protocols for mixed bitwidths instead of uniform-width secure computation.The protocols switch bitwidths, support differing operand widths, and mimic low-bitwidth cleartext computations.
  • Results: 423× lower communication is achieved by the proposed 2PC math protocols compared with prior work.Lookup tables provide initial approximations, while iterative methods improve them using fixed-point arithmetic and non-uniform bitwidths.
  • Results: Three orders of magnitude lower latency and communication are reported for SIRNN than for the ABY baseline on evaluated secure-inference benchmarks.The evaluated models include RNNs for speech and sensor data and a CNN-RNN model for identifying human heads in images.
  • Applications: SIRNN enables secure inference for speech RNNs, sensor-data RNNs, and a CNN-RNN head-detection model while retaining cleartext model accuracy.The head-detection model runs securely in under 7 minutes despite roughly 3 million sigmoid and tanh calls each.

III. PRELIMINARIES

The paper establishes the fixed-point, security, and 2PC building blocks used by its secure math protocols. It also motivates ULP error as a precision measure and defines core functionalities such as conversion, multiplexing, lookup, comparison, and Boolean operations.

  • Math Precision: Standard libraries do not generally provide correctly rounded results because the Table maker’s dilemma makes such implementations computationally expensive.The paper therefore treats low ULP error as a practical measure of numerical precision.
  • Math Precision: ULP error counts representable numbers between an exact real result and the finite-bit library output, remaining well-defined across magnitudes.The paper uses ULPs because absolute and relative error have important limitations.
  • Threat Model: The security model considers static semi-honest probabilistic-polynomial-time adversaries corrupting one party and uses simulation-based security.Protocols are described in a hybrid model where subprotocols are replaced by trusted functionality calls.
  • Fixed-Point Representation: Fixed-point values use a bitwidth ℓ and scale s, with encoding Fix(x, ℓ, s) = ⌊x·2^s⌋ mod 2^ℓ.The scale determines the fractional-part width, while ℓ−s determines the integer-part width.
  • 2PC Functionalities: Core 2PC functionalities include Boolean-to-arithmetic conversion, multiplexing, lookup tables, comparisons, wrap detection, and Boolean AND.Their protocols use additive secret sharing, oblivious transfer, correlated OT, and Beaver bit-triples.
  • 2PC Functionalities: Lookup tables map an m-bit shared input to an n-bit shared table value using one 1-out-of-k oblivious transfer.The stated communication is 2λ + Mn bits for a table with M entries of n bits each.

IV. BUILDING BLOCK PROTOCOLS

The building blocks support secure mixed-bitwidth computation through extension protocols and specialized handling of signed values. These protocols improve communication over garbled-circuit baselines while preserving correctness across ring representations.

  • Extension: Zero and signed extension lift m-bit values to n bits while preserving unsigned or signed interpretation, respectively.Zero extension preserves uint(x), whereas signed extension preserves int(x).
  • Extension: The zero-extension protocol uses log m + 2 rounds and less than λ(m + 1) + 13m + n bits of communication.
  • Signed extension: Signed extension converts the signed interpretation into a zero-extension computation followed by subtraction of 2^(m−1).The conversion uses int(x) = x′ − 2^(m−1), where x′ = x + 2^(m−1) mod M.
  • Extension: Garbled-circuit zero and signed extension costs λ(4m+2n−4) bits, roughly 6× the cost of the proposed protocols.

B. Truncation

The truncation protocols cover shifts, truncate-and-reduce, and division by powers of two while exploiting mixed-width wrap computations. Their communication improves over prior generic or garbled-circuit approaches, especially when reducing the output ring.

  • Operations: The truncation suite includes logical and arithmetic right shifts, truncate-and-reduce, and C-style division by a power of two.These operations either preserve the original bitwidth or output in a smaller ring.
  • Right shifts: The logical-right-shift protocol computes separate wrap terms over ℓ and s bits and combines them through a Boolean-share conversion.Its construction is based on decomposing each share into upper and lower bit strings.
  • Right shifts: The optimized shift protocol costs less than λ(ℓ + 3) + 15ℓ + s + 20 bits and requires log ℓ + 3 rounds.
  • Truncate and reduce: Truncate-and-reduce costs λ(s + 1) + ℓ + 13s bits, versus λ(ℓ + s + 2) + 19ℓ + 14s bits for the prior arithmetic-right-shift approach.The proposed protocol avoids computing intermediate shares that are unnecessary after reducing the output ring.
  • Division by a power of two: Division by 2^s requires roughly λ(ℓ + 2s + 4) bits, compared with λ(8ℓ + 2s − 6) bits for a garbled-circuit implementation.The protocol rounds toward zero for signed values as required by the fixed-point benchmarks.

C. Multiplication with non-uniform bitwidths

The multiplication protocols directly support operands with different bitwidths instead of first extending them to a common width. They reduce communication for secure products and extend the same ideas to matrix multiplication and convolution.

  • Core functionality: The protocols multiply operands of m and n bits while producing outputs in a larger ring, supporting the non-uniform widths used by the models.
  • Unsigned multiplication: The mixed-width multiplication protocol has communication complexity µ(λ + µ/2 + 1/2) + mn, where µ = min(m,n).
  • Unsigned multiplication: The unsigned multiplication protocol uses local products, cross-term computation, wrap values, and multiplexing to assemble the mixed-width result.
  • Communication comparison: The new protocol is roughly 1.5× cheaper than extend-then-multiply, whose communication is approximately 3λ(µ+ν)+(m+n)^2+15(m+n).Here µ = min(m,n) and ν = max(m,n).
  • Signed multiplication: Signed multiplication reuses the unsigned multiplication protocol and incorporates signed corrections without additional cost.The correction terms use the wrap indicators of shifted signed representations.
  • Matrix multiplication and convolutions: Matrix multiplication extends only the larger-width operands by e = ⌈log d2⌉ bits, preventing addition overflow while exploiting repeated matrix elements.The resulting protocol also extends to convolutions.

D. Digit Decomposition and MSNZB

Digit decomposition splits a shared bitstring into variable-length digits, while MSNZB identifies the position of its most significant nonzero bit. These functionalities supply structured bit information for later secure math protocols.

  • Digit decomposition: Digit decomposition outputs c shared digits with specified lengths {d_i} whose concatenation reconstructs the original ℓ-bit value.
  • MSNZB: MSNZB outputs one-hot Boolean shares indicating the index of the most significant nonzero bit of an ℓ-bit input.
  • Protocols: The paper describes protocols for digit decomposition and MSNZB in its appendices.

E. MSB-to-Wrap Optimization

The paper’s math functionalities use mixed bitwidths and lookup-table-based approximations, with specialized protocols for the required arithmetic operations. Exponential, sigmoid, and tanh are built from digit decomposition, LUT lookup, mixed-width multiplication, truncation, extension, and reciprocal computation.

  • E. MSB-to-Wrap Optimization: MSB-to-Wrap computes wrap shares more efficiently when the most significant bit is known or shared.The optimization applies to extension, multiplication, and truncation-related operations; exponential LUT products often have publicly known zero MSBs because their operands are positive.
  • E. MSB-to-Wrap Optimization: Exponentiation decomposes its input into digits, applies LUTs to the digits, multiplies the resulting fixed-point values, and extends the result.For m = n = 16, d = 8, and s′ = 14, two LUTs process the upper and lower 8-bit portions of the input.

C. Reciprocal of Square Root

The reciprocal-square-root functionality normalizes inputs, obtains an LUT-based initial approximation, and refines it with Goldschmidt iterations using variable bitwidths. The paper formally verifies precise results for its evaluated parameter settings and reports ULP guarantees for the implemented math functions.

  • C. Reciprocal of Square Root: Reciprocal square root maps positive x to 1/√x and adds a public ε when x is small to avoid divide-by-zero errors.The presented functionality assumes z ≥ ε.
  • C. Reciprocal of Square Root: The protocol first reduces the input range to 1 ≤ x′ < 2 by computing the most significant non-zero bit and normalizing x.The normalization uses parameters A, B, and C before forming x′ through mixed-width multiplication.
  • C. Reciprocal of Square Root: For evaluated parameters, the paper formally verifies precise reciprocal-square-root results.The chosen g and t parameters are verified for the evaluated values of ℓ, s, and s′.
  • C. Reciprocal of Square Root: The initial reciprocal-square-root approximation is obtained with digit decomposition and LUT protocols, then refined by Goldschmidt iterations using variable bitwidths and truncation.The protocol computes terms from a one-hot encoding of the most significant non-zero bit and uses those terms in the approximation procedure.
  • C. Reciprocal of Square Root: ULP error is at most 4 for reciprocal square root over scales sx, sy ∈ [4, 13] with ε = 0.1 and t = 1.The broader verification reports maximum ULP errors of 3 for exponential, 3 for sigmoid, and 4 for tanh, with ULP error below 5 overall.

A. Microbenchmarks

SIRNN’s specialized protocols substantially reduce communication and preserve numerical precision across math-function microbenchmarks, while enabling secure inference on RNN and CNN-RNN workloads. The case studies show practical latency and accuracy, including models with far more sigmoid/tanh calls than prior benchmarks.

  • Math-function protocols: Less than 5KB of communication per sigmoid evaluation achieves at most 3 ULPs of error at 12-bit precision.Communication grows linearly with the number of instances, while observed latency grows sub-linearly.
  • Math-function protocols: MiniONN’s 48-piece spline incurs a 70× communication overhead for error below 5 ULPs, whereas its 12-piece spline incurs 19× overhead and 104 ULPs of error.The 12-piece spline suffices for the cited RNN’s cross-entropy loss but remains inferior in both precision and performance.
  • Math-function protocols: MP-SPDZ’s polynomial sigmoid communicates 201× more than SIRNN at comparable error, while its piecewise-linear baseline is worse in both precision and communication.The comparison covers two general-purpose 2PC sigmoid implementations.
  • Math-function protocols: A 3-piece sigmoid spline used by SecureML and ABY2.0 has 1547 ULPs of error and reduces Google-30 accuracy from 84.4% to 60.95%.The cited passage reports that this approximation is unsuitable for generic math libraries.
  • Math-function protocols: SIRNN’s protocols are orders of magnitude better than MP-SPDZ for exponentiation and reciprocal square root in both time and communication.The comparison uses power-of-2 ring-based protocols at scale 12.
  • End-to-end case studies: SIRNN evaluates RNNs on sensor and speech data and a CNN-RNN head-detection model, preserving or exceeding the provided fixed-point models’ accuracy.The case studies cover Industrial-72, Google-30, and Heads; the Heads workload includes reciprocal square-root operations.
  • End-to-end case studies: The Heads model makes about 3 million sigmoid/tanh calls, three orders of magnitude more than prior-work benchmarks, yet SIRNN completes it in under 7 minutes.SIRNN also reports 4 seconds for Industrial and under a minute for Google-30; batching reduces amortized times to 0.1s and 1.1s, respectively.
  • End-to-end case studies: SIRNN achieves over 500× lower communication than ABY and more than an order-of-magnitude faster runtime in the reported comparison.The comparison uses a code generator translating EZPC code to ABY code.

APPENDIX

This appendix develops optimized 2PC primitives for selection, comparison, wrapping, addition, and division-related operations over mixed representations.

  • MUX: The MUX protocol uses COT to combine Boolean and ℓ-bit shared values, with local computation for same-party terms.The remaining cross terms are computed using two parallel COTs, yielding a 2-round solution.
  • MUX: The optimized MUX communicates 2ℓ fewer bits than the prior approach using two instances of the earlier protocol.
  • Wrap and all ones: Wrap-and-all-ones computes a wrap bit and an all-ones indicator, using millionaires’ and equality computations on all relevant nodes.This marginally increases cost compared with the corresponding Fℓ protocol.
  • Comparison and equality: Equality on ℓ-bit values is decomposed into equality checks on the two component shares, while comparison reduces to smaller-string comparisons and equalities.The comparison recurrence combines the higher-part comparison with a lower-part comparison conditioned on higher-part equality.
  • Wrap and all ones: The addition derivation rewrites the wrap output as d ⊕ (c ∧ e), where d, c, and e capture carry and boundary conditions.The derivation shows that at most one of d and the intermediate wrap bit is 1 in each case.
  • Division by power-of-2: Division by 2^s combines an arithmetic shift with a correction based on the input’s most significant bit and whether its discarded bits are nonzero.The most significant bit and nonzero-remainder condition are computed using specialized comparison, equality, and AND functionalities.

2) Division by power-of-2:

This section presents mixed-bitwidth protocols for division by powers of two and cross-term multiplication, including a COT-based protocol that supports unequal operand widths.

  • Division by power-of-2: The division protocol computes the correction term m_x ∧ c using a most-significant-bit test and an equality check on the discarded s-bit portion.An arithmetic-right-shift protocol then produces DivPow2(x, s).
  • Division by power-of-2: The MSB-to-wrap optimization is used to reduce the cost of the division functionality, whose exact communication is reported in Table V.
  • Cross-term multiplication: The cross-term multiplication protocol accepts operands with different bitlengths and performs only n COTs when m > n by reversing party roles.Correctness follows similarly to prior cross-term multiplication protocols.

2) Matrix Multiplication:

The matrix-multiplication protocols extend mixed-bitwidth cross-term multiplication with batching, bit-matrix multiplication, and extra bits that prevent overflow from additions.

  • Matrix multiplication: The matrix cross-term functionality computes products between shared low and high components, together with wrap-related correction terms.
  • Matrix multiplication: Matrix multiplication uses ℓ = m + n + ⌈log d2⌉ bits, adding e = ⌈log d2⌉ bits to prevent overflow from summing d2 products.When m ≤ n, the protocol extends Y before computing the matrix cross terms.
  • Matrix multiplication: The protocol outputs a matrix product over the target ring, with output width ℓ = m + n + e.Its inputs are matrices whose entries are shared at widths m and n.
  • Matrix multiplication: Batching performs one COT across d3 · (ℓ − i) bit strings instead of d3 independent COTs for each matrix-product contribution.The resulting communication is d1d2(mλ + (mn′ + m2/2 + m/2)d3) bits.
  • Matrix multiplication: The bit-matrix multiplication protocol uses an OT-based MUX with batching and communicates 2d1d2(λ + 2ℓd3) bits.
  • Matrix multiplication: The complete matrix-multiplication protocol extends the larger-width matrix and provides an explicit total communication formula.For m ≤ n, the protocol extends Y; for m > n, it instead extends X by e bits.

E. Digit Decomposition

Digit decomposition splits a shared ℓ-bit value into possibly unequal digits for lookup-table inputs, using carry computation to reduce communication relative to garbled circuits.

  • E. Digit Decomposition: DigDec decomposes an ℓ-bit shared number into c shared digits with lengths {d_i}, preserving the concatenation x = z_{c−1} || … || z_0.The functionality supports unequal digit sizes as well as equal-size digits.
  • E. Digit Decomposition: The resulting digits feed lookup tables for approximating exponentials, reciprocal functions in sigmoid and tanh, and reciprocal square roots.
  • E. Digit Decomposition: The protocol computes each digit from the corresponding share sum and the carry entering that digit during reconstruction.Carries are computed iteratively using wrap operations.
  • E. Digit Decomposition: For equal digit size d, the communication is (c − 1)(λ(d + 2) + 15d + 20) bits.
  • E. Digit Decomposition: For ℓ = 32 and d = 8, the digit-decomposition protocol improves communication by 5.5× over garbled circuits.The generalized unequal-digit communication is Σ_{i∈[c−1]}(λ(d_i + 2) + 15d_i + 20) bits.

F. Most Significant Non-zero Bit (MSNZB)

The MSNZB protocol identifies the most significant non-zero bit of an ℓ-bit integer by decomposing the input into smaller digits, processing candidate digits, and combining the results into a one-hot output. It uses specialized zero testing, MSNZB computation, multiplexing, AND, and lookup-table functionalities.

  • Definition: MSNZB(x) is the index k of the most significant 1-bit in x, with MSNZB(0) = 0.Equivalently, 2^k ≤ x < 2^(k+1) for a nonzero input.
  • Protocol construction: The protocol decomposes x into c = ℓ/d d-bit integers and selects the highest-position nonzero digit after accounting for its offset i·d.It also computes whether each digit is zero so that only the highest nonzero digit contributes.
  • Protocol construction: For each digit, specialized MSNZB and zero-testing functionalities produce candidate indices and zero indicators used to identify the globally most significant nonzero bit.The zero indicators are combined through multiplexing and AND operations before the selected index is assembled.
  • Output encoding: The selected index is converted into a one-hot vector whose i-th entry is 1 exactly when MSNZB(x) = i.The final one-hot functionality takes the assembled index as input and outputs ℓ bit shares.
  • Implementation: The implementation uses lookup tables for digit decomposition, combined MSNZB-and-zero computations, and one-hot encoding, with d = 8 chosen empirically.For d dividing ℓ, the protocol makes one call to the digit-decomposition functionality; the general case is handled similarly.
Loading 2105.04236v1…