Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles

Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles Based on: Jodie Knapp and Elizabeth A. Quaglia, IACR Cryptol. ePrint Arch. 2020, p. 1078

Gregory Morse — Eötvös Loránd University (ELTE), Budapest, Hungary Presented at the Cryptography Seminar, Fall Semester 2020, December 14, 2020

---

Abstract

This repository accompanies a study of how prior research on Homomorphic Time-Lock Puzzles (HTLPs) can be incorporated into Secret Sharing schemes. This allows for the guarantee that a certain amount of elapsed time has occurred over some number of sharing rounds — determined by the dealer — based on well-established cryptographic security assumptions. A concrete implementation is given using the multiplicatively homomorphic variant (MHTLP), which was further implemented as a protocol simulation suite in Python and tested to obtain real-world performance measurements based on the security bit-size and the time-hardness parameter τ.

The paper under study contained several errors in the appendix which were discovered through careful implementation: an unused prime parameter, a potential information-loss issue from double reduction modulo p then N, a degree-off-by-one in the polynomial threshold, and a misuse of a product symbol in the outer sum of Lagrange interpolation.

---

Repository Structure

mhtlpss/
└── mhtlpss.py    # Full Python protocol simulation suite

---

Background

Secret Sharing (SS)

A $(t, n)$ SS scheme has a (presumed honest) dealer $D$, a secret $s$, and a set $P = {P_1, \ldots, P_n}$ of $n$ players. No subset of fewer than $t$ players can learn $s$; every subset of at least $t$ players can reconstruct $s$. The scheme is a tuple of three PPT algorithms: $(Setup, Share, Recon)$.

Rational Secret Sharing (RSS) introduces game-theoretic fairness and soundness: a player is rational if they have a preference over outcomes. The protocol must achieve a computationally strict Nash equilibrium so that deviating from the prescribed strategy is never beneficial.

Time-Lock Puzzles (TLPs)

A TLP embeds a secret into a puzzle such that it cannot be decrypted until time parameter $\tau$ has elapsed. Formally it is $(PGen, PSolve)$ where:

• $Z \leftarrow PGen(\tau, s)$ — probabilistic puzzle generation
• $s \leftarrow PSolve(Z)$ — deterministic puzzle solving, requiring $\Omega(2^\tau)$ work

A Homomorphic TLP (HTLP) additionally supports evaluation of a function over encrypted puzzles without solving them first. This work uses the Multiplicative HTLP (MHTLP) from:

G. Malavolta and S. A. K. Thyagarajan. Homomorphic time-lock puzzles and applications. CRYPTO 2019, LNCS vol. 11692, pp. 620–649. Springer, 2019.

---

Concrete Instantiation (MHTLP)

The MHTLP operates over the Jacobi subgroup $\mathbb{J}_N \subseteq \mathbb{Z}_N^*$, the group of elements with Jacobi symbol $+1$, which is closed under multiplication.

MHP.Setup(1^λ, τ)

• Generate $\lambda$-bit RSA safe primes $p, q$ (i.e. $p = 2p' + 1$, $q = 2q' + 1$ where $p', q'$ are Sophie Germain primes)
• $N := p \cdot q$; $\phi(N) = (p-1)(q-1)$
• Sample $\tilde{g}$ uniformly at random from $\mathbb{Z}_N^*$; set $g := -\tilde{g}^2 \bmod N$ so that $g \in \mathbb{J}_N$
• Compute $h := g^{2^\tau \bmod \phi(N)/2} \bmod N$
• Output public parameters $pp := (\tau, N, g, h)$

MHP.PGen(pp, s)

• Sample uniform $r \leftarrow {1, \ldots, N^2}$
• Output puzzle $Z := (u, v) = (g^r \bmod N,\ h^r \cdot s \bmod N)$

MHP.PSolve(pp, Z)

• Compute $w := u^{2^\tau} \bmod N$ via sequential squaring (no totient shortcut available to solver)
• Output $s := v \cdot w^{-1} \bmod N$

MHP.PEval(⊗, pp, Z₁, …, Zₙ)

• Compute $\tilde{u} := \prod u_i \bmod N$, $\tilde{v} := \prod v_i \bmod N$
• Output combined puzzle $(\tilde{u}, \tilde{v})$
• This reduces the number of sequential squarings required from $n \cdot \tau$ to $\tau$

---

Protocol

The protocol is a $(r, r+1)$ threshold scheme over $m = r + d$ shares, where $r$ is the reconstruction threshold and $d$ is the number of decoy (fake) shares.

Setup Phase

The dealer $D$ runs MHP.Setup to obtain $pp_1$, samples evaluation points ${y_0, \ldots, y_m}$ uniformly at random from $\mathbb{J}_N$, and draws geometric distribution parameters $r$ and $d$.

Share Phase

The dealer D generates a random secret $s$ from the Jacobi group 𝕁_N and a random polynomial of degree $r-1$ with constant term a₀ = s:

$$f(x) = a_0 + a_1 x + \cdots + a_{r-1}, x^{r-1}$$

Real shares are computed as s_i = f(y_i) mod N for $i = 0, \ldots, r$. Fake shares s_r+1, …, s_m are drawn uniformly at random from 𝕁_N.

Each share s_i is split into $n$ sub-shares: for each $j = 1, \ldots, n-1$, sub-share s_i,j is drawn uniformly at random from QR_N. The last sub-share enforces the product relation:

$$s_{i,n} = s_i \cdot \Bigl(\prod_{j=1}^{n-1} s_{i,j}\Bigr)^{-1} \bmod N$$

Each sub-share is wrapped in a time-lock puzzle:

$$\mathcal{Z}_{i,j} := \mathrm{MHP.PGen}(pp_1,; s_{i,j})$$

Finally D broadcasts $pp'$ and checking share s₀ = f(y₀), and sends to each player P_j the list:

$$\mathrm{list}_j = \left\lbrace \mathcal{Z}_{1,j}, \ldots, \mathcal{Z}_{m,j} \right\rbrace$$

Reconstruction Phase

In each round $k$ (where $1 \le k \le m$), all players broadcast their sub-share $s_{k,j}$. From round 2 onward, each player:

1. Combines the sub-puzzles homomorphically:

$$\mathcal{Z}_k \leftarrow \mathrm{MHP.PEval}\left(\otimes,; pp_1,; \mathcal{Z}_{k,1}, \ldots, \mathcal{Z}_{k,n}\right)$$

2. Solves the combined puzzle to obtain $s_k \leftarrow \mathrm{MHP.PSolve}(pp_1, \mathcal{Z}_k)$.
3. Recovers $f'(x)$ by Lagrange interpolation over $(y_1, s_1), \ldots, (y_k, s_k)$.
4. Checks: if $f'(y_0) \bmod N = s_0$, outputs $s = f'(0)$; otherwise waits for the next round.

---

Running

python3 mhtlpss.py

Prerequisites: Python 3.x, standard library only (uses random, timeit, functools).

Example Output

Secret 177752076808708683724019157938862414660819843138117806454785143209647261648387
Secret recovered:  42992640874959428435985600054132028856757633984717618489627487864674394068400
Verification check:  False
Secret recovered:  47882224558090490054864839956187730250673258445210066817503657188159850231087
Verification check:  False
Secret recovered:  119675411572083612811154639174043756103610737852506437200371014482416860367104
Verification check:  False
Secret recovered:  177752076808708683724019157938862414660819843138117806454785143209647261648387
Verification check:  True

The secret is recovered only once the Lagrange interpolation has accumulated enough real shares and the checking share $s_0$ is satisfied.

---

Experimental Results

Benchmarks were collected with parameters $n=4$, $r=4$, $d=3$ ($m=7$ total shares), measuring the wall-clock time for a single full protocol execution (MHP.PEval + MHP.PSolve for all $m$ shares) across varying security parameter $\lambda$ and hardness parameter $\tau$:

$\tau$	$\lambda=128$ (s)	$\lambda=256$ (s)	$\lambda=512$ (s)	$\lambda=1024$ (s)
1,048,576	3.24	7.44	21.24	69.29
2,097,152	7.05	15.29	42.43	137.90
4,194,304	13.94	31.46	83.48	279.59
8,388,608	26.77	63.45	173.49	556.34

Observations:

• Run time scales linearly in $\tau$ as expected (sequential squarings dominate)
• Run time scales super-linearly in $\lambda$ due to the quadratic cost of modular multiplication on large integers $\mathcal{O}(n^2)$; practically $\mathcal{O}(\lambda^2)$
• Prime generation time is excluded from measurements as it has high variance

A professional implementation in C/C++ using optimized modular arithmetic e.g., Karatsuba $\mathcal{O}(n^{\log_2 3})$, Schönhage-Strassen $\mathcal{O}(n \log n \cdot \log \log n)$, or Harvey–van der Hoeven $\mathcal{O}(n \log n)$ would yield substantially lower absolute times.

---

Security Assumptions

The scheme's security rests on three standard hardness assumptions:

1. Strong RSA — Given strong RSA modulus $N$, it is hard to compute $e$-th roots modulo $N$ for random prime $e$.

2. Sequential Squaring — Given generator $g$ of $\mathbb{J}_N$ and time bound $\tau$, no circuit of depth $< \tau^\epsilon$ (for some $0 < \epsilon < 1$) can distinguish $x^{2^\tau}$ from a random element of $\mathbb{J}_N$ with advantage non-negligibly greater than $\frac{1}{2}$.

3. Decisional Diffie-Hellman (DDH) over $\mathbb{J}_N$ — $(g, g^x, g^y, g^{xy})$ is computationally indistinguishable from $(g, g^x, g^y, g^z)$ for random $z$.

Known Weaknesses

• The checking share $s_0$ allows any player to test candidate secrets in each round, meaning $r-1$ shares may suffice if an external verification oracle exists.
• If an adversary factors $N$ (knowing $p, q$), the $2^\tau$ exponentiation shortcut used by the dealer becomes available, breaking the time-hardness guarantee.
• The scheme is not post-quantum: security relies on the hardness of integer factoring, which Shor's algorithm breaks in polynomial time.
• A cryptographically secure PRNG (CSPRNG) must replace random in any real deployment.

---

Errors Found in the Paper

During implementation, the following issues were identified in the appendix of the original paper (Knapp & Quaglia, 2020):

• Unused prime $p$ — Public parameters specified a prime $p > {s, n}$ (seemingly as the polynomial field) that was never referenced in the protocol.
• Double reduction — $y = f(x) \bmod p \bmod N$ would cause information loss when $f(x) > p > N$.
• Degree off by one — The protocol specified $r$ shares to recover a polynomial of degree $r$, which of course must be degree $r - 1$.
• Wrong symbol — Lagrange interpolation used a product symbol $\prod$ for the outer summation instead of $\sum$.

---

Implementation Notes

The code builds on a subset of the Shamir's Secret Sharing Python example from Wikipedia (CC0 / OWFa licensed). The functions retained from that base are:

• _extended_gcd(a, b) — extended Euclidean algorithm for modular inverse
• _eval_at(poly, x, prime) — Horner's method polynomial evaluation
• _divmod(num, den, p) — modular division via _extended_gcd

All cryptographic primitives (MHTLP setup, puzzle generation, solving, evaluation), the Miller-Rabin primality tester, safe prime generation, Jacobi symbol computation, Lagrange interpolation with full polynomial recovery, and the protocol simulation are original implementations written for this study.

---

References

• Knapp, J., Quaglia, E. A. (2020). Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles. IACR Cryptol. ePrint Arch. 2020, p. 1078. https://eprint.iacr.org/2020/1078
• Malavolta, G., Thyagarajan, S. A. K. (2019). Homomorphic time-lock puzzles and applications. CRYPTO 2019, LNCS vol. 11692, pp. 620–649. Springer. https://eprint.iacr.org/2019/477
• Rivest, R. L., Shamir, A., Wagner, D. A. (1996). Time-lock puzzles and timed-release crypto. MIT/LCS/TR-684.
• Shamir, A. (1979). How to share a secret. Commun. ACM, 22(11), 612–613.
• Wikipedia contributors. Miller–Rabin primality test. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
• Wikipedia contributors. Jacobi symbol. https://en.wikipedia.org/wiki/Jacobi_symbol
• Wikipedia contributors. Safe and Sophie Germain primes. https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes
• Wikipedia contributors. Shamir's Secret Sharing — Python example. https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Python_example

---

Citation

If you use or build upon this work, please cite:

@misc{morse2020mhtlpss,
  author    = {Gregory Morse},
  title     = {Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles:
               Python Protocol Simulation Suite},
  year      = {2020},
  note      = {Cryptography Seminar, Fall Semester 2020,
               E\"{o}tv\"{o}s Lor\'{a}nd University (ELTE),
               Budapest, Hungary. December 14, 2020},
  url       = {https://github.com/GregoryMorse/mhtlpss}
}

---

License

MIT License. See LICENSE for details.

---

Contact

Gregory Morse — gregory.morse@live.com Eötvös Loránd University (ELTE), Budapest, Hungary