Dietmar Trippner

Stefan Rude

Andreas Schreiber

Challenges for Digital Product and Process Design Systems at BMW

Keywords: Systems Engineering, PDM, TDM, CAE, Simulation, RFLP, Codex of PLM Openness (CPO)

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Dr. Dietmar Trippner, Dr. Stefan Rude, Dr. Andreas Schreiber dietmar.trippner, stefan.rude, andreas.as.schreiber@bmw.de Abstract. The methods of model based product development are today well understood by industry across branches as in automotive and aerospace including their supply chain. Actual challenges of these industries however let question the capacity of the concept. Such major changes in Automotive are light weight design, electro-mobility as well as modern mobility concepts, all increasing the product complexity. Increasingly an overall approach is requested that is able to consistently integrate Requirements, Functions, Logic and Physics (RFLP approach). Not only with regards to mechanical aspects, but also considering demands of electric/electronic as well as software development. The Systems Engineering approach is addressing the consistent availability and linkage of product information. Well established in aerospace and defence since decades the concept arrives in Automotives just right now, driven for example by the introduction of integrated product development environments. However the Systems Engineering introduction to an automotive OEM still might be a challenge. Typical obstacles are different structured and detailed design requirements (customer requirements versus vehicle requirements and component characteristics) as well as missing consideration of configuration, effectivity and maturity. Additionally the two dimensions of automotive consistency (Vehicle to component -vertical integration -versus integration of early concept stages via development, verification, approval until the final start of production -horizontal integration) contribute to the challenge. Finally also an improvement of interdisciplinary interaction is needed (mechanics including simulation, electric/electronics and software). The introduction of Systems Engineering is not only challenging the coordination of process IT infrastructure (Authoring systems, TDM and PDM) but also needs to consider organizational aspects (process and appropriate organizational units, integration of design partners and suppliers). Frequent acquisitions among IT system vendors -especially in the CAD/PLM/CAE market -as well as the need to select a system considering functional as well as economic aspects drive the demand for open interfaces. The presentation highlights the success and payoff of the application of Systems Engineering for Automotive processes. Implications for the process IT infrastructure coordination will be introduced. Necessary process IT adaptations will be addressed using target templates for processes, design system infrastructure, integration and mapping. Finally BMW's concept to enforce openness from all OEM, Supplier and System Vendor based on the Codex of PLM Openness (CPO) will be discussed. Success stories as well as lessons learned will be shared.

Introduction

Digital Product-and Process development are getting more and more important at BMW and all related brands, as Mini or Rolls-Royce, for example. See Fig. 1. and Fig. 2. Major challenges in Automotive are light weight design, electro-mobility as well as modern mobility concepts, all increasing the product complexity (see Fig. 3). To meet these different requirements for the development of a complex product program a highly optimized design methodology is needed (see Fig. 4).

Fig. 4. Design process principles

The Systems Engineering V-Model is a good base for such a design process (see Fig. 5).

Fig. 5. The development process in the V-Model

The use of virtualization dramatically increased over the years. But its success was created by introducing many IT applications covering the various aspects of simulation. The next level of efficiency therefore needs to address the topic of consistent integration of all these applications (see Fig. 6).

Fig. 1 .Fig. 2 .

 12 Fig. 1. BMW Group -Company Portrait

Fig. 3 .

 3 Fig. 3. Increased product complexity in product design

Fig. 6 .

 6 Fig. 6. Product design challenges


Prof Alfred Katzenbach
email: alfred.katzenbach@daimler.com

Dr Sebastian Handschuh
email: sebastian.handschuh@daimler.com

Dr Steven Vettermann
email: steven.vettermann@prostep.com

JT Format (ISO 14306) and AP 242 (ISO 10303) the Step to the Next Generation Collaborative Product Creation

Keywords: JT Format, ISO 14306, STEP AP 242, ISO 10303, Engineering Collaboration, Product Creation 1

JT format became ISO Standard ISO14306 in December 2012 [1]. It is the beginning of new effective CAD collaboration in Multi-CAD environments. In parallel it gives innovative IT providers the chance to contribute with advanced solutions to challenge the established IT vendors. Through smart combination with the upcoming STEP AP 242 XML for the first time a process-oriented solution for supporting automotive data exchange requirements is available.

INTRODUCTION

Digital Engineering Visualization is an approach which gives a broad number of individuals, being part of the product creation processes, the access to 3D data without using a traditional CAD system. As depicted in Figure 1, the number of people who only need to view information is 10 times higher than of its creators.

Over the last 5 to 8 years, JT Format (at this time owned by Siemens PLM) became more and more a de facto standard for 3D visualization in the automotive and aerospace industry. Hence, the Global Automotive Advisory Group, a forum of the international heads of automotive engineering IT, recommended Siemens PLM to handover the JT file format description to ISO for international standardization. To make this happen, ProSTEP iViP Association, the well-known organization for standardization in the field of engineering collaboration took over the operational lead to provide all documents and arrangements to support the ISO organization in the formal process to get ISO 14306 approved. Fig. 1. Figure 1 -Hugh need for viewing information [START_REF]ISO: Industrial automation systems and integration --JT file format specification for 3D visualization[END_REF] The JT format contents not only a definition of a tessellated representation with dedicated level of detail. It defines also an exact geometry description based on BREP and e.g. product and manufacturing information.

But for supporting all industrial visualization requirements JT itself could reach its full potential only by applying it in combined application with the smart XMLfunctionalities of the new STEP AP 242. Thus, in 2010, the decision was taken to establish STEP AP 242 XML and JT as the standard-combination for enabling lightweight data exchange. STEP AP 242 XML, as the process backbone, for assembly, meta, kinematic data etc. And JT as lightweight visualization format for 3D industrial data. By this, for the first time a process-oriented solution for supporting automotive data exchange requirements was agreed.

JT BASED PROCESSES

Process overview

Only to provide an international standard without defining, how this standard can be used gains only limited value. So it is crucial to define processes first and underline these processes by concrete use cases. Figure 2 gives an overview of the possible work share of native CAD and JT in an international automotive enterprise. Here we have to distinguish between internal company value adding processes which still require native CAD representation and integration processes between the OEM and the various numbers of suppliers. For this integration tasks, JT can contribute to be more flexible, faster and especially cost efficient.

JT Use Cases

To go into more detail it is recommended to detail the usage of JT in dedicated workflow descriptions.

The JT Workflow Forum, a working group under the umbrella of Pro STEP iViP Association defined such scenarios and published it in a whitepaper (cf. [START_REF] Prostep Ivip | White Paper Applying JT[END_REF]).

The different use cases were classified in three categories, related to the complexity of usage

 Viewing  Digital Mock Up  Design in Context

Viewing.

Viewing was the foundation of using JT. This includes also high end visualization, bidding and inquiry processes as well as material specification.

Digital Mock Up.

Beside DMU analysis, the use cases in this cluster define processes for tolerance analysis, drawingless manufacturing, tolerance studies, supplier integration and al processes of digital factory.

Design in Context.

Here the more advanced processes are defined. This includes hybrid design in context, all simulation activities as long term data retention.

DESGIN IN CONTEXT USING JT

Hybrid and non-hybrid design in context

The Design in Context (DiC) process is one of the most complex processes which could be based on JT-and structure information (in future e.g. STEP AP 242XML) coming from various 3D-CAD-systems. These formats can be combined with native 3D-CAD-data which is often needed and beneficial in design processes (no media break). It is to be distinguished into [START_REF] Handschuh | Wertextrahierende Nutzung von offenen leichtgewichtigen Datenformaten in automobilen Kollaborations-und Entwicklungs-prozessketten[END_REF]:

 Hybrid-(HDiC)and  Non-hybrid design in context (NHDiC).

The hybrid design in context process directly uses JT-/ structure data as an input format without data translation into native 3D-CAD-formats (cf. Figure3).

Fig. 3. Hybrid design in context use case [3]

In today's design in context processes often the exchange of geometrical change information is needed. The design in context process often refers to interface regions of (e.g. externally created) parts. Information located in these regions (e.g. geometrical elements) can be used for DiC-processes. The main categories in which this information can be divided are:

 Geometrical-and  Technological information Geoemtrical information is often used to define geometrical elements in surrounding parts on customer/OEM side. Therefore information such as diameters, curves or supplemental geometry is used. In case technological information is needed a broad range of information is thinkable in interface regions of parts e.g. mechanical-, electrical-information [START_REF] Handschuh | Wertextrahierende Nutzung von offenen leichtgewichtigen Datenformaten in automobilen Kollaborations-und Entwicklungs-prozessketten[END_REF]. These interface related feature information can be transfered out of the sourcing 3D-CAD-system into JT-data using e.g. Product Manufacturing Information (PMI) or in future using a combination of JT and XML-based accompanying dataformats such as STEP AP242XML for the transfer of additional information. Work on this topic was done e.g. at the University of Kaiserslautern in context of value extracting use of open lightweight data formats (such as JT) in automotive collaboration and development process chains [START_REF] Handschuh | Wertextrahierende Nutzung von offenen leichtgewichtigen Datenformaten in automobilen Kollaborations-und Entwicklungs-prozessketten[END_REF], [START_REF] Roth | Prozessüber-greifende Nutzung von VR-Technologien im Schiffbau (Tagungsband Go3D)[END_REF]. Due to this fact the next chapter gives an overview of the value added chain in automotive industry and describes (as an example) a JT-based data exchange pilot project.

SUPPLIER INTEGRATION

JT based supply chains in automotive industry

The value added in many industries is decreasing on OEM side and increasing on supplier side. Several studies record this (cf.Figure 4) [START_REF]Studie: Innovationsstrategien für erfolgreiche Automobilzulieferer[END_REF],[6] Fig. 4. Value added on OEM/Supplier side [START_REF]Studie: Innovationsstrategien für erfolgreiche Automobilzulieferer[END_REF] In the automotive industry often suppliers deliver complete moduls such as door panels or dash boards. While system landscapes in context of global sourcing processes are typically heterogeneous the usage of ISO standardized data formats (JT /STEP APA242) for data exchange is getting more and more important. Figure 5 gives an overview of the pro-cesslandscape in such supplier integration scenarios. These processes are validated in automotive industry in several pilot projects e.g. with global automotive suppliers (cf. Figure 6). The results of these JT-based data exchange processes are very promising and further potentials in using JT instead of native 3D-CAD-data in collaboration processes are identified e.g. in the fields of data-preparation,-handling and -storage. To reach such a duo of complemented and ISO standardized data formats a lot of work has to be done.

In the next chapter some detail of the standardization activities are shown.

JT AND STEP AP 242 BASIS FOR PROCESS-ORIENTED DATA EXCHANGE

Following Modern Standardization Concepts

Modern IT standards must be flexible and fulfil the industrial requirements. The challenge is to figure out the 20% that are needed to cover the 80% of practical applications (Pareto principle).

Standards can only provide industry with the necessary value added if there is a stable basis on which additional functionality can be developed to respond to contextspecific needs. This may take the form of new developments or, preferably, developments that are already in widespread use but which can now be simply transferred to other areas. It should not be necessary to continuously reinvent the wheel. Within the context of Multi-CAD environments this has been seriously addressed by starting the standardization JT and STEP AP 242.

STEP forms the backbone

In 2010 representatives of leading aerospace and automotive companies as well as standardization organization came together in order to discuss measures for strengthen the future position of STEP. By this time, with regard to 3D engineering the two major standards "ISO 10303-203 -Configuration controlled 3D design of mechanical parts and assemblies" and "ISO 10303-214 -Core data for automotive mechanical design processes" reached an overlap of functionality by 75% over the years (cf. Figure 2). This was regarded as costly and a dissemination hindrance. Thus, the merger of these two standards was decided: STEP AP 242 (ISO 10303-24 -Managed model based 3d engineering). AP 242 is designed to address the common aerospace and automotive use cases and to provide a single data backbone. Its publication as ISO standard is planned for beginning of 2014.

AP 242 offers more and/or enhanced functionalities compared with its parents AP's, AP 203 and AP 214. But it also offers additionally a new concept: the Business Object Model, the so-called BO-Model.

Major enhancements are provided in AP 242 by adding functionalities for (cf. Unlike in the past, by this mechanism it is not only possible to reference a file (e.g. from an assembly tree to parts), it is now possible to reference elements within a (STEP)file (e.g. a curve, an edge, an axis). This is extremely important for e.g. kinematics, where one needs to reference certain constraints.

The BO-Model is a subset of the AP 242 functionalities. It covers all data relevant for data management, e.g. meta data. This also means, that it does not cover e.g. 3D geometry itself, it only links to it. Beside the tradition representation of a STEP-File via a STEP Physical File (SPF), the BO-Model also provides a representation expressing the equivalent information in XML. Thus, the intent behind the BO-Model is to provide a standard-based representation of product data management data, as SPF and in XML.

Especially the new capabilities to express PDM-relevant data in XML and the described External Element Reference Mechanism make AP 242 so attractive to use it together with JT in the field of visualization. And this was one of the main motivations to go for this.

JT as the leafs of a (STEP)tree

In the past, STEP became the standard for the exchange of product model data. There is no better. But in one field it failed: visualization.

One could now state: So, let's invest resources and in some years we could close this gap. But in 2010 industry required a standard 'right now'.

In the same time, STEP matured to what it is today, JT matured to the leading visualization solution. Thus, it was obvious to start the standardization of JT via ISO and to take care, that the two standards could by applied separately, but if they are used together, that they form a process-supporting solution which is more powerful than its pieces.

In 2010, the decision was taken to propose the standardization of the complete JT Version 9.5 via ISO, so that independent and royalty-free solutions can be realized. Figure 4 show the harmonized roadmap between the two standardization projects JT and STEP AP 242. The agreed aim was to establish a visualization standard which could use the enhanced XML-functionalities of STEP AP 242. By this, JT should be kept lightweight. Frankly said, JT provides the 3D-relevant data within a STEP-tree.

JT data model

The data model for JT includes more than just geometry models (cf. Figure 5). On the one hand, it offers the option of displaying the models in various degrees of precision and, on the other hand, other information that is important for product development and downstream processes can be stored together with the model.

Fig. 9. : JT Data Model

In addition to the ability to display geometry, it was the fact that product manufacturing information (PMI) such as tolerances, toleranced dimensions and information about surface properties could be displayed together with the 3D models and processed further that contributed to its fast proliferation.

Geometry:

 At one of the lowest levels, simple regular geometry such as cuboids, cylinders and pyramidsfor the definition of designed spaces for exampleare located in what is referred to as the bounding box.  Tessellated or faceted geometry allows the representation of solids and surfaces. JT offers the option of defining different levels of detail (LOD), i.e. specifying how precisely something is to be represented. A very low LOD means less precision and a smaller volume of data, a very high LOD means a level of precision approaching the exact geometry and a larger volume of data.  The latest form of compression is JT ULP, which was released in 2008 and allows the volume of data to be reduced to almost one hundredth the size of the original data.  BREP (boundary representation) geometry offers the highest level of precision.

They are an exact representation of the solids and surfaces that were generated in the CAD system, for example. The exact JT file is also only a fraction of the size of the original file.

Through certain compression algorithms it's possible to reduce the size of a representing the same content tremendously (cf. Figure 6).

OPPORTUNITIES FOR INNOVATIVE IT PROVIDER

The various application scenarios give rise to numerous requirements that need to be met by the JT and STEP data. Questions also rise with regard to the quality of the JT data supplied by the systems involved. In other words, on the one hand they relate to the authoring systems and on the other hand to the translators that generate JT from a native format or can convert JT into a native format.

In order to provide a reliable answer to these questions, systematic benchmarking of the tools involved is needed. Until now, the ProSTEP iViP Association, together with the VDA PLM Working Group, conducted three neutral Benchmarks. The latest was published beginning of 2013 (cf. [START_REF] Prostep Ivip | JT Application Benchmark[END_REF]). In this benchmark the focus was on LODund PMI-related functionalities as well as the performance of available JT viewers.

Based on the derived use cases and the related requirements that the JT and STEP need to satisfy the JT Workflow Forum, which comprises a number of companies from the automotive industry, and the JT Implementor Forum, which comprises leading IT vendors and providers of translators and system integrations, set up metrics and test models for conducting state-of-the-art benchmarks. A participants gathered rich information out of the fruitful discussions and took the chance for process and product enhancements.

The next benchmark is already in preparation and the complexity as well as the expectations with regard to the performance of the tested products is rising year by year (cf. Figure 7). The upcoming benchmark will focus on the two building blocks illustrated in Fig. 8. The already gathered information underline that industry took the right step when deciding to address the challenge of Multi-CAD environments with a combination of the standards JT and STEP.

CONCLUSIONS

JT and STEP AP 242 are on the way to change CAD based development and gain much more benefits out of 3D data than possible in the past.

The ISO Standards provide a reliable and sustainable definition for product describing data including product structure and behaviour models.

Powerful low cost and or freeware solutions will appear for a more intensive use of product data. Special solutions for ultra-light weight descriptions under JT definitions are on the way to be established.

For DMU and other integration processes international and multi partner collaboration can be defined in a new way. Here the specific solutions of each partner can be respected as long as he is committed to the two ISO standards.

Design in context solutions have a better chance when they support JT and AP 242. This will based force the reincarnation of the special CAD solutions for dedicated tasks. Secondly special solutions will be developed directly using JT definition. The one fits all CAD "Dinos" might have a tough future.

In this spirit ProSTEP iViP Association and most of the associated companies are engaged to work on JT Version 2 to enhance to value added position of JT and AP 242.

Fig. 2 .

 2 Fig. 2. Figure 2 -Future work share between CAD and JT (Source: Daimler, cf. [3])

Fig. 5 .

 5 Fig. 5. Big Picture JT-based process land-scape

Fig. 6 .

 6 Fig. 6. JT-Pilot project (exchange of an ECU)

  Figure 3):  Composites  Kinematics  Product Manufacturing Information  Rules and Requirements  Shape Data Quality

Fig. 7 .

 7 Fig. 7. Figure 3: AP 242 information model overview

Fig. 8 .

 8 Fig. 8. Figure 4: ISO Roadmap for JT and STEP AP242

Fig. 10 .

 10 Fig. 10. Figure 6: JT file size comparison (Source: Siemens PLM)

Fig. 11 .

 11 Fig. 11. : Complexity of the test scenarios is raising

Fig. 12 .

 12 Fig. 12. : Building blocks of the JT Benchmark 2013


Kun Peng
email: dr.kun.peng@gmail.com

Matt Henricksen

Multiplicative Homomorphic E-Auction With Formally Provable Security

A new method, homomorphic e-auction based on multiplicative homomorphic encryption algorithm like ElGamal encryption is proposed in this paper. Its advantage is obvious and useful in practice: efficient distributed private key generation and thus efficient trust sharing. A long existing problem in homomorphic e-auction, inefficiency of bid validity check, is solved in the new multiplicative homomorphic e-auction scheme in this paper, which employs efficient bid re-formatting to enforce bid validity. Another contribution of the new multiplicative homomorphic e-auction scheme is that it is the first e-auction scheme to provide formal and comprehensive security analysis to achieve formally provable security (especially privacy).

1 Introduction E-auction is a popular e-commerce application to distribute resources. In eauction applications, the bids are often sealed for fairness and security. In many sealed-bid e-auction schemes, it is desired to protect privacy of the losing bids, which is called bid privacy. An obvious solution to protect bid privacy in eauction is secure multiparty computation (called secure evaluation in [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF]) as eauction can be regarded as computation (evaluation) of some secret inputs (the bids) to obtain an output (the auction result). Secure-multiparty-computationbased solution to e-auction includes a few schemes [START_REF] Naor | Privacy perserving auctions and mechanism design[END_REF][START_REF] Juels | A two-server, sealed-bid auction protocol[END_REF][START_REF] Jakobsson | Mix and match: Secure function evaluation via ciphertexts[END_REF][START_REF] Cramer | Multiparty computation from threshold homomorphic encryption[END_REF][START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF][START_REF] Kurosawa | Bit-slice auction circuit[END_REF]. As analysed in [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF], these schemes are not efficient as they employ general multiparty computation techniques designed to evaluate any function. In comparison, special techniques designed to handle e-auction only are usually more efficient. A very popular such method is homomorphic bid opening. With this mechanism, each bidder employs a homomorphic encryption algorithm or a homomorphic secret sharing algorithm to seal their bids, while the auctioneers exploit homomorphism of the encryption algorithm or secret sharing algorithm to open the bids collectively instead of separately so that no losing bid is revealed. As the power of secret reconstruction or decryption is shared by multiple auctioneers such that the number of cooperating auctioneers must be over a threshold to gain the power, bid privacy is retained if the number of malicious auctioneers is not over the threshold.

Well known homomorphic e-auction schemes include [START_REF] Kikuchi | Multi-round anonymous auction[END_REF][START_REF] Kikuchi | Distributed auction servers resolving winner and winning bid without revealing privacy of bids[END_REF][START_REF] Abe | M+1-st price auction using homomorphic encryption[END_REF][START_REF] Omote | A second-price sealed-bid auction with the discriminant of the p-th root[END_REF][START_REF] Peng | Robust, privacy protecting and publicly verifiable sealed-bid auction[END_REF][START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF][START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF][START_REF] Peng | Efficiency improvement of homomorphic e-auction[END_REF]. They usually require that each bidder includes a bidding choice for every biddable price in his bid where every bidding choice must be one of two appointed integers, representing YES and NO respectively. To test whether there is a bid at a price, usually homomorphic bid opening schemes sum up all the bidders' bidding choices at that price. No separate bid choice is revealed and the sum is enough to show whether there is a bid at that price. Together with binary search for the wining price among the biddable prices, this summing-up bid opening mechanism is very efficient in finding the winning bid.

In the beginning, homomorphic e-auction schemes [START_REF] Kikuchi | Multi-round anonymous auction[END_REF][START_REF] Kikuchi | Distributed auction servers resolving winner and winning bid without revealing privacy of bids[END_REF][START_REF] Peng | Robust, privacy protecting and publicly verifiable sealed-bid auction[END_REF][START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF]] employ Shamir's secret sharing [START_REF] Shamir | How to share a secret[END_REF] to seal the bids and exploit its homomorphism to implement homomorphic bid opening. As secret sharing and reconstruction have to be repeated multiple times in secret-sharing-based homomorphic e-auction, it is not efficient enough, especially when public verifiability is required and validity of secret sharing needs to be publicly verified. So homomorphic encryption algorithm becomes more popular and gradually replaces secret sharing in homomorphic e-auction [START_REF] Abe | M+1-st price auction using homomorphic encryption[END_REF][START_REF] Omote | A second-price sealed-bid auction with the discriminant of the p-th root[END_REF][START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF][START_REF] Peng | Efficiency improvement of homomorphic e-auction[END_REF] as a bid sealing tool.

The advantage of homomorphic encryption algorithm is obvious in homomorphic e-auction. Secret sharing only needs to be performed once to share the private key among the auctioneers. However, there is a difficulty in using homomorphic encryption in e-auction applications: the difficulty in threshold private key sharing for homomorphic algorithm. Most homomorphic e-auction schemes employ an additive homomorphic algorithm to seal the bids, where D(c 1 ) + D(c 2 ) = D(c 1 c 2 ) for any ciphertexts c 1 , c 2 and D() denotes the decryption function. It is interesting to note that all the known additive homomorphic algorithms (e.g. [START_REF] Okamoto | A new public-key encyptosystem as secure as factoring[END_REF][START_REF] Naccache | A new public key cryptosystem based on higher residues[END_REF][START_REF] Paillier | Public key cryptosystem based on composite degree residuosity classes[END_REF]) employ factorization problem as a trapdoor. Although there exist some distributed key generation mechanisms for RSA [START_REF] Boneh | Efficient generation of shared RSA keys[END_REF][START_REF] Mackenzie | Robust efficient distributed rsa-key generation[END_REF][START_REF] Damgård | Practical threshold rsa signatures without a trusted dealer[END_REF], which is also factorization based, they (especially [START_REF] Boneh | Efficient generation of shared RSA keys[END_REF][START_REF] Mackenzie | Robust efficient distributed rsa-key generation[END_REF]) are inefficient. The distributed key generation technique in [START_REF] Damgård | Practical threshold rsa signatures without a trusted dealer[END_REF] improves efficiency to some extent by loosening the requirements on the parameters and using additional security assumptions, but is still inefficient compared to distributed key generation of DL based encryption algorithms [START_REF] Feldman | A practical scheme for non-interactive verifiable secret sharing[END_REF][START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF] like ElGamal. So they cannot provide an efficient solution to distributed key generation for additive homomorphic encryption, not to mention their difficulty in public verification and that the relatively more efficient mechanism among them may not satisfy the parameter requirements with reasonable security assumptions when applied to e-auction. It is easy for a central trusted dealer to generate the private key [START_REF] P Fouque | Sharing decryption in the context of voting or lotteries[END_REF][START_REF] O Baudron | Practical multicandidate election system[END_REF][START_REF] Damgård | A generalisation, a simplification and some applications of paillier's probabilistic public-key system[END_REF] and then distribute it among the auctioneers. However, it requires too strong a trust and compromises the advantage of threshold trust, so is impractical in applications like e-auction. Although a modified ElGamal encryption in [START_REF] Lee | Receipt-free electronic voting through collaboration of voter and honest verifier[END_REF][START_REF] Peng | Efficient Bid Validity Check in ElGamal-Based Sealed-Bid E-auction[END_REF] is additive homomorphic and support efficient distributed key generation [START_REF] Feldman | A practical scheme for non-interactive verifiable secret sharing[END_REF][START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF], it is not practical in most cases as it does not support efficient decryption.

Peng et al [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF] design a special homomorphic e-auction scheme based on Goldwasser-Micali encryption, which is not additive homomorphic. As encryption and decryption operations are very efficient with Goldwasser-Micali encryption, their auction scheme needs few exponentiations with long exponents in computation. However, Goldwasser-Micali encryption depends on hardness of factorization problem as well, so suffers from lack of efficient distributed key generation as well. Moreover, as the message space of Goldwasser-Micali encryption is only one bit long, bid opening must be repeated multiple times at any price in [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF], which leads to two drawbacks in efficiency. Firstly, communicational cost is high. Secondly, a large number of multiplications are needed in computation.

A common efficiency bottleneck in homomorphic e-auction is bid validity check. Validity of homomorphic bid opening depends on two assumptions about validity of the bids. Firstly, each biding choice must represent either YES or NO. An attack called BBC attack is proposed in [START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF] to compromise correctness of auction when this condition is not satisfied. Secondly, each bidder chooses YES for all the biddable prices no higher than his offer and chooses NO for all the biddable prices higher than his offer. An attack called challenge attack is shown to work when this condition is not satisfied in Section 4. So validity of bids should be publicly proved and verified in secure homomorphic e-auction. Homomorphic e-auction schemes without bid validity check [START_REF] Kikuchi | Multi-round anonymous auction[END_REF][START_REF] Kikuchi | Distributed auction servers resolving winner and winning bid without revealing privacy of bids[END_REF][START_REF] Peng | Robust, privacy protecting and publicly verifiable sealed-bid auction[END_REF][START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF][START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF] are vulnerable to various attacks. For example, as explained in [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF], colluding bidders in [START_REF] Kikuchi | Multi-round anonymous auction[END_REF][START_REF] Kikuchi | Distributed auction servers resolving winner and winning bid without revealing privacy of bids[END_REF][START_REF] Peng | Robust, privacy protecting and publicly verifiable sealed-bid auction[END_REF] can launch BBC attack. In [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF][START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF], a malicious bidder can launch challenge attack as described in Section 4. Those attacks threatens fairness of the auction, so must be prevented. Some other homomorphic e-auction schemes [START_REF] Abe | M+1-st price auction using homomorphic encryption[END_REF][START_REF] Omote | A second-price sealed-bid auction with the discriminant of the p-th root[END_REF] employ zero knowledge proof to prove validity of bids, but their proof is inefficient.

In [START_REF] Peng | Batch verification of validity of bids in homomorphic e-auction[END_REF][START_REF] Peng | Efficient Bid Validity Check in ElGamal-Based Sealed-Bid E-auction[END_REF], batch zero knowledge proof is employed to improve efficiency of bid validity check. Another batch proof technique is proposed in [START_REF] Chida | Batch processing for proofs of partial knowledge and its applications[END_REF], which can be applied to bid validity check. However, their improvement in efficiency is not great enough to ease the efficiency concern in bid validity check. The most recent attempt to improve efficiency of bid validity check is [START_REF] Peng | Efficiency improvement of homomorphic e-auction[END_REF], which allows the auctioneers to efficiently verify validity of the bids. However, it is not universally verifiable and one instance of proof can only convince one verifier. When there are other verifiers the bidders must provide a different proof to each of them. Moreover, it is required in [START_REF] Peng | Efficiency improvement of homomorphic e-auction[END_REF] to extend the digital signature algorithm in [START_REF] Boneh | Short signatures without random oracles[END_REF] to distributed signature generation, where the power of signature generation is shared by the auctioneers. However, there is no known method to distribute signature generation for the digital signature algorithm in [START_REF] Boneh | Short signatures without random oracles[END_REF] as it is a special signature scheme to prevent malleability.

In this paper, a new homomorphic e-auction scheme is designed to overcome the two main drawbacks in the existing homomorphic e-auction schemes: lack of efficient distributed key generation and inefficiency of bid validity check. Firstly, a multiplicative homomorphic encryption algorithm, ElGamal encryption, is employed to seal the bids such that distributed key generation of the encryption algorithm can be efficiently implemented. Secondly, simpler operations are employed to replace bid validity proof and verification such that correctness of auction can be guaranteed even at the presence of malicious bidders. The new homomorphic e-auction scheme is designed in two steps. In the first step, efficient distributed key generation and multiplicative homomorphic bid opening are specified in Section 3 such that homomorphic bid opening at any price is always correct with an overwhelmingly large probability. In the second step, the e-auction scheme is optimised in Section 4 to prevent the known attacks. A special contribution of this paper is that it presents the first formal and comprehensive security analysis for e-auction, while security (especially comprehensive privacy) of the existing e-auction schemes is intuitive only. Especially, privacy of the whole new e-auction scheme including all the published information is comprehensively and formally proved using a simulation-based model.

Symbols and Security Model

The most important security properties in e-auction are as follows.

-Correctness: the auction result is determined strictly according to the auction rule, while no bid is ignored or tampered with. -Robustness: in abnormal situations (e.g. at presence of invalid bid), the auction can still run properly.

-Privacy: no secret information (e.g. the losing bid) except for the auctionresult is revealed. More precisely, the auction transcript including all the published information in the auction can be simulated by a party without any secret knowledge but the auction result such that the simulating transcript is indistinguishable from the real auction transcript. -Universal (public) verifiability: any one can publicly verify that no participant deviates from the auction protocol.

As the bids must be sealed to achieve bid privacy, privacy of e-auction at least depends on security of the employed sealing function (e.g. encryption algorithm) and no stronger privacy (e.g. unconditional privacy) is possible. We will formally illustrates that privacy of our new e-auction scheme only depends on semantic security of the employed encryption algorithm and a threshold trust in sharing the private key. The following symbols and parameters are used in this paper.

-There are m auctioneers A 1 , A 2 , . . . , A m and n bidders B 1 , B 2 , . . . , B n .

-There are L biddable prices and they are denoted as P 1 , P 2 , . . . , P L in descending order. p and q are large primes such that p -1 = 2q. G is the cyclic subgroup in Z * p with order q and g is a generator of G. -Integer l smaller than m is the trust threshold such that cooperation of at least l auctioneers is necessary to open any bid. -L 1 and L 2 are security parameters smaller than q. They do not need to be very large on the condition that 2 (L-1)L2 < q and 2 -L1 , 2 -L2 are negligible. -H() is a one-way and collision-resistent hash function.

The formal proof to illustrate privacy of the new e-auction scheme in this paper needs to extend the traditional definition of semantic security [START_REF] Goldwasser | Probabilistic encryption[END_REF] in Definition 1 to a new property called semantic security regarding multiple encryptions, which is defined in Definition 2 and illustrated to be a deduction of traditional semantic security in Theorem 1.

Definition 1 (Traditional semantic security) An encryption algorithm with a random probabilistic encryption function E() is semantically secure in the traditional definition if no polynomial adversary can win the following game with a probability non-negligibly larger than 0.5.

1. The adversary chooses two different messages m 0 and m 1 in the message space in any way he likes and sends them to a probabilistic encryption oracle. 2. The encryption oracle randomly chooses a bit I and returns c = E(m I ).

Receiving c, the adversary wins the game if it finds out I.

Definition 2 A random probabilistic encryption function is semantically secure regarding multiple encryptions if no polynomial adversary can win the following game with a probability non-negligibly larger than 0.5.

1. Messages m 1 , m 2 , . . . , m N with any possible distribution in the message space are given where N ≥ 1. 2. Ciphertext c 0,1 , c 0,2 , . . . , c 0,N and c 1,1 , c 1,2 , . . . , c 1,N are given such that i is randomly chosen from {0, 1} and c i,j = E(m j ) for j = 1, 2, . . . , N and every c 1-i,j may be encryption of any message in the message space. 3. The adversary wins the game if it finds out i.

Theorem 1. If an encryption algorithm is semantically secure in the traditional definition, then it is semantically secure regarding multiple encryptions.

Proof: If an encryption algorithm is not semantically secure regarding multiple encryptions, there is a polynomial algorithm A to win the game in Definition 2 with a probability non-negligibly larger than 0.5. A polynomial adversary can use A to break traditional semantic security of the encryption algorithm as follows.

1. Choosing m 0 , m 1 and given c the adversary in Definition 1 needs to find I. 2. The adversary randomly chooses m 2 , m 3 , . . . , m N from Z q and generates two encryptions for each of them: c j = E(m j ) and c j = E (m j ) for j = 2, 3, . . . , N where E () denotes the same encryption algorithm using the same key but different probabilistic randomization from E(). 3. The adversary generates c = E(m 0 ). 4. The adversary submits messages m 0 , m 2 , m 3 , . . . , m N and ciphertexts c , c 2 , c 3 , . . . , c N and c, c 2 , c 3 , . . . , c N to A. 5. A returns i and the adversary outputs I = i.

Note that

P [I = i] = P [I = i = 1] + P [I = i = 0] = P [I = 1]P [i = 1|I = 1] + P [I = 0]P [i = 0|I = 0]
where P [E] denotes the probability that event E happens and P [E 1 |E 2 ] denotes the probability that event E 1 happens on the condition that event E 2 happens. As A breaks semantic security regarding multiple encryptions, P [i = 1|I = 1] is non-negligibly larger than 0.5 and denoted as . When I = 0, both c, c 2 , c 3 , . . . , c N and c , c 2 , c 3 , . . . , c N are encryptions of m 0 , m 2 , m 3 , . . . , m N , so A outputs 0 or 1 with the same chance and thus P [i = 0|I = 0] = 0.5. So

P [I = i] = 0.5 + 0.5 × 0.5,
which is non-negligibly larger than 0.5. So the adversary can break traditional semantic security of the encryption algorithm in polynomial time by querying A. Since breaking semantic security regarding multiple encryptions implies breaking traditional semantic security, traditional semantic security implies semantic security regarding multiple encryptions. 2

3 The Basic Protocol, Efficient Distributed Key Generation and Multiplicative Homomorphic Bid Opening

In this section, we start with a simple question: how to design homomorphic bid opening in first-bid sealed-bid auction, while the private key of the employed bid-sealing encryption algorithm must be generated in a distributed way to avoid too strong trust. Discussions of more complex questions will be given in Section 4 and Section 5. In our design, the auctioneers set up ElGamal encryption with distributed decryption for bid sealing as follows.

1. Each A j randomly chooses x j from Z q and calculates y j = g xj mod p and publishes H j = H(y j ). 2. After H 1 , H 2 , . . . , H m have been published, each A j publishes y j and any one can verify H j = H(y j ) for j = 1, 2, . . . , m. 3. The public key of ElGamal encryption is y = m j=1 y j mod p and the private key x = m j=1 x j mod q needs to be secretly shared among the auctioneers with the trust threshold l. 4. Each A j builds a polynomial F j (X) = l-1 k=0 a j,k X k where a j,0 = x j . 5. Each A j calculates s j,J = F j (J) mod q and secretly sends s j,J to every A J for j = 1, 2, . . . , m and J = 1, 2, , . . . , m. 6. Each A J calculates his private key share s J = m j=1 s j,J mod q.

Public verification of the key distribution can be easily implemented by publishing α j,k = g a j,k mod p for j = 1, 2, . . . , m and k = 0, 1, . . . , l -1 and verifying each of the secret sharing operations using the existing publicly verifiable secret sharing techniques (e.g. [START_REF] Traore | Efficient public verifiable secret sharing schemes with fast or delayed recovery[END_REF][START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF]). Encryption and decryption are as follows.

-Encryption of a message M in G is E(M ) = (g r mod p, M y r mod p) where r is randomly chosen from Z q . -A ciphertext c = (a, b) can be decrypted by the cooperation of at least l auctioneers (denoted as A 1 , A 2 , . . . , A l for simplicity of description) as follows.

1. Each auctioneers A j calculates and publishes β j = a sj mod p for j = 1, 2, . . . , l. If public verification is required, A j publicly proves log a β j = log g l-1 k=0 θ j k k using zero knowledge proof of equality of discrete logarithms [START_REF] Chaum | Wallet databases with observers[END_REF] where

θ k = m j=1 α j,k mod p. 2. The final result is D(c) = b/ l j=1 β uj j mod p where u j = 1≤v≤l,v =j v/(v -j) mod q.
Note that unlike the encryption algorithms employed in traditional homomorphic e-auction schemes ElGamal encryption is not additive homomorphic. Instead, it is multiplicative homomorphic. More precisely, in ElGamal encryption D(c 1 )D(c 2 ) = D(c 1 c 2 ) for any ciphertexts c 1 , c 2 . So our homomorphic bid opening is different from the existing homomorphic bid opening mechanisms. It exploits multiplicative homomorphism instead of additive homomorphism of the employed encryption algorithm, so is called multiplicative homomorphic eauction. One-choice-per-price strategy is employed in our design. The biddable prices are limited in a definite set and each bidder must make a choice (indicating willingness or unwillingness to pay) at every biddable price. If a bidder is willing to pay a price, he chooses an integer standing for "YES" as his choice at that price. If a bidder is unwilling to pay a price, he chooses an integer standing for "NO" as his choice at that price. The bidders seal their bidding vectors (including their choices at all the biddable prices) and publish the sealed bidding vectors. The detailed design of bid sealing is as follows.

1. Each bidder B i chooses his evaluation P ei from {P 1 , P 2 , . . . , P L }.

Each B i builds his bidding vector: b

i = (b i,1 , b i,2 , . . . , b i,L ) where b i,t = 1
for t < e i and b i,t is a random integer larger than 1 in G for t ≥ e i . 3. Each B i seals his bidding vector in a ciphertext vector

c i = (c i,1 , c i,2 , . . . , c i,L ) = (E(b i,1 ), E(b i,2 ), . . . , E(b i,L )).
Note that in our new design the bidders do not need to prove validity of any of his bidding choices as a bidding choice indicating "YES" can be any integer larger than 1. Namely, any integer in the messages space of the employed encryption algorithm is a valid bidding choice (1 for "NO" and otherwise for "YES"). It is illustrated in the following bid opening procedure that homomorphic bid opening can still work with such a tolerating bid format. The bid opening procedure employs binary search, where the biddable prices form a binary tree and the searching route starts at the tree root (P L/2 ) and ends at a tree leaf. On each node of the route it is tested whether there is at least one "YES" choice without revealing the choices at that price. If there is one "YES" choice at that price, the search goes into the sub-tree with higher prices. If there is no "YES" choice at that price, the search goes into the sub-tree with lower prices. At every price P ρ on the searching route the homomorphic bid opening is as follows.

1. The auctioneers cooperate to choose random integers T ρ,1 , T ρ,2 , . . . , T ρ,n in Z 2 L 1 as follows.

(a) Each A j randomly chooses T ρ,i,j in Z 2 L 1 and publishes T ρ,i,j = H(T ρ,i,j ) for i = 1, 2, . . . , n. (b) After all the T ρ,i,j s are published, each A j publishes T ρ,i,j for i = 1, 2, . . . , n. (c) T ρ,i = m j=1 T ρ,i,j mod 2 L1 for i = 1, 2, . . . , n.

The auctioneers calculate

C ρ = (a ρ , b ρ ) = n i=1 c Tρ,i i,ρ = ( n i=1 a Tρ,i i,ρ mod p, n i=1 b Tρ,i i,ρ mod p)
where c i,ρ is denoted as (a i,ρ , b i,ρ ).

An enough number of auctioneers cooperate to decrypt

C ρ into d ρ = D(C ρ ).
The binary search goes on until it stops at a leaf of the binary searching tree, which is declared as the winning price. Finally, the winner opens his bid (e.g. by publishing its encryption detail) to claim winning. It is illustrated in Theorem 2 that our homomorphic bid opening mechanism can work although any integer in G is a valid bidding choice.

Theorem 2. Homomorphic bid opening at any price in the new multiplicative homomorphic e-auction is correct. More precisely, with an overwhelmingly large probability the decryption result at a price is larger than one iff there is at least one bidding choice larger than one at the price.

Before Theorem 2 is proved, a lemma needs to be proved first.

( k-1 i=1 b Ti i )b Tk k N i=k+1 b Ti i = 1 mod p (1)
Otherwise, for any L 1 -bit integers T 1 , T 2 , . . . , T k-1 , T k+1 , . . . , T N there is at most one L 1 -bit integer T k to satisfy equation N i=1 b Ti i = 1 mod p, which implies that equation N i=1 b Ti i = 1 mod p is satisfied with a probability no larger than 2 -L1 (with at most 2 (N -1)L1 combinations among the 2 N L1 possible combinations of T 1 , T 2 , . . . , T N ) and is a contradiction.

(1) divided by ( 2) yields

b T k -Tk k = 1 mod p.
Note that T k and Tk are L 1 -bit integers, 2 L1 < q and q is prime, so GCD(S k -Ŝk , q) = 1. Therefore, b k = 1 mod p. Also note that k can be any integer in {1, 2, . . . , n} and thus b i = 1 mod p for i = 1, 2, . . . , n.

2

Proof of Theorem 2: At a price P ρ the result of multiplicative homomorphic bid opening is

d ρ = D(C ρ ) = D( n i=1 c Tρ,i i,ρ ) = n i=1 D(c i,ρ ) Tρ,i = n i=1 b
Tρ,i i,ρ mod p.

-When all the bidding choices, b 1,ρ , b 2,ρ , . . . , b n,ρ are 1, d ρ is always 1.

-According to Lemma 1, when any of b 1,ρ , b 2,ρ , . . . , b n,ρ modulo p is larger than 1, d ρ is larger than 1 with an overwhelmingly large probability. 2

As traditional semantic security has been reduced to semantic security regarding multiple encryptions in Theorem 1, formal privacy of the new e-auction scheme can be proved in Theorem 3, which reduces distinguishability between the e-auction transcript and a simulating transcript to breaking semantic security regarding multiple encryptions as defined in Definition 2.

Theorem 3. The new multiplicative homomorphic e-auction scheme is private and computationally reveals no bidding information other than the auction result. More precisely, the information revealed in the e-auction scheme can be simulated by a party without any knowledge of any bid but the auction result such that the simulating transcript is indistinguishable from the real transcript of the revealed information on the condition that ElGamal encryption algorithm is semantically secure regarding multiple encryptions.

Proof: The revealed information in the new multiplicative homomorphic eauction scheme includes:

c i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L; at each price p ρ on the binary searching route C ρ , d ρ , T ρ,i,j and T ρ,i,j for i = 1, 2, . . . , n and j = 1, 2, . . . , m and T ρ,i for i = 1, 2, . . . , n; the integers published in the the multiple instances of underlying zero knowledge proof of equality of discrete logarithms, when complete public verifiability is required to include key generation and distributed decryption.

As ZK proof of equality of discrete logarithms in [START_REF] Chaum | Wallet databases with observers[END_REF] has been formally proved to be zero knowledge, we only need to prove that c i,t , C ρ , d ρ , T ρ,i , T ρ,i,j , T ρ,i,j for p ρ on the searching route, 1 ≤ i ≤ n, 1 ≤ t ≤ L and 1 ≤ j ≤ m can be simulated by a party without any secret knowledge but the auction result. A party without any secret knowledge but the auction result can simulate them as follows.

1. He finds the binary searching route according to the auction result. 2. He randomly chooses T ρ,i,j for p ρ on the searching route, i = 1, 2, . . . , n and j = 1, 2, . . . , m from Z 2 L 1 and calculates T ρ,i,j = H(T ρ,i,j ). 3. He calculates T ρ,i = m j=1 T ρ,i,j mod 2 L1 for p ρ on the searching route and i = 1, 2, . . . , n. 4. He randomly chooses b i,t from G for 1 ≤ i ≤ n and 1 ≤ t ≤ L. 5. He calculates c i,t = (a i,t , b i,t ) = (g r i,t mod p, b i,t y r i,t mod p) for i = 1, 2, . . . , n and t = 1, 2, . . . , L where r i,t is randomly chosen from Z q .

6. He calculates C ρ = ( Tρ,i i,ρ mod p for p ρ on the searching route. In this simulating transcript of the revealed information,

-each T ρ,i,j is uniformly distributed in Z 2 L-1 ; -each T ρ,i is uniformly distributed in Z 2 L-1 ; -each c i,t is distributed in G 2 in
a way independent of the secret bids but depending on how b i,t is chosen in the simulation;

-each d ρ is uniformly distributed in G; -each C ρ is uniformly distributed in G 2 ; -T ρ,i = m j=1 T ρ,i,j mod 2 L1
for p ρ on the searching route and 1 ≤ i ≤ n; -T ρ,i,j = H(T ρ,i,j ) for p ρ on the searching route ,1 ≤ j ≤ m and 1

≤ i ≤ n; -C ρ = ( n i=1 a Tρ,i i,ρ mod p,
-each T ρ,i,j is uniformly distributed in Z 2 L-1 ; -each T ρ,i is uniformly distributed in Z 2 L-1 ; -each c i,t encrypts B i 's choice at p t ; -each d ρ is uniformly distributed in G; -each C ρ is uniformly distributed in G 2 ; -T ρ,i = m j=1 T ρ,i,j mod 2 L1
for p ρ on the searching route and 1 ≤ i ≤ n; -T ρ,i,j = H(T ρ,i,j ) for p ρ on the searching route ,1 ≤ j ≤ m and 1 The only difference between the two transcripts lies in distribution of c i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L. If a polynomial adversary can distinguish the two transcripts of c i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L, it can be employed to break semantic security of ElGamal encryption regarding multiple encryptions as follows. Since the the adversary can distinguish the two transcripts of c i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L without any other information, given additional information b i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L, it can still distinguish the two transcripts as the additional information only makes the distinguishing work easier (or at least does not make it harder). So given messages b i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L and two sets of ciphertexts c i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L, one of which is encryption of b i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L, the adversary can distinguish which set of ciphertexts are in the real e-auction transcript and thus encryption of b i,t for i = 1, 2, . . . , n and t = 1, 2, . . . , L. Namely, the adversary breaks semantic security of ElGamal encryption regarding multiple encryptions.

≤ i ≤ n; -C ρ = ( n i=1 a Tρ,i i,ρ mod p,
2

According to Theorem 1 and Theorem 3, when the number of colluding malicious auctioneers is not over l, compromising privacy of the new e-auction scheme implies breaking semantic security of ElGamal encryption, which is widely known to be hard assuming hardness of the Decisional Diffie-Hellman problem. So the new e-auction scheme is private on the condition that the DDH problem is hard. [START_REF] Boneh | Efficient generation of shared RSA keys[END_REF] The Final Protocol, Optimisation to Achieve Robustness

Although the multiplicative homomorphic bid opening mechanism in Section 3 can work at any price, achieving correctness in the auction still needs an assumption: each bidder submits a 1 as his bidding choice at any price higher than his evaluation and an integer larger than 1 as his bidding choice at any price no higher than his evaluation. More precisely, although it is not needed to assume validity of every single bidding choice in multiplicative homomorphic e-auction (as any bidding choice in the message place of the employed encryption algorithm is valid), it is still necessary to assume that in each bid vector 1s are at the higher prices and larger integers are at the lower prices. If this assumption is not satisfied, the auction scheme is still vulnerable to some attacks. For example, a malicious bidder can submit YES at higher prices and submit NO at lower prices to launch a challenge attack (mentioned in Section 1), which enables him to dispute the auction result like attacking [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF][START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF] as follows.

1. A malicious bidder includes in his bid vector a larger integer at price P γ and 1s at lower prices.

In the binary search for winning bid, multiplicative homomorphic bid open-

ing is performed at one price lower than P γ and returns a decryption result 1. So the binary search goes on to lower prices and finally stops at a winning price lower than P γ . 3. After the auction result is published, the malicious bidder can choose to challenge validity of the result by publishing his bidding choice at P γ if he likes (e.g. if his colluding co-bidder does not win or he is not satisfied with the auction result for other reasons). His challenge is effective as he does submit YES at a price higher than the winning bid.

This attack obviously violates robustness of auction. Can the malicious bidder be denied of his winning or penalized or kicked out? It is a complex question. Note that in an open-cry auction, a bidder is usually allowed to keep silent at a lower price but bid at a higher price later. Then why is the bid invalid in sealed-bid auction while it is accepted in the bidding phase? If the challenge is acceptable, the malicious bidder compromises fairness of the auction and takes advantage of the other bidders. Even if the challenge can be clarified and rejected, the clarification needs to open the bidding choices separately and compromises privacy of the auction.

Our countermeasure to this attack is simple: before bid opening the auctioneers re-format the encrypted bids such that in each bid if there is a bidding choice larger than 1 all the other bidding choices at lower prices in the same bid vector are larger than 1 with an overwhelmingly large probability. It is described in details as follows.

1. The bidders still seal and submit their bids as in Section 3. Namely each bidder B i builds his bidding vector: b i = (b i,1 , b i,2 , . . . , b i,L ) and seals it in a ciphertext vector c i = (c i,1 , c i,2 , . . . , c i,L ) 2. The auctioneers cooperate to choose random integers S i,t in Z 2 L 2 for i = 1, 2, . . . , n and t = 1, 2, . . . , L -1 just like they choose T i,t in Section 3.

The auctioneers calculate

c i,t = c Si,t-1 i,t-1 c i,t = (a Si,t-1 i,t-1 a i,t mod p, b
Si,t-1 i,t-1 b i,t mod p) for i = 1, 2, . . . , n and t = 2, 3, . . . , L where c i,1 = c i,1 , c i,t is denoted as (a i,t , b i,t ) and c i,t is denoted as (a i,t , b i,t ).

After the re-formating, the encrypted bidding choices become

c i,t = (( t-1 K=1 a t-1 J=K S i,J i,K )a i,t mod p, ( t-1 K=1 b t-1 J=K S i,J i,K )b i,t mod p) (3)
for i = 1, 2, . . . , n and t = 2, 3, . . . , L.

In this new bid format, every c i,t encrypts an integer larger than 1 with an overwhelmingly large probability as illustrated in Theorem 4 if any of the bidding choices at higher prices in the same bid vector is larger than 1.

Theorem 4. If any of D(c i,1 ), D(c i,2 ), . . . , D(c i,t-1 ) is larger than 1 for any t in {2, 3, . . . , n}, then D(c i,t ) > 1 with a probability no smaller than 1 -2 -L2 .

Before Theorem 4 is proved, a lemma is proved first. i = 1 mod p with a probability larger than 2 -L2 where S 1 , S 2 , . . . , S N -1 are random integers at least L 2 bits long and smaller than q, then b i = 1 mod p for i = 1, 2, . . . , N -1.

Proof: Given any integer k in {1, 2, . . . , N -1}, there must exist one instance of integers S 1 , S 2 , . . . , S k-1 , S k+1 , . . . , S N -1 among all their possible choices and two different instances for the choice of S k , denoted as S k and Ŝk , such that the following two equations are correct.

b N N -1 i=1 b Si i = 1 mod p (4) b N ( k-1 i=1 b Si i )b Ŝk k N -1 i=k+1 b Si i = 1 mod p (5)
Otherwise, for any possible choice of integers S 1 , S 2 , . . . , S k-1 , S k+1 , . . . , S N there is at most one choice for integer S k among all its possible choices to satisfy equation b

N N -1 i=1 b Si i = 1 mod p, which implies equation b N N -1 i=1 b Si i = 1
mod p is satisfied with a probability no larger than 2 -L2 (as the number of possible choices for S k is at least 2 L2 ) and is a contradiction. Note that S k and Ŝk are smaller than q and q is prime, so GCD(S k -Ŝk , q) = 1. Therefore, b k = 1 mod p. Also note that k can be any integer in {1, 2, . . . , N -1} and thus b i = 1 mod p for i = 1, 2, . . . , N -1. 2

Proof of Theorem 4: (3) and multiplicative homomorphism of ElGamal encryption imply

D(c i,t ) = ( t-1 K=1 D(c i,K ) t-1 J=K S i,J )D(c i,t
) mod p for i = 1, 2, . . . , n and t = 2, 3, . . . , L.

Note that any

t-1 J=K S i,J is smaller than q as 2 (L-1)L2 < q. If D(c i,t ) > 1 is not guaranteed with a probability no smaller than 1 -2 -L2 for any t, then D(c i,t ) = 1 with a probability larger than 2 -L2 . So according to Lemma 2, all of D(c i,1 ), D(c i,2 ), . . . , D(c i,t-1 ) are 1s, which is contradictory to the fact that at least one of D(c i,1 ), D(c i,2 ), . . . , D(c i,t-1 ) is larger than 1. Therefore, D(c i,t ) > 1 must be guaranteed with a probability no smaller than 1 -2 -L2 . 2

As the re-formatted encrypted bids are enforced to contain consistent bidding choices with an overwhelmingly large probability, multiplicative homomorphic bid opening and binary search can be performed on them and challenge attack can be prevented. Moreover, as the bidding choices except those at the top price in all the bids are already randomized, multiplicative homomorphic bid opening can actually be simplified and the randomization through raising the encrypted bidding choices to the power of T i,t in Section 3 can be removed unless multiplicative homomorphic bid opening is performed at the top price. The simplified bid opening operation is as follows.

1. The auctioneers reformat the encrypted bids as detailed earlier in this section and obtain the re-formatted encrypted bids c i,t = (a i,t , b i,t ) for i = 1, 2, . . . , n and t = 1, 2, . . . , L. 2. The auctioneers perform binary search for the winning bid. If the binary search goes to the top price P 1 , the multiplicative homomorphic bid opening at P 1 is the same as described in Section 3. Otherwise, the multiplicative homomorphic bid opening at any price P ρ is as follows.

(a) The auctioneers calculate

C ρ = n i=1 c i,ρ = ( n i=1 a i,ρ mod p, n i=1 b i,ρ mod p).
(b) An enough number of them cooperate to decrypt C ρ into d ρ = D(C ρ ) as described in Section 3. (c) If d ρ > 1, the search goes into the sub-tree with prices higher than P ρ .

If d ρ = 1, the search goes into the sub-tree with prices lower than P ρ . 3. The binary search goes on until it stops at a leaf of the binary searching tree, which is declared as the winning price. Finally, the winner opens his bid to claim winning. challenge attack [START_REF] Kikuchi | Distributed auction servers resolving winner and winning bid without revealing privacy of bids[END_REF] nL instances of no yes BBC attack and intuitive secret sharing challenge attack [START_REF] Peng | Robust, privacy protecting and publicly verifiable sealed-bid auction[END_REF] nL instances of no yes BBC attack and intuitive secret sharing challenge attack [START_REF] Abe | M+1-st price auction using homomorphic encryption[END_REF] sharing 1 key only but no efficient yes yes no intuitive distributed key generation [START_REF] Omote | A second-price sealed-bid auction with the discriminant of the p-th root[END_REF] sharing 1 key only but no efficient yes yes no intuitive distributed key generation [START_REF] Peng | A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption[END_REF] sharing 1 key only but no efficient no yes challenge attack intuitive distributed key generation [START_REF] Peng | Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing[END_REF] nL instances of no yes challenge attack intuitive secret sharing [START_REF] Peng | Efficiency improvement of homomorphic e-auction[END_REF] sharing In comparison with the original e-auction scheme in Section 3, the optimisation in this section changes the way the bidding choices are randomized. The new randomization operation not only enables multiplicative homomorphic bid opening but also enforces validity of the bids. The optimised e-auction scheme is correct and private as illustrated in Theorem 2 and Theorem 3 (since the change in randomization operation does not affect their applicability to the e-auction scheme) and its robustness is guaranteed by Theorem 4.

Comparison and Conclusion

Security and efficiency of the new e-auction scheme is compared with the existing e-auction schemes with bid privacy in this section. As explained in Section 1, secure-multiparty-computation-based e-auction schemes [START_REF] Naor | Privacy perserving auctions and mechanism design[END_REF][START_REF] Juels | A two-server, sealed-bid auction protocol[END_REF][START_REF] Jakobsson | Mix and match: Secure function evaluation via ciphertexts[END_REF][START_REF] Cramer | Multiparty computation from threshold homomorphic encryption[END_REF][START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF][START_REF] Kurosawa | Bit-slice auction circuit[END_REF]] and e-auction schemes employing downward search [START_REF] Sakurai | A bulletin-board based digital auction scheme with bidding down strategy[END_REF][START_REF] Suzuki | Efficient sealed-bid auction using hash chain[END_REF][START_REF] Watanabe | Reducing the round complexity of a sealed-bid auction protocol with an off-line ttp[END_REF][START_REF] Sako | An auction scheme which hides the bids of losers[END_REF][START_REF] Peng | Non-interactive auction scheme with strong privacy[END_REF] are less efficient and so we focus our comparison on homomorphic e-auction. Firstly, comparison of security properties is given in Table 1. Then, efficiency comparison of secure homomorphic e-auction schemes (with bid validity check and invulnerable to known attacks) is given in Table 2, where the number of multiplications is counted and for simplicity an exponentiation with a L-bit exponent is counted as 1.5L multiplications. A full-length exponent in cryptographic operations in G or Z p is supposed to be 1024 bits long. Note that like the analysis in the existing e-auction schemes, cost of preparation work (e.g. distributed key generation) is not included in Table 2. If it is taken into account, advantage of our new scheme will be greater as it is the only homomorphic e-auction scheme with efficient distributed key generation. In the example in Table 2, n = 1000 and L = 4096, while L 2 = 30 such that 2 -L2 is smaller than one out of one billion.

The comparisons clearly demonstrate that the new e-auction scheme is secure and efficient. It satisfies all the security properties and is the only e-auction scheme to achieve formally provable security. It is much more efficient than any secure homomorphic e-auction scheme, which already employs a relatively more efficient solution to secure e-auction. Extending our technique to more complex auction rules is an open question.

Lemma 1 .

 1 Suppose b 1 , b 2 , . . . , b N are integers in G. If N i=1 b Ti i = 1 mod p with a probability larger than 2 -L1 for random L 1 -bit integers T 1 , T 2 , . . . , T N , then b i = 1 mod p for i = 1, 2, . . . , N . Proof: Given any integer k in {1, 2, . . . , N }, there must exist integers T 1 , T 2 , . . . , T k-1 , T k+1 , . . . , T N in {0, 1, . . . , 2 L1 -1} and two different integers T k and Tk in {0, 1, . . . , 2 L1 -1} such that the following two equations are correct. N i=1 b Ti i = 1 mod p

  mod p) for p ρ on the searching route. 7. He calculates d ρ = n i=1 b

  mod p) for p ρ on the searching route; d ρ = n i=1 b Tρ,i i,ρ mod p and d ρ = D(C ρ ) for p ρ on the searching route. In comparison, in the real transcript of the same information,

  mod p) for p ρ on the searching route; d ρ = n i=1 b Tρ,i i,ρ mod p and d ρ = D(C ρ ) for p ρ on the searching route.

Lemma 2 .

 2 Suppose b 1 , b 2 , . . . , b N are integers in G. If b N N -1 i=1 b Si

( 4 )

 4 divided by (5) yields b S k -Ŝk k = 1 mod p.

Table 1 .

 1 Security comparison of homomorphic e-auction schemes

	Auction	Bid opening	Bid validity	Universal	Vulnerability	Correctness
	schemes	power sharing	check	verifiability	or problem	& privacy
	[18]	nL instances of	no	yes	BBC attack and	intuitive
		secret sharing

Table 2 .

 2 Efficiency comparison of secure homomorphic e-auction schemes

		1 key only			unknown how to
		but no efficient	yes		no	generate Boneh	intuitive
		distributed				signature [3] in a
		key generation				distributed way
	New	sharing 1 key only	enforcing	formally
	efficient distributed validity by bid	yes	no	proved
		key generation		re-formatting
	Auction	Bidder			Auctioneer
	schemes multiplication		example		multiplication	example
	[1, 26]	≥ 12291.5L		50346140 ≥ 12292nL + (10752 + 2n) log 2 L 50348957633
	[29]	1536(2L + 8)		12595200	1536(0.2nL + 20 log 2 L + 16n)	1283297280
		per verifier	per verifier
	New	3072L		12582912	3L 2 n(L -1) + 4608 log 2 L	368605296