0
$\begingroup$

With the term GPU programming, I'm referring to highly parallelizable computing in general.

Lastly, I have built a bit of a background in cryptography. So I have started to wonder if/where GPU programming is applicable for cryptographic use. I am thinking that in most use cases it will offer little to no advantage because cryptographic algorithms from their are build around the concept of offering little to no advantage on parallelization cause this will probably need to consider alternative security models and also since on some occasions we want data dependencies to exist. For example in block ciphers or in stream ciphers (e.g. AES or Salsa), however parallelization it may offer a small advantage in cipher block chaining. But on the other hand, most modern processor architectures (e.g. x64 or ARMv8) has already built-in instructions for a round of AES or for some hash functions and they also have SIMD instructions which can help on some occasions. But let's not limit our scope, cryptography is not only about these schemes and these primitives. What about asymmetric cryptography primitives? And also what about the "newborn" fields like FHE, MPC, ZKP, or Lattice Based Cryptography?

To summarize :

  • Do we want to allow/Have we allowed parallelization to enter the cryptographic field? If yes, will this need us to reconsider the security models?
  • Which are the most common cryptographic primitives that are parallelizable by design?
  • What about the "newborn" fields like FHE, MPC, ZKP, or Lattice Based Cryptography?
$\endgroup$
3
  • $\begingroup$ Does this alter the common security models we can consider? $\endgroup$
    – tur11ng
    Jun 12, 2022 at 20:12
  • 2
    $\begingroup$ Something like PBKDF2 implemented in OpenCL might be neat, but most cryptography doesn't benefit from running in parallel. $\endgroup$
    – forest
    Jun 12, 2022 at 21:46
  • $\begingroup$ Cryptanalysis of the enigma might have been one of the first applications of parallelization on a major scale. $\endgroup$
    – tylo
    Jun 14, 2022 at 2:49

3 Answers 3

4
$\begingroup$

cryptographic algorithms from their are build around the concept of offering little to no advantage on parallelization cause this will probably need to consider alternative security models

This isn't true. There are algorithms of the kind you describe (often going by names such as inherently sequential algorithms, or time lock puzzles, or verifiable delay functions) but it is by no means the majority of the field.

In most settings, the algorithms honest parties compute are very efficient, and making them more efficient (such as via parallelization) does not really impact security at all.

What matters is how cryptanalysis behaves with respect to parallelization. Even this tends to parallelize very well though. Many cryptanalysis algorithms (say varients of the number field sieve, or lattice algorithms) are often called "embarrassingly parallel", as often the majority of the algorithm can be easily parallelized. Sometimes estimates here are wrong, leading to attacks (LogJam is a famous example), but for the most part parameters are set assuming some degree of parallelization is being done already.

So, the answers are

  1. Yes. Ignoring special cases (that I described above), this doesn't impact security definitions much.

  2. I can't claim to give a comprehensive answer here, but lattice-based primitives are often highly parallelizable at least, and are quite common now.

  3. As mentioned, lattice-based primitives (and therefore FHE) are highly parallelizable. I can't comment on other areas though.

$\endgroup$
2
$\begingroup$
  • We have parallel Hashes

    • NIST SP 800-185 – ParallelHash:

    The purpose of ParallelHash is to support the efficient hashing of very long strings, by taking advantage of the parallelism available in modern processors.

    • Blake3 is another parallel hash.
  • Encryption modes; CTR by nature highly parallel, to disk encryption modes due to the requirement.

  • Building a Rainbow table.

  • FHE implementations; FHE is already resource and time-consuming. Implementing them in parallel is a must;

  • Factoring algorithms include many parallel subroutines like Gaussian Elimination. For example CADA-NFS performance depends on the number of cores;

  • The GCD attack on RSA modules can be paralyzed.

  • Pollard's kangaroo algorithm for the discrete log is paralyzed with GPU support.

  • Lattice algorithms and attacks are parallelizable by their nature.

  • Quantum computation simulations. This is a must and by nature.

  • Brute forcing: While modern algorithms like AES cannot be brute-forced, there are already parallel key searches executed on DES. All listed crackers on this answer were parallelized.

  • Some parts of ZKPs can be parallized.

  • Password hashing; parallelization is required on 2015 the competition. This provides some mitigation against parallel searches, see hashcat.

Do we want to allow/Have we allowed parallelization enter the cryptographic field? If yes, will this need us to reconsider the security models?

AS we can see it is already in. The security model is really depends on the case.

Which are the most common cryptographic primitives that are parallelizable by design?

  • Brute force by nature
  • FHE by nature

Note that it is abundant in cryptography to implement algorithms in ASIC/FGGA. CHES and Fast Software Encryption conferences were pioneer on this subject.

$\endgroup$
2
  • $\begingroup$ do u know fhe or zkp fpga repos? i'd be grateful $\endgroup$
    – benia
    Jun 20, 2022 at 18:06
  • $\begingroup$ @benia They are easy to search. What are you looking for? $\endgroup$
    – kelalaka
    Jun 20, 2022 at 18:59
0
$\begingroup$

The use of GPUs (and parallelism in general) is standard in cryptanalysis. Two well-known examples:

$\endgroup$

Your Answer

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

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