Technical Summary: PIVOT – Proactive and Verifiable Threshold Oblivious Pseudorandom Functions from Isogeny Group Actions

1. Problem Statement

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a keyed function on a private input without revealing the input to the server. In a threshold OPRF, the secret key is distributed among $n$ servers, requiring at least $t$ servers to cooperate for evaluation. While standard threshold schemes protect against static corruption (where a fixed set of servers is compromised), they fail against a mobile adversary. In a mobile threat model, an attacker can compromise different servers over time, accumulating shares from different epochs. If shares remain static, the adversary can eventually collect $t$ shares from the same sharing state and reconstruct the master key, even if they never control $t$ servers simultaneously.

Existing isogeny-based threshold OPRFs are primarily designed for static corruption models. Furthermore, existing proactive secret sharing mechanisms in classical groups do not easily translate to the isogeny setting due to the need to link polynomial commitments (in the scalar field) with isogeny group actions (on elliptic curves). There is a lack of a construction that simultaneously offers:

1. Post-quantum security (based on isogenies).
2. Verifiability (ensuring servers evaluate under the correct key).
3. Proactive security (periodically refreshing shares to thwart mobile adversaries).
4. Dealerless key generation (no trusted setup).
5. Committee migration (changing the server set or threshold without re-encrypting application data).

2. Methodology and Construction

The paper introduces PIVOT (Proactive Isogeny-based Verifiable Oblivious Threshold PRF), a framework built on effective isogeny group actions (e.g., CSIDH). The core algebraic structure relies on the commutative property of isogeny actions: $[a]([b]E) = [a+b]E$.

Core Architecture

PIVOT maintains a single long-lived master key $k$ and a public key $pk = [k]E_0$. However, the representation of $k$ changes over time. The system operates in epochs. In epoch $e$, the servers hold shares $s^{(e)}_i = F_e(i)$ of a Shamir polynomial $F_e(X)$ where $F_e(0) = k$. The public coefficient commitment vector $A^{(e)}$ certifies the polynomial $F_e$.

The protocol consists of five main procedures:

1. Dealerless Distributed Key Generation (DKG):

   • Every server acts as a Verifiable Secret Sharing (VSS) dealer, sampling a random polynomial and distributing shares.
   • Qualified contributions are aggregated to form the initial master polynomial $F_0(X) = \sum f_j(X)$.
   • Link Proofs: A critical innovation is the use of Non-Interactive Zero-Knowledge (NIZK) proofs to link the constant term of the committed polynomial (the scalar share) to the exponent used in the sequential isogeny action chain that generates the public key $pk$. This ensures the public key corresponds to the shared secret without reconstructing $k$.

2. Threshold Evaluation:

   • The client blinds its input $x$ by mapping it to a curve $X = H_1(ctx \| x)$ and applying a random action $[r]$, sending $B = [r]X$.
   • A quorum of $t$ servers applies their Lagrange-weighted shares sequentially: $Q_h = [\lambda^I_{i_h} s^{(e)}_{i_h}] Q_{h-1}$.
   • Due to the additive property of the action, the final curve is $Q_t = [k]B$.
   • The client unblinds to get $Y = [k]X$ and derives the output.
   • Verification: Each server provides a NIZK proof ($\pi_{eval}$) certifying that the action they performed corresponds to the share committed in the current epoch's public vector $A^{(e)}$.

3. Proactive Share Refresh:

   • To counter mobile adversaries, servers periodically refresh shares without changing $k$.
   • Qualified "refresh dealers" sample zero-sharing polynomials $z_j(X)$ where $z_j(0)=0$.
   • The new polynomial is $F_{e+1}(X) = F_e(X) + \sum z_j(X)$. Since the constant terms sum to zero, $F_{e+1}(0) = k$.
   • Coefficient commitments are updated homomorphically. Old shares are securely erased after the transition.

4. Verification, Blame, and Robust Restart:

   • If a server submits a malformed proof or share, the detecting party generates a blame certificate (a signed transcript of the failure).
   • The blamed server is removed, and the protocol restarts with a new quorum. This ensures identifiable aborts.

5. Committee Resharing:

   • Allows migration to a new set of servers or a new threshold $t'$.
   • An old quorum treats their Lagrange-weighted shares as constant terms for new polynomials distributed to the new committee.
   • Crucially, this transfers the secret $k$ without reconstructing it, preserving the public key and all previously generated OPRF outputs.

Technical Challenges Addressed

• Cross-Domain Witness Consistency: The paper formalizes the need for joint NP relations (e.g., $R_{link}, R_{eval}$) that bind a scalar committed in the field to the same scalar used in the isogeny action. Proving these separately is insufficient; the witness must be identical across domains.
• Epoch Consistency: The protocol enforces that evaluation chains must use shares from a single epoch certificate to prevent mixing shares from different polynomials.

3. Key Contributions

1. Formal Functionality: The authors define an ideal functionality $\mathcal{F}_{pTVOPRF}$ for a long-lived proactive threshold VOPRF, explicitly modeling mobile adversaries who can change the set of corrupted servers between epochs.
2. Dealerless Construction: A construction combining effective isogeny group actions with Shamir secret sharing and additively homomorphic commitments, where the master key is never reconstructed by any single party.
3. Proactive Maintenance: A mechanism to renew server shares against mobile adversaries while preserving the master key, public key, and all historical OPRF outputs. This includes a coordinated epoch transition protocol.
4. Joint NP Relations: The identification and formalization of specific NIZK relations required to link the secret-sharing domain (polynomial coefficients) with the isogeny-action domain (curve transformations).
5. Committee Resharing: A protocol to migrate the secret to a new committee or change the threshold without invalidating existing encrypted databases indexed by OPRF outputs.
6. Security Analysis: A simulation-based security proof in the random oracle model under the vectorization and one-more hidden-group-action assumptions, proving input privacy and key secrecy against mobile semi-honest adversaries.

4. Results and Performance

• Correctness: The paper proves that the protocol maintains the invariant that the master key $k$ and public key $pk$ remain constant across DKG, evaluation, refresh, and resharing operations.
• Security: The construction is proven secure against a mobile semi-honest adversary who corrupts fewer than $t$ servers in any single epoch. The security relies on the secure erasure of old shares and the information-theoretic privacy of Shamir sharing.
• Efficiency Trade-offs:
  • Transcript Size: Unlike MPC-based virtual server approaches that offer constant-size client transcripts, PIVOT has an $O(t)$ client transcript because it exposes the sequential chain of $t$ partial evaluations and proofs.
  • Latency: Evaluation requires $t$ sequential group actions and proofs, creating a linear latency bottleneck relative to the threshold.
  • Maintenance: Proactive refresh and committee resharing involve $O(n^2)$ communication (due to point-to-point share distribution) but do not require isogeny actions, making them suitable for amortization over long periods.
  • Applications: The paper highlights that while the online cost is higher, the ability to refresh shares and migrate committees without re-encrypting large databases (e.g., in private lookup services) provides significant operational efficiency for long-lived services.

5. Significance and Claims

The paper claims to present the first threshold VOPRF from isogeny group actions that provides proactive security against a mobile adversary.

The authors position PIVOT not as a performance optimization over existing single-server or MPC-based OPRFs, but as a feature-complete framework for long-lived services. The significance lies in the architectural choice to expose the threshold structure explicitly rather than hiding it behind a virtual server. This explicitness enables:

• Direct application of proactive refresh (adding zero-sharing polynomials).
• Individual accountability (blame attribution).
• Seamless committee migration without key reconstruction.

The paper concludes that for services requiring operational longevity over years in the presence of gradual compromise, the cost of an $O(t)$ transcript is a necessary trade-off for the ability to periodically renew the system's security state without disrupting the underlying cryptographic service or re-encrypting dependent data.