2
$\begingroup$

I've seen the word 'cost' being used several times in describing algorithms e.g. algorithm A costs more to compute than algorithm B. What does 'cost' mean in this sense?

$\endgroup$
  • 1
    $\begingroup$ In that sense, it means that one algorithm requires more CPU cycles to compute (so it's slower), but more often "cost" refers to difficulty of a cryptographic attack. $\endgroup$ – forest May 19 at 10:11
  • $\begingroup$ Then, in the latter, does a high cost refer to a more difficult encryption to decrypt? $\endgroup$ – dkssud10 May 19 at 10:24
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it's a question about general terminology unrelated to cryptography. $\endgroup$ – Maeher May 19 at 12:40
  • $\begingroup$ @Maeher To be fair, we have a lot of questions like that which are open, even questions asking about the history behind naming conventions or why constructions were named such. $\endgroup$ – forest May 19 at 23:03
  • 1
    $\begingroup$ I'm not voting to close this question as off-topic because it is a common source of confusion even among cryptographers how to model costs of cryptanalytic attacks, as discussed in, e.g., the Nonuniform cracks in the concrete paper, but I lack the time at the moment to write a detailed answer about standard metrics like RAM, NAND, and the most physically realistic (but still not perfect) area*time or AT metric. $\endgroup$ – Squeamish Ossifrage May 20 at 0:19
2
$\begingroup$

There is not one commonly accepted definition of "cost" in cryptography, other than the definition of "cost" in a common dictionary; this is not jargon or slang to my knowledge.

Here is the most logical definition from Merriam Webster:

b: the outlay or expenditure (as of effort or sacrifice) made to achieve an object

I'd say that "object" is not a particular object here, it should be read as "objective".


Usually "cost" refers to CPU time, commonly counted using the number of CPU cycles as unit for a particular CPU.

Depending on the context it may also refer to memory usage requirements or even energy expenditure. For hardware it may also relay to transistor count, die size or other costly elements within chip design.

$\endgroup$
0
$\begingroup$

In general it means that it's too inefficient to compute (it would take far too long).

In the context of your question it means that algorithm B is faster than algorithm A.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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