@inproceedings {27709,
	title = {Boolean Polynomials, BDDs and CRHS Equations {\textendash} Connecting the Dots with CryptaPath},
	journal = {Selected Areas in Cryptography},
	volume = {12804},
	year = {2021},
	month = {07/2021},
	pages = {229-251},
	publisher = { Springer},
	address = {Cham},
	abstract = {When new symmetric-key ciphers and hash functions are proposed they are expected to document resilience against a number of known attacks. Good, easy to use tools may help designers in this process and give improved cryptanalysis. In this paper we introduce CryptaPath, a tool for doing algebraic cryptanalysis which utilizes Compressed Right-Hand Side (CRHS) equations to attack SPN ciphers and sponge constructions. It requires no previous knowledge of CRHS equations to be used, only a reference implementation of a primitive.
The connections between CRHS equations, binary decision diagrams and Boolean polynomials have not been described earlier in literature. A comprehensive treatment of these relationships is made before we explain how CryptaPath works. We then describe the process of solving CRHS equation systems while introducing a new operation, dropping variables.},
	keywords = {algebraic cryptanalysis, binary decision diagram, block cipher, equation system, Open Source, tool},
	isbn = {978-3-030-81651-3},
	doi = {https://doi.org/10.1007/978-3-030-81652-0_9},
	url = {https://link.springer.com/chapter/10.1007/978-3-030-81652-0_9},
	author = {John Petter {Indr{\o}y} and Costes, Nicolas and Raddum, H{\r a}vard},
	editor = {O., Dunkelman and Jr. M.J. {Jacobson} and C., O{\textquoteright}Flynn}
}
@article {26351,
	title = {MRHS solver based on linear algebra and exhaustive search},
	journal = {Journal of Mathematical Cryptology},
	volume = {12},
	year = {2018},
	month = {09/2018},
	pages = {143-157},
	publisher = {De Gruyter},
	abstract = {We show how to build a binary matrix from the MRHS representation of a symmetric-key cipher. The matrix contains the cipher represented as an equation system and can be used to assess a cipher{\textquoteright}s resistance against algebraic attacks. We give an algorithm for solving the system and compute its complexity. The complexity is normally close to exhaustive search on the variables representing the user-selected key. Finally, we show that for some variants of LowMC, the joined MRHS matrix representation can be used to speed up regular encryption in addition to exhaustive key search.},
	keywords = {algebraic cryptanalysis, LowMC, MRHS},
	issn = {1862-2976},
	doi = {https://doi.org/10.1515/jmc-2017-0005},
	url = {https://www.degruyter.com/view/j/jmc.2018.12.issue-3/jmc-2017-0005/jmc-2017-0005.xml?format=INT},
	author = {Raddum, H{\r a}vard and Zajac, Pavol}
}
@inproceedings {24094,
	title = {Solving Compressed Right Hand Side Equation Systems with Linear Absorption},
	journal = {7th International Conference on Sequences and Their Applications, SETA 2012},
	volume = {7280},
	year = {2012},
	month = {06/2012},
	pages = {291-302},
	publisher = {Lecture Notes in Computer Science, Springer Verlag},
	abstract = {In this paper we describe an approach for solving complex multivariate equation systems related to algebraic cryptanalysis. The work uses the newly introduced Compressed Right Hand Sides (CRHS) representation, where equations are represented using Binary Decision Diagrams (BDD). The paper introduces a new technique for manipulating a BDD, similar to swapping variables in the well-known sifting-method. Using this technique we develop a new solving method for CRHS equation systems. The new algorithm is successfully tested on systems representing reduced variants of Trivium.
},
	keywords = {algebraic cryptanalysis, BDD, multivariate equation system, Trivium},
	isbn = {978-3-642-30614-3},
	issn = {0302-9743},
	doi = {10.1007/978-3-642-30615-0_27},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-30615-0_27},
	author = {Thorsten Ernst {Schilling} and Raddum, H{\r a}vard}
}
@inproceedings {24093,
	title = {Analysis of Trivium Using Compressed Right Hand Side Equations},
	journal = {14th International Conference on Information Security and Cryptology - ICISC 2011},
	volume = {7259},
	year = {2011},
	month = {12/2011},
	pages = {18-32},
	publisher = {Lecture Notes in Computer Science, Springer Verlag},
	abstract = {We study a new representation of non-linear multivariate equations for algebraic cryptanalysis. Using a combination of multiple right hand side equations and binary decision diagrams, our new representation allows a very efficient conjunction of a large number of separate equations. We apply our new technique to the stream cipher Trivium and variants of Trivium reduced in size. By merging all equations into one single constraint, manageable in size and processing time, we get a representation of the Trivium cipher as one single equation.},
	keywords = {algebraic cryptanalysis, BDD, multivariate equation system, Trivium},
	isbn = {978-3-642-31911-2},
	issn = {0302-9743},
	doi = {10.1007/978-3-642-31912-9_2},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-31912-9_2},
	author = {Thorsten Ernst {Schilling} and Raddum, H{\r a}vard}
}
