FALCON mínithe go matamaiticiúil

1. Cad atá i gceist anseo

Ní réimse téacs i mbunachar sonraí é léirmheas ar McGesund a chaithfeá a chreidiúint. Nuair a sheoltar isteach é sínítear go digiteach é, agus is féidir le gach cuairteoir an síniú sin a athríomh níos déanaí ina bhrabhsálaí féin.

Úsáidimid FALCON do chuid de na sínithe seo — FN-DSA-512 agus FN-DSA-1024 go beacht. Míníonn an t-alt seo cad a tharlaíonn go matamaiticiúil.

Rud tábhachtach ar dtús:

Ní criptiú é FALCON. Is é is aidhm dó go léifear téacs an léirmheasa. Ní rúndacht a chruthaíonn FALCON ach bunús agus sláine.

---

2. Cad go díreach a shínítear

Ní hé an téacs leanúnach a shínítear ach oibiacht sonraí dhlúth a dhaingníonn an téacs gan athbhrí:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<Aitheantas an ghnólachta>",
  "c":   "<Aitheantas an léirmheasa>",
  "h":   "<SHA-256 de théacs an léirmheasa>",
  "rh":  "<SHA-256 den taifead aighneachta iomlán>",
  "rv":  1,
  "qh":  "<SHA-256 den chlúdach QR, léirmheasanna QR amháin>",
  "iat": 1757203200
}

Is í sin ár dteachtaireacht $m$. Ceanglaíonn sí le chéile:

1. cén gnólacht lena mbaineann an léirmheas (f),
2. cén léirmheas atá i gceist (c),
3. cén téacs a bhí taobh thiar de — mar haisluach (h),
4. cén taifead a cuireadh isteach ina iomláine (rh): téacs, croíthe, geo-stádas agus sonraí faoin ócáid, srathaithe go canónta agus haiseáilte, i leagan scéime rv,
5. as cén cód QR a tháinig an léirmheas (qh) — i gcás léirmheasa gan QR fágtar an réimse ar lár,
6. cathain a síníodh (iat).

Briseann carachtar athraithe amháin i dtéacs an léirmheasa an slabhra sin. Is é sin an aidhm go díreach — agus ó tháinig rh isteach is amhlaidh an scéal do chroí a bogadh nó do gheo-stádas a athraíodh ina dhiaidh sin.

---

3. An bhunfhadhb

Léitheoir a thagann ar phróifíl gnólachta, bíonn dhá cheist os a chomhair:

1. An as córas McGesund a tháinig an léirmheas seo i ndáiríre?
2. Ar athraíodh ina dhiaidh sin é?

Chuige sin tá péire eochracha ann:

• eochair phríobháideach — fanann sí sa tseirbhís sínithe
• eochair phoiblí — is ceadmhach do chách í a bheith aige

Sínítear leis an eochair phríobháideach, fíoraítear leis an gceann poiblí. Agus sin ar ghléas an léitheora, ní ar ár bhfreastalaí féin.

---

4. Cén fáth FALCON?

Tá go leor de na scéimeanna sínithe atá in úsáid inniu bunaithe ar fhadhbanna atá deacair do ríomhairí clasaiceacha ach a d'fhéadfadh a bheith i bhfad níos éasca do ríomhairí candamacha atá mór go leor.

I gcás léirmheasa tá sé sin níos ábhartha ná i gcás teachtaireachta gearrshaolaí: ba cheart go mbeadh léirmheas infhíoraithe fós i gceann cúig nó deich mbliana. An té a shíníonn inniu, síníonn sé ar feadh shaolré iomlán an iontrála.

Dá bhrí sin tá FALCON bunaithe ar chriptagrafaíocht laitíse:

Tógtar laitís ar féidir cur síos matamaiticiúil simplí a dhéanamh uirthi, ach ina bhfuil tasc cuardaigh áirithe fíordheacair.

---

5. Cad is laitís mhatamaiticiúil ann?

Dhá veicteoir:

Tugann gach teaglaim slánuimhriúil

laitís de phointí. Mar shampla:

Is é an rud cinntitheach:

Tá an laitís féin éasca le cur síos. Ach tá sé an-deacair airíonna áirithe inti a aimsiú.

---

6. Is iad na veicteoirí gearra an rún

Seo an tasc deacair clasaiceach:

Is í sin an Shortest Vector Problem. In dhá thoise is féidir í a réiteach le triail agus earráid. Oibríonn FALCON i dtoise 512 nó 1024 — agus ansin níl aon dul as.

Ach ní hé an veicteoir is giorra ar fad a theastaíonn ó FALCON, ach rud gaolmhar: pointe laitíse a aimsiú atá gar do sprioc-phointe tugtha. Tá sé sin deacair freisin gan an t-eolas breise ceart.

---

7. Polanaim in ionad uimhreacha

Úsáideann FALCON laitís NTRU agus ríomhann sé le polanaim. In ionad uimhreacha aonair, mar sin, le liostaí comhéifeachtaí:

Ríomhtar sa fháinne

Ciallaíonn sin:

• $\mathbb{Z}_q$: ríomh módúlas $q$. Le $q=7$, cuir i gcás, $10\equiv3$, mar $10-7=3$.
• $x^n=-1$: coinníonn sé na polanaim ar fhad daingean.

Úsáideann FALCON go sonrach:

---

8. An cleas lárnach

Tá an eochair phríobháideach comhdhéanta de cheithre pholanam bheaga

leis an gcothromóid NTRU

Cruthaíonn na ceithre cinn sin le chéile bonn laitíse rúnda soghabhálach — cur síos ar an laitís as veicteoirí gearra.

Níl san eochair phoiblí go bunúsach ach aon pholanam amháin:

As $h$ eascraíonn an laitís chéanna, ach i mbonn místuama as veicteoirí fada:

Sin croí iomlán FALCON. Cuireann an dá bhonn síos ar an laitís chéanna. Ach tá ceann acu inúsáidte don ríomh agus an ceann eile as feidhm.

Is féidir é sin a shamhlú mar léarscáil cathrach: tá an léarscáil iomlán poiblí. Is é eolas na n-aicearraí atá rúnda.

---

9. Déantar pointe den léirmheas

Sula sínítear, gabhann oibiacht an phálasta trí fheidhm haiseála. Baineann FALCON úsáid as Hash-to-Point chuige sin: ní luach uimhriúil a eascraíonn as an teachtaireacht ach pointe san fháinne go díreach.

Ina theannta sin tarraingíonn an tseirbhís sínithe salann randamach $r$ (320 giotán) agus haiseálann sé leis é:

Ní maisiúchán é an salann. Dá uireasa thabharfadh an léirmheas céanna an síniú céanna i gcónaí, agus d'fhéadfaí an bonn rúnda a athchruthú as go leor sínithe. Dá bhrí sin téann sé isteach sa síniú freisin.

---

10. Cad is síniú bailí ann

Tá péire á lorg

a bhfuil dhá airí aige:

Tá an chéad choinníoll leis féin fánach le comhlíonadh — socraítear $s_2=0$ agus $s_1=c$. Is é an dara coinníoll a dhéanann an tasc deacair.

---

11. Mionsampla arna ríomh ina iomláine

Laghdaímid gach rud go méid bréagáin: polanaim nach bhfuil ach aon chomhéifeacht amháin acu, is é sin gnáthuimhreacha, agus

An eochair rúnda. Dhá uimhir bheaga:

An eochair phoiblí. Tá $3^{-1}\equiv65 \pmod{97}$, mar $3\cdot65=195=2\cdot97+1$. Mar sin:

An laitís. $L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}$.

Eascraíonn an bonn poiblí go díreach as $h$:

Tá an dá cheann in $L$ — agus tá an dá cheann fada.

Níl an bonn rúnda ar eolas ach ag an tseirbhís sínithe:

mar $-5+34\cdot3=97\equiv0$ agus $-9+34\cdot(-14)=-485=-5\cdot97\equiv0$. Is é an deitéarmanant

agus oibríonn an chothromóid NTRU dá bhrí sin. Tá an dá veicteoir gearr.

---

Céim 1: An léirmheas a haiseáil

Cuir i gcás go dtugann oibiacht phálasta an léirmheasa

Céim 2: An chéad réiteach lag

sásaíonn sé $71+34\cdot0=71\equiv c$. Ach is é $71$ an fad — i bhfad rófhada.

Céim 3: Giorrú leis an mbonn rúnda

Cuireann an tseirbhís sínithe an sprioc-phointe in iúl ina bonn gearr féin:

Tugann sin $a\approx-10.25$ agus $b\approx-2.20$. Slánaithe go $a=-10$, $b=-2$, eascraíonn an pointe laitíse

Seiceáil: $68+34\cdot(-2)=68-68=0$, agus tá sé in $L$ dáiríre. Dealú:

Fad:

Sin é an síniú.

Céim 4: An scéim chéanna leis an mbonn poiblí

An té nach bhfuil aige ach $h=34$, tá an bonn $\{(97,0),(-34,1)\}$ aige. Tugann an ríomh slánaithe céanna an pointe laitíse $(97,0)$ ansin agus dá bharr

Réiteach bailí ar an gcothromóid freisin — ach seacht n-uaire níos faide. Má shocraítear an teorainn glactha faoi bhun 26, níl aon fhiúntas leis.

Sin comhla thógála FALCON in aon líne amháin.

Céim 5: Fíoraíonn an brabhsálaí

Faigheann an brabhsálaí an léirmheas, an salann agus $s_2=2$. Ríomhann sé an hais as an nua, faigheann sé $c=71$, athchruthaíonn sé

agus seiceálann sé an fad:

Céim 6: Athraíonn duine téacs an léirmheasa

Má athraítear an téacs ina dhiaidh sin, athraíonn hais an ábhair agus dá bharr sin an pointe, abraimis go

Fanann an seansíniú ag $(3,2)$, ach

Is féidir linn léirmheas a scriosadh. Ní féidir linn é a athrú gan é a bheith le tabhairt faoi deara.

Nóta ionracais faoin sampla

In dhá thoise is féidir le hionsaitheoir réitigh ghearra a thriail go simplí — do $c'=40$, cuir i gcás, $(6,1)$. Níl an sampla slán; ní thaispeánann sé ach an meicníocht. I gcás FALCON-1024 tá 2048 comhéifeacht sa veicteoir, agus ansin ní thugann triail agus earráid áit ar bith thú.

---

12. Cén fáth nach ndéantar slánú go simplí?

Tugtar slánú Babai ar an modh as Céim 3. Is leor é do shampla teagaisc — ach ní leor do scéim shínithe fhíordhearfach.

Is é an chúis: níl na sínithe slánaithe dáilte go cothrom. Braitheann a gcruth ar chéimseata an bhoinn rúnda. As líon leordhóthanach sínithe d'fhéadfaí an chéimseata sin a athchruthú — agus dá bharr sin an eochair phríobháideach. Is air sin go díreach a theip ar scéimeanna sínithe laitísbhunaithe níos luaithe.

Dá bhrí sin tarraingíonn FALCON na veicteoirí gearra as dáileadh Gaussach discréideach ar an laitís:

Tá luachanna gar don sprioc-phointe níos dóchúla, ach tá sé randamach cé acu go beacht a roghnaítear. Is é an toradh dáileadh nach sceitheann faic faoin mbonn a úsáideadh — go matamaiticiúil: ní féidir idirdhealú a dhéanamh idir é agus dáileadh nach mbraitheann ach ar an laitís féin.

Is é an samplóir seo an chuid is dúshlánaí de FALCON. Ritheann sé go hathchúrsach thar struchtúr crainn agus oibríonn sé le huimhreacha snámhphointe — rud a fhágann an cur i bhfeidhm íogair agus arb é an phríomhchúis é go bhfuil FALCON níos deacra a chur i bhfeidhm i gceart ná ML-DSA.

---

13. Cad a tharchuirtear i ndáiríre

Tá an síniú comhdhéanta de

$s_2$ amháin — ní an péire. Ríomhann an fíoraitheoir $s_1$ é féin:

Ós rud é go bhfuil comhéifeachtaí $s_2$ beag agus scaipthe timpeall nialais, is féidir iad a chomhbhrú go mór. Sin an chúis le sínithe FALCON atá suntasach dlúth:

Mar chomparáid: teastaíonn 4,627 beart ó ML-DSA-87. Ag McGesund, áfach, níl aon cheann de na sínithe seo sa chód QR féin — níl ar an ngreamán ach an clúdach Ed25519; luíonn na stampaí PQ leis an taifead agus lódáiltear iad agus an fíorú ar siúl. Ní hí an mhéid a shocraíonn an in-inphriontáilteacht anseo mar sin, ach an stóráil agus an tarchur: tá stampa FALCON tuairim is ceathrú de mhéid stampa ML-DSA.

---

14. Cén fáth a bhfíoraíonn FALCON go tapa

Cosnaíonn iolrú polanam go soineanta

Leis an gclaochlú tapa Fourier titeann sé sin go dtí timpeall

Le $n=1024$ is é sin an difear idir milliún agus timpeall deich míle oibríocht. Sin an fáth a ritheann an fíorú i mbrabhsálaí cuairteora i milleasoicindí — agus sin an fáth a bhfuil an F san ainm:

FAst Fourier Lattice-based COmpact signatures over NTRU.

---

15. An próiseas i bpictiúr

---

16. Cén fáth a dteipeann ar ionsaitheoir

Tá $h$ ar eolas aige agus dá bharr sin an laitís ar fad. Tá an sprioc-phointe $c$ ar eolas aige freisin chomh luath is atá an léirmheas poiblí. Is é an bonn gearr atá in easnamh air.

Chun léirmheas a bhrionnú chaithfeadh sé veicteoir gearr a aimsiú do $c$ a roghnódh sé féin — as an gcur síos poiblí amháin. Is é sin an tasc a léirigh Céim 4 den sampla: gan na veicteoirí maithe tagann an ríomh céanna i dtír ar réiteach atá i bhfad rófhada.

I dtoise 1024 tá na modhanna is fearr atá ar eolas — idir chlasaiceach agus chandamach — i bhfad uaidh sin.

---

17. Cad a dhéanann McGesund leis go praiticiúil

An clúdach. Iompraíonn gach léirmheas sínithe síniú Ed25519. Is í sin an leagan éigeantach — clasaiceach, an-bheag, infhíoraithe ó dhúchas i ngach brabhsálaí.

Na stampaí iar-chandamacha. Taobh leis luíonn síniú amháin nó dhá shíniú chandam-fhriotaíocha. Braitheann sé ar an bplean cé acu:

Tá an leagan comhthreomhar iomarcach d'aon ghnó. Tá FALCON bunaithe ar laitísí NTRU, ML-DSA ar laitísí modúil. Dá mbeadh ceann den dá theaghlach níos laige ná mar a cheaptar inniu, iompraíonn an ceann eile ar aghaidh.

An t-ancaire ama. Ancairítear méarlorg na heochrach sínithe i mbloc Bitcoin trí OpenTimestamps. Cruthaítear leis sin ní hamháin go bhfuil an síniú fíor ach freisin go raibh sé ann cheana ag am ar leith — gan gá le duine ar bith ár stampa ama a chreidiúint.

Ríomhtar é sin ar fad i mbrabhsálaí an léitheora, trí mhodúl WASM. Soláthraímid na sonraí; ritheann an fíorú ar ghléas an chuairteora. Dá rachaimis den líne amárach, d'fhanfadh léirmheas a lódáladh uair amháin infhíoraithe.

Maidir leis na hainmneacha: tá FALCON á chaighdeánú faoi láthair mar FN-DSA; tá an dréacht beartaithe mar FIPS 206, ach níl sé críochnaithe fós. Dá bhrí sin tugtar FN-DSA-512 agus FN-DSA-1024 ar na leibhéil i gcód McGesund, cé go labhraítear ar FALCON i gcónaí sa ghnáthchaint.

---

18. An intuigse is tábhachtaí

Is í an eochair phoiblí an cur síos iomlán ar lúbra. Is ceadmhach do chách féachaint uirthi.

Is é an síniú an cruthúnas: "D'aimsigh mé cosán an-ghearr don léirmheas seo go beacht."

Is é an eochair phríobháideach eolas na n-aicearraí.

Ní gá don léitheoir na haicearraí a bheith ar eolas aige. Ní dhéanann sé ach a thomhas an bhfuil an cosán a cuireadh faoina bhráid gearr i ndáiríre agus an mbaineann sé leis an léirmheas seo i ndáiríre. Is féidir leis an dá rud a dhéanamh gan sinne.

An té a athraíonn an téacs, bogann sé an pointe — agus ní thugann an seanchosán áit ar bith é.