Error-Free Multiparty Homomorphic Secret Sharing

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

Homomorphic secret sharing distributes an input among parties so that local computations yield shares of the target output. A branching program is a directed decision graph evaluating a function by following input-labelled transitions. DDH is the decisional Diffie-Hellman assumption in the selected group.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The error convention, compactness target, and group/security models are not specified in the short question.

Source-record limitation: The sharing security model, branching-program class, compactness condition, and error/running-time requirement are not specified.

Statement recorded in the supplied source.

For DDH-based homomorphic secret sharing supporting compact evaluation of branching programs, can the inverse-polynomial evaluation error be eliminated or its running-time dependence improved, and can analogous results be obtained for three or more parties? [S2]

Source status.

The supplied catalogue labels this source record partially solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Remove or improve the stated homomorphic-sharing error and extend the result to three or more parties.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003378 (OWR-15210-004). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cryptography $2018$, Oberwolfach Reports, DOI 10.4171/owr/2017/5, pp. 213--266 https://doi.org/10.4171/owr/2017/5.
• S3 Abram et al., Succinct Homomorphic Secret Sharing https://eprint.iacr.org/2024/814.pdf.
• S4 Multi-Party Homomorphic Secret Sharing https://eprint.iacr.org/2023/1593.pdf.
• S5 Homomorphic Secret Sharing https://eprint.iacr.org/2018/419.pdf.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30003378 and code OWR-15210-004 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

Boyle's HSS talk in OWR 5/2017, pp. 237--238, and the primary abstract of ePrint 2016/585 were read. The abstract specifies two one-bit local evaluation outputs whose XOR is correct except with probability $\delta$, with running time polynomial in $1/\delta$. The report asks for zero error, better dependence, and more parties. The analysis below tests repetition and simple resharing as attempted transformations; it is not a new DDH construction.

Research attempt: Amplification fails to preserve a single additive output share

Repetition helps after reconstruction.

Suppose independent executions on a fixed input produce a reconstructed Boolean output with error probability at most $1/4$ each. For odd $t$, reconstructing all $t$ outputs and taking their majority has failure probability at most \[ (\sqrt3/2)^t. \] To prove this, let $E_i$ indicate an error. For $\lambda=\log3$, independence gives \[ \Pr\left(\sum_iE_i\ge t/2\right) \le 3^{-t/2}\prod_i\mathbb E3^{E_i} \le3^{-t/2}(3/2)^t. \] Thus a receiver allowed $t$ reconstructed outputs can obtain exponentially small error in $t$, assuming the required independent sharing executions and their privacy composition are available. Finite repetition does not make the error exactly zero: for a base procedure with independent error probability $p>0$, the event that all copies err still has probability $p^t>0$.

Local majority is not additive.

The desired source interface has one local bit per party, not an external majority circuit with all shares revealed. Already for three copies there are no maps $a,b:\mathbb F_2^3\to\mathbb F_2$ satisfying \[ a(u)+b(v)=\operatorname{Maj}(u+v)\quad\text{for every }u,v. \] Take $u\in\{0,e_1\}$ and $v\in\{0,e_2\}$. The XOR of the four left sides is zero, since each term occurs twice. On the right, the values at $0,e_1,e_2,e_1+e_2$ are $0,0,0,1$, whose XOR is one. This contradiction disproves a universal postprocessing rule that takes local share vectors to one additive majority share. It does not prove that the particular HSS key distribution contains every such vector pair, or exclude a specialized new construction; it invalidates the unrestricted black-box rule.

Simple resharing has the same algebraic barrier.

A proposed three-party extension might split one party's arithmetic input share $z$ as $a+b$ and ask the two new parties to evaluate its nonlinear local function separately. For maps on an abelian group, a decomposition $f(a+b)=g(a)+h(b)$ for all $a,b$ forces \[ f(a+b)=f(a)+f(b)-f(0), \] by substituting $a=0$ and $b=0$. Conversely this identity permits $g(a)=f(a)-f(0)$, $h(b)=f(b)$. Thus it works exactly when $f-f(0)$ is additive. For $f(z_1,z_2)=z_1z_2$ on $\mathbb F_2^2$, the same four points $0,e_1,e_2,e_1+e_2$ violate the identity. Nonlinear branching-program evaluation therefore cannot in general be extended to another party merely by linearly splitting a share and evaluating independently.

The two obstructions identify the missing operations: privately computing a nonlinear combiner for amplification and constructing evaluation-compatible multiparty keys. Revealing shares to compute a majority would change the compact additive interface and possibly its security use; adding interaction would change round guarantees. Neither cost is removed by the probability calculation.

Verification and adversarial audit

The exponential bound uses independent executions conditional on a fixed input and a base error at most $1/4$; no independence is inferred from merely repeating the same randomness. The majority contradiction checks all four required values exactly. The affine characterization is proved in both directions and is limited to the stated universal local-postprocessing model.

Audit corrections.

Distinguished negligible error from zero error, reconstruction-time majority from local additive evaluation, and splitting a value from splitting a homomorphic key. Avoided claiming a universal impossibility for every HSS construction from an auxiliary four-point obstruction.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No zero-error DDH scheme or source-compatible improved error dependence is constructed, and no secure three-party key-generation/evaluation algorithm is given. A relaxed receiver can amplify at the cost of multiple outputs, but preserving a single additive local output needs more structure. The actual source's computational privacy and parameter constraints are not established by these algebraic tests.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46669 (consulted 2026-10-11).
• https://eprint.iacr.org/2016/585 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written-proof review of this attempt; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.