[Resource Topic] 2023/1745: New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb F_p$

Welcome to the resource topic for 2023/1745

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

Authors: 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 upon this problem.

We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.

ePrint: https://eprint.iacr.org/2023/1745

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .