DGK Cryptosystem Key Generation and Decryption Issues
Just in case someone else is trying to implement this cryptosystem, I wish to share the implementation that I am currently using. Someone helped me pick another approach for generating $ h $ and $ g $, and, intuitively, it seems secure.

In order to generate $ h $ and $ g $, I now apply certain algorithms described in the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone

Specifically, I use Algorithm 4.83, Chapter 4: Selecting an element of maximum order in $ \mathbb{Z}_n^* $, where $ n = p q $:

INPUT: two distinct odd primes, $ p $, $ q $, and the factorizations of $ p - 1 $ and $ q - 1 $.

OUTPUT: an element $ \alpha $ of maximum order $ lcm(p - 1; q - 1) $ in $ \mathbb{Z}_n^* $, where $ n = p q $.


Use Algorithm 4.80 with $ G = \mathbb{Z}_p^* $ and $ n = p - 1 $ to find a generator $ a $ of $ \mathbb{Z}_p^* $.
Use Algorithm 4.80 with $ G = \mathbb{Z}_q^* $ and $ n = q - 1 $ to find a generator $ b $ of $ \mathbb{Z}_q^* $.
Use Gauss's algorithm (Algorithm 2.121) to find an integer $ \alpha $, $ 1 \leq \alpha \leq n - 1 $, satisfying $ \alpha \equiv a \pmod p $ and $ \alpha \equiv b \pmod q $.
Return $ \alpha $.


For completeness, here are the two algorithms referenced above in Algorithm 4.83:

Algorithm 4.80, Chapter 4 : Finding a generator of a cyclic group:

INPUT: a cyclic group $ G $ of order $ n $, and the prime factorization $ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} $

OUTPUT: a generator $ \alpha $ of $ G $


Choose a random element $ \alpha $ in $ G $
For $ i $ from $ 1 $ to $ k $ do the following:


Compute $ b \gets a^{n/p_i} $ (N.B. $ \pmod n $)
If $ b = 1 $ then go to step 1.

Return $ \alpha $.


Algorithm 2.121, Chapter 2 (Gauss's algorithm):
The solution $ x $ to the simultaneous congruences in the Chinese Remainder Theorem (Fact 2.120) may be computed as $ \sum_{i = 1}^{k}{a_i N_i M_i \pmod n} $, where $ N_i = n / n_i $ and $ M_i = N_i^{-1} \pmod {n_i} $. These computations can be performed in $ O((\lg n)^2) $ bit operations.

Fact 2.120, Chapter 2: (Chinese remainder theorem, CRT) If the integers $ n_1 $, $ n_2 $, ..., $ n_k $ are pairwise relatively prime, then the system of simultaneous congruences

$ x \equiv a_1 \pmod {n_1} $

$ x \equiv a_2 \pmod {n_2} $

$ \vdots $

$ x \equiv a_k \pmod {n_k} $

has a unique solution modulo $ n = n_1 n_2 \cdots n_k $.

In order to apply Algorithm 4.83, we require the factorizations of $ p - 1 $ and $ q - 1 $. The standard approach would be to just factor the random ~200 bit factors $ p_r $ and $ q_r $. On the other hand, assuming that we don't break the security assumptions, we can use $ p_r = 2 p_r' $ and $ q_r = 2 q_r' $, where $ p_r' $ and $ q_r' $ are random primes of the required size. After ensuring that $ p = 2 p_r' v_p u + 1 $ and $ q = 2 q_r' v_q u + 1 $ are also primes, we may compute $ h $ and $ g $ with the above algorithms:


First, we compute $ h_r $ and $ g_r $ of order $ LCM(p - 1, q - 1) = (p - 1)(q - 1) / GCD(p - 1, q - 1) = 2 u p_r' v_p q_r' v_q $ in $ \mathbb{Z}_n^* $ with Algorithm 4.83
$ h $ must have order $ v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ h = h_r^{2 u p_r' q_r'} \pmod n $
$ g $ must have order $ u v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ g = g_r^{2 p_r' q_r'} \pmod n $


And that about wraps it up. Please feel free to add comments if more explanations are needed.

PS: The factor $ 2 $ is required for $ p - 1 = 2 p_r' v_p u $ and for $ q - 1 = 2 q_r' v_q u $ because the product of three odd primes is odd, and, thus, by adding one, we get an even number larger than 2, which can't be prime, but both $ p $ and $ q $ need to be prime numbers.