Source author record

Virendra Sule

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

5works
4topics
1close collaborators

Published work

5 publications

preprint2022arXiv

A Complete algorithm for local inversion of maps: Application to Cryptanalysis

For a map (function) $F(x):\ftwo^n\rightarrow\ftwo^n$ and a given yy in the image of FF the problem of \emph{local inversion} of FF is to find all inverse images xx in $\ftwo^n$ such that y=F(x)y=F(x). In Cryptology, such a problem arises in Cryptanalysis of One way Functions (OWFs). The well known TMTO attack in Cryptanalysis is a probabilistic algorithm for computing one solution of local inversion using O(N)O(\sqrt N) order computation in offline as well as online for N=2nN=2^n. This paper proposes a complete algorithm for solving the local inversion problem which uses linear complexity for a unique solution in a periodic orbit. The algorithm is shown to require an offline computation to solve a hard problem (possibly requiring exponential computation) and an online computation dependent on yy that of repeated forward evaluation F(x)F(x) on points xx in $\ff_{2^n}$ which is polynomial time at each evaluation. However the forward evaluation is repeated at most as many number of times as the Linear Complexity of the sequence {y,F(y),…}\{y,F(y),\ldots\} to get one possible solution when this sequence is periodic. All other solutions are obtained in chains {e,F(e),…}\{e,F(e),\ldots\} for all points ee in the Garden of Eden (GOE) of the map FF. Hence a solution xx exists iff either the former sequence is periodic or a solution occurs in a chain starting from a point in GOE. The online computation then turns out to be polynomial time O(Lk)O(L^k) in the linear complexity LL of the sequence to compute one possible solution in a periodic orbit or O(l)O(l) the chain length for a fixed nn. Hence this is a complete algorithm for solving the problem of finding all rational solutions xx of the equation F(x)=yF(x)=y for a given yy and a map FF in $\ff_{2^n}$.

preprint2022arXiv

Local inversion of maps: A new attack on Symmetric encryption, RSA and ECDLP

This paper presents algorithms for local inversion of maps and shows how several important computational problems such as cryptanalysis of symmetric encryption algorithms, RSA algorithm and solving the elliptic curve discrete log problem (ECDLP) can be addressed as local inversion problems. The methodology is termed as the \emph{Local Inversion Attack}. It utilizes the concept of \emph{Linear Complexity} (LC) of a recurrence sequence generated by the map defined by the cryptanalysis problem and the given data. It is shown that when the LC of the recurrence is bounded by a bound of polynomial order in the bit length of the input to the map, the local inversion can be accomplished in polynomial time. Hence an incomplete local inversion algorithm which searches a solution within a specified bound on computation can estimate the density of weak cases of cryptanalysis defined by such data causing low LC. Such cases can happen accidentally but cannot be avoided in practice and are fatal insecurity flaws of cryptographic primitives which are wrongly assumed to be secure on the basis of exponential average case complexity. An incomplete algorithm is proposed for solving problems such as key recovery of symmetric encryption algorithms, decryption of RSA ciphertext without factoring the modulus, decrypting any ciphertext of RSA given one plaintext ciphertext pair created with same public key in chosen ciphertext attack and solving the discrete logarithm on elliptic curves over finite fields (ECDLP) as local inversion problems. It is shown that when the LCs of the respective recurrences for given data are small, solutions of these problems are possible in practically feasible time and memory resources.

preprint2014arXiv

An algorithm for Boolean satisfiability based on generalized orthonormal expansion

This paper proposes an algorithm for deciding consistency of systems of Boolean equations in several variables with co-efficients in the two element Boolean algebra B0={0,1}B_{0}=\{0,1\} and find all satisfying assignments. The algorithm is based on the application of a well known generalized Boole-Shannon orthonormal (ON) expansion of Boolean functions. A necessary and sufficient consistency condition for a special class of functions was developed in \cite{sule} using such an expansion. Paper \cite{sule} develops a condition for consistency of the equation f(X)=0f(X)=0 for the special classes of Boolean functions 1) ff in B(Φ(X))B(Φ(X)) for an ON set ΦΦ of Boolean functions in XX over a general Boolean algebra BB and 2) ff in B(X2)(Φ(X1))B(X_{2})(Φ(X_{1})). The present paper addresses the problem of obtaining the consistency conditions for arbitrary Boolean functions in B0(X)B_{0}(X). Next, the consistency for a single equation is shown equivalent to another system of Boolean equations which involves the ON functions and characterizes all solutions. This result is then extended for Boolean systems in several variables over the algebra B0={0,1}B_{0}=\{0,1\} which does not convert the system into a single equation. This condition leads to the algorithm for computing all solutions of the Boolean system without using analogous resolution and determine satisfiability. For special systems defined by CNF formulas this algorithm results into an extension of the DPLL algorithm in which the \emph{splitting rule} is generalized to several variables in terms of ON terms in the sense that splitting of CNF set in a single variable xx is equivalent to ON terms x,x′x,x'.

preprint2014arXiv

Generalized cofactors and decomposition of Boolean satisfiability problems

We propose an approach for decomposing Boolean satisfiability problems while extending recent results of \cite{sul2} on solving Boolean systems of equations. Developments in \cite{sul2} were aimed at the expansion of functions ff in orthonormal (ON) sets of base functions as a generalization of the Boole-Shannon expansion and the derivation of the consistency condition for the equation f=0f=0 in terms of the expansion co-efficients. In this paper, we further extend the Boole-Shannon expansion over an arbitrary set of base functions and derive the consistency condition for f=1f=1. The generalization of the Boole-Shannon formula presented in this paper is in terms of \emph{cofactors} as co-efficients with respect to a set of CNFs called a \emph{base} which appear in a given Boolean CNF formula itself. This approach results in a novel parallel algorithm for decomposition of a CNF formula and computation of all satisfying assignments when they exist by using the given data set of CNFs itself as the base.

preprint2013arXiv

Generalization of Boole-Shannon expansion, consistency of Boolean equations and elimination by orthonormal expansion

The well known Boole-Shannon expansion of Boolean functions in several variables (with co-efficients in a Boolean algebra BB) is also known in more general form in terms of expansion in a set ΦΦ of orthonormal functions. However, unlike the one variable step of this expansion an analogous elimination theorem and consistency is not well known. This article proves such an elimination theorem for a special class of Boolean functions denoted B(Φ)B(Φ). When the orthonormal set ΦΦ is of polynomial size in number nn of variables, the consistency of a Boolean equation f=0f=0 can be determined in polynomial number of BB-operations. A characterization of B(Φ)B(Φ) is also shown and an elimination based procedure for computing consistency of Boolean equations is proposed.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.