Differential and Linear Cryptanalysis on Random Sbox Assume that we use the key to perform a uniform permutation to generate a sbox. The literature is rich supporting the statement that a random Sbox can make any cryptographic scheme weaker. I have tested and found the randomly permuted sboxes possess weak nonlinearity and high differential probability. We know that to perform differential and linear attack the DDT and LAT should be handy. If we make the sbox key-dependent and every distinct key results a distinct sbox(best case).
Now if someone tries to perform a differential/ linear cryptanalysis then will it be logical to consider the Bruteforce complexity of guessing the proper sbox?
If it is logical then what should be the approach to such an attack?
Typical attacks on Secret SPNs (i.e. with secret uniform S-Boxes) are integrals, see e.g. [1].
Even for AES: the S-Box is too good against differential/linear attacks (strong mixing in MixColumns is also necessary), so best attacks are of another kinds. (Not counting related-key attacks, which allow to deactivate many S-Boxes).
More to the question: in some special cases it may be indeed useful to consider differential cryptanalysis with ``random'' difference. See for example [2], where the output of the Feistel function is very small so that it does not matter which difference to choose - the differential will be sufficiently strong anyway.
[1] Biryukov, A., Khovratovich, D., &amp; Perrin, L. (2017). Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs. IACR Transactions on Symmetric Cryptology, 2016(2), 226-247. https://doi.org/10.13154/tosc.v2016.i2.226-247
[2] Orr Dunkelman, Abhishek Kumar, Eran Lambooij, Somitra Kumar Sanadhya:
Cryptanalysis of Feistel-Based Format-Preserving Encryption. IACR Cryptol. ePrint Arch. 2020: 1311 https://eprint.iacr.org/2020/1311