Up to now, the design of block ciphers has been mainly driven by heuristic arguments, and little theory is known to constitute a good guideline for the development of their architecture. Trying to remedy this situation, we introduce a new type of design for symmetric cryptographic primitives with high self-similarity. Our design strategy enables to give a reductionist security proof for the primitive based on plausible assumptions regarding the complexity of the best distinguishing attacks on random Feistel schemes or other ideal constructions. Under these assumptions, the cryptographic primitives we obtain are perfectly secure against any adversary with computational resources less than a given bound. By opposition, other provably secure symmetric primitives, as for example C [3] and KFC [4], designed using information-theoretic results, are only proved to resist a limited (though significant) range of attacks. Our construction strategy leads to a large expanded key size, though still usable in practice (around 1 MB).