Efficient group authentication with multiple authentications on resource-limited devices

Jiangtao Yuan, Jing Yang, Chenyu Wang, Shijie Zhou

TL;DR

This paper proposes a new asynchronous group authentication protocol designed specifically for resource-constrained IoT devices. By combining bivariate symmetric polynomials with the discrete logarithm problem, the authors create a system where multiple devices can be authenticated simultaneously without the need for heavy 1-to-1 handshakes or revealing long-term secrets.

What Problem Does This Paper Address?

As the Internet of Things (IoT) scales to millions of devices, traditional one-to-one identity authentication becomes a massive bottleneck. These devices often have very limited memory, battery life, and processing power, making standard heavy encryption impractical.

While "Group Authentication" (GA) schemes exist to verify multiple users at once, they face three major hurdles:

  1. Scalability: Managing massive numbers of individual connections is inefficient.
  2. Reusability: Many existing schemes are "one-time use"; once a device reveals its authentication token, it can't be used again securely.
  3. Security Vulnerabilities: Previous models (like Harn’s original GAS) have been found vulnerable to "collusion attacks," where a few malicious internal members combine their information to spoof the entire group.

Methods

The authors introduce a framework that moves away from simple secret sharing toward a more robust algebraic approach:

  • Bivariate Symmetric Polynomials: The Group Manager (GM) generates a polynomial $f(x, y)$ where $f(x, y) = f(y, x)$. Each user $i$ receives a unique "token" derived from this polynomial. Because it is symmetric, any two users can also generate a shared private key without communicating.
  • Non-Interactive Token Updates: To prevent token theft, users generate a local random value ($\tau_i$) using their original token. Crucially, these random values are designed to sum to zero across the entire group ($\sum \tau_i = 0$). This "hides" the user's real contribution in the session while allowing the group to still reach a valid sum.
  • Discrete Logarithm Problem (DLP): Instead of recovering the master secret $s$ directly (which would compromise the system), the protocol recovers $sg_r$ (the secret multiplied by a session-specific generator on an elliptic curve). This leverages the hardness of the DLP to ensure that even if an attacker intercepts the session data, they cannot work backward to find the master secret.

Datasets

Not discussed in the paper. As this is a theoretical cryptography paper focusing on protocol design and mathematical proofs of security, it does not utilize empirical datasets or machine learning benchmarks.

Key Insights and Ideas

  • The "Zero-Sum" Trick: The most elegant part of the paper is how users protect their tokens. By adding a random value $\tau_i$ that cancels out when all users' contributions are added together, the protocol achieves "privacy-preserving" authentication. No single user reveals their true share, yet the group can still prove its collective legitimacy.
  • Asynchronous Efficiency: The framework is non-interactive. Users don't need to perform a "handshake" with every other member. They simply compute their value and release it, significantly lowering the communication overhead for low-power sensors.
  • Dual-Purpose Tokens: The tokens issued by the Group Manager serve two roles: they are used for group authentication and can simultaneously act as seeds for pairwise encryption between any two devices in the network.

Key Results

  • Collusion Resistance: The authors mathematically prove (Theorem 2) that the scheme can withstand collusion attacks by up to $t-1$ internal members, where $t$ is the degree of the polynomial.
  • Computational Speedup: By utilizing the FastEval algorithm for polynomial evaluation, the computational complexity for each device is reduced to $O((t-1)\log^2(t-1) + (m-1)\log(m-1))$. This makes it viable for hardware with very low clock speeds.
  • Communication Efficiency: Compared to asymmetric bivariate schemes, this method requires the Group Manager to send fewer tokens during the registration phase, reducing the initial setup burden on the network.

Limitations and Future Work

  • Threshold Constraints: The security of the system relies on a specific ratio between the number of users ($n$) and the threshold ($t$). Specifically, it requires $1 + \frac{t(t+1)}{2} \leq n$. If a group is too small relative to the desired security level, the secret cannot be reconstructed.
  • Centralized Trust: The system relies on a "Group Manager" (GM) to be a trusted authority. If the GM is compromised, the entire group's security fails.
  • Future Directions: While not explicitly detailed, a logical next step for this research would be "decentralized" group authentication, where the role of the GM is distributed across multiple nodes to eliminate the single point of failure.

Summary updated

Abstract

<title>Abstract</title> In the era of the Internet of Everything, the Internet of Things (IoT) has become an integral part of people’s lives. Identity authentication faces significant challenges when dealing with various devices. Traditional one-to-one authentication methods struggle to meet the requirements of massive connected devices and do not account for the resource limitations of these devices. Group authentication (GA) in many-to-many authentication methods can effectively address the issues of large-scale authentication. Since Harn [1] proposed the group authentication scheme (GAS), extensive research has been conducted on GA. In GAS, the authentication of different users is conducted simultaneously rather than individually. Harn’s GAS [1] is based on Shamir’s threshold scheme, which has low computational resource requirements. Therefore, GA can be applied to resource-constrained IoT devices. While ensuring computational efficiency, security remains a significant challenge for current GA methods. However, many existing schemes cannot provide security guarantees for widespread use. In this paper, an asynchronous group authentication protocol based on bivari-ate symmetric polynomials and discrete logarithm problem are proposed. The method uses bivariate symmetric polynomials to generate tokens for group members. These tokens enable users to generate random values, which are then used to update the original tokens. This ensures that each user can protect the product of the Lagrange component and a generator of a cyclic group. The proposed scheme in this paper offer enhanced security.
BibTeX
@article{yuan2025efficient,
  author = {Jiangtao Yuan and Jing Yang and Chenyu Wang and Shijie Zhou},
  title = {{Efficient group authentication with multiple authentications on resource-limited devices}},
  journal = {The Journal of Supercomputing},
  year = {2025},
  doi = {10.1007/s11227-025-07404-6},
}

Loading related content...

Figure