11
$\begingroup$

An encryption function can be used to obfuscate pieces of information and later on retrieve them.

What is the yardstick for measuring how well the function encrypts the information ? Given any invertible function, which are the quantified parameters which measure how effective the function is to encrypt a message ?

I am assuming a finite domain for the function. Any other assumption may be stated.

Motivation: Is there any mathematical/set theoretic formulation at all... I ask this specially because I don't see this approach ever being used as has been rightly observed. My motivation is to find out weather the notion of 'encryption' can be captured fully in a mathematical formalism.-- or that we require other kind of 'concepts' to describe it fully. –

Improve this question
$\endgroup$
4
  • 8
    $\begingroup$ One thing nobody's mentioned so far is the concept of cryptographic advantage. $\endgroup$
    – Stephen Touset
    Jan 27, 2017 at 19:52
  • 2
    $\begingroup$ I down voted the question because I think it will generate a lot of discussion about things which aren't very mathematical. To start you could qualify your question a little. Give a type of message or thing which is to be encrypted. The parties involved. Then a good encryption is one where you can prove mathematically some party doesn't have the contents of the message. $\endgroup$
    – marshal craft
    Jan 28, 2017 at 3:55
  • $\begingroup$ Shockingly, nobody yet brought up our canonical question on the usual security definitions (for public-key encryption at least, but private-key encryption is similar): "Easy explanation of 'IND-' security notions?" (Disclosure: It's my question) $\endgroup$
    – SEJPM
    Jan 28, 2017 at 13:27
  • $\begingroup$ @ARi Please don’t forget to accept an answer if you think it satisfies your question. You can do so with a single click on the ✓ symbol on the left, next to the related answer you want to accept. $\endgroup$
    – e-sushi
    Jan 30, 2017 at 18:59

5 Answers 5

Reset to default
13
$\begingroup$

There isn't just one, because there are many different scenarios where you'd use such a function, where the attacker has lesser or greater powers, or variably stringent success goals—different attack models. For example:

  • Does the attacker know any plaintext/ciphertext pairs encrypted with the same key? (Known plaintext attack)
  • Is the attacker able to trick the defender into encrypting plaintexts of the attacker's choice, and observe the corresponding ciphertexts? (Chosen plaintext attack)
  • In the latter case, is the attacker able to observe the ciphertexts in real time, and use this to make smarter choices of plaintext to submit? (Adaptive chosen plaintext attack)
  • Is the attacker's goal to decrypt a message, or something weaker like telling true encrypted messages apart from random bits? (The latter is what's called a "distinguishing attack," and strengths are often expressed in terms of that.)

So it's common for algorithms to have different security levels in different scenarios. If you look for example at the "Known attacks" section in Wikipedia's entry on AES, you'll see a variety of figures, all qualified by the relevant attack model.

Another detail is that strengths are often expressed not as one number but as a function of the resources that the attacker expends in some model (e.g., in a chosen plaintext attack, the number queries, i.e. the number of plaintexts that they submit to the defender). Such functions generally give the probability that a randomized attacker will succeed if they expend that many resources.

And yet another detail is that often for some algorithms like block cipher modes of operation, which are parametrized by one or more primitives, the strength is often given as a function of the strengths of the primitives. If you're math-inclined or even just math-curious, two papers I found very useful to understand this are:

These two papers are perhaps overwhelmingly detailed, but even just skimming the major points might be instructive.

Improve this answer
$\endgroup$
8
$\begingroup$

One of the definition is stated in the other answer (indistinguishably). Another way to assert the strength of an algorithm is to compute the complexity of an attack.

Let us assume $$E : \mathcal{K} \times \mathcal{M} \to \mathcal{C}$$ be your encryption function.
It takes as an input a key and a message (or plaintext) and return a ciphertext.

Given a list of pair of (plaintext,ciphertexts) encrypted with the same $key$, the strength of $E$ is given by the number of computations required to find the right $key$.

In other words, if your binary key as a length of $n$ bits. The size of the $\mathcal{K}$ is $2^n$. If you have a strong function, finding the right $k$ will require you on average $2^{n-1}$ computations.

Your function can be weakened by different kinds of attacks. e.g. the initial strength of DES is $\mathcal{O}(2^{55})$ as the size of the key is 56 bits. Matsui showed that with linear cryptanalysis, you can find the key with $2^{43}$ pairs of (plaintext,ciphertexts)[1], thus dicreasing the complexity to $\mathcal{O}(2^{43})$.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ It's not the key that we want to protect with a cipher, but the plaintext. In general, the effort required to find the key is not very interesting, except as an upper bound for security against other attacks that knowing the key would trivially enable. Indeed, it's very easy to make a cipher that is perfectly secure against all key recovery attacks, but trivially leaks the plaintext. $\endgroup$
    – Ilmari Karonen
    Jan 27, 2017 at 21:01
  • 3
    $\begingroup$ such as E(k,m) = m ? $\endgroup$
    – Biv
    Jan 27, 2017 at 21:02
  • $\begingroup$ Yes, that's the obvious example. :) $\endgroup$
    – Ilmari Karonen
    Jan 27, 2017 at 21:04
  • $\begingroup$ But the usual assumption is that you have another cipher text that you want to decrypt and you do a lunch-break attack. Thus under that assumption, you have the requirement of key recovery or to find a distinguisher (assuming no trivial leakage). No ? $\endgroup$
    – Biv
    Jan 27, 2017 at 21:07
  • $\begingroup$ Honestly, I don't entirely follow your comment. But the classical example of a practical non-key-recovery attack is what happens if you reuse the same stream cipher key and nonce for two messages. If one of the messages is known to the attacker, they can trivially decrypt the other one, even if they have no hope of figuring out the key. $\endgroup$
    – Ilmari Karonen
    Jan 27, 2017 at 21:17
4
$\begingroup$

One common definition is IND-CCA2 which, roughly, states that even given many pairs of plaintext and ciphertext an attacker cannot distinguish another ciphertext from randomness.

Note that some sort of randomness is commonly introduced to prevent simple attacks like frequency analysis which would work on bijections.

Improve this answer
$\endgroup$
2
$\begingroup$

I think encryption strength isn't a mathematical notion but a computational science. Though completely possible probably to state and characterize it in the language of sets and logic, I dontthink this approach is used ever. Instead a notion of deterministic algorithms or problem difficulty hierarchy is used, though often isomorphic to arithmetic hierarchy.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I find your answer wonderful ... but is there any mathematical/set theoretic formulation at all... I ask this specially because I don't see this approach ever being used as you rightly observe. My motivation is to find out weather the notion of 'encryption' can be captured fully in a mathematical formalism.-- or that we require other kind of 'concepts' to describe it fully. $\endgroup$
    – ARi
    Jan 28, 2017 at 12:39
  • $\begingroup$ That's not really a question specific to encryption(Incompleteness of mathematics). $\endgroup$
    – marshal craft
    Jan 28, 2017 at 14:37
  • $\begingroup$ Yes, but a system say ZFC would be strong enough to express and prove all truths pertaining to encryption, while it may not be able to prove all true statements within it (incompleteness) .. but here I am not talking about provability at all, so the question of 'completeness' does not seem to arise. $\endgroup$
    – ARi
    Jan 28, 2017 at 15:20
  • $\begingroup$ I wasn't making an assertion about the incompleteness theorems. You can't just strip the context out of every thing sometimes. Mind you the Incompleteness theorems came about during a time when people believed mathematics could describe everything. My point is that asking to define rigorously encryption isn't very much different than asking to define a dog mathematically and then expecting ONLY greek and latin and fancy scrypts. $\endgroup$
    – marshal craft
    Jan 28, 2017 at 16:05
  • $\begingroup$ Another area, the Reimann Zeta function which is impotantly related to the distribution of prime numbers, is not known to be true or not, it could be independent of ZFC. How can one mathematically define encryptions related or that use prime number factoring when important statements, relating to the secureness of the encryption are still out for proving. Clearly that hypothesis could relate to encryption strength. Something which once was encrypted could now not be. $\endgroup$
    – marshal craft
    Jan 28, 2017 at 16:16
2
$\begingroup$

Given any invertible function which are the quantified parameters which measure how effective the function is to encrypt a message?

This answer addresses the units that are used to measure things related encryption. There are two quantifiable aspects of an algorithm: Security and Efficiency.

Many things influence security, as was thoroughly covered in the other answers. Context is important:

  • things like key size and block size are measured in bits
  • time-to-break can be measured in a model which replaces the unit of time to an invocation of the algorithm in question.

Efficiency is generally measured in Cycles per byte for symmetric algorithms. Asymmetric algorithms are often measured by the quantity of messages that can be enciphered/deciphered or signed/verified per second.

eBATS has even finer grained measurements of efficiency:

The eBATS (ECRYPT Benchmarking of Asymmetric Systems) project, part of eBACS, measures public-key systems according to the following criteria:

  • Time to generate a key pair (a private key and a corresponding public key).
  • Length of the private key.
  • Length of the public key.
  • Time to generate a secret shared with another user, given a private key and the other user's public key.
  • Length of the shared secret.
  • Time to encrypt a message using a public key.
  • Length of the encrypted message.
  • Time to decrypt an encrypted message using a private key.
  • Time to sign a message using a private key.
  • Length of the signed message.
  • Time to verify a signed message using a public key.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Efficiency is not necessarily correlated with encryption strength, as the question title asks. But the body asks for what quantified parameters exist regarding the efficiency of the algorithm, so I decided to address it. $\endgroup$
    – Ella Rose
    Jan 27, 2017 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.