Nav: Home

An MSU-based researcher developed an algorithm to improve information security tools

July 13, 2018

Cryptography is a science of data encryption providing its confidentiality and integrity. After cryptographic transformations (the basis of encryption algorithms) are applied, only the users that possess a relevant key can have access to the initial text.

Transformations based on elliptical curves have been widely used for data protection recently. They are able to provide the same security levels as other types of cryptographic algorithms but require substantially shorter keys.

Transformations based on elliptical curves are in high demand due to the fact that modern technologies aim at the reduction of memory and computational power consumption. Until recently people used desktop devices connected to power sources, and this issue was not a burning one. However, today mobile devices, sim cards, portable devices, and sensors became widely spread. They usually have small dimensions and are limited in accumulator capacity and computational power. At the same time, mobile devices, blockchain technologies, and the Internet of things require additional safety measures, causing the demand for new algorithms of cryptographic transformations with lower computational power consumption to increase. The Internet of things is a concept according to which devices communicate not only with the users, but also with each other. For example, a door and a lighting system may communicate as follows: when someone opens a door to enter the room, lights turn on, and when the door is opened and someone leaves the room, the lights go off. Blockchain technologies also cover the Internet of things and personal mobile devices and are based on the digital signature technology.

The main mathematical operation in transformations based on elliptical curves is scalar multiplication. In the course of it a point on an elliptical curve is multiplied by a parameter (scalar). The main disadvantage of scalar multiplication is its high calculational complexity which may be reduced by using new efficient algorithms with lower complexity and therefore lower computational power consumption.

"In the course of the study we found an algorithm and identified different parameters of its operation. When these parameters are used, and depending on available memory volumes and the value of the scalar, the algorithm allows us to perform scalar multiplication - the main operation on the elliptical curve - with minimum computational power consumption," said Denis Khleborodov, the author of the article, PhD, CCIE Security, and a researcher at MSU.

The new algorithm is based on window non-adjacent form of scalar representation that is classified as an algorithm with a precomputation step. Precomputations are single-time calculations that are performed before the main part of the work, and their results are saved in the memory. The main advantage of algorithms with precomputations is the division of calculation into two parts: the precomputations themselves followed by the new calculations reusing their results. Therefore, the computational complexity of consecutive scalar multiplication operations is reduced.

The author also performed comparative analysis of the obtained result with another effective algorithm based on the same method. The scientist managed to reduce the average computational complexity of the precomputation stage by 5% to 46%, and of the main stage - by 4% to 22% depending on the input data.

The new algorithm may be used on blockchain platforms for digital signing of transactions and authentication, as well as on the Internet of things for the authentication of its devices, in session keys development protocols for the encryption of transferred data, and to secure the integrity of transmitted information.

"We expect to develop an improved algorithm based on the sliding window non-adjacent form of scalar representation, i.e. with changeable parameters of precomputations. We also want to adapt the algorithms for simultaneous calculations. The results may be used in security features of the Internet of things and blockchain platforms," concluded the scientist.

Lomonosov Moscow State University

Related Algorithm Articles:

Scientists use algorithm to peer through opaque brains
A new algorithm helps scientists record the activity of individual neurons within a volume of brain tissue.
Algorithm generates origami folding patterns for any shape
A new algorithm generates practical paper-folding patterns to produce any 3-D structure.
New algorithm tracks neurons in bendy brain of freely crawling worm
Scientists at Princeton University have developed a new algorithm to track neurons in the brain of the worm Caenorhabditis elegans while it crawls.
Does my algorithm work? There's no shortcut for community detection
Community detection is an important tool for scientists studying networks, but a new paper published in Science Advances calls into question the common practice of using metadata for ground truth validation.
'Cyclops' algorithm spots daily rhythms in cells
Humans, like virtually all other complex organisms on Earth, have adapted to their planet's 24-hour cycle of sunlight and darkness.
An algorithm that knows when you'll get bored with your favorite mobile game
Researchers from the Tokyo-based company Silicon Studio, led by Spanish data scientist África Periáñez, have developed a new algorithm that predicts when a user will leave a mobile game.
Algorithm identified Trump as 'not-married'
Scientists from Russia and Singapore created an algorithm that predicts user marital status with 86% precision using data from three social networks instead of one.
A novel positioning algorithm based on self-adaptive algorithm
Much attention has been paid to the Taylor series expansion (TSE) method these years, which has been extensively used for solving nonlinear equations for its good robustness and accuracy of positioning.
Algorithm can create a bridge between Clinton and Trump supporters
The article that received the best student-paper award in the Tenth International Conference on Web Search and Data Mining (WSDM 2017) builds algorithmic techniques to mitigate the rising polarization by connecting people with opposing views -- and evaluates them on Twitter.
Deep learning algorithm does as well as dermatologists in identifying skin cancer
In hopes of creating better access to medical care, Stanford researchers have trained an algorithm to diagnose skin cancer.

Related Algorithm Reading:

Introduction to Algorithms, 3rd Edition (The MIT Press)
by Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)

Algorithms (4th Edition)
by Robert Sedgewick (Author), Kevin Wayne (Author)

The Algorithm Design Manual
by Steven S Skiena (Author)

Grokking Algorithms: An illustrated guide for programmers and other curious people
by Aditya Bhargava (Author)

by Sanjoy Dasgupta Algorithms (Author), Christos H. Papadimitriou Algorithms (Author), Umesh Vazirani Algorithms (Author)

Algorithm Design
by Jon Kleinberg (Author), Éva Tardos (Author)

Once Upon an Algorithm: How Stories Explain Computing (The MIT Press)
by Martin Erwig (Author)

Algorithms of Oppression: How Search Engines Reinforce Racism
by Safiya Noble (Author)

Computer Vision: Algorithms and Applications (Texts in Computer Science)
by Richard Szeliski (Author)

Understanding Machine Learning: From Theory to Algorithms
by Shai Shalev-Shwartz (Author), Shai Ben-David (Author)

Best Science Podcasts 2018

We have hand picked the best science podcasts for 2018. Sit back and enjoy new science podcasts updated daily from your favorite science news services and scientists.
Now Playing: TED Radio Hour

Unintended Consequences
Human innovation has transformed the way we live, often for the better. But as our technologies grow more powerful, so do their consequences. This hour, TED speakers explore technology's dark side. Guests include writer and artist James Bridle, historians Yuval Noah Harari and Edward Tenner, internet security strategist Yasmin Green, and journalist Kashmir Hill.
Now Playing: Science for the People

#499 Technology, Work and The Future (Rebroadcast)
This week, we're thinking about how rapidly advancing technology will change our future, our work, and our well-being. We speak to Richard and Daniel Susskind about their book "The Future of Professions: How Technology Will Transform the Work of Human Experts" about the impacts technology may have on professional work. And Nicholas Agar comes on to talk about his book "The Sceptical Optimist" and the ways new technologies will affect our perceptions and well-being.