Skip to content

Questions about “Precomputed data”(Section 3.2.1.1) in SQIsign Algorithm specifications and supporting documentation #13

@ECCTF

Description

@ECCTF

Issue 1: In the original reference Ibukiyama (1982) [Ibu82], the auxiliary prime is taken such that $q≡3(mod8)$ and $r`^2+m≡0(mod4q)$. However, in the SQIsign specification, $q≡1(mod4)$ and the condition is $r^2≡-p(modq)$.

Issue 2: When I tried to validate the construction in Sage, I found that the statement/results in [Ibu82] behave as expected for both $B=(−1,−p)$ and $B′=(−q,−p)$ (from ESPV23, Lemma 10). However, under the SQIsign conditions (with $q≡1(mod4)$ and $r^2≡-p(modq)$), the $O_t$ does not seem to be closed under multiplication (i.e., it does not appear to be an order/ring).

Issue 3: In the precomputation section, the connecting ideal is written as $I=O_0\cdot O_t$. However, earlier in the document (around p.28), the connecting ideal is given as $I=N*O_l\cdot O_r$.

Issue 4: In the “equivalent ideal” step, the document defines $J=I\cdot\frac{\overline{\alpha}}{N(I)}$. However, in the precomputation section it defines $J_t=O_0O_t*\gamma^{-1}=O_0O_t\cdot\frac{\overline{\gamma}}{N(\gamma)}$. If these formulas are meant to be consistent, it seems to suggest $N(I)=N(\gamma)$, which would then imply $N(J_t)=1$. I find this hard to reconcile.

Image Image

on-maximal-orders-of-division-quaternion-algebras-over-the-rational-number-field-with-certain-optimal-embeddings.pdf

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions