Visible to the public On Generation of Cycles, Chains and Graphs of Pairing-Friendly Elliptic Curves

TitleOn Generation of Cycles, Chains and Graphs of Pairing-Friendly Elliptic Curves
Publication TypeConference Paper
Year of Publication2020
AuthorsBespalov, Yuri, Nelasa, Hanna, Kovalchuk, Lyudmila, Oliynykov, Roman
Conference Name2020 IEEE International Conference on Problems of Infocommunications. Science and Technology (PIC S T)
Date Publishedoct
Keywordsblockchain, complex multiplication method, composability, compositionality, Elliptic curves, Estimation, pairing-friendly elliptic curves, Protocols, pubcrawl, SNARKs, Task Analysis, theoretical cryptography
AbstractWe study the problem of generation of cycles, chains and graphs of pairing-friendly elliptic curves using in succinct non-interactive arguments for knowledge protocols in blockchain. The task to build a "stick" for existing MNT753 cycle is reduced to the factorization problem for big numbers. Together with graphs of pairing friendly elliptic curves we consider auxiliary graphs of their orders (primes or irreducible polynomials) associated to vertices and embedding degrees to edges. Numerical experiments allow us to conjecture that (except of MNT case): 1) for any fixed embedding degrees there exist only finite number of such cycles and, hence, there are no families of such cycles; 2) chains of prime order are very rare; we suppose that there are no polynomial families of such chains. It is hard to find a family of pairing friendly elliptic curves with the base field order q(x) such that zk Q[x]/(q(x)) for k \textbackslashtextgreater 6. From other hand our examples show that we can apply Brezing-Weng construction with k=6 and D=3 iteratively to obtain chains of length 3-4. We build 1) a family of 1-chains with embedding degrees 8 and 7, where all orders are given by cyclotomic polynomials; 2) a combination of MNT cycle and near-MNT curve.
DOI10.1109/PICST51311.2020.9468050
Citation Keybespalov_generation_2020