Article

Secure computations in a minimal model using multiple-valued ESOP expressions

Authors:

Takaaki Mizuki,

Hideaki SoneAuthors Info & Claims

TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of Computation

Pages 547 - 554

https://doi.org/10.1007/11750321_52

Published: 15 May 2006 Publication History

Abstract

This paper deals with secure computations in a minimal model, and gives a protocol which securely computes every function by means of the techniques of exclusive-or sum-of-products (ESOP) expressions. The communication complexity of our protocol is proportional to the size of an obtained multiple-valued-input ESOP expression. Since the historical research on minimizing ESOP expressions is now still active, our protocol will turn to an efficient one as this research progresses. Thus, this paper gives an application of ESOP expressions to designing cryptographic protocols, and we hope that it would motivate further research on minimizing ESOP expressions.

References

[1]

C. Cachin and J. Camenisch, "Optimistic fair secure computation," Proc. CRYPTO 2000, Lecture Notes in Computer Science, vol. 1880, pp. 93-111, Springer-Verlag, 2000.

Digital Library

[2]

C. Cachin, J. Camenisch, J. Kilian, and J. Müller, "One-round secure computation and secure autonomous mobile agents," Proc. ICALP 2000, Lecture Notes in Computer Science, vol. 1853, pp. 512-523, Springer-Verlag, 2000.

Digital Library

[3]

U. Feige, J. Kilian, and M. Naor, "A minimal model for secure computation," Proceedings of the 26th ACM Symposium on Theory of Computing (STOC '94), pp. 554-563, 1994.

Digital Library

[4]

H. Fleisher, M. Tavel, and J. Yeager, "A computer algorithm for minimizing Reed-Muller canonical forms," IEEE Transactions on Computers, vol. 36, no. 2, pp. 247- 250, 1987.

Digital Library

[5]

A. Gaidukov, "Algorithm to derive minimum esop for 6-variable. function," Proceedings of the fifth International Workshop on Boolean Problems, 2002.

[6]

A. Gál and A. Rosén, "A theorem on sensitivity and applications in private computation," SIAM Journal on Computing, vol. 31, no. 5, pp. 1424-1437, 2002.

Digital Library

[7]

A. Gál and A. Rosén, "Lower bounds on the amount of randomness in private computation," Proceedings of the 35th ACM Symposium on Theory of Computing (STOC '03), pp. 659-666, 2003.

Digital Library

[8]

O. Goldreich, "Foundations of Cryptography II: Basic Applications," Cambridge University Press, Cambridge, 2004.

Digital Library

[9]

T. Hirayama, Y. Nishitani, and T. Sato, "A faster algorithm of minimizing ANDEXOR expressions," IEICE Trans. Fundamentals, vol. E85-A, no. 12, pp. 2708- 2714, 2002.

[10]

Y. Ishai and E. Kushilevitz, "Private simultaneous messages protocols with applications," Proceedings of the fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), pp. 174-183, 1997.

Digital Library

[11]

E. Kushilevitz, R. Ostrovsky, and A. Rosén, "Characterizing linear size circuits in terms of privacy," Journal of Computer and System Sciences, vol. 58, no. 1, pp. 129-136, 1999.

Digital Library

[12]

T. Sasao, "EXMIN2: a simplification algorithm for exclusive-or sum-of-products expressions for multiple-valued-input two-valued-output functions," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 5, pp. 621-632, 1993.

Digital Library

[13]

T. Sasao, "Switching Theory for Logic Synthesis," Kluwer Academic Publishers, Boston, MA, 1999.

Digital Library

[14]

T. Sasao and P. Besslich, "On the complexity of mod-2 sum PLA's," IEEE Transactions on Computers, vol. 39, no. 2, pp. 262-266, 1990.

Digital Library

[15]

N. Song and M. A. Perkowski, "Minimization of exclusive sum-of-products expressions for multiple-valued input, incompletely specified functions," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 4, pp. 385-395, 1996.

Digital Library

[16]

S. Stergiou and G. Papakonstantinou, "Exact minimization of ESOP expressions with less than eight product terms," Journal of Circuits, Systems and Computers, vol. 13, no. 1, pp. 1-15, 2004.

[17]

S. Stergiou, D. Voudouris, and G. Papakonstantinou, "Multiple-value exclusive-or sum-of-products minimization algorithms," IEICE Trans. Fundamentals, vol. E87- A, no. 5, pp. 1226-1234, 2004.

[18]

A. Yao, "Protocols for secure computations," Proceedings of the 23th IEEE Symposium on Foundations of Computer Science (FOCS '82), pp. 160-164, 1982.

Digital Library

[19]

Y. Ye and K. Roy, "An XOR-based decomposition diagram and its application in synthesis of AND/XOR networks," IEICE Trans. Fundamentals, vol. E80-A, no. 10, pp. 1742-1748, 1997.

Cited By

Mizuki TKugimoto YSone H(2007)Secure multiparty computations using a dial lockProceedings of the 4th international conference on Theory and applications of models of computation10.5555/1767854.1767901(499-510)Online publication date: 22-May-2007
https://dl.acm.org/doi/10.5555/1767854.1767901

Index Terms

Secure computations in a minimal model using multiple-valued ESOP expressions

Index terms have been assigned to the content through auto-classification.

Recommendations

Multiple-Valued Logic Charge-Coupled Devices

A new method to implement multiple-valued logic in large scale integrated circuits is introduced. The data are represented by discrete amounts of charge in a charge-coupled device. In this paper the design principles and realizations in four-valued ...
High-Speed Area-Efficient Multiplier Design Using Multiple-Valued Current-Mode Circuits

Presents a very-large-scale-integration (VLSI)-oriented high-speed multiplier design method based on carry-propagation-free addition trees and a circuit technique, so-called multiple-valued current-mode (MVCM) circuits. The carry-propagation-free ...
Implementation of Multiple-Valued Flip-Flips Using Pass Transistor Logic
DSD '04: Proceedings of the Digital System Design, EUROMICRO Systems

This paper presents the realization of multiple-valued flip-flops (MVFF) using Pass Transistor logic. Realization of MVFF has been discussed by many authors. The existing techniques are mainly extensions of binary flip-flops, based on CMOS or TTL logic. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of Computation

May 2006

792 pages

ISBN:3540340211

Editors:
Jin-Yi Cai
Computer Sciences Department, University of Wisconsin, Madison, WI
,
S. Barry Cooper
School of Mathematics, University of Leeds, Leeds, WI, U.K.
,
Angsheng Li
State Key Lab. of Computer Science, Institute of Software, Chinese Academy of Sciences, Leeds, WI

Sponsors

Institute of Software, Chinese Academy of Sciences
NSF of China: The National Natural Science Foundation of China
Chinese Academy of Sciences

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 May 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mizuki TKugimoto YSone H(2007)Secure multiparty computations using a dial lockProceedings of the 4th international conference on Theory and applications of models of computation10.5555/1767854.1767901(499-510)Online publication date: 22-May-2007
https://dl.acm.org/doi/10.5555/1767854.1767901

View Options

View options

Media

Figures

Other

Tables

View Table of Contents