Tropical cryptography

In tropical analysis, tropical cryptography refers to the study of a class of cryptographic protocols built upon tropical algebras.[1] In many cases, tropical cryptographic schemes have arisen from adapting classical (non-tropical) schemes to instead rely on tropical algebras. The case for the use of tropical algebras in cryptography rests on at least two key features of tropical mathematics: in the tropical world, there is no classical multiplication (a computationally expensive operation), and the problem of solving systems of tropical polynomial equations has been shown to be NP-hard.

Basic Definitions

The key mathematical object at the heart of tropical cryptography is the tropical semiring $(\mathbb {R} \cup \{\infty \},\oplus ,\otimes )$ (also known as the min-plus algebra), or a generalization thereof. The operations are defined as follows for $x,y\in \mathbb {R} \cup \{\infty \}$ :

$x\oplus y=\min\{x,y\}$
$x\otimes y=x+y$

It is easily verified that with $\infty$ as the additive identity, these binary operations on $\mathbb {R} \cup \{\infty \}$ form a semiring.

gollark: Oops, it turns out I'm accidentally sorting by it instead of the rank, but it's equally slow after fixing that.

gollark: ```nonlocality=# EXPLAIN ANALYZE SELECT url, ts_rank(fts, query), ts_headline(fts::text, query, 'MaxWords=60') AS rank FROM pages, websearch_to_tsquery('bee') query WHERE fts @@ query ORDER BY rank LIMIT 1; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=860.92..860.92 rows=1 width=96) (actual time=8506.425..8506.427 rows=1 loops=1) -> Sort (cost=860.92..861.05 rows=52 width=96) (actual time=8506.423..8506.425 rows=1 loops=1) Sort Key: (ts_headline((pages.fts)::text, query.query, 'MaxWords=60'::text)) Sort Method: top-N heapsort Memory: 25kB -> Nested Loop (cost=688.65..860.66 rows=52 width=96) (actual time=1.362..8505.403 rows=348 loops=1) -> Function Scan on websearch_to_tsquery query (cost=0.25..0.26 rows=1 width=32) (actual time=0.023..0.025 rows=1 loops=1) -> Bitmap Heap Scan on pages (cost=688.40..846.49 rows=52 width=142) (actual time=0.353..1.502 rows=348 loops=1) Recheck Cond: (fts @@ query.query) Heap Blocks: exact=231 -> Bitmap Index Scan on page_search_index (cost=0.00..688.39 rows=52 width=0) (actual time=0.320..0.320 rows=387 loops=1) Index Cond: (fts @@ query.query) Planning Time: 0.190 ms Execution Time: 8506.463 ms(13 rows)```

gollark: It's not a condition, it's an extra row on the output, and I can see exactly what it does via `EXPLAIN ANALYZE`.

gollark: Maybe I need a better full text search backend?!

gollark: This is apioform.

References

Grigoriev, Dima; Shpilrain, Vladimir (2014). "Tropical Cryptography". Communications in Algebra. 42 (6): 2624–2632. arXiv:1301.1195. doi:10.1080/00927872.2013.766827. ISSN 0092-7872.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[GrigorievShpilrain2014-1] Grigoriev, Dima; Shpilrain, Vladimir (2014). "Tropical Cryptography". Communications in Algebra. 42 (6): 2624–2632. arXiv:1301.1195. doi:10.1080/00927872.2013.766827. ISSN 0092-7872.