The main contribution is to design a cryptographically keyed strong S-Box construction method, based on a non-degenerate 3D improved quadratic map (3D-IQM). First, a 3D-IQM is constructed, dynamics analysis demonstrated its ergodicity and better randomness in phase space. Based on 3D-IQM, a keyed dynamic strong S-Box construction method is designed, which can satisfy six criteria and without fixed-point, reverse fixed-point, or short cycles. To verify its effectiveness in cryptography, the red, green and blue components of color image are encrypted using three S-Boxes, to further enhance the encryption intensity, three random substitution-depth sequences are generated to substitute each pixel with S-Box for random times. Security analysis and experimental statistics verified the algorithm’s security and effectiveness. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.