Published April 9, 2024
| Version v1
Publication
Open
Fast polynomial multiplication using matrix multiplication accelerators with applications to NTRU on Apple M1/M3 SoCs
- 1. Universidade Estadual de Campinas (UNICAMP)
- 2. Universidade Estadual de Londrina
Description
Efficient polynomial multiplication routines are critical to the performance of lattice-based post-quantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflops-level of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions, coprocessors and special-purpose cores to accelerate such operations. In particular, Apple ships an undocumented matrix-multiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systems-on-chip (SoCs): polynomial multiplication, key generation, encapsulation and decapsulation are sped up by 1.54 – 3.07 × , 1.08 – 1.33 × , 1.11 – 1.50 × and 1.20 – 1.98 × , respectively, over the previous state-of-the-art.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تعد إجراءات الضرب متعدد الحدود الفعالة أمرًا بالغ الأهمية لأداء التشفير ما بعد الكم القائم على الشبكة (PQC). نظرًا لأن معايير مراقبة الجودة الأولية لم تبدأ في الظهور إلا مؤخرًا، لا تزال وحدات المعالجة المركزية تفتقر إلى التعليمات المتخصصة لتسريع مثل هذه الإجراءات الروتينية. وفي الوقت نفسه، نمت أهمية التعلم العميق بشكل لا يقاس. تتطلب أعباء عملها مستوى تيرافلوبس من قوة المعالجة لعمليات الجبر الخطي، وخاصة ضرب المصفوفة. استجاب مهندسو الكمبيوتر من خلال إدخال ملحقات ISA والمعالجات المشتركة والنوى ذات الأغراض الخاصة لتسريع مثل هذه العمليات. على وجه الخصوص، تشحن شركة آبل معالجًا مشاركًا غير موثق لمصفوفة الضرب، AMX، في مئات الملايين من الهواتف المحمولة والأجهزة اللوحية وأجهزة الكمبيوتر الشخصية. يعيد عملنا استخدام AMX لتنفيذ الضرب متعدد الحدود ويطبقه على نظام تشفير NTRU، مما يؤدي إلى تسجيل سجلات سرعة جديدة على أنظمة Apple M1 و M3 على الرقاقة (SoCs): يتم تسريع الضرب متعدد الحدود وتوليد المفاتيح والتغليف وفك التغليف بمقدار 1.54 – 3.07 × ، 1.08 – 1.33 × ، 1.11 – 1.50 × و 1.20 – 1.98 × ، على التوالي، على أحدث التقنيات السابقة.Translated Description (French)
Des routines de multiplication polynomiales efficaces sont essentielles à la performance de la cryptographie post-quantique (PQC) basée sur le réseau. Comme les normes PQC n'ont commencé à émerger que récemment, les processeurs manquent encore d'instructions spécialisées pour accélérer de telles routines. Pendant ce temps, l'apprentissage profond a pris une importance incommensurable. Ses charges de travail nécessitent une puissance de traitement de niveau téraflops pour les opérations d'algèbre linéaire, principalement la multiplication matricielle. Les architectes informatiques ont réagi en introduisant des extensions ISA, des coprocesseurs et des cœurs spéciaux pour accélérer ces opérations. En particulier, Apple expédie un coprocesseur de multiplication matricielle non documenté, AMX, dans des centaines de millions de téléphones mobiles, de tablettes et d'ordinateurs personnels. Notre travail réoriente AMX pour implémenter la multiplication polynomiale et l'applique au cryptosystème NTRU, établissant de nouveaux records de vitesse sur les systèmes sur puce (SoC) M1 et M3 d'Apple : la multiplication polynomiale, la génération de clés, l'encapsulation et la décapsulation sont accélérées de 1,54 à 3,07 × , 1,08 à 1,33 × , 1,11 à 1,50 × et 1,20 à 1,98 × , respectivement, par rapport à l'état de la technique précédent.Translated Description (Spanish)
Las rutinas de multiplicación polinómica eficientes son fundamentales para el rendimiento de la criptografía post-cuántica (PQC) basada en redes. Como los estándares de PQC comenzaron a surgir recientemente, las CPU aún carecen de instrucciones especializadas para acelerar dichas rutinas. Mientras tanto, el aprendizaje profundo ha crecido inconmensurablemente en importancia. Sus cargas de trabajo requieren un nivel de potencia de procesamiento de teraflops para las operaciones de álgebra lineal, principalmente la multiplicación de matrices. Los arquitectos informáticos han respondido introduciendo extensiones ISA, coprocesadores y núcleos especiales para acelerar dichas operaciones. En particular, Apple envía un coprocesador de multiplicación de matriz indocumentado, AMX, en cientos de millones de teléfonos móviles, tabletas y ordenadores personales. Nuestro trabajo reutiliza AMX para implementar la multiplicación polinómica y la aplica al criptosistema NTRU, estableciendo nuevos récords de velocidad en los sistemas en chip (SoC) Apple M1 y M3: la multiplicación polinómica, la generación de claves, la encapsulación y la desencapsulación se aceleran en 1,54 – 3,07 × , 1,08 – 1,33 × , 1,11 – 1,50 × y 1,20 – 1,98 × , respectivamente, con respecto al estado de la técnica anterior.Files
pdf.pdf
Files
(1.1 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:9916e705d0d0fde5e1391824058d36aa
|
1.1 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- الضرب السريع متعدد الحدود باستخدام معجلات ضرب المصفوفة مع التطبيقات إلى NTRU على Apple M1/M3 SoCs
- Translated title (French)
- Multiplication polynomiale rapide à l'aide d'accélérateurs de multiplication matricielle avec des applications à NTRU sur les SoC M1/M3 d'Apple
- Translated title (Spanish)
- Multiplicación polinómica rápida utilizando aceleradores de multiplicación matricial con aplicaciones a NTRU en SoC M1/M3 de Apple
Identifiers
- Other
- https://openalex.org/W4394595254
- DOI
- 10.62056/a3txommol
References
- https://openalex.org/W1525161423
- https://openalex.org/W1675339804
- https://openalex.org/W1988425770
- https://openalex.org/W2168991419
- https://openalex.org/W2514893051
- https://openalex.org/W2606722458
- https://openalex.org/W2610765860
- https://openalex.org/W2740966734
- https://openalex.org/W2741854956
- https://openalex.org/W2912012512
- https://openalex.org/W3101543398
- https://openalex.org/W3111297213
- https://openalex.org/W3141394081
- https://openalex.org/W3179873149
- https://openalex.org/W3217399103
- https://openalex.org/W4213195788
- https://openalex.org/W4243242894
- https://openalex.org/W4285230782
- https://openalex.org/W4285520720
- https://openalex.org/W4296831830
- https://openalex.org/W4318603197
- https://openalex.org/W4393258384