Private collaborative forecasting and benchmarking

ABSTRACT

Suppose a number of hospitals in a geographic area want to learn how their own heart-surgery unit is doing compared with the others in terms of mortality rates, subsequent complications, or any other quality metric. Similarly, a number of small businesses might want to use their recent point-of-sales data to cooperatively forecast future demand and thus make more informed decisions about inventory, capacity, employment, etc. These are simple examples of cooperative benchmarking and (respectively) forecasting that would benefit all participants as well as the public at large, as they would make it possible for participants to avail themselves of more precise and reliable data collected from many sources, to assess their own local performance in comparison to global trends, and to avoid many of the inefficiencies that currently arise because of having less information available for their decision-making. And yet, in spite of all these advantages, cooperative benchmarking and forecasting typically do not take place, because of the participants' unwillingness to share their information with others. Their reluctance to share is quite rational, and is due to fears of embarrassment, lawsuits, weakening their negotiating position (e.g., in case of over-capacity), revealing corporate performance and strategies, etc. The development and deployment of <i>private</i> benchmarking and forecasting technologies would allow such collaborations to take place without revealing any participant's data to the others, reaping the benefits of collaboration while avoiding the drawbacks. Moreover, this kind of technology would empower smaller organizations who could then cooperatively base their decisions on a much broader information base, in a way that is today restricted to only the largest corporations. This paper is a step towards this goal, as it gives protocols for forecasting and benchmarking that reveal to the participants the desired answers yet do not reveal to any participant any other participant's private data. We consider several forecasting methods, including linear regression and time series techniques such as moving average and exponential smoothing. One of the novel parts of this work, that further distinguishes it from previous work in secure multi-party computation, is that it involves floating point arithmetic, in particular it provides protocols to securely and efficiently perform division.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: K. Allan, M. Stemper, and O. Tucker. Collaborative forecasting. http://e-business.pwcglobal.com/pdf/ CollaborativeForecasting.pdf.
• 3: Helmut Alt, Comparing the combinational complexities of arithmetic functions, Journal of the ACM (JACM), v.35 n.2, p.447-460, April 1988 [doi>10.1145/42282.214084]
• 4: M. Atallah, M. Bykova, J. Li, and M. Karahan. Secure collaborative forecasting and benchmarking. Technical Report CERIAS TR 2004--22, Purdue University, 2004.
• 5: Mikhail J. Atallah , Wenliang Du, Secure Multi-party Computational Geometry, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.165-179, August 08-10, 2001
• 6: M. Atallah, H. Elmongui, V. Deshpande, and L. Schwarz. Secure supply-chain protocols. In IEEE International Conference on Electronic Commerce, pages 293--302, 2003.
• 7: Olivier Baudron , Jacques Stern, Non-interactive Private Auctions, Proceedings of the 5th International Conference on Financial Cryptography, p.364-378, February 19-22, 2002
• 8: P. Beame, S. Cook, and H. Hoover. Log depth circuits for division and related problems. In Annual IEEE Symposium on Foundations of Computer Science, pages l--6, 1984.
• 9: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 10: Collaborative planning, forecasting, and replenishment (CPFR). http://www.cpfr.org/Members.html.
• 11: Wenliang Du , Mikhail J. Atallah , Eugene H. Spafford, A study of several specific secure two-party computation problems, 2001
• 12: Wenliang Du , Mikhail J. Atallah, Privacy-Preserving Cooperative Scientific Computations, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.273, June 11-13, 2001
• 13: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 14: J. Evans. Applied production and operations management. West Publishing Company, 4th edition, 1993.
• 15: G. Fliedner. Collaborative planning, forecasting, and replenishment in the retail supply chain. Decision and Information Sciences Department, Oakland University.
• 16: O. Goldreich. Secure multi-party computation. http://www.wisdom.weizmann.ac.il/home/oded/public_html/pp.html, 2001.
• 17: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 18: Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259405]
• 19: John galt solution, inc. http://www.johngalt.com/.
• 20: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 21: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 22: T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In Advances in Cryptology - EUROCRYPT'98, volume 1403 of LNCS, pages 308--318, 1998.
• 23: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 24: A. Schoehage and V. Strassen. Schnelle multiplikation grosser zahlen. Computing, 7:281--292, 1971.
• 25: H. Singh. Collaborative forecasting. http://www.supplychain.com/docs/collaborativeforecasting.pdf, 2002.
• 26: W. Stevenson. Production/Operations Management. Richard D. Irwin, Inc., 4th edition, 1993.
• 27: A. Yao. Protocols for secure computations. In Annual IEEE Symposium on Foundations of Computer Science, 1982.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Design, Security

Keywords:
benchmarking, e-commerce, forecasting, privacy, secure multi-party computation, secure protocol