Block ciphers are essential for the secure exchange of data and communication, as they are one of the primary components of network security systems. Modern-day block ciphers are most significantly reliant on substitution-boxes (S-boxes). In essence, the security of these cryptosystems is contingent upon the quality of the S-box that is implemented. Robustness and assurance of the security competency necessary to block ciphers are provided by the cryptographically strong S-boxes. A novel coset graph-based algebraic method was proposed to evolve a robust and efficient S-box in order to address the challenges of strong S-box generation. To begin, the vertices of coset graphs for two Galois fields and a bijective function were employed to generate an initial S-box of sufficient cryptographic strength. Afterwards, a permutation group of large order enhances the robustness of the initial S-box, ensuring its resistance against various cryptanalytic attacks. The proposed method's efficacy was verified by comparing the attributes of our S-box with those of S-boxes that have been recently investigated. Furthermore, the proposed S-box was used for image encryption. The outcome of the majority logic criterion (MLC) criteria, differential analysis, and histogram test demonstrates the suitability of the proposed S-box for secure multimedia applications in the results.