Paper 2023/1745
New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb F_p$
, Qualcomm (United States)Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Public-key cryptosystemMatrix groupNon-commutative cryptography
- Contact author(s)
-
rgerauds @ qti qualcomm com
david naccache @ ens fr - History
- 2023-12-04: last of 5 revisions
- 2023-11-11: received
- See all versions
- Short URL
- https://ia.cr/2023/1745
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1745,
author = {Remi Geraud-Stewart and David Naccache},
title = {New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb F_p$},
howpublished = {Cryptology ePrint Archive, Paper 2023/1745},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1745}},
url = {https://eprint.iacr.org/2023/1745}
}
