3
$\begingroup$

I'm using the Rivest Shamir Wagner Time Lock Puzzle setup in an application, leveraging Pietrzak's algorithm for generating the proof. My question has to do with selecting a proper starting point. In this paper the authors talk about verifying that the starting point is a modular square root. They discuss the choice of groups on page 9 and they provide a proof I don't understand in Appendix 1 on p51. I follow their suggestion, to pick starting values where $\gcd(x+1,N)=1$. From these articles, it seems to me the QR group modulo $N$ should be the size of the totient function for $N$, $(p-1)(q-1)$, but when I tried this for small values $(p=5,q=7)$, it's absolutely not true. The largest group looks like it has just 3 values, and there are several other groups this size. I'm confused.
Can someone point me to some lecture or book chapter where this is explained?
I'm trying to understand how to select a proper starting value, and how to calculate the size of the ring, knowing the factorization of $N$.

$\endgroup$
2
  • $\begingroup$ Are we talking about the squaring map $g,g^2,g^{2^2}...$ or the generator map $g,g^2,g^3,...$ here? $\endgroup$
    – ckamath
    May 2, 2023 at 13:14
  • $\begingroup$ The squaring map. Thanks. $\endgroup$
    – jdbertron
    May 3, 2023 at 20:26

1 Answer 1

1
$\begingroup$

The cycle structure of the squaring map modulo $N$ was studied in [BBS,Sections 7 and 8]. A summary follows.

Let's assume that $N=pq$ for $p=2p'+1$ and $q=2q'+1$. The cardinality of $QR_N:=\{x^2:x\in\mathbb{Z}_N^*\}$, the subgroup of quadratic residues modulo $N$, is $\phi(N)/4=p'q'$ (and not $\phi(N)$). To see this, note that:

  1. $\mathbb{Z}_N^*\cong\mathbb{Z}_p^*\times\mathbb{Z}_q^*$ (Chinese remainder theorem);
  2. An $x\in\mathbb{Z}_N^*$ is a (quadratic) residue if and only if both $x\bmod{p}$ and $x\bmod{q}$ are residues in $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$, respectively; and
  3. Exactly half the elements in $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$ are residues (since $p$ and $q$ are primes).

Now, for your example: $N=35=5\cdot7=(2\cdot2+1)\cdot(2\cdot 3+1)$ and $|QR_{35}=\{1,4,16,29,11,9\}|=6$.

For the squaring map (or, for that matter, any exponentiation map with exponent $e$), we are essentially working in the multiplicative group modulo the order of the exponent, i.e., $\mathbb{Z}_{p'q'}^*$ for the squaring map over $QR_N$. Therefore the length of a cycle induced by the squaring map in $QR_N$ depends on order of $2$ in $\mathbb{Z}_{p'q'}^*$, which divides $\lambda(p'q')$ (i.e., the length of the largest cycle in $\mathbb{Z}_{p'q'}^*$), where $\lambda$ is the Carmichael function.. This is usually fine since we pick large $p$ and $q$ and $p,q\neq 2$ (and therefore $2\in\mathbb{Z}_{p'q'}^*$). However, for the case of $N=35$, $2\not\in\mathbb{Z}_{p'q'}^*$ but note that when you carry out $2,2^2,2^3...\bmod{6}$, it results in a cycle $2,4$. You are possibly seeing sequences of length $3=2+1$ since you are starting off with a modular square root that is a non-residue (could you confirm?).

[BBS]: Blum, Blum and Shub, A Simple Unpredictable Pseudo-Random Number Generator, SICOMP'86

$\endgroup$
10
  • $\begingroup$ Wow. Thank you ! $\endgroup$
    – jdbertron
    May 4, 2023 at 17:08
  • $\begingroup$ Ok, so I'm not sure I understand that last part, well enough. Using a new example: N= p.q = 167 . 227 = 37909. Theory: phi(N)=37516, phi(N)/4=9379.0 p'q'=9379.0 then phi(n)/4/2=4644 Actual Max Size 1149 . Number of distinct maps: 21 Number of max_size maps: 6. I still don't get it. I wrote code to generate the squaring maps for every integer, and it looks like there are 21 distinct maps generated, with 6 maps that all seem to have 1149 elements, including the map with 2 as a starting point. $\endgroup$
    – jdbertron
    May 8, 2023 at 1:14
  • $\begingroup$ I guess the size is far from phi(n)/4, and I still don't have a method of selecting a starting point in one of these maps for when my primes are 2048 bits. $\endgroup$
    – jdbertron
    May 8, 2023 at 2:03
  • $\begingroup$ In the new example, $N=167\cdot227=(2\cdot83+1)\cdot(2\cdot113+1)$. Again, I believe you are starting off with a non-residue, which is why it is yielding a sequence of length $1149=1148+1$. Here $1148=2^2\cdot 7\cdot 41$ does divide $\phi(p'q')=\phi(83\cdot 113)=2^5\cdot7\cdot41=9184$. $\endgroup$
    – ckamath
    May 8, 2023 at 13:27
  • 1
    $\begingroup$ Hey thanks for all the help. I think I got it. I really appreciate it. $\endgroup$
    – jdbertron
    May 13, 2023 at 19:48

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.