Do we want to allow/Have we allowed parallelization (e.g GPU programming) to enter the cryptographic field? What are the consequences?

Question

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?

Answer 1

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.

Answer 2

• 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;

  • FHE sorting is already based on the parallel sort due to the nature of the Semantic security of the FHE.
  • FHE Private Information Retrival
  • FHE AES evaluations
  • And, the others ( there are already FPGA/GPU implementations)

• 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.

Answer 3

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

• 2017: SHAttered collision attack on SHA1.
• 2009: Pollard‑𝜌 attack on 112‑bit ECDLP using a cluster of PlayStation 3 consoles.