combinatorial lattice security?

[D. J. Bernstein]

My understanding is that SMAUG and TiGER each have public keys of the
form As+e where A is public, e is small (chosen by rounding As in the
case of TiGER), and s is a {-1,0,1} vector of the following shape:

* SMAUG128: 140 nonzero positions out of 512;
* SMAUG192: 150 nonzero positions out of 768;
* SMAUG256: 145 nonzero positions out of 1280;
* TiGER128: 160 nonzero positions out of 512;
* TiGER192: 84 nonzero positions out of 1024;
* TiGER256: 198 nonzero positions out of 1024.

I'm basing this on https://www.kpqc.or.kr/images/pdf/Smaug.pdf Table 3
(h_s row for the number of nonzero positions, n row times k row for the
total number of positions) and Algorithm 1 (s is output of HWT_h_s); and
on https://www.kpqc.or.kr/images/pdf/TiGER.pdf Table 1 (h_s column for
the number of nonzero positions, n row for the total number of
positions) and Algorithm 1 (s is output of HWT(h_s)).

When s is a {-1,0,1} vector with h nonzero positions out of N, the total
number of possible s choices is 2^h times binomial(N,h), which is
approximately

* 2^568.67 for SMAUG128;
* 2^692.38 for SMAUG192;
* 2^792.63 for SMAUG256;
* 2^614.05 for TiGER128;
* 2^498.66 for TiGER192;
* 2^918.46 for TiGER256.

If I've calculated these correctly then a simple brute-force search for
s is safely above the target security level in all cases.

However, there are more sophisticated combinatorial searches in the
literature, such as an attack from Odlyzko with exponent approximately
0.5, and a newer attack from May (https://eprint.iacr.org/2021/216) that
reportedly has asymptotic exponent around 0.25 and concrete exponent
around 0.3.

There are also various efforts to combine combinatorial searches with
lattice attacks into "hybrid" attacks. In the following chart, moving
down increases the sophistication of combinatorial techniques (generally
making analyses more difficult) and moving from "pure" to "primal" or
"dual" increases the sophistication of lattice techniques (generally
making analyses more difficult):

| pure | primal | dual |
+ ------------------ + ------- + --------------- + -------- +
| no searching | | Core-SVP | Core-SVP |
+ ------------------ + ------- + --------------- + -------- +
| brute-force search | easy | Howgrave-Graham | MATZOV |
+ ------------------ + ------- + --------------- + -------- +
| collisions | Odlyzko | Howgrave-Graham | |
+ ------------------ + ------- + --------------- + -------- +
| representations | May | | |
+ ------------------ + ------- + --------------- + -------- +

This chart is not a complete summary of the literature but gives
illustrative examples of attacks. The first Howgrave-Graham entry is
much easier to analyze than the second, but there is evidence of the
second being more powerful.

Many sources follow the Core-SVP approach from ADPS2016. This approach
ignores the combinatorial techniques. This is dangerous: for example,
moving in the primal column from Core-SVP to the next row decreases
heuristic asymptotic lattice security levels, and it is easy to write
down systems that are broken by combinatorial techniques but that seem
secure according to Core-SVP. The MATZOV entry sees some of the
combinatorial dangers, but can still easily miss attacks.

If I multiply 792.63 for SMAUG256 by the 0.3 estimate from May then I
obtain 237.79, which is below the 260 reported for Core-SVP hardness;
and if I multiply 498.66 for TiGER192 by 0.3 then I obtain 149.60, which
is below the 200 reported for Core-SVP hardness (and the 210 reported
for MATZOV). Obviously this is just a back-of-the-envelope calculation,
not a serious attack analysis, but I'm concerned about the possibility
of this reflecting a real reduction in security level, even without any
of the hybrid techniques:

* The attack in https://eprint.iacr.org/2021/216 is memory-intensive,
but the same is true for the sieving attacks modeled by Core-SVP,
and at first glance the quantification seems similar.

* The attack in https://eprint.iacr.org/2021/216 involves some work
in the inner loop, but the same is true for the attacks modeled by
Core-SVP, and again the quantification seems similar.

* The real objective is to protect against quantum computers, but
here the loss seems even larger: the quantum combinatorial attacks
in https://eprint.iacr.org/2021/815 have about 25% better exponents
than the non-quantum attacks in https://eprint.iacr.org/2021/216,
while known quantum sieving attacks have only about 10% better
exponents than known non-quantum sieving attacks.

I would suggest adding an analysis of https://eprint.iacr.org/2021/216
to the documentation of SMAUG and TiGER. Sorry if I missed something!

I should also note that, as https://eprint.iacr.org/2022/1337
illustrates, combinatorial concerns and hybrid concerns are not limited
to {-1,0,1}. I started looking at SMAUG and TiGER because the case
{-1,0,1} is easiest to analyze; I don't mean to suggest that other KEMs
avoid these concerns.

---D. J. Bernstein

[정치곤]

Thanks for your invaluable comment. 

We agree that the hamming-weight significantly affects the security strength. 

Therefore, we carefully selected the Hamming weight that exceeds the minimum value for each security strength, considering the Grover algorithm in the quantum environment studied by the Round5 team(in NIST competition).

However, the papers you referenced were not considered. We agree with your comments about our scheme.  

Intuitively, this issue can be counteracted by increasing the hamming-weight.

We will review the parameters in consideration of the effect on efficiency (multiplication) and especially on the probability of decryption failure rate.  

Once we've modified the scheme, we will release it on our GitHub repository (https://github.com/honggoonin/TiGER).

Thank you for your interest and time in our scheme.

2022년 12월 28일 (수) 18:37, D. J. Bernstein <authorcon...@box.cr.yp.to>님이 작성:

--
You received this message because you are subscribed to the Google Groups "KpqC-bulletin" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kpqc-bulleti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/kpqc-bulletin/20221228093720.563233.qmail%40cr.yp.to.

[Hyeongmin Choe]

We first thank you for your interest in SMAUG and KpqC competition.

We agreed with your calculation and concerns about security. We considered lattice
attacks with both approaches, ADPS2016 and MATZOV, but not May's meet-LWE attack
in the submission document. To check the effect of the meet-LWE attack in more detail,
we analyzed and applied it to SMAUG. As a result, we obtain the following time and
memory complexity. May's paper does not specify the units for the time and memory
complexity; we just followed May's.

SMAUG128: 2^167.2 (time) and 2^152.0 (memory)
SMAUG192: 2^216.0 (time) and 2^192.4 (memory)
SMAUG256: 2^256.4 (time) and 2^237.3 (memory)

It assumes that the number of 1's and -1's are equal, which is not our case. With a high 

probability they are similar, so we expect additional several bits of security. 

In the next version of our specification, we will put this analysis in more detail. We may
change the parameters set SMAUG256 to have h_r = 145, resulting in the following
security (in the base two logarithms) with a little bit more decryption failure probability. 

The public key and ciphertext sizes will remain the same.

Core-SVP: 265.8 (classic) and 245.1 (quantum)
Meet-LWE: 263.7 with 233.6 for memory
DFP: 2^-164.4.

We will keep our eyes on sparse-secret LWE attacks. Thank you again for your interest
and effort.

We additionally thank Changmin, who first pointed out that May's attack may lower the
security of SMAUG.

Best Regards,
Hyeongmin Choe,
SMAUG team

*references
[1] Alexander May, How to Meet Ternary LWE Keys. https://eprint.iacr.org/2021/216

2022년 12월 28일 수요일 오후 6시 37분 47초 UTC+9에 D. J. Bernstein님이 작성: