[toc]

###### tags: `Reading sessions`
# 2023
<https://crypto.iacr.org/2023/acceptedpapers.php>

## [Security Analysis of the WhatsApp End-to-End Encrypted Backup Protocol](https://link.springer.com/chapter/10.1007/978-3-031-38551-3_11)
* Gareth T. Davies, Sebastian Faller, Kai Gellert, Tobias Handirk, Julia Hesse, Máté Horváth & Tibor Jager
* CRYPTO 2023
* [MD]

# 2022
<https://crypto.iacr.org/2022/program.php>

## [Constructing and Deconstructing Intentional Weaknesses in Symmetric Ciphers](https://eprint.iacr.org/2021/829.pdf)
* By Christof Beierle, Tim Beyne, Patrick Felke, Gregor Leander
* CRYPTO 2022

* [SS] This work is based on the framework of Malicious cipher (Crypto 2020), that is, how to insert backdoor to a cipher and based on the backdoor key can be recovered. The framework has the following security notions:

Undetectability: this security notion represents the inability for an external entity to realize the existence of the hidden backdoor.
Undiscoverability: it represents the inability for an attacker to find the hidden backdoor, even if the general form of the backdoor is known.
Untraceability: it states that an attack based on the backdoor should not reveal any information about the backdoor itself.
Practicability: this usability notion stipulates that the backdoor is practical.

They have presented malicious-AES. The backdoor is implaneted through a tweak. This work applies tweak in the key scheduling algorithm so that it makes invaraint subsppace attack easy.

###### tags: `` ``

---
## [Breaking Rainbow Takes a Weekend on a Laptop](https://link.springer.com/chapter/10.1007/978-3-031-15979-4_16)
* Ward Beullens
* [SS] Rainbow was a signature scheme competing in the NIST post-quantum standard. This paper shows a practical attack on it. The Rainbow signature scheme has a public key which is a quadratic polynomial over a field
P : (x_1,..,x_n) -> (y_1, ..., y_m)
For a message m, the signer first calculate Hash(m) and then find an inverse z = P^{-1}(Hash(m)). Then z is the signature of m. The signer has a trapdoor that allows her to find a inverse of Hash(m). To break the system one has to solve equations of multivariate quadratic polynomials over F_q. However, this is a hard problem that even quatum computers cannot solve as of now, thus it falls under post-quantum cryptography.
This paper made an observation that the polynomial can be written as per the following decompositon:
P(v+u) = P(v) + P(u) + P'(v,u), or
P'(v,u) = P(v+u) - P(v) - P(u).
Note that for a fixed v, P'(v,u) is a linear map.
The secret knowledge that the signer has is that there is a subspace O such that P(O) = 0. This paper observes that for a randomly chosen v, P'(v,u) has a solution u \in O with probability 1/q. So once such an u is found then it reduces the total number of unknowns so that remaining system of equations becomes easy to solve for some set of parameters that Rainbow has suggested. This makes it possible to find the secret key and forgey attack.
For SL1 parameter the total expected running time of the attack is 53 h.

## [Nova: Recursive Zero-Knowledge Arguments from Folding Schemes](https://eprint.iacr.org/2021/370)
* By Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla

* Incrementally verifiable computation scheme, introduced in 2008, is a powerful primitive enabling a possibly infinite computation defined on path graphs such that the correctness can be verified efficiently and incrementally at any point. They are widely used in verifiable delay functions, succinct blockchains, and verifiable state machines, etc.
* Historically, IVC was built from recursive SNARKs. The prover not only proves the correctness of the current computation, but also proves the correctness of the former proof. But it yields high overhaed since the prover generates a new SNARK proof at each step.
* Recently, IVC was built from accumulation schemes. At each step, the prover only accumulates former accumulators and accumulation instances in this step. The overhead is much cheaper than traditional SNARKs. But it is still high and hard to use in practice.

* This paper introduced folding schemes and use them to construct a highly efficient IVC scheme--Nova.
* Folding schemes are defined for a NP relation over instance-witness tuples. They can reduce the task of checking two instances to the task of checking a single instance. They must be much more efficient than traditional SNARKs.
* Nova provides the fastest prover in the literature (two multiexponentiations of circuit size) and lowest recursion overhead (two group exponentiations).

* Limitations:
* only support rank-one constraint systems.
* not non-uniform.