Криптографиялық көп сызықты карта - Cryptographic multilinear map - Wikipedia

A криптографиялық ${ displaystyle n}$- көп сызықты карта түрі болып табылады көп сызықты карта, яғни функция ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ кез келген бүтін сандар үшін ${ displaystyle a_ {1}, ldots, a_ {n}}$ және элементтер ${ displaystyle g_ {i} in G_ {i}}$, ${ displaystyle e (g_ {1} ^ {a_ {1}}, ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, ldots, g_ {n}) ^ { prod _ {i = 1} ^ {n} a_ {i}}}$және қосымша тиімді есептелетін және кейбір қауіпсіздік қасиеттерін қанағаттандыратын. Оның криптографияда бірнеше қосымшалары бар кілттермен алмасу хаттамалар, сәйкестендіруге негізделген шифрлау, және тарату шифрлау. Екі сызықты карталардың құрылымдары бар, олар екі сызықты карталар деп аталады,^[1] дегенмен, осындай көпжелісті құру проблемасы^[1] үшін карталар ${ displaystyle n> 2}$ әлдеқайда қиын болып көрінеді^[2] және ұсынылған кандидаттардың қауіпсіздігі әлі түсініксіз.^[3]

Анықтама

Үшін n = 2

Бұл жағдайда көп сызықты карталар көбінесе екі сызықты карталар немесе парингтер деп аталады және олар әдетте келесідей анықталады:^[4] Келіңіздер ${ displaystyle G_ {1}, G_ {2}}$ қарапайым тәртіптің екі аддитивті циклдік тобы бол ${ displaystyle q}$, және ${ displaystyle G_ {T}}$ тәртіптің басқа циклдік тобы ${ displaystyle q}$ көбейтіліп жазылады. Жұптау - бұл карта: ${ displaystyle e: G_ {1} times G_ {2} rightarrow G_ {T}}$, ол келесі қасиеттерді қанағаттандырады:

Біліктілік

${ displaystyle forall a, b in F_ {q} ^ {*}, forall P in G_ {1}, Q in G_ {2}: e (aP, bQ) = e (P, Q) ^ {ab}}$

Азғындау емес

Егер ${ displaystyle g_ {1}}$ және ${ displaystyle g_ {2}}$ генераторлары болып табылады ${ displaystyle G_ {1}}$ және ${ displaystyle G_ {2}}$сәйкесінше, содан кейін ${ displaystyle e (g_ {1}, g_ {2})}$ генераторы болып табылады ${ displaystyle G_ {T}}$.

Есептеу

Есептеудің тиімді алгоритмі бар ${ displaystyle e}$.

Сонымен қатар, қауіпсіздік мақсатында дискретті логарифм есебі екеуінде де қатал болу талап етіледі ${ displaystyle G_ {1}}$ және ${ displaystyle G_ {2}}$.

Жалпы жағдай (кез-келгені үшін n)

Біз карта деп айтамыз ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ Бұл ${ displaystyle n}$-көпфункционалды карта, егер ол келесі қасиеттерді қанағаттандырса:

1. Барлық ${ displaystyle G_ {i}}$ (үшін ${ displaystyle 1 leq i leq n}$) және ${ displaystyle G_ {T}}$ бір ретті топтар;
2. егер ${ displaystyle a_ {1}, ldots, a_ {n} in mathbb {Z}}$ және ${ displaystyle (g_ {1}, ldots, g_ {n}) in G_ {1} times cdots times G_ {n}}$, содан кейін ${ displaystyle e (g_ {1} ^ {a_ {1}}, ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, ldots, g_ {n}) ^ { prod _ {i = 1} ^ {n} a_ {i}}}$;
3. егер деген мағынада карта дегенеративті емес ${ displaystyle g_ {1}, ldots, g_ {n}}$ генераторлары болып табылады ${ displaystyle G_ {1}, ldots, G_ {n}}$сәйкесінше, содан кейін ${ displaystyle e (g_ {1}, ldots, g_ {n})}$ генераторы болып табылады ${ displaystyle G_ {T}}$
4. Есептеудің тиімді алгоритмі бар ${ displaystyle e}$.

Сонымен қатар, қауіпсіздік мақсатында дискретті логарифм есебі қиын болуы талап етіледі ${ displaystyle G_ {1}, ldots, G_ {n}}$.

Үміткерлер

Барлық үміткерлер көпжелілік карталар, шын мәнінде, көп деңгейлі карталардың аздап қорытылуы болып табылады, өйткені олар жүйеленген кодтау жүйелері деп аталады, өйткені олар картаға мүмкіндік береді ${ displaystyle e}$ ішінара қолданылуы керек: барлық қолданудың орнына ${ displaystyle n}$ мақсатты жиынтықта мән тудыратын бірден мәндер ${ displaystyle G_ {T}}$, өтініш беруге болады ${ displaystyle e}$ аралық мақсаттық жиынтықта мәндер тудыратын кейбір мәндерге. Мысалы, үшін ${ displaystyle n = 3}$, жасауға болады ${ displaystyle y = e (g_ {2}, g_ {3}) in G_ {T_ {2}}}$ содан кейін ${ displaystyle e (g_ {1}, y) in G_ {T}}$.

Үш негізгі үміткер - GGH13,^[5] негізделген көпмүшелік сақиналардың идеалдары; CLT13,^[6] шамамен GCD есебіне негізделген және бүтін сандармен жұмыс жасайтын, сондықтан GGH13 көп сызықты картасына қарағанда оны түсіну оңайырақ болады; және GGH15,^[7] графиктерге негізделген.

Әдебиеттер тізімі