Linear Cryptanalysis of TFHE-Friendly Cipher FRAST in the Average Key Setting

What it is

A preprint (ePrint 2026/2599, received 22 October 2026) by Xingwei Ren, Zhenyu Xiong, Bo Xu, Yongqiang Li and Mingsheng Wang. It gives a linear attack on FRAST, a TFHE-friendly stream cipher, in the average key setting. It closes the open problem left by the attack of Bak et al., whose filter let wrong key guesses pass.

How it works

FRAST's S-boxes are public and random for every keystream block. For the mask on the least significant bit, key differences fall into five indistinguishable classes per round. The Bak et al. filter gives some wrong classes of the right parity a nonzero expected score, which causes the false positives.

The authors compute the trail correlation exactly through the real cipher. They bound the success of their statistic for every fixed master key. They also bound false alarms in two cases: a fixed master key with the last round kept and no filter, and any attack against an ideal keystream.

The attack algorithm is called Contract. With known XOF inputs it recovered the classes of a branch pair at 15 rounds and the master key at 10 rounds. Those are experimental results.

Preconditions / Affected

• The 15-round and 10-round results assume known XOF inputs.
• The longer-round figures come from a cost model, not from runs. It gives class recovery for every sampled key at 26 rounds with known inputs. With chosen inputs it gives recovery for a third of sampled keys at 38 rounds.
• Full FRAST is reached only on weak master keys, with density between 2^-11.8 and 2^-5.4. This is within the claimed security, using the cost accounting of Bak et al.
• A distinguisher of full FRAST has a proved advantage on these weak keys. Its time divided by advantage also stays below the claimed security.

What to do

The abstract names one countermeasure: independent branch S-boxes remove the cheap classes. It says this costs more in TFHE, and it gives no figure for that cost. Anyone evaluating FRAST should treat the weak-key density as the exposure measure and weigh it against that overhead.

Caveats

• The page is an abstract only. Round-by-round parameters, data and time complexities, and the cost model's assumptions are not shown.
• Full-round results cover weak keys only, not the average key. The full-cipher claim rests on the Bak et al. accounting.
• The work is a preprint with no peer review noted.