-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLWE.html
More file actions
975 lines (831 loc) · 35.6 KB
/
Copy pathLWE.html
File metadata and controls
975 lines (831 loc) · 35.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
<html>
<head>
<title>Implications of the Proposed Quantum Attack on LWE</title>
<script>
MathJax = {
tex: {
inlineMath: [['$', '$'], ['\\(', '\\)']]
},
svg: {
fontCache: 'global'
}
};
</script>
<script type="text/javascript" id="MathJax-script" async
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js">
</script>
</head>
<body background="back4.jpg"
TEXT="#ffffff"
LINK="#ffff00"
VLINK="#00ff00"
>
<h1>Implications of the Proposed Quantum Attack on LWE</h1>
On April 10th 2024 Yilei Chen published a paper on ePrint
entitled <a href="https://eprint.iacr.org/2024/555"><em>Quantum Algorithms for Lattice Problems</em></a>.
In it he proposes a "polynomial time" quantum algorithm
for certain parameters sets for the Learning-With-Errors (LWE)
problem.
This is important as LWE forms the basis of the majority of the
post-quantum algorithms selected by NIST, and it also forms
the basis of a number of cryptographic constructions which
offer advanced functionalities such as Fully Homomorphic Encryption
(FHE).
In this note I try to work out what the implications of this
work are.
<p>
Updates to this post are at the bottom
<ul>
<li><a href="#April16">Update on April 16th </a>
<li><a href="#April17">Update on April 17th </a>
<li><a href="#April18">Update on April 18th </a>
<li><a href="#April19">Update on April 19th </a>
</ul>
<h4>Caveats</h4>
The following should be read with a number of caveats in the
back of ones mind.
The most notable of these are:
<ol>
<li>I am not an expert in quantum algorithms.
<li>The paper of Chen has not yet been peer reviewed, so
it may contain some errors.
<li>Quantum computers may never be built. Indeed it is
a running joke that quantum computers are always
ten years in the future!
</ol>
<h2>The LWE Problem</h2>
So we are all on the same page let us define the LWE problem
itself.
This is a noisy version of linear algebra. It is (in its most
basic form) parametrized by four values $n, m, q \in \mathbb{N}$,
$\alpha \in [0,1]$.
<p>
The value $q$ is used to define the modulus in modular
reduction.
In what follows we assume that we represent $\mathbb{Z}_q$
as the integer values in the range $(-q/2,\ldots,q/2]$, i.e.
we take a centered reduction in all modular operations.
<p>
The value $\alpha$ is used to define a distribution $D$.
Usually this is chosen to be a Gaussian like distribution on
$\mathbb{Z}$ with standard deviation $\alpha \cdot q/\sqrt{2 \pi}$,
although other distributions (such as a uniform distribution
with roughly the same standard deviation) could also be used.
In any case the distribution $D$ produces an integer value
in the range $[-c \cdot \alpha \cdot q, \ldots, c \cdot \alpha \cdot q]$
with overwhelming probability for some small constant $c$.
One can think of this $c$ as say $10$ in what follows.
<p>
The LWE problem is defined by a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$
and a secret vector $\mathbf{e} \in D^m$, i.e. we select $\mathbf{e}$
from the product of $m$ copies of the distribution $D$.
Thus $\mathbf{e}$ contains $m$ "small" values.
<p>
Then a public matrix $A$ of dimension $m \times n$ is selected
with entries selected in $\mathbb{Z}_q$, and the value
$$\mathbf{y} = A \cdot \mathbf{s} + \mathbf{e} \pmod{q} $$
is computed.
<p>
The (computational) LWE problem is to recover $\mathbf{s}$
from the pair $(A, \mathbf{y})$.
There is also a decisional variant, which is more used in
cryptographic definitions, but it is essentially as hard
as the computational version and so we will not consider
it further here.
<p>
A key point to note, from a complexity point of view, is the
following.
In complexity theory usually looks at complexity as
a function of the size of the input to the problem.
The size of the input problem in LWE is
$$ n \cdot (m+1) \cdot \log_2 q \approx n \cdot m \cdot \log_2 q. $$
Thus the size does not depend on $\alpha$.
When talking about a polynomial time algorithm to solve
LWE (in the normal complexity theoretic sense) we should
only consider algorithms whose complexity is a polynomial
function of $ n \cdot m \cdot \log_2 q$.
<p>
The value $n$ is called the LWE dimension and the value
$m$ denotes the number of "LWE samples".
Just as in normal linear algebra one requires at least
as many equations as variables in order to fix the
solution, one requires $m \ge n$ here in order to fix
$\mathbf{s}$.
This means we require the number of samples
to be $m \ge \Omega(n \cdot \log q)$.
<em>See <a href="#April16Vadim">update from April 16th</a> below for a note on this</em>
<p>
But $\alpha$ is crucial to the hardness of LWE:
<ul>
<li>
If $\alpha=0$ then one can interpret this as there being
no error vector $\mathbf{e}$.
Thus in such a situation the LWE problem is just normal
linear algebra and naive algorithms can solve it in (essentially)
quadratic time complexity.
<li>
If $\alpha \approx 1$ then the equations are basically
random, and no algorithm will be able to recover $\mathbf{s}$,
as the equations contain essentially no information about $\mathbf{s}$
to aid in the recovery.
</ul>
The value of $\alpha$ is important in applications:
<ol>
<li>
For applications such as traditional Public Key Encryption
(as in <a href="https://en.wikipedia.org/wiki/Kyber">Kyber</a>)
the standard deviation of the distribution $D$ is chosen
to be the fixed value of $\sqrt{(3+1)/2}=2$ (since the distribution
is the NewHope distribution with parameter $B=3$).
Thus we have $\alpha \cdot q = 2 \cdot \sqrt{2 \cdot \pi} = \sqrt{8 \cdot \pi}$,
i.e. $\alpha \cdot q$ is constant.
However, we have $q$ as the fixed value of $q=3329$,
and so $\alpha = 0.0015 \approx q^{-0.801}$.
So $\alpha \cdot q \approx q^{0.1987}$.
In Kyber we have $n \approx q$.
<li>
For Public Key Signatures (as in
<a href="https://pq-crystals.org/dilithium/index.shtml">Dilithium</a>)
the distribution $D$ (in the Dilithium secret key)
is a uniform distribution in the range $[-\eta,\ldots,\eta]$,
where $\eta$ is $2$ or $4$.
However the modulus $q$ in Dilithium is much larger than
in Kyber, being $q=8380417$.
Thus we have a standard deviation of $D$ of at most
$\sqrt{(2 \cdot \eta)^2/12} = 4/\sqrt{3}$,
and so $\alpha \cdot q = \sqrt{64 \cdot \pi/3} \approx q^{0.1318}$.
In Dilthium we have $n = 5 \cdot 256$ for the Level 3 parameters.
<li>
For applications such as levelled FHE (as typified by the
BGV and BFV FHE schemes) the depth of the supported
homomorphic operations is governed by the gap between
the values $q$ and $\alpha \cdot q$, i.e. a very very small
value of $\alpha$ is desired.
For such schemes one can think of $\alpha \cdot q$
as being a small constant.
Indeed one can think of $\alpha \cdot q$ as being the
same value as in Kyber, i.e. $\sqrt{8 \cdot \pi}$.
But then one then picks $n, m$ and $q$ to obtain both security
and homomorphic depth.
This results in very large values of $q$ indeed, for
example one could have $q \approx 2^{1024}$, in which case
$\alpha \cdot q \approx q^{0.00227}$.
For BGV typical values of $n$, with $q \approx 2^{1024}$,
are of the order of $2^{15}$ or $2^{16}$.
(See <a href="https://eprint.iacr.org/2014/873">
Bootstrapping for HElib</a> for a discussion
of parameters for BGV which support bootstrapping).
<li>
For applications such as FHE schemes which support
efficient bootstrapping (as typified by TFHE and FHEW), one does
not need a huge gap between $q$ and $\alpha \cdot q$.
Indeed for these one can think of $\alpha$ (for the purposes
of this post we think of TFHE with $q=2^{64}$)
as being of the order of $1/\sqrt{q}$, and so $\alpha \cdot q \approx \sqrt{q}$.
For such TFHE parameters the dimension $n$ is under $2^{11}$.
</ol>
<p>
This importance of the value of $\alpha \cdot q$ has been known for a
long time <a href="https://en.wikipedia.org/wiki/Learning_with_errors#Regev's_result">
Regev's original hardness result</a> for LWE only holds when
$\alpha \cdot q > 2 \sqrt{n}$.
Interestingly this inequality is only satisfied for the TFHE
style parameters above, it does not hold for the parameter sets
for Kyber, Dilithium or BGV.
<p>
The classical manner to determine parameters for the LWE
problem is to use the <a href="https://lattice-estimator.readthedocs.io/en/latest/">
lattice-estimator</a>.
This runs all known lattice algorithms against a given
parameter set, and tries to determine the number of classical
operations needed to solve the LWE problem.
If it comes up with a value of more than $2^{128}$ then usually
one considers the parameters to be secure.
<p>
Intuition though can be a bit strange.
For example if one keeps $m, n$ and $\alpha \cdot q$ constant,
but one just increases $q$, then the LWE problem becomes easier!
This is unlike (say) RSA or DLP were to make things more secure
we just increase the modulus.
<p>
When looking at quantum complexity intuition can also be
a bit strange.
For example Grover's algorithm should imply that AES-128 is
not considered secure in a post-quantum world, as the
attack via Grover's algorithm on AES-128 would require
$2^{64}$ quantum "operations".
However, most people think AES-128 will still remain secure
in a post-quantum world as the overall complexity of Grover's
algorithm when applies to AES-128 would be way beyond any
feasible quantum computer.
<h4>LWE Problem Summary</h4>
The key take away points:
<ol>
<li>Polynomial time should be measured in terms of the input
problem size.
<li>The $\alpha$ value is important, both for security and
applications.
<li>The $\alpha$ value is significantly different in different
practical applications of LWE.
<li>A "low" complexity quantum attack may not actually translate
into a practical quantum attack (as in AES-128), even
when/if a quantum computer is built.
</ol>
<h2>The Proposed Algorithm</h2>
The algorithm of Chen uses a quantum subroutine, which is
called $O(n)$ times, in order to generate a system of linear
equations which can then be solved by classical means.
The quantum subroutine is called as many times as is needed
in order to obtain a full rank linear system.
<p>
The algorithm is only given for when $D$ is a Gaussian-like
distribution, but let us assume that this restriction
can be removed (so we can apply it to the distributions
used in practical schemes based on LWE).
<p>
As said earlier I am not an expert on quantum algorithms,
so I will not discuss the quantum subroutine, but we can
discuss the theorem statement given by Chen.
This is
<p>
<b>Theorem:</b>
Let $n,m,q \in \mathbf{N}$, $\alpha \in (0,1)$ be
such that
<ul>
<li>$m \ge \Omega(n \cdot \log q)$,
<li>$q \in \tilde{\Omega}((\alpha \cdot q)^4 \cdot m^2)$.
</ul>
There is then a quantum algorithm that solves LWE in time
$\mathsf{poly}(m, \log q, \alpha \cdot q)$.
<p>
Now let us consider this statement in more detail.
<p>
<h3>The Conditions</h3>
The first thing one needs to consider are the conditions.
<p>
We have already discussed that we need more samples $m$
than variables $n$ in our secret, so the first condition
should not be a surprise.
<p>
We now need to look at the second condition, i.e.
$q \in \tilde{\Omega}((\alpha \cdot q)^4 \cdot m^2)$.
The key point is the dependence of $q$ on $\alpha \cdot q$.
Let us map these to our four cases considered above.
<ol>
<li><b>Kyber:</b>
Here, recall, $\alpha \cdot q \approx q^{0.1987}$ so
the condition is that
$$ q \in \tilde{\Omega}(q^{0.7948} \cdot m^2). $$
However, we also have for Kyber that $m > n \approx q$.
Thus, we do not have
$$ q \in \tilde{\Omega}(n^{2.7948}).$$
Of course the proposed attack (if correct) could be
improved possibly, but it would seem highly unlikely that
it could be applied to Kyber as is.<p>
<li><b>Dilithium:</b>
Here, recall, $\alpha \cdot q \approx q^{0.1318}$.
But now we have the dimension $n = 5 \cdot 256$ (for
the Level 3 parameters) with $q=8380417$,
thus $q \approx n^{2.22}$.
This means $\alpha \cdot q \approx n^{0.2925}$,
and the second condition becomes
$$ q \in \tilde{\Omega}(n^{3.170}).$$
Thus less of an improvement is needed in the attack for
it to apply to Dilithium. <p>
<li><b>BGV:</b>
Recall, we have $\alpha \cdot q \approx q^{0.00227}$
and $n$ could be around $2^{15}$ or $2^{16}$,
with $q \approx 2^{1024}$.
Thus we have $\alpha \cdot q \approx n^{.1550}$.
Our second condition then becomes
$$ q \in \tilde{\Omega}(n^{2.620}).$$
But for BGV we have $q \approx n^{68.266}$.
So it would appear that the attack should apply to BGV. <p>
<li><b>TFHE:</b>
In this case, recall, we have $\alpha \cdot q \approx \sqrt{q}$.
We also have that $q =2^{64}$ and $n \le 2048$
and so $q \approx n^{5.818}$, and so we have
that $\alpha \cdot q$ can approximated by $n^{2.909}$.
The second condition of the theorem then becomes
$$ q \in \tilde{\Omega}( n^{13.636} ).$$
Yet we have $q \approx n^{5.818}$!
Thus the attack would need to improve quite a bit to apply
to TFHE. <p>
</ol>
<h3>The Complexity</h3>
Having discussed the conditions under which the theorem applies
we can now turn to the conclusion.
Here we need to consider the algorithm complexity, i.e.
$$\mathsf{poly}(m, \log q, \alpha \cdot q).$$
Alas, the theorem does not give any implied constants
or the polynomial degrees.
<p>
Schor's algorithm is devasting against RSA and ECDLP because
the quantum complexity is really not that large. So if a
quantum computer was ever built then it is plausible that
RSA and ECDLP would be broken.
On the other hand the quantum complexity of Grover's algorithm
against AES-128 is really high, and so it would take a huge
quantum computer in order to dent the security of AES-128.
From these two examples we can conclude that constants
matter.
<p>
We note, however, that the complexity depends on $\alpha \cdot q$,
i.e. it depends on a parameter which is not specified
by the input problem size.
Thus we have to look at each scheme in turn, where different
values of $\alpha \cdot q$ are given.
<p>
The following is a very crude examination, but it shows
why the constants matter here.
And we can have a view as to whether the complexity is
going to be feasible or infeasible to launch an attack
on an early stage quantum computer.
<p>
What I do is replace the terms $m$, $\log q$ and
$\alpha \cdot q$ in the complexity estimate by the
powers of two of these values for the four schemes
being discussed (I approximate $m$ with $n \cdot \log q$).
One then make ones own guess as to the implied constants,
and decide on which scheme one needs to worry about.
<ol>
<li><b>Kyber:</b>
$\mathsf{poly}(2^{13.87}, 2^{3.55}, 2^{2.32}).$
<li><b>Dilithium:</b>
$\mathsf{poly}(2^{14.84}, 2^{4.52}, 2^{3.03}).$
<li><b>BGV:</b>
$\mathsf{poly}(2^{25.00}, 2^{10.00}, 2^{2.32}).$
<li><b>TFHE:</b>
$\mathsf{poly}(2^{17.00}, 2^{6.00}, 2^{32.00}).$
</ol>
For Kyber and Dilithium we see that, assuming the implied
constants and degree are relatively small, the attack may be
feasible, if the conditions of the theorem can be improved.
<p>
For BGV we already noted that the conditions of the theorem are
satisfied, thus whether the attack is practical (on a future
quantum computer) depends on the dependence of the attack
on the value of $m$.
<ol>I suspect the dependence on $m$ is quite mild, as it
probably related to the repetition of the quantum
sub-routine and not the complexity of the sub-routine
itself. But that is a pure guess on my part at this point.
</ol>
<p>
For TFHE we see that, assuming the conditions of the theorem
can be improved in order to bring TFHE into scope, the complexity
would also need to not depend on too high a polynomial
in $\alpha \cdot q$, as this is already $2^{32}$ for
standard TFHE parameters.
<h2>Conclusion</h2>
One should not necessarily throw the baby out with the bathwater
over this new paper.
There are extra caveats as well as my earlier ones of it not
yet being peer reviewed, or a quantum computer not yet being built.
<ol>
<li>The theorem pre-conditions do not apply to Kyber, Dilithium or
TFHE as currently proposed; they do however apply to BGV.
<li>Even if the pre-conditions were improved, the importance of
the complexity estimate on the noise term $\alpha \cdot q$
needs to be considered as to whether any attack is feasible.
<li>Even a low quantum complexity value of the form of $2^x$
quantum operations, for $30 \le x \le 100$, may not result
in a viable quantum algorithm (as per Grover applied to
AES-128).
<li>The attack only defeats quantum adversaries, if no large
scale quantum computer is ever built then we can still
happily use (any form of) FHE.
<li> Companies are happily deploying SNARKs based on
pairing based crypto, even though pairing based crypto
will fall long before LWE to any quantum computer; simply
due to the complexity of the different quantum algorithms.
</ol>
<hr>
Nigel Smart<br>
April 15th 2024.
<hr>
<a name="April16"></a>
<h1>Update April 16th</h1>
I give two updates
<ol>
<li><a href="#April16Paper">One from reading the paper</a>
<li><a href="#April16Vadim">One from discussion with Vadim Lyubashevksy</a>
</ol>
<a name="April16Paper"></a>
<h2>Update From Reading the Paper</h2>
Today I had a more detailed look at Section 3 of the paper where
the parameters of the attack are given in more detail.
<p>
<h4>Section 3.1</h4>
This section maps the input LWE problem (now the LWE dimension
is referred to as $\ell$ instead of $n$ and the author
sets $\beta=\alpha \cdot q$ to make things easier to parse)
with uniform secret into a problem with a secret chosen
from the error distribution, but with $\kappa$ values
chosen to be of the attackers choice.
<p>
Basically there is a map between the input problem
$$ \mathsf{LWE}_{\ell-(\kappa-1),m+\ell-(\kappa-1),q,U(\mathbb{Z}_q),\chi} $$
for error distribution $\chi$ with parameter $\beta$, to
the problem
$$ \mathsf{LWE}^{\kappa-1 \mathsf{\ chosen\ secret}}_{\ell,m,q,\chi,\chi}. $$
<h4>Section 3.2</h4>
Then odd coprime values $p_1,\ldots,p_\kappa$ are picked so that
$$ p_2,\ldots,p_\kappa \le \frac{\log n}{p_1}, $$
where $n = 1+\ell+m$.
It would appear for the small values of $\ell$ one would
expect $\kappa$ therefore to be equal to one or two,
unless $m$ (and hence $n$) is selected to be huge.
So the selection of $\kappa$ is going to also affect
how many LWE samples, i.e. $m$, we need to start with
(see below for a comment on what increasing $m$ means
for concrete LWE problem instances).
<p>
The $\kappa-1$ chosen parts of the secret key are selected
to be $p_2,\ldots,p_\kappa$.
The key aspect now is we are solving a equation
$$ A \cdot \mathbf{b} =0 \pmod{q} $$
where the vector $\mathbf{b}$ is of the special form
$$ \mathbf{b} = [-1,2 p_1 p_2, \ldots, 2 p_2 p_\kappa,
2 p_1 \mathbf{s}_{[\kappa,\ldots,\ell]},
2 p_1 \mathbf{e}]. $$
The algorithm works by guessing the value of $b_2 = \Vert \mathbf{b} \Vert^2$.
Lemma 3.6 tells us that there are at least $\beta^2$ such choices
for $\Vert \mathbf{b} \Vert^2$.
Indeed we have, with high probability
$$ b_2 \in 1+4 p_1^2 (p_2^2+\ldots+p_\kappa^2) + [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa). $$
<p>
<b>First Main Point:</b>
This means the complexity seems at this point to be at least $\beta^2$,
as we need to guess $b_2$ from a range of size roughly $p_1^2 \beta^2 (n-\kappa)$.
<h4>Section 3.3</h4>
Section 3.3 then defines a bunch of constants and constraints which enable
the main quantum subroutine to work, and be successfull in solving the
underlying LWE problem.
<p>
Constraint <b>C.3</b> seems to be an issue.
For the guessed value of $b_2$ we need to find a value $c \in 4 \mathbb{Z}$
such that
$$ (c+1) b_2 = p_1 p_2 \cdots p_\kappa, $$
and we need to select the $p_i$ so that
$$ p_2 \cdots p_\kappa = -1 \pmod{p_1}.$$
<p>
The only way I can get things to work out in order would be as
follows (which is almost what the author suggests):
<ol>
<li>Pick a value for $c \in 4 \mathbb{Z}$.
<li>Set $p_1 = c+1$.
<li>Use the bound from Lemma 3.6
$\sqrt{b_2} \le 3 p_1 \beta \sqrt{n}$
to guess a value for $b_2$, i.e.
$0 \le b_2 \le 9 p_1^2 \beta^2 n$.
We have the constraint $b_2 = 1 \pmod{4 p_1^2}$, so we only need
to consider roughly $2 \beta^2 n$ values for $b_2$.
<li>Now factor $b_2$ into coprimes $p_2,\ldots,p_\kappa$ for some $\kappa$ value.
<li>Set $A = b_2 - 1 - 4 p_1^2 (p_2^2+\ldots+p_\kappa^2)$.
<li>Reject if $A \not\in [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa)$.
<em>Maybe we dont even bother rejecting such values?</em>
</ol>
I cannot get the $p_2 \cdots p_\kappa = -1 \pmod{p_1}$ condition to hold though using
this method.
<em>Note, the authors example in the paper has $p_2 \cdots p_\kappa=1 \pmod{p_1}$ and not $-1 \pmod{p_1}$. So perhaps this is a typo!</em>
<p>
Suppose our guess for $b_2$ is a prime, and that this is the correct value.
Then we would have to have $\kappa=2$ and $p_2 = b_2$.
There seems no reason why we should have $p_2 = -1 \pmod{p_1}$ at this point.
We would also have
$$ p_2 = 1+p_1^2 p_2^2 + [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa). $$
Which obviously cannot hold.
Thus for this factorization into $p_2 \cdots p_\kappa$ to make sense we
really need a special value of $b_2$.
So something seems very weird!
<a name="April16Vadim"></a>
<h2>Update in Relation to $m \ge \Omega(n \cdot \log q)$</h2>
As Vadim Lyubashevksy has pointed out to me that the problem
considered in the paper is really for generic LWE, i.e.
for a potentially unlimited or large number of samples.
In real world cryptosystems one has a fixed number of
basic samples, in particular normally we are only given
$m=n$ such samples.
<p>
If the attack requires more samples then we need to generate
these from the samples we have been given.
This is done by combining small linear combinations of
the existing samples.
But we cannot use too small values in the linear combinations,
otherwise you introduce <em>known</em> small vectors into the resulting
lattice, which the algorithm then solves for; i.e. it
ends up solving for vectors which you already know.
Thus we need to pick combinations for which the multipliers
are small, but not too small.
But this itself blows up the noise (i.e. the $\alpha$
value).
Which makes the attack less practical.
<p>
For example suppose our input LWE samples are
$$\mathbf{y} = A \cdot \mathbf{s} + \mathbf{e} \pmod{q} $$
for an $n \times n$ square matrix $A$.
Then to generate new samples one would multiply the
equation on the right by a matrix $R$ which contains
small values, is not too sparse, but the small values
are not too small.
i.e. we would form the system
$$\mathbf{z} = R \cdot \mathbf{y} = (R \cdot A) \cdot \mathbf{s}
+ R \cdot \mathbf{e} \pmod{q}. $$
But now the noise values have gone up from $\Vert\mathbf{e}\Vert_\infty$
to $\Vert R \cdot \mathbf{e}\Vert_\infty$.
This increases the value of $\alpha$, and hence the $\beta$ value
above, and hence the attack complexity.
<hr>
Nigel Smart<br>
April 16th 2024.
<hr>
<a name="April17"></a>
<h1>Update April 17th</h1>
So yesterday I had two problems with the Condition C.3.
These have been somewhat solved via communication with Yilei.
<ul>
<li>
The first was the issue of having $p_2 \cdots p_\kappa = -1 \pmod{p_1}$.
It turns out this was only done to avoid having to carry around another
variable of $c' = p_2 \cdots p_\kappa \pmod{p_1}$.
So we can ignore this.
<li>
The second problem was the bound of $p_i \le (\log n)/p_1$ for $i>2$.
If you impose this condition then there is simply not enough odd coprime
$p_i$'s to make the algorithm work unless $n$ is super big, think $2^{10^x}$
for some largish $x$. Thus if you keep this condition then the algorithm is
certainly not practically feasible in any sense of the word.
Yilei pointed out to me that this condition is also not needed (except
to get a nice approximation factor) and one can replace it with $p_i = O(\log n)$
and perhaps even $p_i \le 10 \log n$.
In another direction one could take $\kappa = O(1)$ and perhaps $\kappa = 10$.
</ul>
<p>
<h2>Revisiting Condition C.3</h2>
With these points in mind let us revisit C.3 and come up with an algorithm taking
into account the two fixes of either assuming $p_i \le 10 \log n$, or
assuming $\kappa$ is fixed.
<h4>Option A: Setting $p_i \le 10 \log n$</h4>
<ol>
<li>Pick a value for $\kappa$ (to be determined).
<li>Pick a value for $c \in 4 \mathbb{Z}$, say $c=4$.
<li>Set $p_1 = c+1$, i.e. $p_1=5$.
<li>Pick odd coprime values $p_2,\ldots,p_\kappa$ (coprime also to $p_1$)
subject to $p_i \approx 10 \log n$.
</ol>
The question is, how big should we pick $\kappa$?
<p>
Again, we know $b_2 = p_2 \cdots p_\kappa$ and we also know that (assuming $\kappa>4$)
that the size of $b_2$ will dominated by the term $p_1^2 \beta^2 (n-\kappa)$.
Since $\kappa$ is tiny compared to $n$ we basically get something like
$$ p_i^{\kappa-1} \approx p_1^2 n \beta^2. $$
Recall, we have $\beta = \sqrt{8 \pi}$ for Kyber and BGV,
$\beta = \sqrt{64 \pi/3}$ for Dilithium, and
$\beta =2^{32}$ for TFHE.
This is assuming $\beta$ has not needed to be increased due to the need to generate
more samples as explained <a href="#April16Vadim">above</a>, so these assumptions
on $\beta$ are the best possible scenario.
<p>
When $\beta = \sqrt{8 \pi}$ we see we need
$$ (\kappa-1) \log ( 10 \log n) \approx 2 \log (p_1 \beta) + \log n
\approx 6.443 + \log n. $$
i.e.
$$ \kappa \approx \frac{6.443+\log n}{\log (10 \log n)}+1. $$
Note, to get $\kappa>4$ this means we need an $n$ bigger than $2^{29}$ here.
This is a lot of LWE samples by any stretch of the imagination.
<p>
When $\beta=2^{32}$ we obtain
$$ (\kappa-1) \log ( 10 \log n) \approx 2 \log (p_1 \beta) + \log n
\approx 47.58 + \log n. $$
i.e.
$$ \kappa \approx \frac{47.58 + \log n}{\log (10 \log n) }+1. $$
Note, we always obtain $\kappa>4$ here, irrespective of the value of $n$.
<h4>Option B: Setting $\kappa=10$</h4>
<ol>
<li>Pick $\kappa=10$. In any case pick $\kappa > 4$.
<li>Pick a value for $c \in 4 \mathbb{Z}$, say $c=4$.
<li>Set $p_1 = c+1$, i.e. $p_1=5$.
<li>Pick odd coprime values $p_2,\ldots,p_\kappa$ (coprime also to $p_1$).
</ol>
Now the question is, how big should we pick the coprime values $p_2,\ldots,p_\kappa$?
<p>
Again, we know $b_2 = p_2 \cdots p_\kappa$ and we also know that (assuming $\kappa>4$)
that the size of $b_2$ will dominated by the term $p_1^2 \beta^2 (n-\kappa)$.
Since $\kappa$ is tiny compared to $n$ we basically get something like
$$ p_i^{\kappa-1} \approx p_1^2 n \beta^2. $$
So
$$ \log p_i \approx \frac{2 \log (p_1 \beta) + \log n}{\kappa-1}. $$
<p>
Using $\beta = \sqrt{8 \pi}$ we see we need
$$ \log p_i \approx 0.715 + \frac{\log n}{9}.$$
i.e.
$$ p_i \approx 2 n^{1/9}.$$
However to obtain $\kappa=10$ such coprime values we would need $2 n^{1/9} \ge 31$,
i.e. $n>2^{35}$.
Which again is a large number of samples.
<p>
Using $\beta = 2^{32}$ we see we need
$$ \log p_i \approx 5.286 + \frac{\log n}{9}.$$
i.e.
$$ p_i \approx 198 n^{1/9}.$$
Any value of $n$ would result in such coprime values existing.
<h4>Summary of C.3</h4>
By weakening the approximation factors we can select kind of practical values
for the coprimes $p_1,\ldots,p_\kappa$ and the value $\kappa$.
We see that for Kyber, Dilthium and BGV the number of samples $m$ required
is going to be very large to enable a choice of such coprimes,
however for TFHE the $\beta$ value is so large that the existing of
such coprimes is immediate, since this forces $b_2$ to be very large indeed.
<p>
<b>Second Main Point:</b>
For small values of $\beta$ the number of samples required to enable
the attack to work is going to be very large indeed.
<h2>Continueing with Section 3.3</h2>
Having picked our values for $p_1,\ldots,p_\kappa$ we have fixed our
guess for $b_2$.
But this guess may be wrong. Indeed it's probability of being correct
is around
$$ \frac{1}{\beta^2 p_1^2 (n-k)}. $$
So we need to keep performing the attack, tweaking the parameters
via randomizing the input samples (as described <a href="#April16Vadim">above</a>.
Until the attack works.
<p>
So we reiterate our first main point from above
<p>
<b>First Main Point (Recap):</b>
The complexity is at least $\beta^2$.
<p>
So if $\beta^2$ is large, as it is in TFHE this is already a no-go.
<p>
Let us continueing assuming $b_2$ is correct.
<p>
So having picked our coprime values we need to pick a value for $D$,
which the paper says should be odd and $O((\log n)^2)$.
For the moment let us assume this is picked.
<p>
We then set
$$ M = 2 (c+1) D^2 b_2$$
$$ P = M^2/2$$
$$ u^2 = D^2 b_2$$
<p>
Now we need to fix $t^2$ which is defined as
$$ t^2 = \frac{M}{2}-u^2.$$
This ensures that Condition C.2 is satisfied.
<p>Note
$$ \frac{t^2}{u^2} = \frac{M}{2 u^2}-1
= \frac{2 (c+1) D^2 b_2}{2 u^2}-1
= \frac{2 (c+1) D^2 b_2}{2 D^2 b_2}-1
= (c+1)-1 = c.
$$
So Condition C.1 is satisfied already. The only thing in Condition C.1 we have
not satisfied is having $\sqrt{c} \in (64 (\log n)^3, 65 (\log n)^3)$.
<p>
We then need to pick a value for $r$ from Condition C.4.
The relevant inequalies are
$$ M \le r \le \frac{P}{2 \log n} = \frac{M^2}{4 \log n} $$
and
$$ r \le \frac{D q}{2 (\log n)^3}. $$
Note the second inequality imples the following
$$ \frac{D q}{2 (\log n)^3} \ge M = 2 (c+1) D^2 b_2 $$
i.e.
$$ q \ge 4 (c+1) D b_2 (\log n)^3 \approx 4 (c+1) D (\log n)^3 p_1^2 n \beta^2. $$
Plugging in our values above we see that we have
$$ q \ge c' n \beta^2, $$
for some value $c'$ which we can ignore.
<p>
<b>Third Main Point:</b>
Note, that this means the attack does not apply to TFHE's standard
parameters, since we have $\beta \approx \sqrt{q}$, and the multiplication by
$n$ results in $q$ being too small in TFHE for the attack to apply.
<p>
<b>Fourth Main Point:</b>
The attack does not apply to Kyber, Dilithium or BGV as here the large
value of $n$ needed (discussed above) implies the used value of $q$ used
in these schemes is also too small.
<p>
In Condition C.7 the value of $r$ is actually chosen to be
$$ r = \frac{u t^3}{4 \log n}. $$
<p>
The final parameter to pick is $s^2$, which is chosen from Condition C.5 by
$$ s^2 = 2 u^2 t^2 + \epsilon. $$
<p>
There are then some extra conditions, Condition C.6 and C.7, which define
ranges for various parameters. My understanding is that these impact the
approximation factors which the algorithm obtains.
<h2>Summary from April 17th</h2>
<ol>
<li>The algorithm definitely requires $O(\beta^2)$ repetitions.
Thus for large $\beta^2$ (TFHE) this is infeasible. (First Main Point)
<li>For small $\beta$ values (Kyber, Dilithium, BGV) the algorithm requires a huge number of LWE
samples $m$. (Second Main Point)
<li>The algorithm requires $q > c' n \beta^2$,
which is either too high
because $\beta$ is big (TFHE), or it is too high
because $n = \ell+m+1$ is big (Kyber, Dilithium) (because $\beta$
is small due to the previous point). (Third/Fourth Main Points)
<li>Generating large numbers of samples from the fixed number of
samples we have in public key schemes, creates larger values
of $\beta$ than considered here.
This makes the attack less practical.
</ol>
<hr>
Nigel Smart<br>
April 17th 2024.
<hr>
<a name="April18"></a>
<h1>Update April 18th</h1>
Dave Archer asked me some questions related to BGV stlye FHE so I decided
to have a more detailed look at this.
For the description of BGV and the noise equations I refer to the
relatively <a href="https://eprint.iacr.org/2012/099">old paper</a> of
Gentry, Halevi and myself (called the GHS paper below) where we evaluate
the AES circuit using BGV.
However GHS only looks at plaintext modulus $p=2$, the extension
of these formulae for other plaintext spaces was done in
<a href="https://eprint.iacr.org/2015/889">another paper</a> of Costache and
myself (called the CS paper below).
<p>
I use these papers as these are the ones I know best, so it is quicker to
use them to do a quick-and-dirty analysis.
More modern papers, with more tuned noise equations, will have a similar
analysis, so the overall conclusions should <em>roughly</em> be the same.
<p>
The main difference between GHS/CS and perhaps more modern papers is that
the secret key is given with a fixed hamming weight in GHS, whereas more
modern papers performs rejection sampling on the secret key in order
to obtain a secret key with low canonical norm.
For both methods we can assume that they produce secret keys with the
same low canonical norm, they just do it in different ways.
<ul>
<li>The canonnical norm bounds give us high probability bounds
on the canonical norm of the noise term, these are
roughly speaking (upto a small constant, a product of
something called the ring constant in GHS and the inverse of
the small constant obtained from the $\mathsf{erfc}$ function)
the same as the $\beta$ values given above.
So in what follows we will just assume the canonical
norm bounds correspond to $10 \cdot \beta$, which
equates to an error probability of around $2^{-80}$.
This can be made more precise, but again with little
change to the overall analysis.
</ul>
<p>
Recall the key points above:
<ul>
<li>If $\beta$ is small we need a lot of LWE samples $m$
to make the attack work, and in BGV the public key has a very small $\beta$,
i.e. $\beta = \sqrt{8 \pi}$.
<li>But recall the discussion arising from a <a href="#April16Vadim">discussion with Vadim Lyubashevksy</a>.
To generate these extra samples itself increaes the noise value $\beta$.
</ul>
Now in the GHS/CS papers the noise formulae for producing new encryptions
are given, after all it is vital to understand how BGV operates in
order to give these formulae.
<p>
The method for public key encryption produces ciphertexts whose noise term
has canonical norm bounded by a constant called $B_{\mathsf{clean}}$.
Roughly speaking we have
$$ B_{\mathsf{clean}} = O(p \cdot \ell). $$
However, we can then perform a modulus switch to obtain a ciphertext,
with a smaller ciphertext modulus $q$, whose noise term has canonical norm bounded by
$2 B_{\mathsf{scale}}$.
Roughly speaking we have
$$ B_{\mathsf{scale}} = O(p \cdot \sqrt{\ell}). $$
The implied constants here in the big-Oh's are small integers (think fifty or less).
When performing the modulus switch the smallest modulus we can use
is something of size slightly roughly $4 \cdot B_{\mathsf{scale}}$.
<p>
This would result in a BGV scheme with
<ul>
<li>$\beta \approx 2 \cdot 50 p \sqrt{\ell}/10 = 10 p \sqrt{\ell} = O(p \cdot \sqrt{\ell})$.
<li>$q \approx 400 p \sqrt{\ell} = O(p \cdot \sqrt{\ell})$.
</ul>
i.e. the $\alpha$ value would be the constant value of about $1/40$.
<p>
Recall the complexity of the attack is at least $O(\beta^2)$ so we would have
a complexity of at least $O(p^2 \cdot \ell)$.
<p>
<b>Fifth Main Point:</b>
BGV with large plaintext modulus (as used for example in the
<a href="https://eprint.iacr.org/2011/535">SPDZ protocol</a>)
is immune from the attack it seems.
<hr>
Nigel Smart<br>
April 18th 2024.
<hr>
<a name="April19"></a>
<h1>Update April 19th</h1>
The author published an update to his paper overnight:
<pre>
Step 9 of the algorithm contains a bug, which I don’t know how to fix.
See the updated version of eprint/2024/555 - Section 3.5.9 (Page 37) for details.
I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today.
</pre>
So the panic in lattice quarters is now over.
<hr>
Nigel Smart<br>
April 19th 2024.
<hr>
</body>
</html>