Polynomial reconstruction based cryptography.

摘要

An important direction in Cryptographic Research is the identification and investigation of hard computational problems upon which the security of cryptographic primitives and protocols can be based. This is important because: (i) the properties of a certain cryptographic primitive depend to a great extent on the properties of the underlying hard computational problem that is used as an intractability assumption. Employing new plausible intractability assumptions with rich algebraic structure would presumably give rise to cryptographic primitives with unique and novel properties; (ii) the listing of “hard” computational problems that has been utilized in the design of cryptographic primitives is not very large; this motivates the investigation of novel cryptographic assumptions, as different problems will most likely react differently in stronger adversarial models that become feasible with technical/technological advances.; In this thesis, the Problem of Reed-Solomon Codes Decoding—a well-known computational problem in the theory of Error-Correcting Codes, also known as Polynomial Reconstruction (PR)—is considered from the cryptographic hardness perspective. Following the standard methodology in the cryptographic literature which includes the investigation of a Decisional Intractability Assumption related to PR as well as the establishment of results such as Hardness of Partial Information Extraction and Pseudorandomness, we lay out the theoretical framework for the exploitation of PR in Cryptography.; Subsequently, we present a wide array of concrete applications of PR in Cryptography: (i) basic primitives, such as a probabilistic one-way function with strong concealment properties which gives rise to commitment schemes with unique properties; (ii) symmetric encryption methods with strong security properties such as forward secrecy, computational perfect secrecy, and key-equivalence; (iii) a generic protocol for efficient secure function evaluation over the domain of polynomial expressions. We also consider applications of our work in the Coding Theoretic setting: we investigate the solvability of Interleaved Reed-Solomon Codes Decoding in the presence of random errors, and we discover interesting hardness/self-reducibility tradeoffs in Decoding Problems (including the PR problem). Finally we describe directions for future research that are spawned from the results of this thesis.