Score:1

What are security reductions of symmetric-key algorithms?

cz flag

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of the system should be essentially stemming from hardness of some mathematical problem.

For example, lattice-based cryptography, Diffie-Hellman, RSA, McEliece system, multivariate cryptography reduce to shortest vector problem, discrete logarithm problem, integer factorization, syndrome decoding problem, multivariate quadratic equation solving problem respectively.

I was unable to see any examples for symmetric key algorithms. Why is that? I assume that they don't need this property due to very nature of symmetric key cryptography?

Is it because since it's not public key cryptography asymmetry isn't required and hence there's no need for some easy to encrypt, hard to decrypt system that translates into some one-way function, which's hard to inverse due to mathematics behind it?

thanks for the answers, it was helpful.

kelalaka avatar
in flag
[What are recommended, general strategies to start block-cipher design and/or analysis?](https://crypto.stackexchange.com/q/39791/18298)
kelalaka avatar
in flag
Related [Are there any symmetric cryptosystems based on computational complexity assumptions?](https://crypto.stackexchange.com/q/70597/18298)
Score:2
my flag

i was unable to see any examples for symmetric key algorithms. but why?

There are several possible ways to answer this; the most straight-forward is that symmetric key algorithms are based on specific mathematical problems (we just don't usually express it that way).

To take some examples of assymetric algorithms:

for example ... diffie-hellman, rsa ... reduce to ... discrete logarithm problem, integer factorization ... respectively.

That is incorrect; if you are given an Oracle that can break Diffie-Hellman, there is no known way to use that to solve discrete log problems; if you are given an Oracle that can break RSA, there is no known way to use that to factor.

Instead, what Diffie-Hellman reduces to is known as the "Diffie-Hellman problem" (technically, either cDH or dDH, depending on what your Oracle does); what RSA reduces to is known as the "RSA problem".

Now, what is the distinction between the "Diffie-Hellman problem" or the "RSA problem" and the "AES problem"? Other than the fact that the "AES problem" takes longer to describe and feels more arbitrary, I can't see one (and certainly the "AES problem" has been quite well studied). And, if we are using AES in some mode, there is generally a proof that the security of the mode reduces to the "AES problem", hence this is not just a silly word game.


Another way of approaching the question (if we insist on 'simple mathematical problems' as a way of disqualifying the 'AES problem') is to note that we do know of symmetric primitives that reduce to simply mathematical problems; however those primitives generally run much slower (and usually have much larger ciphertexts) than what we use in practice, and so we never use them, especially since we don't know of any proof that the 'simple mathematical problem' is actually any harder than the 'complex mathematical problem' we use in practice.

One can turn this around and ask 'why do we insist on basing asymmetric algorithms on specific hard problems?'. One answer is that asymmetric algorithms try to do more than a symmetric algorithm; not only does an asymmetric algorithm need to look 'random', it still needs to be secure even if the attacker is given a hint in the form of a public key. This public key must be related somehow to the private key, but not in an obvious way (and, of course, operations that are easy given the private key must be infeasible given only the public key). The only way we know to have such an obscure relationship involves reducing that to a simpler hard problem.

Score:1
ru flag

Insofar as there are security reductions in symmetric cryptography, they tend to apply to constructions using idealised primitives such as a pseudo-random function or a pseudo-random permutation. Thus for example, Luby and Rackoff have proven that it is possible to construct a pseudo-random permutation from a pseudo-random function using a three-round Feistel construction. Likewise symmetric cryptographers might try to prove that a block cipher mode of operation extends a pseudo-random permutation on the block size to a pseudo-random permutation on a larger piece of data.

Assurance then comes from faith that the symmetric primitives that we use are distinguishable from their idealised pseudo-random counterparts. Whether there is more assurance in the statement "breaking this construction is as hard as distinguishing SHA256 from a pseduo-random function" or "breaking this construct is as hard as the decisional Diffie-Hellman problem in this group" is up to the consumer.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.