Clarification

[hellman]

Is it correct that the linear layer matrix / constants are known to the attacker? Does not seem to be written on the challenge page, but only mentioned in the paper by Banik et al.

Also, are weak linear layers / constants considered in the main challenges? High-density (realistic) or low-density (artificial).

[mschof]

Hi Aleksei, yes, the linear layer matrices and the round constants are public information and hence known to the attacker. The only unknown is the key (this is usually the case for symmetric-key primitives).

Regarding the weak linear layers: I'd say it depends. For example, there exist trivial linear layers which do not achieve any mixing (or only a weak mixing) and immediately lead to attacks. Anyway, we are also looking for interesting properties of LowMC, which includes attacks based on the linear layers. I assume by the density you refer to the number of ones in the matrix?

Regards, Markus

On Wed, Aug 19, 2020, 19:24 Aleksei notifications@github.com wrote:

Is it correct that the linear layer matrix / constants are known to the attacker? Does not seem to be written on the challenge page, but only mentioned in the paper by Banik et al.

Also, are weak linear layers / constants considered in the main challenges? High-density (realistic) or low-density (artificial).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/lowmcchallenge/lowmcchallenge.github.io/issues/1, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACO7R2VCJ3E3WCI3IH55QJDSBQDFLANCNFSM4QFFTSDQ .

[mschof]

To be clear: the cryptanalysis challenge is mainly about a specific choice of affine layer as described in the Picnic specification and on the challenge website. Possible are of course generic approaches independent of such specific choices like the round-1 winner did.

About the density: As already noted in the original publication of LowMC [1], the security arguments used in this paper against large classes of statistical attacks break down when the density gets lowered. However those classes of attacks are ruled out anyhow due to the very restrictive way LowMC is used in the Picnic signature scheme.

Hence results about low density choices, or other weak choices, are generally interesting. But they are not the main focus of the cryptanalysis challenge, albeit they might still qualify for the bonus price '...for finding an interesting property of LowMC or for showing a new technique'. In that context, variants of malicious/unlucky choices have already been investigated in [2].

[1] Martin Albrecht; Christian Rechberger; Thomas Schneider; Tyge Tiessen; Michael Zohner; Ciphers for MPC and FHE, EUROCRYPT 2015.

[2] Itai Dinur, Yunwen Liu, Willi Meier, Qingju Wang: Optimized Interpolation Attacks on LowMC. ASIACRYPT 2015

Very best, Christian

On 19.08.20 22:34, Markus Schofnegger wrote:

Hi Aleksei, yes, the linear layer matrices and the round constants are public information and hence known to the attacker. The only unknown is the key (this is usually the case for symmetric-key primitives).

Regarding the weak linear layers: I'd say it depends. For example, there exist trivial linear layers which do not achieve any mixing (or only a weak mixing) and immediately lead to attacks. Anyway, we are also looking for interesting properties of LowMC, which includes attacks based on the linear layers. I assume by the density you refer to the number of ones in the matrix?

Regards, Markus

On Wed, Aug 19, 2020, 19:24 Aleksei <notifications@github.com mailto:notifications@github.com> wrote:

Is it correct that the linear layer matrix / constants are known to
the attacker? Does not seem to be written on the challenge page, but
only mentioned in the paper by Banik et al.

Also, are weak linear layers / constants considered in the main
challenges? High-density (realistic) or low-density (artificial).

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<https://github.com/lowmcchallenge/lowmcchallenge.github.io/issues/1>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACO7R2VCJ3E3WCI3IH55QJDSBQDFLANCNFSM4QFFTSDQ>.

[hellman]

Thank you for the clarifications, Markus and Christian.

By "a specific choice of affine layer" do you mean the data from https://github.com/lowmcchallenge/lowmcchallenge-material/tree/master/code/reference ? It seems not to be linked from the challenge page.

Concrete instances would indeed make the question clear for the non-bonus task.

Best Regards, Aleksei