Security of Interactive Lattice-Based Group Key Exchange

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.

A lattice generated by independent vectors $b_1,\ldots,b_d$ is $L=\{\sum_i z_i b_i:z_i\in\mathbb Z\}$. SVP seeks a shortest nonzero lattice vector; SIVP seeks $d$ independent short vectors, with approximation measured against the relevant successive minimum.

Learning with errors gives noisy linear equations $b_i=\langle a_i,s\rangle+e_i\pmod q$ for a hidden vector $s$. Ring-LWE uses the analogous equations in a polynomial quotient ring, under specified sample and error distributions.

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.

Can provable security be established for the interactive multiparty key exchange protocol of Ding, Xie, and Lin based on LWE and RLWE, viewed as a generalization of their two-party protocol? [S2]

Scope qualification.

The full protocol and security experiment are not reproduced in the supplied question; the report's information and adversary models are required.

Source status.

The supplied catalogue labels this record open. 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

Prove security of the cited interactive multiparty lattice key-exchange protocol.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003376 (OWR-15210-002). 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 Ding et al., A Simple Provably Secure Key Exchange https://archive.ymsc.tsinghua.edu.cn/pacm_download/672/12694-dingjt-i28.pdf.
• S4 Oberwolfach Report 5/2017 https://ems.press/doi/pdf/10.4171/OWR/2017/5. 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 30003376 and source code OWR-15210-002 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

Ding's primary OWR 5/2017 talk, pp. 229--231, was read, including the bilinear-form explanation and the explicit unresolved multiparty-security sentence. The report cites Ding--Xie--Lin, ePrint 2012/688. An attempted web retrieval of its PDF returned HTTP 403, so the full multiparty message schedule, reconciliation rule and security experiment were not inspected. The following is explicitly an auxiliary noisy-bilinear model and a failed hybrid-proof route, not a reconstruction of that unavailable protocol or a security claim about it.

Research attempt: Bilinear agreement does not supply a joint-transcript security proof

A correctness calculation in a stated toy model.

Work modulo an integer $q$. Let $A$ be a public $n\times n$ matrix and let two parties publish $x^TA+e_A^T$ and $Ay+e_B$, respectively. They form \[ K_A=(x^TA+e_A^T)y,\qquad K_B=x^T(Ay+e_B). \] Their difference is \[ K_A-K_B=e_A^Ty-x^Te_B\pmod q. \] If integer lifts satisfy $|x_i|,|y_i|\le S$ and $|(e_A)_i|,|(e_B)_i|\le E$, the displayed lift of the difference has absolute value at most $D=2nSE$. This is a deterministic agreement estimate, not an LWE indistinguishability argument.

For illustration, let an integer bin width $L\ge2$ divide $q$, assume $q\ge2L$ and $D<L$, and choose a public uniform offset $U\in\{0,\ldots,q-1\}$. Quantize by \[ Q_U(z)=\left\lfloor\frac{(z+U)\bmod q}{L}\right\rfloor. \] Two residues with a signed circular difference $d$, $|d|<L$, get different bin labels for exactly $(q/L)|d|$ offsets: each of the $q/L$ boundaries has exactly $|d|$ offsets which move the two values across it, and these sets are disjoint because the boundaries are $L$ apart. Therefore \[ \Pr(Q_U(K_A)\ne Q_U(K_B))\le D/L. \] For several proposed group values whose circular distances from one reference value are bounded by $D_j<L$, the same offset and a union bound give disagreement probability at most $\sum_jD_j/L$. No independence of those errors is needed. Increasing $L$ reduces this bound but also reduces the number $q/L$ of possible bin labels. None of this proves that the resulting label is uniform or secret conditioned on public messages and the public offset; the toy quantizer is not claimed to be the source's reconciliation mechanism.

A concrete obstruction to a marginal-by-marginal hybrid.

Suppose one tried to prove transcript security by showing that every message, or every pair of messages, has a uniform-looking marginal. Let $U,V$ be independent uniform elements of a finite field $F$ and consider \[ (T_1,T_2,T_3)=(U,V,U+V). \] Every individual message is uniform, and every pair is independent uniform: for example $(u,w)$ determines uniquely $v=w-u$. Yet the full triple is distinguished from three independent uniforms by checking $T_3=T_1+T_2$. This test accepts the correlated transcript with probability one and the independent transcript with probability $1/|F|$, giving gap $1-1/|F|$.

Thus even exact pairwise uniformity cannot justify replacing an interactive joint transcript by independent samples. In a multiparty LWE/RLWE proof, later messages may depend on reused secrets and earlier messages, so a valid reduction must simulate those dependencies while embedding its challenge. The example is not an attack on the actual protocol: it identifies the missing logical step in this proposed proof route. Likewise, a small key-disagreement probability is a correctness property and cannot replace a reduction proving session-key indistinguishability under the chosen passive or active adversary experiment.

Verification and adversarial audit

The noise bound is derived from integer lifts, and the quantization calculation treats cyclic wraparound, at least two bins and the strict $D<L$ requirement. The several-party estimate uses only a union bound. The transcript counterexample checks all pairwise marginals and the exact distinguishing probability. No actual protocol transcript, lattice parameter set or attack experiment was available, and no theorem about the security of the named multiparty protocol is asserted.

Audit corrections.

Did not fill missing protocol details with the toy model. Separated correctness, marginal pseudorandomness and full transcript/session-key security. Recorded the failed ePrint PDF retrieval rather than listing it as a consulted full source.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The original protocol specification and its security experiment remain uninspected because the cited full PDF was inaccessible in the attempted retrieval. No faithful transcript simulation, LWE/RLWE hybrid, reconciliation leakage bound or adversarial-corruption analysis is supplied. The proved auxiliary correctness bound and joint-distribution counterexample explain why the attempted route stops before the original security target.

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.