แผนที่ เข้ารหัสแบบหลายเชิง เส้น (cryptographic -multilinear map) เป็น ${\displaystyle n}$แผนที่แบบหลายเชิงเส้นชนิดหนึ่งกล่าวคือ เป็นฟังก์ชันที่สำหรับจำนวนเต็มและองค์ประกอบ ใดๆ และซึ่งนอกจากนี้ยังสามารถคำนวณได้อย่างมีประสิทธิภาพและเป็นไปตามคุณสมบัติด้านความปลอดภัยบางประการ มีการประยุกต์ใช้หลายอย่างในด้านการเข้ารหัสเช่นโปรโตคอลการแลกเปลี่ยนคีย์การเข้ารหัสตามเอกลักษณ์และการเข้ารหัสแบบกระจายเสียงมีการสร้างแผนที่เข้ารหัสแบบหลายเชิงเส้น 2 มิติ (cryptographic 2-multilinear maps) ซึ่งรู้จักกันในชื่อแผนที่แบบสองเชิงเส้น (bilinear maps) ^{[ 1 ]}อย่างไรก็ตาม ปัญหาของการสร้างแผนที่ แบบหลายเชิงเส้น ^{[ 1 ]} ดังกล่าวสำหรับ ดูเหมือนจะยากกว่ามาก^{[ 2 ]} และความปลอดภัยของตัวเลือกที่เสนอมายังไม่ชัดเจน^{[ 3 ]}${\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}}}$${\displaystyle 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}}$

เรากล่าวว่าแผนที่หนึ่งเป็นแผนที่เชิงเส้นหลายตัวแปร (multilinear map) หากแผนที่นั้นมีคุณสมบัติดังต่อไปนี้: ${\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 ]}ซึ่งอิงตามกราฟ