Introduction
Bilinear pairings serve as the mathematical foundation for advanced cryptographic primitives, including Identity-Based Encryption (IBE) and Attribute-Based Encryption (ABE). Despite their utility, these operations are computationally intensive, presenting a significant bottleneck for resource-constrained devices such as IoT sensors and RFID tags. To address this, researchers have explored secure outsourcing, where heavy computations are offloaded to cloud servers. However, this transition introduces critical challenges regarding data privacy and the verification of result correctness. This paper proposes two novel algorithms, Pair and FPair, designed to optimize the secure outsourcing of bilinear pairings while maintaining robust security guarantees.
Problem Statement
The primary objective of secure outsourcing is to allow a computationally weak client to delegate tasks to a powerful server without compromising the underlying data or accepting incorrect results. In the context of bilinear pairings, two major risks emerge:
- Security/Privacy: The cloud server must not be able to recover the sensitive inputs being processed.
- Checkability: The client must be able to detect if a malicious or "lazy" server has returned an incorrect result to save its own computational resources.
Previous solutions often suffered from high local computational overhead—sometimes nearly equaling the cost of the original pairing—or inefficient pre-computation phases that made them impractical for real-world deployment. This research seeks to minimize the user's local workload and storage requirements while maximizing the probability of error detection.
Proposed Algorithms
The authors introduce two algorithms tailored to different trust environments, both utilizing a Rand subroutine to handle pre-computation via lookup tables.
The Pair Algorithm
Designed for the One-Malicious version of Two Untrusted Program (OMTUP) model, this algorithm assumes the user outsources to two distinct cloud servers, with the guarantee that at least one remains honest. The core innovation is a "logical splitting" technique. The input points are decomposed into random-looking components and distributed across the servers. The user then reassembles the final result $e(A, B)$ using a minimal number of local multiplications, ensuring the servers never see the actual inputs.
The FPair Algorithm
For more adversarial environments, the Two Untrusted Program (TUP) model is used, where both servers may be malicious or colluding. The FPair algorithm introduces "flexible checkability." By utilizing a random small integer $t$ during the verification phase, the user can tune the probability of detecting a failure, providing a scalable balance between security and performance.
Performance and Efficiency Analysis
The proposed algorithms were evaluated against existing benchmarks, specifically the models proposed by Chen et al. and Tian et al. The results demonstrate significant improvements across three key metrics:
- Online Efficiency: In the
Pairalgorithm, the user's local workload is reduced to just 4 Point Additions (PA) and 3 Modular Multiplications (M). This outperforms previous state-of-the-art methods which required 5 PA and 4 M. - Pre-computation Gains: The efficiency of the
Randsubroutine is a major highlight. ThePairalgorithm requires only 2 Scalar Multiplications (SM) during pre-computation, a stark contrast to the 9 SM required by Chen’s model and 3 SM by Tian’s. - Storage Optimization: For memory-constrained devices like RFID tags, storage is at a premium. The authors reduced the "tuple-size" (the data stored in the lookup table) to 8 units, down from the 18 units required in earlier literature.
Conclusion and Future Work
This research provides a more efficient path for integrating advanced cryptography into the IoT ecosystem. By optimizing both the online calculation phase and the pre-computation setup, the Pair and FPair algorithms offer a practical solution for secure outsourcing.
However, limitations remain. The reliance on a pre-computed table still poses a challenge for devices with extremely limited or volatile memory. Furthermore, the Rand subroutine requires a trusted setup phase; if this initial environment is compromised, the security of the entire process is at risk. Future research may focus on reducing local computational costs even further—approaching near-zero overhead—and extending these optimizations to non-supersingular curves and other pairing types.
Summary updated