Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Efficient K-Nearest Neighbor Query Processing in Metric Spaces Based on Precise Radius Estimation

 

Can Şardan
MSc. Student
Computer Engineering Department
Bilkent University

Function sharing deals with the problem of distribution of the computation of a function (such as decryption or signature) among several parties. The necessary values for the computation are distributed to the participating parties using a secret sharing scheme (SSS). Several function sharing schemes have been proposed in the literature, with most of them using Shamir secret sharing as the underlying SSS. In this work, we investigate how threshold cryptography can be conducted with the RSA cryptosystem. The challenge is that constructing the secret in a linear SSS requires the solution of a linear system, which normally involves computing inverses, while computing an inverse modulo $\phi(N)$ cannot be tolerated in an RSA system in any way. The threshold RSA scheme we propose is a generalization of Shoup's Shamir-based scheme. It is similarly robust and provably secure under the static adversary model. We also show how this scheme can be extended to other public key cryptosystems and give examples on Paillier decryption and Digital Signature Standard (DSS) signatures. Multipartite access structures are more general access structures than threshold access structures. To investigate secret sharing schemes using these access structures, we used Mignotte and Asmuth-Bloom secret sharing schemes which are based on Chinese remainder theorem (CRT). An interesting question to answer in CRT based secret sharing schemes is whether one can find a Mignotte or Asmuth-Bloom sequence for an arbitrary access structure. We modified Galibus and Matveev's work on secret sharing using polynomials to work with integers. They proved that any access structure can be realized with their approach. We implemented the modified Galibus and Matveev algorithm that work with integers. We also propose another more practical method of generating Asmuth-Bloom sequences for multipartite access structures. The proposed method increases the number of shares and hence decreases the information rate but the information rate is significantly better compared to the modified method of Galibus and Matveev. We also show how threshold RSA signatures can be computed using the proposed SSS as the underlying SSS.

 

DATE: 27 August,2009, Thursday @ 13:30
PLACE: EA 409