openfheorg / openfhe-development

This is the development repository for the OpenFHE library. The current (stable) version is v1.2.3 (released on October 30, 2024).
BSD 2-Clause "Simplified" License
765 stars 189 forks source link

Unsigned remainder in ApproxSwitchCRTBasis at NATIVEINT=64-bit and HAVE_INT128=yes #237

Open caesaretos opened 1 year ago

caesaretos commented 1 year ago

In ApproxSwitchCRTBasis, SwitchModulus is not called explicitly nor seems to be called implicitly in the above build settings. The specific code referenced here can be found here.

The following trace shows the output of ApproxSwitchCRTBasis with and without calling SwitchModulus.

Ql parameters: `Input:paramsQl:ILDCRTParams [m=32 n=16 q=1852673427799064227109187249159859999929012667700461710314088099977918534255329 ru=0 bigq=0 bigru=0] Parms: 0:ILParams [m=32 n=16 q=1152921504606845473 ru=3291845140097365 bigq=0 bigru=0]

1:ILParams [m=32* n=16 q=1125899906843009 ru=23304908302335 bigq=0 bigru=0]

2:ILParams [m=32* n=16 q=1125899906843617 ru=112077617521556 bigq=0 bigru=0]

3:ILParams [m=32* n=16 q=1125899906842273 ru=150844171873508 bigq=0 bigru=0]

4:ILParams [m=32* n=16 q=1125899906842817 ru=12581553119851 bigq=0 bigru=0] `

P parameters `Input:paramsP:ILDCRTParams [m=32 n=16 q=1329227995784910082932010924701133921 ru=0 bigq=0 bigru=0] Parms: 0:ILParams [m=32 n=16 q=1152921504606844513 ru=7645792537133126 bigq=0 bigru=0]

1:ILParams [m=32* n=16 q=1152921504606844417 ru=97466480447807994 bigq=0 bigru=0] ` alpha = 2, thus QTilde_0 is defined over the first two moduli of Ql (q0, q1). Note that we only show the trace related to QTilde0.

Input polys in coefficient representation: `0: COEF: [971748549302351832 1037296440753227540 932275078846317741 595657151977581261 22688292097599972 0 287817675110054269 360631025769889649 534997210666582342 840900573797250872 107336109388953099 964572498420429635 621330777861098263 69818184114991109 508859731272508694 287611322158910584] modulus: 1152921504606845473

1: COEF: [20458284542960 890010693855842 129992177792711 417000667950608 460965717549973 0 746200474519014 793743828172645 160395090966537 519939516460895 652136753585251 1069252429186558 348385112335616 89434257267949 1105293704259123 889886266769526] modulus: 1125899906843009 `

Output polys mod (Ql[2,3,4] U P) WITHOUT SwitchModulus `0: COEF: [530480203260542 359355763345947 353672876619231 340505747663783 660179653364109 0 848932232582114 982637967017453 179929547606751 477787096531809 823115858181869 622147640504996 131761702116470 345107252714542 973836253378243 31419229707848] modulus: 1125899906843617

1: COEF: [114159934535870 880547338763284 688832765082953 331827140280212 397586677931502 0 621842068615322 742856833585262 492296489145933 748741264597494 859968678495486 543843285328682 136551174391146 609546589263930 612590537565722 329121093747731] modulus: 1125899906842273

2: COEF: [926041047375866 642780966340371 177872180515917 737446567332873 101766760131294 0 713759036072814 437803701092238 687547484094288 236961585285844 657401459613162 736380414511002 831597864624721 127211314831553 732001497160342 449886584325582] modulus: 1125899906842817

3: COEF: [721326003728730646 518900789848802514 229047466719992875 539472572964409388 1092593815395122532 0 298751060331798876 1066906079441403569 484366174682733669 98358307902519606 450063805078726826 623198900923833442 366927037352391030 884578474988270789 335276908368534901 108810990861042711] modulus: 1152921504606844513

4: COEF: [926868050092737622 697645525679729106 389309006428729483 649146265523776748 46662863118030371 0 415136549314657884 1137533584808554961 594595221545033349 254688382234415574 599628725108388746 704353691634858370 456778813762204854 966054504075598757 433210776538822069 206223108191940471] modulus: 1152921504606844417 `

Output polys mod (Ql[2,3,4] U P) WITH SwitchModulus `0: COEF: [530478964965182 359354525050587 353671638323871 340505128516103 660179034216429 0 848931613434434 982637347869773 179928928459071 477785858236449 823114619886509 622147640504996 131761082968790 345107252714542 973835634230563 31418610560168] modulus: 1125899906843617

1: COEF: [114159407676158 880546811903572 688832238223241 331826876850356 397586414501646 0 621841805185466 742856570155406 492296225716077 748740737737782 859968151635774 543843285328682 136550910961290 609546589263930 612590274135866 329120830317875] modulus: 1125899906842273

2: COEF: [926041123843706 642781042808211 177872256983757 737446605566793 101766798365214 0 713759074306734 437803739326158 687547522328208 236961661753684 657401536081002 736380414511002 831597902858641 127211314831553 732001535394262 449886622559502] modulus: 1125899906842817

3: COEF: [865441191803842392 663015977923914260 373162654795104621 611530167001965261 11729904825833892 0 370808654369354749 1138963673478959442 556423768720289542 242473495977631352 594178993153838572 623198900923833442 438984631389946903 884578474988270789 407334502406090774 180868584898598584] modulus: 1152921504606844513

4: COEF: [854810456053991448 625587931640982932 317251412389983309 613117468504403661 10634066098657284 0 379107752295284797 1101504787789181874 558566424525660262 182630788195669400 527571131069642572 704353691634858370 420750016742831767 966054504075598757 397181979519448982 170194311172567384] modulus: 1152921504606844417 `

The discrepancy between the two cases (if it exists) is related to how the extra multiples of QTilde0 are added, in the case where no SwitchModulus is called we get (x + 1QTilde0), whereas in the other case (where SwitchModulus is called), we get (x - 1QTilde0).

Does removing the call to SwitchModulus affect the approximation noise? If not, SwitchModulus might not be needed in this procedure.

yspolyakov commented 1 year ago

The difference can be summarized as follows:

  1. In the case of NATIVE_SIZE=64 and HAVE_INT128=yes, we use unsigned remainder in the fast basis extension. If we go from $Q$ with $k$ moduli to $P$ with $k'$ moduli, a number $[x]_Q$ gets represented as $[x]_Q + \alpha Q \bmod P$, where $\alpha < k$.
  2. In the case of NATIVE_SIZE=64 and HAVE_INT128=no, we use the signed remainder in the fast basis extension (negative values are changed from $q_i - x$ to $p_j - x$ by adding $p_j - q_i$). The main benefit of this approach is that a number $[x]_Q$ gets represented as $[x]_Q + \beta Q \bmod P$, where $\beta < k/2$.

In the second case, the noise can be one bit smaller.

yspolyakov commented 1 year ago

Also adding @pascoec We should change the implementation for HAVE_INT128=yes to use the signed remainder. There are two options:

  1. Use the HAVE_INT128=no implementation (depending on the benchmarking)
  2. Do the summation over signed integers instead of unsigned integers in the current implementation for HAVE_INT128=yes.
yspolyakov commented 1 year ago

ApproxScaleAndRound appears to have the same issue.