2020 Выпуск №4

Рассмотрена возможность использования данных, собираемых при помощи CRM-системы для работы с клиентами банка, в целях опреде­ления эффективности работы сотрудников банка. В результате анали­за функций CRM-системы получено порядка 20 атрибутов для форми­рования профиля сотрудника, по которым можно рассчитать его инте­гральную эффективность.

The paper considers the possibility of using data collected by the CRM system for working with Bank clients to analyze the efficiency of Bank em­ployees. An analysis of the CRM system functions was performed, from which about 20 attributes were obtained for forming the employee profile and by which it is possible to calculate its integral efficiency.

В 2007 г. Н. Хаугрейв-Грэм предложил атаку на криптосистему NTRU, которая заключается в совмещении техники редукции решеток и комбинаторного метода «встречи посередине» (атаки meet-in-the-middle, MiTM). В данной работе этот подход применяется к задаче Lear­ning with Errors (LWE) с секретом малой длины. Задача LWE явля­ется одной из самых важных в теории криптографии на решетках. Безопасность большого количества криптографических схем, начиная от простых подписей и схем и заканчивая продвинутыми схемами, такими как групповые подписи и полностью гомоморфное шифрование, основывается на предположениях о сложности LWE. В статье пред­ставлен обзор гибридной атаки, а также используемых в ней алгорит­мов. Это необходимо для дальнейшей практически значимой реализации атаки, главной целью которой является верификация корректности применения метода MiTM к гибридной атаке на LWE.

In 2007, Howgrave-Graham proposed attack against NTRU cryptosys­tem, which consists of two parts, combining lattice reduction technique and a combinatorial method called meet-in-the-middle (MiTM). In this article, we apply hybrid attack to the Learning with Errors Problem (LWE) with sparse sec­ret. The LWE problem is considered to be one of the most important in lat­tice-based cryptography. Large number of cryprographic schemes ranging from basic signature and encryption schemes to advanced schemes like group sig­natures and fully homomorphic encryption, base their security on the hard­ness assumption of LWE. In this paper, we review the hybrid attack and the algorithms it is based on. It is required for further practical implementation of the attack, whose main objective is to verify correctness of MiTM to the hyb­rid attack against the LWE problem.

Рассмотрен вопрос подбора оптимальных параметров для атаки методом редукции решетки с применением BKZ-алгоритма на решет­чатые криптосистемы, использующие решетки с подрешетками малого ранга. Иллюстрируются проблемы некоторых подходов к организации та­ких решетчатых криптосистем. Описаны условия для существо­вания полиномиальной атаки, представлен эффективный алгоритм, находящий параметры для данной атаки. Разработанный алгоритм является довольно быстрым и работает за время, оцениваемое как O(log2n), где n — размерность решетки. Его корректность проверена численными эксперементами. Также приведены графики, связывающие параметры решетки и минимальные необходимые для ее успешной реду­кции параметры.

This article is devoted to selection of optimal parameters for lattice reduction attack against lattice-based cryptosystems that use lattices with low rank sublattices. It illustrates design flaws caused by current approach to buiding these types of cryptosystems. Its relevance and novelty lies in the description of the conditions for the existence of a polynomial attack and in constructing an efficient algorithm that allows us to find optimal reduction attack parameters. The algorithm developed during the work on this article is quite fast and requires of time to return results where is the di­men­sion of lattice. Its correctness has been verified by numerical experiments. As a result, graphs are shown connecting the parameters of the lattice and the minimum smallest parameters necessary for its successful reduction.

Рассмотрены основные проблемы, решение которых необходимо для обес­печения безопасности конфиденциальности коммуникации между участниками мобильных меш-сетей на основе смартфонов. Представ­лены важные характеристики технологий Bluetooth и Bluetooth Low En­ergy, с помощью которых можно решить часть проблем. Кратко описа­на криптография на эллиптических кривых, выбрана конкретная кри­вая. На основе обмена ключами на эллиптических кривых и различных криптопримитивов построена гибридная модель шифрования, позво­ля­ю­щая обмениваться защищенной информацией с использованием сим­мет­ричного шифрования. Показаны процессы зашифрования и рас­шиф­ро­вания сообщений с использованием данной схемы. В результате опи­сан­ные технологии и гибридная схема объединяются в базовый алго­ритм защищенной передачи данных по меш-сети на основе Bluetooth, до­ста­точный для программной реализации.

In the paper we discuss the main problems that have to be solved to en­sure the confidentiality of communication between the nodes of mesh networks based on smartphones. We describe the important details of Bluetooth and Bluetooth Low Energy technologies, using which you can solve some of the problems described. Next, we briefly describe elliptic curve cryptography and choose a specific curve for it. We build an Elliptic Curve Integrated Encryp­tion Scheme based on the elliptic curves key exchange and various crypto primitives that allows exchanging protected information using symmetric en­cryption. We also describe the processes of encryption and decryption of mes­sages using this. As a result, the described technologies and the hybrid scheme are combined into the basic algorithm for secure data transmission over a mesh network based on Bluetooth, sufficient for software implementation.

Описан общий принцип работы (этапы, используемые параметры) схемы доказательства с нулевым разглашением zk-SNARK, возможность и перспективы его улучшения. Реализации zk-SNARK, которые извест­ны на данный момент, имеют ограничения масштабируемости, обу­словленные величиной доказываемого вычисления. Во-первых, размер до­казывающего ключа по крайней мере линейно зависит от верхней грани­цы структуры, в которой мы работаем. Во-вторых, при доказатель­стве требуется запись всех предыдущих шагов. В статье описывается алгоритм достижения новой реализации zk-SNARK с использованием криптографии на эллиптических кривых, особенностей структуры по­ля и цельности доказательств. Практически такая реализация являет­ся рекурсивной композицией доказательства, при этом генерация клю­чей для любых размеров вычислений несет постоянные расходы по па­мяти. В дальнейшем в процессе доказательства осуществляются толь­ко постоянные мультипликативные по времени и аддитивные по па­мяти расходы. Таким образом, описанная реализация zk-SNARK наделя­ется двумя важными свойствами: емкость и инкрементальная вычис­лимость.

This article describes the General principle of operation (stages, parame­ters used) of the ZK-SNARK zero-knowledge proof scheme, the possibility and prospects for its improvement. Implementations of zk-SNARK that are cur­rently known have scalability limitations that depend on the magnitude of the computation being proved. First, the size of the proving key depends at least linearly on the upper bound of the structure in which we work. Second, the proof requires a record of all previous steps. The article describes an algorithm for achieving a new implementation of zk-SNARK using elliptic curve cryp­tography, field structure features, and proof integrity. In practice, this imple­mentation is a recursive composition of the proof, while generating keys for any size of calculations carries constant memory costs. Subsequently, the en­tire process of proof is solely multiplicative constant costs overtime and addi­tivecosts in memory. Thus, the described implementation of zk-SNARK has two important properties: capacity and incremental computability.

Задача вычисления порядка якобиана гиперэллиптической кривой является классической задачей теории чисел с приложениями в совре­менной криптографии. Якобиан кривой используется для построения криптосистем, основанных на дискретном логарифме; как группа боль­шого «неизвестного» порядка в конструкциях верифицируемых функ­ций задержки (VDF) и других приложениях. В статье приводится обзор подходов к ускорению наиболее быстрого алгоритма подсчета точек в якобианах гиперэллиптических кривых — алгоритма Годри — Шоста. Данный алгоритм состоит из двух этапов: 1) нахождение числа точек (характеристического многочлена) по модулю малых простых чисел с объединением результата в один большой модуль по китайской теореме об остатках (полиномиальная часть алгоритма); 2) восстановление полного числа точек из информации по модулю с помощью алгоритмов, основанных на парадоксе дней рождения (экспоненциальная часть алго­ритма). В теории алгоритм терминируется в первой части и имеет полиномиальную сложность , где  — размер конечного поля. Однако на практике полиномиальная часть алгоритма останавливает­ся на некотором простом числе  из-за ограничений по использованию памяти, которая растет как , и полное число точек находят уже по экспоненциальному алгоритму. В данной работе выполнена многопо­точ­ная реализация экспоненциальной части алгоритма Годри — Шос­та на языке программирования C++, дается оценка ее эффективности по затратам времени и памяти.

Computing the order of Jacobian of a hyperelliptic curve is a common number-theoretical problem that has lots of applications in modern cryptog­raphy. Namely, Jacobians are applicable to constructions of DLP-based cryp­tosystems, as well as constructions of verifiable delay functions (VDF’s), since they can be viewed as large groups of unknown order. In this article, we pre­sent an overview of approaches to accelerate Gaudry-Schost point counting algorithm that is the fastest known algorithm for computing the order of Jaco­bians of hyperelliptic curves of genus 2. This algorithm consists of two stages: 1) computing the number of points (equivalently, the characteristic polynomi­al of the curve) modulo some small primes and combining the result into a large module using CRT (polynomial-time part); 2) restoring the number of points utilizing modular data using algorithms based on birthday paradox (exponential-time part). Theoretically, the algorithm terminates after the first stage with time-complexity, where is a finite field modulus. How­ever, in practice we terminate the polynomial-time part (due to high memory consumption), and we proceed to the second, memory-efficient, exponential-time part. This article presents a multithreaded C++ implementation of expo­nential part of Gaudry-Schost’s point counting algorithm. We evaluate the ef­ficiency of our multithreaded implementation.