Assumptions and Function Classes for Function Secret Sharing

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Function secret sharing distributes keys whose local evaluations combine to the output of a function while hiding that function from the prescribed coalitions. A point function is nonzero at one designated input and zero elsewhere.

A cryptographic security requirement compares an efficient adversary's advantage with a negligible function of the security parameter. A negligible function is smaller than every inverse polynomial eventually; computational and information-theoretic security are different requirements.

Statement recorded in the supplied source.

Characterize the function classes for which efficient function secret-sharing schemes follow from one-way functions, and determine the necessary and sufficient cryptographic assumptions for useful FSS instances; in particular, improve one-way-function-based FSS for point functions with at least three parties. [S2]

Scope qualification.

The coalition threshold, leakage, output group, and efficiency parameters are source-specific.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Characterize which functions admit efficient secret sharing from one-way functions and improve the stated multiparty point-function case.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003377 (OWR-15210-003). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary 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 Boyle, Gilboa, and Ishai, Function Secret Sharing https://www.iacr.org/archive/eurocrypt2015/90560300/90560300.pdf.
• S4 Function Secret Sharing, Improvements and Extensions https://eprint.iacr.org/2018/707.pdf. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003377 and source code OWR-15210-003 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

Ishai's FSS talk in OWR 5/2017, p. 236, was read. It defines additive function shares, privacy against every strict subset of parties, and asks specifically about efficient one-way-function-based point-function FSS for at least three parties. The source already compares with truth-table sharing. The following information-theoretic lower bound investigates why replacing computational privacy by perfect privacy is not a free simplification; it does not characterize one-way-function constructions.

Research attempt: Perfect-privacy point sharing requires long additive keys

A baseline with exact privacy.

Let the domain have $N$ points, and represent a Boolean function by its truth table $F\in\mathbb F_2^N$. For $m\ge2$, choose independent uniform vectors $K_1,\ldots,K_{m-1}\in\mathbb F_2^N$ and set $K_m=F+\sum_{j<m}K_j$. Party $j$ outputs the requested coordinate of $K_j$. Their sum is $F$ at every point. Every strict coalition sees a uniform tuple independent of $F$: if it omits party $m$, this is immediate; otherwise at least one independent uniform mask is missing, and it makes $K_m$ uniform conditional on all the observed masks. Each key has $N$ bits.

A near-matching lower bound even for point functions.

Now restrict the hidden function to $F=e_i$, the point function at $i\in[N]$, where $N\ge2$. Consider any $m$-party scheme with the following additional hypotheses: local evaluations are deterministic functions of a key and the public input; outputs add in $\mathbb F_2$; correctness holds with probability one simultaneously at all $N$ points; and every strict coalition's key distribution is exactly independent of $i$. Let $V_j\in\mathbb F_2^N$ be the full evaluation vector determined by party $j$'s key.

Fix a party $j$. Let $B=V_j$ and $A=\sum_{\ell\ne j}V_\ell$. The laws of $A$ and of $B$ are each independent of the selected point by the two relevant coalition privacy conditions, and correctness gives $B=e_i+A$. Denote the common law of $A$ by $\mu$. Since the law of $B$ is the same for every $i$, the measure $\mu$ is invariant under translation by every vector $e_i+e_{i'}$. These vectors span the even-parity subspace \[ E=\{v\in\mathbb F_2^N:\sum_i v_i=0\},\qquad |E|=2^{N-1}. \] Indeed $e_1+e_i$ for $i>1$ are linearly independent and span that subspace: the last $N-1$ coordinates determine every even-parity vector.

Translation invariance forces $\mu$ to be uniform within each of the two cosets of $E$. Conditional on its parity, $A$ therefore has entropy $N-1$ bits; hence $H(A)\ge N-1$. The same holds for $B=e_i+A$. Since $B$ is a deterministic function of party $j$'s key, that key must have entropy at least $N-1$: grouping key outcomes by their evaluation vector cannot increase entropy, as follows directly by decomposing entropy into the entropy of the group label plus the nonnegative conditional entropy. In particular, if each key is encoded in at most $\ell$ bits in a fixed-length encoding, $\ell\ge N-1$. The argument holds for every party and every $m\ge2$, including three or more parties.

Why this does not refute succinct computational FSS.

The proof uses equality of distributions to propagate invariance along all translations in a subspace of exponential size. Computational indistinguishability is weaker and does not imply equality or uniformity on those cosets. An unbounded observer could enumerate the truth table and distinguish distributions that efficient observers cannot distinguish. Thus the lower bound applies to the explicitly stronger perfect-privacy model, while the source asks for computational constructions from one-way functions. Nor does it establish that one-way functions are necessary for every useful FSS instance: that would need a separate reduction with the source's exact functionality, security and efficiency parameters.

Verification and adversarial audit

The baseline coalition proof handles coalitions containing the final balancing share. The lower bound uses privacy of the single selected party and of its complement; it does not mistakenly assume independent shares. The even-parity span, both cosets, arbitrary party count, $N=2$, and the entropy-to-fixed-key-length implication were checked. For $N=1$ the stated lower bound is zero and the nontrivial span argument is unnecessary.

Audit corrections.

Replaced a weak counting argument based only on the $N$ possible point functions by a proved translation-invariance argument. Kept perfect privacy, deterministic evaluation, exact correctness and fixed-length key encoding explicit; none is silently imposed on the original computational target.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No improved one-way-function-based scheme, full function-class characterization, or necessary-and-sufficient cryptographic assumption theorem is supplied. The actual result is an elementary perfect-privacy obstruction explaining why a tempting information-theoretic replacement cannot give short point-function keys. Computational privacy remains the essential missing ingredient.

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).

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.