臺灣博碩士論文加值系統

如何以較弱的密碼學的假設達到安全的通訊一直是密碼學上的重要課題。
本篇論文嘗試以隱密式資料庫搜尋來建構一個安全的密碼學協定，並且把
隱密式資料庫搜尋所定義的安全性降低，討論其是否能夠建構一個完整的
密碼學協定。

We consider the problem of reducing Oblivious Transfer to Private Information Retrieval. We give a simple reduction from 1-out-of-2 Oblivious Transfer to Private Information Retrieval, where the reduction is against malicious players.
We also consider the completeness of Private Information Retrieval on weakened assumption. We will give a impossibility result and a possibility result.

{1}Introduction}{1}
{2}Preliminaries}{4}
{3}Malicious PIR implies OT}{9}
{4}The Completeness of Weak PIR}{12}
{4.1}Definition}{12}
{4.2}Impossibility Results}{12}
{4.3}Reducing Weak OT to Weak PIR}{13}
{Bibliography}{16}

A. Ambainis, "Upper Bound on the Communication Complexity of
Private Information Retrieval", In Proc. of 24th ICALP, 1997.
Y. Aumann, Y. Z. Ding, and M. O. Rabin, "Everlasting Security in
the Bounded Storage Model".
A. Beimel, T. Malkin and S. Micali, "The All-or-Nothing Nature of Two-Party Secure Computation", In Proc. of Crypto 99, 1999.
C. H. Bennett, G. Brassard, C. Crepeau, and U. Maurer,
"Generalized Privacy Amplification", IEEE Transactions of
Information Theory, 41(6), 1995.
G. Brassard, C. Crepeau and J. M. Robert, "All-or-Nothing
Disclosure of Secrets", In Crypto'86, 1987, pp. 234-238.
G. Brassard and C. Crepeau, "Oblivious Transfer and Privacy
Amplification", EUROCRYPT'97, LNCS series, vol. 1223, pp. 334-347. C. Cachin, "On the foundations of Oblivious Transfer",
EUROCRYPT'98, LNCS series, vol.1403, pp. 361-374.
G. Brassard, C. Crepeau, and M. Santha. "Oblivious Transfer and
Intersecting Codes". IEEE Trans. Info. Theory, vol. 42, No. 6, pp.
1769-1780. 1996.
C. Cachin, "On the Foundations of Oblivious Transfer",
EUROCRYPT'98, LNCS series, vol. 1403, pp. 361-374.
C. Cachin, C. Crepeau, and S. Marcil,"Onlivious Transfer with a
Momory Bounded Receiver", In Proc. of 39th FOCS, 1998.
C. Cachin and U. Maurer, "Unconditional Security Against Memory
Bounded Adversaries", In Advances in Cryptology - Crypto'97, 1997.
B. Chor, abd N. Gilboa, "Computationally Private Information
Retrieval", In Proc. of 29th STOC, 1997.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, "Private
Information Retrieval", FOCS 1995, pp. 41-50.
C. Crepeau, "Equivalence Between Two Flavours of Oblivious
Transfer", CRYPTO'87, LNCS series, pp. 350-354.
C. Crepeau, "Efficient Cryptographic Protocols based on Noisy
Channels", Eurocrypt'97, LNCS series, vol. 1233, pp. 306-317.
C. Crepeau and J. Kilian, "Achieving Oblivious Transfer using
Weakened Security Assumptions", FOCS 88, pp. 42-52.
G. D. Crescenzo, T. Malkin, and R. Ostrovsky, "Single Database
Private Information Implies Oblivious Transfer", EUROCRYPT 2000,
LNCS 1807, pp. 122-138.
I. Damg\aa rd, J. Kilian, and L. Salvail, "On the (Im) possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions". EUROCRYPT'99, LNCS 1592, pp.56-73.
A. De-Santis and P. Persiano, "Zero-Knowledge Proofs of Knowledge without Interaction", In Proc. of 33rd FOCS, 1992.
Y. Z. Ding, "Oblivious Transfer in the Bounded Storage Model",
Crypto 2001, pp. 155-170.
S. Even, O. Goldreich, and A. Lempel, "A randomized Protocol for
signing contracts", Communications of the ACM, Vol. 28, No. 6,
1985, pp. 637-647.
U. Feige and A. Shamir, "Witness Indistinguishable and Witness
Hiding Protocols", In Proc. of 23rd STOC, 1990.
O. Goldreich, S. Micali, and A. Wigderson, "How to play ANY mental game", Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, 1987, pp. 218-229.
O. Goldreich, S. Micali, and A. Wigderson, "Proofs that Yield
Nothing but their Validiaty, and a Methodology of Cryptographic
Protocol Design", In Journal of the ACM, vol. 38, 1991, pp.
691-729.
J. Halpern and M.O. Rabin, "A Logic to Reason about likehood",
Proceedings of the 15th Annual ACM Symposium on the Theory of
Computing, 1983, pp. 310-319.
J. Kilian, "A general completeness theorem for 2-party games",
Proceedings of the 23rd Annual ACM Symposium on the Theory of
Computing, 1991, pp. 553-560.
J. Kilian, "Founding Cryptography on Oblivious Transfer", STOC
1988, pp. 20-31.
U. Maurer and S. Wolf, "Privacy Amplification Secure Against
Active Adversaries", In Advances in Cryptology - Crypto'97, 1997.
M. Naor, "Bit Commitment Using Pseudorandom Generators", Journal
of cryptology 1991, pp. 151-158.