using Zp or Zp^*

Choosing Between ${\mathbb{Z}}_p$ and ${\mathbb{Z}}_p^{\ast }$ in Cryptographic Schemes

In pairing-based cryptographic protocols, the choice of algebraic structures for randomness and messages—specifically whether to use the full field ${\mathbb{Z}}_p$ (integers modulo a prime $p$, i.e., $0,1,\dots ,p-1$) or its multiplicative subgroup ${\mathbb{Z}}_p^{\ast }$ (non-zero elements, i.e., $1,\dots ,p-1$)—has subtle but critical implications for security and correctness. Below, we analyze their tradeoffs.

Why ${\mathbb{Z}}_p^{\ast }$ is Safer

Using ${\mathbb{Z}}_p^{\ast }$ (non-zero exponents) is often preferred for $\text{blinding factors}$ and $\text{randomness}$ due to:

• Avoiding Degenerate Cases: A zero exponent (e.g., $r=0$) can produce trivial group elements:

  $g^0=1\in {\mathbb{G}}_1,0\cdot P=\mathcal{O}\in \text{EC groups}$

  which may leak secrets or break protocol unlinkability. For instance, in PS-style commitments $\text{cm}=g^t\prod Y_i^{m_i}$, a $t=0$ would expose $\prod Y_i^{m_i}$.

• Security Proof Compatibility: Many zero-knowledge proofs (e.g., Schnorr-type responses $z=\tilde{x}+c\cdot x$) implicitly assume $x\ne 0$ to avoid division-by-zero errors in reductions. This is particularly critical because such errors prevent the simulator from properly generating valid transcripts in security proofs, potentially invalidating the entire security argument.

• Invertibility Guarantees: Non-zero elements in ${\mathbb{Z}}_p^{\ast }$ are invertible, simplifying operations like computing $r^{-1}\mathrm{mod}p$ in signature schemes.

Practical Implementation of ${\mathbb{Z}}_p^{\ast }$ Sampling

When implementing schemes requiring sampling from ${\mathbb{Z}}_p^{\ast }$, developers typically use one of two approaches:

• Rejection Sampling: Generate random elements from ${\mathbb{Z}}_p$ and retry if zero is obtained. This is probabilistically efficient given the negligible probability $(1/p)$ of sampling zero.

• Offset Method: Generate a random element $r$ from ${\mathbb{Z}}_p$ and use $r+1\mathrm{mod}p$. This guarantees a non-zero result but may introduce slight biases that should be analyzed in security-critical applications.

Why Some Schemes Use ${\mathbb{Z}}_p$

Despite the risks, protocols like the Pointcheval-Sanders (PS) scheme often sample from ${\mathbb{Z}}_p$ because:

• Pairing Algebraic Requirements: Pairing equations (e.g., $e(g^a,h^b)=e(g,h{)}^{ab}$) require exponents to span the full field ${\mathbb{Z}}_p$ to preserve algebraic relationships. Polynomial evaluations, which are fundamental to PS credentials and many other pairing-based schemes, are defined over the entire field ${\mathbb{Z}}_p$. Restricting to ${\mathbb{Z}}_p^{\ast }$ would break these polynomial properties and their crucial role in constructing witnesses and proofs.

• Negligible Failure Probability: For large $p$, the probability of sampling $r=0$ is $1/p$, which is considered cryptographically negligible. Schemes often accept this risk to simplify implementations.

• Message Flexibility: Messages (e.g., attributes $m_j$) may need to include 0 as a valid value. For example, a credential might encode $m_j=0$ to represent “no value” for an optional field.

Practical Recommendations

• For Blinding Factors: Always use ${\mathbb{Z}}_p^{\ast }$ to eliminate edge cases and align with security assumptions in proofs. Implement proper sampling methods as discussed above.

• For Messages/Attributes: Use ${\mathbb{Z}}_p$ if 0 is a valid semantic value (e.g., default states). Consider adding range proofs or other validation when zero values might impact security.

• In Pairing-Based Schemes: Follow the scheme’s specification—PS uses ${\mathbb{Z}}_p$ for exponents to maintain pairing correctness, but ensure other safeguards (e.g., range proofs) mitigate risks.

Summary

While ${\mathbb{Z}}_p^{\ast }$ is theoretically safer for randomness, practical schemes like PS often use ${\mathbb{Z}}_p$ for compatibility with pairing algebra. Developers must weigh algebraic requirements against edge-case risks when choosing structures, and implement appropriate sampling and validation mechanisms based on their specific security requirements.