NP-Hard Joint Latency and Security Optimization for Task Offloading in IoT-Enabled Vehicular Networks

Abstract

Task offloading in vehicular edge networks must satisfy strict latency limits. At the same time, it must resist security threats such as replay attacks. Existing offloading models treat cryptographic settings as fixed, separate from the scheduling decision. This is a gap, and it exists in part because jointly choosing the best node and the best cryptographic curve for each task is computationally hard. We prove that this joint problem reduces to a generalized assignment problem, a well-known NP-hard problem, once curve-selection variables are fixed. Because of this hardness, we design a polynomial-time greedy heuristic as a practical approximation. Our model treats Elliptic Curve Cryptography (ECC) curve selection as an adaptive decision, and jointly optimizes it together with latency, CPU load, and bandwidth, using one unified scoring function. Results: Task success rate (TSR) with dynamic ECC is within 0.3 percentage points of latency-only scheduling (85.26% vs. 85.58%), while replay success falls from 100% to 8.93%, more than a 10-fold reduction. A single fixed curve that never refreshes (static ECC) performs far worse on both counts (40.29% TSR, 84.54% replay success), since it cannot serve tasks needing stronger security and accumulates staleness without bound. Measured cryptographic overhead is 0.35–1.54 ms per task depending on curve, and the heuristic runs within roughly 2.34% of an exact ILP bound at full scale. These results, from an openly available Python (version 3.9 or later) simulation, confirm real-time feasibility for IoT-enabled vehicular deployments.