New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb F_p$

ePrint Report: New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb F_p$

Remi Geraud-Stewart, David Naccache

Given a set of matrices $\mathbf{A} := \{A_0, \dotsc, A_{k-1}\}$, and a matrix $M$ guaranteed to be the product of some ordered subset of $\mathbf{L}\subset\mathbf{A}$, can $\mathbf{L}$ be efficiently recovered? We begin by observing that the answer is positive under some assumptions on $\mathbf{A}$.


Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based …

eprint report key matrix product products public report