Sarad Venugopalan Home Page

Welcome to data.at.preempted.net
Tuesday, October 17 2017 @ 08:27 PM UTC

View Printable Version

ILP formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems

To fully benefit from a multiprocessor system, the tasks of a program are to be carefully assigned and scheduled on the processors of the system such that the overall execution time is minimal. The associated task scheduling problem with communication delays, P|prec; cij |Cmax, is a well known NP-hard problem. We propose a novel Mixed Integer Linear Programming (MILP) solution to this scheduling problem, despite the fact that scheduling problems are often difficult to handle by MILP solvers. The proposed MILP solution uses problem specific knowledge to eliminate the need to linearise the bilinear equations arising out of communication delays. Further, the size of the proposed formulation in terms of variables is independent of the number of processors. We analyse and discuss the influence of the different MILP components in respect to characteristics of the task graph such as structure and communication to computation ratio. The proposed MILP formulation is experimentally compared with previous MILP formulations used to solve this scheduling problem. The proposed formulation displays a drastic improvement in performance, which allows to solve larger problems optimally. We also observe strengths and weaknesses of the formulation related to the input characteristics.

[IEEEXplore Abstract]

[OPTAli14 Presentation]

View Printable Version

First Order Correlation Attack on a Geffe Generator

First Order Correlation Attack on a Geffe Generator

Read PDF

View Printable Version

String Art: Circle Drawing Using Straight Lines

ArticlesAbstract: An algorithm to generate the locus of a circle using the intersection points of straight lines is proposed. The pixels on the circle are plotted independent of one another and the operations involved in finding the locus of the circle from the intersection of straight lines are parallelizable. Integer only arithmetic and algorithmic optimizations are used for speedup. The proposed algorithm makes use of an envelope to form a parabolic arc which is consequent transformed into a circle. The use of parabolic arcs for the transformation results in higher pixel errors as the radius of the circle to be drawn increases. At its current state, the algorithm presented may be suitable only for generating circles for string art.

Read Full

View Printable Version

Improved Interference Diversity in Multicellular OFDMA Systems

ArticlesAbstract: Orthogonal frequency division multiple access (OFDMA) is becoming a popular technology choice for leading next generation wireless networks. The IEEE 802.16e based systems are the first standardized wireless networks which have incorporated OFDMA. We investigate the use of interference diversity in IEEE 802.16e based networks by considering subchannel formation in different cells. We propose a method for quantifying the interference diversity using suitable arguments and results. Based on these results, a new method for forming subchannels in an 802.16e system is presented.
Read PDF
Presentation slides(PDF)
View Printable Version

Applications to Chinese Remainder Theorem

ArticlesAbstract We demonstrate the usefulness of a simple mathematical result- the Chinese Remainder Theorem (CRT). A short informal introduction is followed by a formal analysis of the Chinese Remainder Theorem.Further, we discuss how the Chinese Remainder Theorem can leak information and why caution is to be exercised when applied to a k-threshold system for secret sharing and also for clever RSA variants, namely RSA-CRT and Rebalanced-RSA-CRT.

Read PDF

View Printable Version

RSA Encryption Algorithm in a Nut Shell

ArticlesAbstract To analyze the RSA encryption algorithm and present a working implementation in python. We discuss the mathematical results and see why the math works. The proofs of various number theoretic results subsequently discussed are available in books mentioned in the bibliography and thus omitted. Detailed discussions on big oh notation, time complexity of basic bit operations, Euclidean and extended Euclidean algorithm, time complexity of Euclidean algorithm, time complexity of extended Euclidean algorithm, linear congruences, Euler totient function, Fermats little theorem, Euler's theorem, the Miller-Rabin test are presented. With this mathematical background we then analyze the RSA algorithm followed by a simplifed example. Finally, the documented python code for the RSA algorithm is presented and is hoped to be of use for serious programmers who intend on implementing the algorithm on a workstation.

Read PDF

View Printable Version

Mini Project on Secure E-Banking

ArticlesFunctionality E-Banking is vulnerable to numerous attacks as it deals with online digital cash transactions. It is hence important to use publicly acclaimed cryptographic algorithms that have been under scrutiny and cryptanalysis for numerous years. We choose a symmetric key cryptosystem such as Blowfish for our implementation. Though encrypted, the transactions between the two banks are still vulnerable to block replay attacks by a man in the middle. To thwart this attack we use a suitable chaining mode such as Cipher Block Chain with checksum (CBCC). A separate Initialization Vector (IV) is generated for chaining each transaction, using a fast Pseudo Random Number Generator (PRNG) with a large period. We use one such PRNG known as Mersenne Twister (MT19937). The public keys of Bank A and Bank B are authenticated by a Certifying Authority (CA). The application is implemented by writing a client and server program using Berkley Sockets. This application assumes the existence of a CA and doesn't implement any Public Key cryptosystem.
report.zip
mt.zip
serverecode.zip
clientcode.zip
testing.zip
View Printable Version

Cryptanalysis of Linear Congruence Generators

ArticlesMultiplicative congruential generators have been first suggested by D.H.Lehmer as an arithmetic procedure to generate pseudo random numbers. A mild variation of it is the linear congruence generator. Over many years both these generators were widely used in simulations and reported to have good statistical properties and favorable cycle length. Cryptanalysts have come up with numerous complex methods to cryptanalyze the generators mentioned above. We discuss a simple method to cryptanalyze both multiplicative and linear congruence generators, which make them unsuitable as raw input to simulations and various cryptosystem. Note: This work is attributed to [1].

Read PDF

View Printable Version

Man in the Middle Attack on the Analog of Massey Omura over Elliptic Curves

ArticlesThe man in the middle attack (MITM) on the analog of Massey Omura over Elliptic curves may look confusing but is trivial and is as discussed.

Read PDF

View Printable Version

Introduction to Elliptic Curves-A prequel

ArticlesElliptic curve cryptography, a few more basics.

Read PDF