domain: shs shs.edu math

text:
Maha Abboud

Claire Cazes
email: claire.cazes@upmc.fr

Maha Abboud-Blanchard
email: maha.abboud-blanchard@univ-paris-diderot.fr

How does an Activity Theory Model Help to Know Better about Teaching with Electronic-Exercise-Bases?

The research presented in this paper relies on Activity Theory and particularly on Engeström's model, to better understand the use of Electronic-Exercise-Bases (EEB) by mathematics teachers. This theory provides a holistic approach to illustrate the complexity of the EEB integration. The results highlight reasons and ways of using EEB and show some dynamic aspects of this use. However, the general character of the model does not allow consideration of some specificities of the teaching mathematics context.

How does an Activity Theory Model Help to Know Better about Teaching with Electronic….

INTRODUCTION

This paper presents research related to the use, by secondary mathematics teachers of Electronic-Exercise-Bases (EEB). The general issues are: Why and how do teachers use EEB? What effect does this use have on their teaching activity?

In order to answer these questions, we observed voluntary mathematics secondary teachers using EEB over the period of 3 years (Abboud-Blanchard, [START_REF] Abboud-Blanchard | Activités d'enseignants de mathématiques intégrant des bases d'exercices en ligne, Quadrante[END_REF][START_REF] Abboud-Blanchard | Teachers' activity in exercices-based lessons. Some case studies[END_REF]. The data analysis is qualitative and relates to: lesson preparation, class observation and answers to questionnaires and interviews. The analysis provides a plurality of local results which are interpreted within an Activity Theory (AT) framework.

THEORETICAL FRAME

The study of the integration of a new tool, here EEB, in the teacher's activity requires taking into account a multiplicity of factors, particularly the institutional and social contexts in which the teacher practices her/his profession. Thus, the framework chosen for this study is AT which offers a holistic approach enabling better understanding of the complexity of EEB integration. This theory developed by the Russian psychologists, [START_REF] Leont'ev | Problems of the Development of the Mind[END_REF] and [START_REF] Vygotsky | Pensée et langage, traduction intégrale par Françoise SEVE[END_REF], studies a subject acting on an object to produce a result. The activity of the subject is not "immediate" but "is mediated" by tools, both psychological and physical at her/his disposal. The system formed by these three poles, is called a "production system". Moreover, the subject does not act alone; her/his activity is socially anchored. [START_REF] Engeström | Developmental studies of work as a tesbench of activity theory: The case of primary care medical practice[END_REF][START_REF] Engeström | Activity theory and individual social transformation[END_REF] modelled the social aspect of activity by adding to the "production system" three new poles: community, the set of subjects aiming for the same object; rules, which govern this community and division of labour, which refers to the hierarchical organisation as well as the horizontal division of tasks between individuals. Thus the activity of the subject is understood as a dynamic process, the result of interrelationships between these poles. Engeström describes tensions between the poles of the system as characterising system activity and driving system innovation.

Figure 1 Model of the Activity Theory of Engeström

The study of the teacher's activity using this type of modelling permits us to consider several aspects which take into account the whole context of the activity, and not only the classic didactical triangle: students, teacher and mathematical knowledge, to which would be added EEB. However, the use of the Engeström's model requires specifying with precision the poles. Thus, when this model is used to study teaching practices, it's clear that the subject is the teacher observed. However, the object of her/his activity can be the whole mathematical learning of the students, but it could also be, the learning of a precise mathematical topic. Further, the community can be the mathematics teachers of a high school or more generally several subjects (teachers, curriculum's leaders, teacher educators…) taking part in the teaching of mathematics. So we first begin by briefly presenting how in our study we consider the poles of the system.

 The object of the activity, in Engeström's model, refers to the "raw material" or the "place where is situated the difficulty" which concerns the activity and which is modelled and transformed in the form of results. In our case, the object of the activity consists of the students and their mathematical work.

 The tool allows the subject to exercise her/his activity. It is a set of tools or of instruments. The essential instrument in our study is the EEB.

 The community concerns in Engeström's model, all the subjects who share the same object. The same subject, for a fixed object, can belong to several communities. Here, we consider different communities to which the teacher might belong, for example the community of the teachers of a high school or the community of the users of an EEB.

 The division of labour is about how members of the same community share the work. For example, several teachers may choose to prepare courses by team or to divide their students into joint workshop or to develop together educational resources (EEB or other ...).

 Rules are all the regulations, the constraints, the implicit or explicit standards which organise the system of activity. For example, in our case, it could be institutional rules concerning the curricula. Rules can also concern the explicit or implicit agreements which govern the community.

Therefore, modelling teaching activity by using Engeström's development of AT facilitates taking account of how the teacher uses different tools and deals with the institutional and social context while integrating EEB. Within AT, only actions of the subject [START_REF] Leont'ev | Problems of the Development of the Mind[END_REF] are observable. The actions of the teacher are thereby going to inform about her/his, activity. The types of such actions are described in the next section.

DATA AND METHODOLOGY

The data consider thirty teachers and in a more particular way, a sub-sample of six teachers. For the latter, data are more numerous including observations in their classes and several interviews. We firstly analysed the activity of the teachers of the sub-sample. Secondly, a comparison with the analyses concerning the wider sample facilitated the production of results related to the regularities and the differences between teachers using EEB.

Data was used to investigate the three phases in the activity of a teacher teaching a mathematics lesson using EEB: the preparation of the lesson, its progress and the reflexive return the teacher makes on this lesson.

The activity of preparation is easily observable through the scenario, made by the teacher and provided to the students via the EEB. It is analysed firstly from the point of view of the choices of the EEB to be used. Then the scenario and the tasks chosen in the EEB by the teacher are analysed considering mainly the complexity of the given task [START_REF] Robert | Outils d'analyse des contenus mathématiques enseignés au lycée et à l'université[END_REF] and the status of the knowledge involved in the students' activity: new knowledge, knowledge in development or old knowledge supposed to be already acquired.

The progress in class is analysed via the transcription of the lesson recording as well as the notes of the observers who are particularly sensitive to the types of use of the various tools: EEB, worksheets, blackboard and textbooks. The latter allows to note associations between these tools and to understand complementarities which they engender. To understand the way the teachers help students solving the tasks proposed through the EEB, the interactions in the classroom are also investigated. Their collective or individual character is particularly taken into account.

Finally, interviewing the teacher provides access to her/his reflexive work after the lesson. Special attention is given to the project of modifications to bring to the lesson itself but also to the whole teaching process. Let us however note that these last data are declarative and not actually observed.

RESULTS AND INTERPRETATIONS

The data analysis shows that using EEB comes along with multiple modifications in the teacher's activity. Engeström's model supplies a unifying frame susceptible to interpret the plurality of the analysis's results. The first subsection below gathers the results characterising the activity of teachers using EEB by referring to the "production system" of Engeström's model. The focus is afterwards put on the social dimension of the activity of the teachers. The last subsection illustrates the dynamics of this activity observed over the three years of experiment.

3.1.

The "production system" of the teacher's activity

The main result here is that the object of the activity, i.e. the mathematical work of the students, has a great regularity in all the data analysis. This regularity is expressed by both a generic schema of preparation and progress of lesson with an EEB and by similar responses to the tensions identified between the poles of the triangle.

Generic schema

All the lesson-observations show that the scenario is constituted by an orderly suite of exercises presented in a numerical work sheet. Only knowledge in development or old knowledge is concerned. It seems unlikely to make students work on new knowledge with EEB because such tools are essentially designed for training activities only. Moreover, the objectives of the teachers for these lessons are always limited to non-complex tasks.

The progress of the sessions split generally into three phases. The first phase of "starting up" is very brief; the teacher tells the students to settle down, to connect and to download the numerical exercise sheet that she/he had prepared. During the second phase, which is very long, the students work individually and the teacher moves from one student to another to provide help, the interventions are thus mainly individual. The final phase is always extremely brief. The teacher declares the end of the session and asks to switch off the computers. Even if these three phases could be usual for a "training session", their durations are particularly specific to the EEB context and seem to arise from the influence of the EEB on the object of the activity.

Dealing with tensions

Let us see how Beatrix, a high school teacher, begins a session intending to make students revise linear functions:

Sit down, rather one by table (…) When you arrive at the working session (the numerical exercise sheet); you pay attention on the comments that I gave you, that I wrote at the beginning. (…). You call me to show me if it is all right. I want to see some good work (…). And you do not forget concerning exercise 7 and 8, to write on your exercises book how you found the right answer (…)

We notice that Beatrix insists on the reading of the comments that she wrote more than on the reading of the statements of exercises which are in the EEB. Beatrix wants also to check and confirm herself the results of the students while the EEB could do it also. These two elements, observed in several cases, illustrate in our opinion, tensions between the subject and the tool. The teachers seem to have the feeling to be in "competition" with the EEB, i.e. it disrupts well-established patterns of their activity.

The numerical work sheets are generally very precise and too long to be accomplished within one session. Questioned on this point, teachers specify that they are afraid that students miss work or do not work in a way that suit them. Everything seems to go on as if the teachers, taking the risk' to introduce a new tool into their learning process, control as much as possible the variability of the situation.

Finally, a recurring difficulty is highlighted by all teachers. Working with EEB allows students to check their answers without having to explicit the processes. However, teachers' aims usually focus on the process more than the answer. For instance, Beatrix specifies at the end of her first intervention:

(…). And you do not forget concerning exercise 7 and 8, to write on your exercises book how you found the good answer. (…)

These two difficulties could be interpreted in terms of tensions between tools and object of the activity, that the teacher has to manage.

Influence of the social dimension on the teacher's activity

The "production system" is not sufficient to explain all the complexity of the subjects' activity. The use of technologies could be felt as difficult by teachers, which sometimes makes them reticent to this use. If teachers are not ready to fully use the EEB, one can wonder why some of them choose to use it. The study of the whole system, including the poles: rules, community and division of the labour, brings elements of explanation.

In the French context, teachers are asked (through curricula recommendations) to use technology on a regularbasis. In addition, they also have to provide individualized assistance to weak students. Thus EEB may appear as tools which make it possible to answer both these two institutional injunctions. This shows how rules can influence teachers' decision-making.

Moreover, we notice that, even if the teachers are apparently free to choose the EEB they prefer, it seems that the rules of membership in a community have a strong influence on this choice. For instance, the choice of the EEB to be used is the same for all the teachers of professional high schools or for most of the teachers belonging to the same regional education authority.

Finally, some EEB offer environments that facilitate cooperation within the educative community; such as group of teachers collaborating with EEB designers to create suitable exercises.

Dynamics of the teacher's activity

Any activity modifies the reality which surrounds it as well as the subject itself. Thus, themodel introduced in first section above requires a dynamic reading: the activity is going to produce results which are going to modify the subject and its environment. The outcomes of the activity system are transformations of reality by the subject's activity. We consider that these changes may affect the "state" of students as well as the "state" of the subject (the teacher).

Evolution of the subject

One of the first results is the modification of the subject. Teachers declared that the EEB-based lessons had enabled them to test extremely simple exercises that they might not otherwise have thought of using, but which appeared useful in the teaching process. They also became aware of student's errors that they had not suspected; which commits them to adjust their teaching practices taking into account these precise points. For example, Claude noticed, thanks to a randomisation of parameters in an EEB exercise, that his students did not understand that a linear function f(x) = ax was a particular case of the function f(x) = ax+b.

An evolution concerning all the teachers observed is the articulation by various devices of the work on computer and the paper-and-pencil work, and more generally the integration of the work with an EEB in the whole teaching process. It is mainly in developing these intermediate devices that the teachers are going to exercise their creativity and are thus going to be transformed themselves.

Modification of the social dimensions

Following the use of an EEB, a teacher can decide to participate in the community of its users and by the same to exchange for example through forums with others teachers and, in certain cases, to get organised to make a division of labour. She/he can also convince colleagues of the same high school to work together so it can facilitate her/his task by a working division. But it also can complicate it when for example the computer room is little available. Finally, some teachers may have fruitful exchanges with the developers of the EEB.

It is also possible that rules change. For instance, due to financial restrictions, institutional injunctions to make sessions of Individualised Assistance for weak students, might disappear..

CONCLUDING REMARKS

The introduction of a new tool, an EEB, in the teaching process is an innovation bringing research questions which mainly are: How and why do teachers use EEB? What effect does this use have on their teaching activity? The use of Engeström's model enabled us to answer these questions.

Firstly, the top of Engeström's model i.e. the "production system" brings to light on the one hand a general view on how do teachers implement EEB in their teaching through a generic format of EEB lessons. On the other hand, focusing on some tensions between the triangle's poles help to understand how teachers deal with some constraints due to the specific design of these technology tools.

Nevertheless, even if teachers seem to manage to implement EEB, this remains difficult for them relatively to the whole teaching process. These difficulties are mainly due to the fact that using EEB disturbs the well-established activity. For instance, a systematic use of EEB would entail to work only on knowledge in progress without collective conclusion and thus would prevent intoducing new notions. Further, we showed that students using EEB focused on results of exercises rather than on solving processes.

The social dimensions i.e. the bottom of Engeström's model allowed understanding why, in spite of these inconveniences, some teachers choose to use EEB. Finally, the study of the dynamic aspects of the model showed how this activity is not stabilised but is the result of various negotiations between strengths in movement.

However the very general character of the model does not seem to allow taking into account specific aspects of the activity connected to the mathematical content at stake. To synthesise, we could say that this model offers a systemic vision allowing drawing the shape of the teacher's activity in its entirety, but at the same time it masks the access to a level of singularity often essential in mathematics education research.

BIOGRAPHICAL NOTE:

Maha Abboud-Blanchard is Associate professor of mathematics education at the UCP and member of the LDAR research team of didactics of mathematics, University Paris-Diderot. Her research interests concern the use of technology in mathematics teaching and in mathematics teacher education. She is the leader of a university team working on developing resources for the training of secondary teachers with a focus on the use of technologies. She had also led, or been involved in, several national projects aiming at understanding mathematics teachers' practices in technology environments and the effects of professional development on such practices.

Claire Cazes is Associate professor of mathematics education at the UPMC (University Pierre et Marie Curie) and a member of LDAR research team of didactics of mathematics, University Paris-Diderot. She in charge of the ICT course for future teachers at UPMC. Her subjects of research are the conception, the use and the integration of ICT in mathematics education. She has already participated in several national research projects (GUPTEn), European projects (TELMA, REMATH, Edumatic, ActivMath) and International projects (PreNum-AC). All these projects concern the conception, the use, the integration and the spread of the ICT and implement cross-experiments between various countries.

www.technologyinmatheducation.com International Journal of Technology in Mathematics Education Vol 19 No 4


Eyal Kushilevitz
email: eyalk@cs.technion.ac.il

Rafail Ostrovsky
email: rafail@cs.ucla.edu

Emmanuel Prouff
email: emmanuel.prouff@ssi.gouv.fr

Adi Rosén

Adrian Thillard
email: adrian.thillard@ssi.gouv.fr

Damien Vergnaud
email: damien.vergnaud@lip6.fr.

Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND

. Together with our lower bound, we thus approach the exact determination of the randomness complexity of and. To the best of our knowledge, the exact randomness complexity of private computation

Introduction

A multi-party private protocol for computing a function f is a distributed protocol that allows n ≥ 3 players P i , for 0 ≤ i ≤ n -1, each possessing an individual secret input x i , to compute the value of f (x) in a way that does not reveal any "unnecessary" information to any player. 1 The protocol proceeds in rounds, where in each round each player sends a message to any other player, over a secure point-to-point channel. The privacy property of such protocol means that no player can learn "anything" (in an information-theoretic sense) from the execution of the protocol, except what is implied by the value of f (x) and its own input. In particular, the players do not learn anything about the inputs of the other players. Private computation in this setting was the subject of considerable research, see e.g., [START_REF] Ben-Or | Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)[END_REF][START_REF] Chaum | Multiparty unconditionally secure protocols (extended abstract)[END_REF][START_REF] Asharov | A full proof of the BGW protocol for perfectly secure multiparty computation[END_REF][START_REF] Chor | A zero-one law for boolean privacy[END_REF][START_REF] Kushilevitz | Randomness in private computations[END_REF][START_REF] Kushilevitz | Characterizing linear size circuits in terms of privacy[END_REF][START_REF] Gál | A theorem on sensitivity and applications in private computation[END_REF]. In addition to its theoretical interest, this setting constitutes the foundation for many cryptographic applications (in information theoretic settings) such as electronic secret ballot.

Randomness is necessary in order to perform private computations involving more than two players (except for the computation of very degenerate functions). That is, the players must have access to (private) random sources. As randomness is regarded as a scarce resource, methods for saving random bits in various contexts have been suggested in the literature, see, e.g., [START_REF] Nisan | Extracting randomness: A survey and new constructions[END_REF][START_REF] Goldreich | Modern Cryptography, Probabilistic Proofs and Pseudorandomness[END_REF] for surveys. Thus, an interesting research topic is the design of randomness-efficient private protocols, and the quantification of the amount of randomness needed to perform private computations of various functions and under various constraints. This line of research has received considerable attention, see, e.g., [START_REF] Kushilevitz | A randomness-rounds tradeoff in private computation[END_REF][START_REF] Kushilevitz | Randomness in private computations[END_REF][START_REF] Kushilevitz | Characterizing linear size circuits in terms of privacy[END_REF][START_REF] Blundo | Randomness complexity of private computation[END_REF][START_REF] Blundo | Randomness recycling in constant-round private computations (extended abstract)[END_REF][START_REF] Jakoby | Private computations in networks: Topology versus randomness[END_REF][START_REF] Data | Communication and randomness lower bounds for secure computation[END_REF][START_REF] Rosén | A new approach to multi-party peer-to-peer communication complexity[END_REF].

As in most of the work on the randomness complexity of private computations, we concentrate here on the computation of boolean functions, where the input x i of each player is a single input bit. Previous work on the randomness complexity of private computations revealed that there is a tradeoff between randomness and time (i.e., number of communication rounds) for the private computation of xor [START_REF] Kushilevitz | A randomness-rounds tradeoff in private computation[END_REF], or gave lower bounds on the number of rounds necessary to privately compute any function, in terms of the sensitivity of the function and the amount of randomness used [START_REF] Gál | A theorem on sensitivity and applications in private computation[END_REF]. However, if one is allowed an arbitrary number of rounds for the computation then, prior to the present work, there were no known lower bounds on the number of random bits necessary for private protocols computing explicit boolean functions (except that some randomness is indeed necessary, i.e., no deterministic private protocol exists). 2 In fact, Kushilevitz et al. [START_REF] Kushilevitz | Characterizing linear size circuits in terms of privacy[END_REF] gave a relation between the number of random bits necessary to privately compute a function f : {0, 1} n → {0, 1}, and the Boolean circuit size necessary to compute f ; it is proved, among other things, that the class of boolean functions that have O(1)-random, 1-private, protocols is equal to the class of boolean functions that have linear size circuits. This, perhaps surprising, connection to circuit size explains the difficulty of proving ω(1) lower bounds on the number of random bits necessary for the private computation of any explicit boolean function f , as such a result would imply superlinear lower bounds on the circuit size of f -a notoriously difficult problem. 3 Additional connections between the randomness complexity of the private computation of a function to other complexity measures, such as its sensitivity, have been shown in, e.g., [START_REF] Kushilevitz | A randomness-rounds tradeoff in private computation[END_REF][START_REF] Blundo | Randomness complexity of private computation[END_REF][START_REF] Kushilevitz | Amortizing randomness in private multiparty computations[END_REF].

This leaves the interesting, and perhaps feasible, task to determine the exact randomness complexity of the private computation of boolean functions of linear circuit size, where each player has a single input bit. This class of functions includes quite a few interesting functions f and, in particular, the basic functions xor and and. Indeed, the functions xor and and serve as basic building blocks for private protocols that rely on the boolean-circuit representation of f (more generally, addition and multiplication are used as building blocks for protocols that use the arithmetic-circuit representation of f ). In the context of lower bounds for communication complexity of private protocols, these building blocks also serve as the center of analysis (as a first step for a more general understanding), see, e.g., [START_REF] Chor | A communication-privacy tradeoff for modular addition[END_REF][START_REF] Damgård | Unconditionally secure computation with reduced interaction[END_REF][START_REF] Damgård | On the communication required for unconditionally secure multiplication[END_REF].

It is known that xor can be computed privately using a single random bit, for any number of players, and this is optimal since no deterministic private multiparty protocol can exist (see [START_REF] Kushilevitz | A randomness-rounds tradeoff in private computation[END_REF]). To the best of our knowledge, there is no exact determination of the randomness complexity of private computation for any other explicit function. Furthermore, prior to the present paper, there was no lower bound showing for any explicit boolean function that it cannot be privately computed (in the natural setting that we consider here, i.e., where each player has one input bit) using a single random bit.

In this paper, we give the first such lower bound, showing that the function and cannot be privately computed using a single random bit. 4 We further case of and (Disjointness with m = 1), the lower bound of [START_REF] Rosén | A new approach to multi-party peer-to-peer communication complexity[END_REF] only implies, in our context, the trivial claim that and cannot be privately computed by a deterministic protocol. 3 When the protocol has to be resilient against coalitions of t > 1 players (so called t-private protocols) several ω(1) lower bounds on the number of random bits necessary for private protocols for explicit functions have been proved. Kushilevitz and Mansour [START_REF] Kushilevitz | Randomness in private computations[END_REF] proved that any t-private protocol for xor requires at least t random bits. Blundo et al. [START_REF] Blundo | Randomness complexity of private computation[END_REF] gave lower bounds for two special cases. Namely, they proved that if t = n -c, for some constant c, then Ω(n 2 ) random bits are necessary for the private computation of xor, and if t ≥ (2 -√ 2)n, then Ω(n) random bits are necessary. Gal and Rosén [START_REF] Gál | Omega(log n) lower bounds on the amount of randomness in 2-private computation[END_REF] proved that Ω(log n) random bits are necessary for 2-private computation of xor. 4 In a different setting, namely, where there are two input players, Alice and Bob, and a third output player, Charlie, Data et al. [START_REF] Data | Communication and randomness lower bounds for secure computation[END_REF] also study the randomness (and make the first step towards determining the exact randomness complexity of the private computation of and by showing an improved upper bound of 8 on the number of random bits necessary for such computation, and we strengthen this upper bound to 7 for the special case of 3 players. The rest of the paper is organized as follows. In Section 2, we define the model and the complexity measures that we consider. In Section 3, we prove that the private computation of and cannot be performed with a single random bit. In Section 4, we give a number of upper bounds on the randomness complexity of private computation of and.

Preliminaries

Let f : {0, 1} n → {0, 1} be any Boolean function. A set of n players P i (0 ≤ i ≤ n -1), each possessing a single input bit x i (known only to P i ), collaborate in a protocol to compute the value of f (x). The protocol operates in rounds.

In each round each player may toss some (fair) random coins, and then sends messages to the other players (messages are sent over private channels so that other than the intended receiver no other player can see them). After sending its messages, each player receives the messages sent to it by the other players in the current round. Without loss of generality (because we are not interested in this paper in the number of rounds), we assume that the messages sent by the players consist of single bits. In addition, each player locally outputs the value of the function at a certain round. We say that the protocol computes the function f : {0, 1} n → {0, 1} if for every input x ∈ {0, 1} n , and for any outcome of all coin tosses, the output produced by each player is always f (x) (i.e., perfect correctness).

To formally define a protocol we first define the notion of a view of a player.

Definition 1. (View)

The view of player P i at round t ≥ 1, denoted V t i , consists of the input bit to player P i , i.e. x i , the messages received by P i in rounds 1 to t -1, and the results of the coin tosses performed by player P i in rounds 1 to t. Let V t i be the set of possible views of player P i at round t. Let V t i be the view V t i without the coins tossed at round t, and let Vt i be the set of possible values of V t i .

Definition 2. (Protocol)

A protocol consists of a sequence of rounds, where each round t ≥ 1 is formally defined by the following functions:

-S t, i : ( Vt i × {0, 1} -1 ) → {stop, toss}, for ≥ 1, defining if another random coin is to be tossed by player P i , given Vt i and the values of the -1 random coins tossed so far by player P i in round t. m t i,j : V t i → {0, 1}, for 0 ≤ i, j ≤ n -1, defining the message P i sends to P j at round t. communication) complexity of secure computation (in particular of the and function; see [START_REF] Data | Communication and randomness lower bounds for secure computation[END_REF]Thm. 11]).

-O t i : V t i → {0, 1, ⊥}, for 0 ≤ i ≤ n -1, defining if and what value player P i outputs at round t. Since the views are increasing, we can require that each player output a non-null output only in one round.

Sometimes it is more convenient to model the coin tossing done by each player, as a set of binary random tapes R i , each R i being provided to player P i . The number of random coins tossed by player P i is the number of random bits it reads from its random tape.

We denote by r i a specific random tape provided to player P i , by r = (r 1 , . . . , r n ) the vector of random tapes of all the players, and by R = (R 1 , . . . , R n ) the random variable for these tapes. Note that if we fix r, we obtain a deterministic protocol. Definition 3. (Randomness Complexity) A d-random protocol is a protocol such that, for any input assignment x, the total number of coins tossed by all players in any execution is at most d.

Our main question in this paper is what is the randomness complexity of the best protocol (in terms of randomness complexity) of private protocols for the boolean function and.

Informally, privacy with respect to player P i means that player P i cannot learn anything (in particular, the inputs of other players) from the messages it receives, except what is implied by its input bit, and the output value of the function f being computed. 5 Formally, denote by c i a specific sequence of messages received by P i , and by C i the random variable (depending also on R) for the sequence of messages received by P i . We define: Definition 4. (Privacy) A protocol A for computing a function f is private with respect to player P i if, for any two input vectors x and y such that f (x) = f (y) and x i = y i , for any sequence of messages c i , and for any random tape r i provided to

P i , P r[C i = c i |r i , x] = P r[C i = c i |r i , y],
where the probability is over the random tapes of all other players. A protocol is said to be private if it is private with respect to all players.

Lower Bound

In this section we prove that private computation of and of n bits, n ≥ 3, cannot be performed with a single random bit. We note that a lower bound on the number of random bits of private computation for n > 3 does not follow from a lower bound for n = 3, because, in general, simulating by 3 players a protocol on n > 3 players may violate the privacy requirement.

Our result for and is in contrast to the situation for the function xor, which can be computed privately using a single random bit. Our result constitutes, to the best of our knowledge, the first lower bound that quantifies the amount of randomness needed to privately compute an explicit boolean function (without any limitation on the protocol, such as its round complexity).

In the course of this proof, we denote by 1 the all-1 input of length n, and by e S , for S ⊆ {1, . . . , n}, the input assignment of all 1's except at the coordinates in S. Specifically, we use e j to denote the vector with 0 at position j and 1's elsewhere 6 and e i,j to denote the vector with 0's at positions i, j and 1's elsewhere.

Assume, towards a contradiction, that π is a 1-random private protocol for and. We assume w.l.o.g. that π is in a "canonical form", that we define as follows: A protocol is in canonical form if no message m, sent from player P i to player P j at round t, can be inferred from the input x j , the private randomness of player P j , and the messages previously received by player P j (i.e., either received in round t < t, or in round t from a player P i , for i < i). In particular, no message in a protocol in canonical form is a constant message.

Obviously, for π to compute and there must be at least one non-constant message defined in π. Consider any such message, m, sent in round t = 1 (since π is in canonical form there must be at least one such message in round t = 1), say, from player P i to player P j . Since the message m is sent in round t = 1, it can depend only on x i and the random bits tossed by P i by round t = 1. To preserve privacy with respect to P j , the message m has to have the same distribution when x i = 0 and when x i = 1. Since π is 1-random, the number of random bits tossed by any single player, in particular P i , in any execution of the protocol, is at most 1. It follows that P r[m = 0] = 1/2, and P r[m = 1] = 1/2 regardless of the value of x i , thus P i must toss a random bit by round t = 1 whether x i = 0 or x i = 1. To conclude, there is some player (the sender of m), w.l.o.g. denote it P 0 , that regardless of its input, and in any execution, tosses in π a single random bit, denote it r. Since π is 1-random, no other random bit is tossed in π in any execution (by any player). Thus, since all messages in π can depend only on the input bits, x i , 0 ≤ i ≤ n -1, and the single random bit r tossed by player P 0 , we may consider any message sent in π as a sum of monomials in x i , 0 ≤ i ≤ n -1, and r. We now analyze some properties of the (assumed) protocol π.

Lemma 5. All messages m sent in π are of the form m = r⊕ i∈S⊆{0,...,n-1} x i or m = 1 ⊕ r ⊕ i∈S⊆{0,...,n-1} x i .
No player receives during the execution of π two (distinct) messages.

Proof. We prove the claim by induction on the round number t ≥ 1, i.e., we prove that until round t ≥ 1 all messages are of the form m = r ⊕ i∈S⊆{0,...,n-1} x i or m = 1 ⊕ r ⊕ i∈S⊆{0,...,n-1} x i and that no player receives by the end of round t two (distinct) messages.

For the basis of the induction consider the first round t = 1 and the messages sent and received in this round. Clearly, a (non-constant) message in the first round can be sent only by player P 0 otherwise it consists of only the input bit of the sending player (or its negation) and the privacy property will be violated. Since no message is received before the messages of the first round are sent, the messages sent by player P 0 at round t = 1 are a function of only r and x 0 . We argue that such message has therefore to be of the form m = r ⊕ x 0 (or m = 1 ⊕ r ⊕ x 0 ) or of the form m = r (or m = 1 ⊕ r): since m depends only on r and x 0 , the monomials in m can only be 1, x 0 , r, and rx 0 . We claim that if the monomial rx 0 appears in the sum representing m then the privacy property is violated with respect to the player receiving the message, say player P j . This is because the possible messages that include rx 0 are: rx 0 , rx 0 ⊕ x 0 = (r ⊕ 1)x 0 , rx 0 ⊕ x 0 ⊕ r = (r ⊕ 1)(x 0 ⊕ 1) ⊕ 1, and rx 0 ⊕ r = r(x 0 ⊕ 1) (and their negations). Consider the two input assignments e 0,j and e j . Observe that the distribution of each one of these messages on the inputs e 0,j and e j is different, which violates the privacy requirement ("leaking some information" on x 0 to P j ). For example, rx 0 is always 0 in e 0,j and uniformly distributed in e j . The argument for the other cases is similar.

It follows that the messages sent in round t = 1 are of the desired form. Since only player P 0 can send messages in round t = 1, it also follows that by the end of round t = 1 each player receives at most a single message. Thus, the claim holds for round t = 1.

We now prove the claim for round t > 1, assuming the induction hypothesis holds for round t -1. Consider player P i and the message m t i,j that it sends in round t to player P j . Since this message is computed by player P i at round t, it can be expressed as a function of x i , of the single message m that player P i receives in some round t < t (if such a message exists) and, if i = 0, of the random bit r. We distinguish between two cases: when i = 0, and when i = 0.

When i = 0, the message m t i,j sent by P i is the sum of a subset of the monomials 1, x i , m, mx i . If the monomial mx i does not appear in the sum, then m t i,j is of the desired form (otherwise m t i,j is either a messages that can be inferred by P j or a message that violates the privacy property with respect to P j ; in any case it cannot be part of the protocol.) 7 On the other hand, we show in the following that any message defined by any of the 8 sums of monomials that include the monomial mx i violates the privacy property with respect to P j , and hence such message cannot be part of the protocol. By the induction hypothesis m = r ⊕ k∈S⊆{0,...,n-1} x k (or 1 ⊕ r ⊕ k∈S⊆{0,...,n-1} x k ), for some S. Consider the former form, the latter is similar. For the message mx i (resp., 1 ⊕ mx i ) consider the inputs e i,j and e j and observe that on the the former input the message is always 0 (resp., 1) while on the latter it is m (resp., 1 ⊕ m), and hence does not exhibit the same distribution on the two inputs. Similarly, consider the messages mx i ⊕ x i = (m ⊕ 1)x i , mx i ⊕m = m(x i ⊕1), and mx i ⊕x i ⊕m = (m⊕1)(x i ⊕1)⊕1 (and their negations), and observe that the message has different distributions on the inputs e i,j and e j (in each of the cases, for one of these two inputs the value of the message is either m or its negation, i.e., the support of the distribution is of size 2, and for the other input the distribution has support of size 1). For i = 0, player P i = P 0 has also the random bit r, so the message sent by P 0 at round t to player P j is the sum of a subset of the monomials 1, x 0 , m, mx 0 , r, rx 0 , rm, rmx i . But, no message m can be received by player P 0 before round t, since any message of the form r ⊕ k∈S⊆{0,...,n-1} x k (or m = 1 ⊕ r ⊕ k∈S⊆{0,...,n-1} x k ) would either violate the privacy (since P 0 knows r), or would be such that P 0 can compute it itself. 8 It follows that the message sent by player P 0 at round t is the sum of a subset of the monomials 1, x 0 , r, rx 0 . But, we have proved above (when proving the base case of the induction) that in this case m t i,j must be r ⊕ x 0 (or 1 ⊕ r ⊕ x 0 ). We conclude that the messages sent in round t are of the desired form. Now, assume towards a contradiction that some player P j receives by the end of round t two (distinct) messages which, as we proved above, must be of the desired form. Denote q 1 = r⊕ i∈S1⊆{0,...,n-1} x i , and q 2 = r⊕ i∈S2⊆{0,...,n-1} x i . The two messages received by player P j are therefore m 1 = q 1 (or m 1 = 1 ⊕ q 1 ) and m 2 = q 2 (or m 2 = 1 ⊕ q 2 ), for some sets S 1 and S 2 . Consider now

Q = m 1 ⊕ m 2 . Observe that Q = i∈S ⊆{0,...,n-1} x i (or Q = 1 ⊕ i∈S ⊆{0,...,n-1} x i ) for S = S 1 S 2 .
If S ⊆ {x j } then, since π is of canonical form, one of the two messages m 1 and m 2 (the one arriving later) cannot exist in π. It follows that S ⊆ {x j } and the privacy property is violated with respect to player P j , as Q reveals information on the xor of the inputs in S . 9 A contradiction to π being private.

Therefore, the claim holds for round t.

Lemma 6. Consider the protocol π, an arbitrary player P j and an arbitrary round t ≥ 1. Then, player P j cannot compute the function and at the end of round t.

Proof. By Lemma 5, player P j receives by the end of round t at most a single message, and this message is of the form m = r ⊕ i∈S⊆{0,...,n-1} x i or m = 1 ⊕ r ⊕ i∈S⊆{0,...,n-1} x i . We distinguish between two cases. Case 1: For all k = j, k ∈ S. Since n ≥ 3, there exist two distinct k 1 , k 2 ∈ S, k 1 = j, k 2 = j. Consider the two inputs 1 and e k1,k2 . While AN D(1) = AN D(e k1,k2 ), the view of P j at the end of round t is the same on 1 and e k1,k2 and hence π must err on at least one of them (note that this in particular holds when j = 0; for all other players, who do not know r, the message m is uniformly distributed). Case 2: There exists an index k = j, k / ∈ S. Consider the two inputs 1 and e k . As in Case 1, π must err on at least one of these inputs.

We conclude that protocol π (a 1-random private protocol for and) does not exist.

Theorem 7. The private computation of the function and cannot be performed with a single random bit.

Upper Bounds

In this section, we provide significantly improved upper bounds on the randomness complexity of and. Specifically, we show that and on any number of players n can be privately computed using 8 random bits, and can be computed with 7 random bits for the special case of n = 3 players.

In order to present our protocol, we first present two building blocks which are used in our constructions. They are both implementations of informationtheoretic 1-out-of-2 Oblivious Transfer.

1-out-of-2 Oblivious Transfer

In a 1-out-of-2 Oblivious Transfer (1-2 OT) protocol two parties, Alice and Bob, engage in a protocol that allows Bob to choose which part of the information that Alice holds he wants to learn, in such a way that Alice does not learn which part of her information Bob learned.

More formally, for a 1-out-of-2 Oblivious Transfer protocol Alice has two bits b 0 and b 1 , and Bob has a selection bit s. Alice and Bob, together with a set of helper players, H, engage in a protocol at the end of which the following holds:

-Bob knows the value of b s .

-Bob does not learn any information on b 1⊕s (i.e., the transcript of Bob, given the values of s and b s , is identically distributed whether b 1⊕s is 0 or 1). -Alice does not learn anything (i.e., the transcript of Alice, given any choice of values for b 0 and b 1 , is identically distributed; in particular, it is independent of s). -The helper players do not learn anything (i.e., the transcript of each of them is distributed independently of the inputs s, b 0 , b 1 ).

We now give two implementations of this building block using a different number of helper players, and a different number of random bits. Both are used in our protocols.

4.1.1 Implementation 1: 3 random bits, 1 helper player. This implementation is given by Beaver [START_REF] Beaver | Precomputing oblivious transfer[END_REF]. There is one helper player, denoted by H. The protocol is defined as follows.

1. The helper player H tosses 2 uniformly distributed and independent random bits, r 0 and r 1 (to be used as masking bits), and one additional independent and uniformly distributed random bit p (to define one of the two possible permutations of {0, 1}). 2. H sends both r 0 and r 1 to Alice and it sends p and r * = r p to Bob. The fact that Bob learns the value of b s follows by simple case analysis (p = 0 or p = 1). For completeness, we sketch a proof of the privacy of this protocol. A more detailed formal proof is incorporated within the privacy proof for our protocol that uses the OT protocol as a sub-protocol. We observe the following:

-H does not receive any message and hence privacy is preserved with respect to H. -Alice receives from H the bits r 0 and r 1 and from Bob the bit i = s ⊕ p. All three are independent and uniformly distributed between 0 and 1 (as r 0 ,r 1 , and p are uniformly distributed and independent random bits). -Bob receives from H the bits p and r * = r p (but not the bit r 1⊕p ), and from Alice the bits m 0 = b 0 ⊕r i and m 1 = b 1 ⊕r 1⊕i . Observe that b s = m s ⊕r * , but p and m 1⊕s are both independent of m s and r * , and uniformly distributed.

4.1.2 Implementation 2: 2 random bits, 2 helper players. Here we assume that there are two helper players, denoted H 0 and H 1 . The protocol is defined as follows.

1. Alice tosses two independent random bits p and r.

2. Alice sends the message m 0 = b 0 ⊕ r to player H p , the message m 1 = b 1 ⊕ r to player H 1⊕p , and p and r to Bob. 3. Bob sends the bit 1 to player H s⊕p and the bit 0 to player H 1⊕s⊕p . 4. If player H 0 (resp., H 1 ) receives 1 from Bob, it sends to Bob the message m it received from Alice (i.e, either m 0 or m 1 ). Otherwise, if player H 0 (resp., H 1 ) receives 0 from Bob, it sends to Bob the (constant) message 0. 10 5. Bob "deciphers" the value of the bit he wants to learn (i.e., b s ) by computing b s = m ⊕ r, where m is the message Bob got from H s⊕p . 10 Clearly in this case the relevant helper player does not need to send any message to Alice. However in order to stay coherent with the model we use, we define which bit is sent in each round between any two players, unless for all inputs and all random coins values, no message is sent between the two.

The fact that Bob learns the value of b s follows from the protocol, by inspection. For completeness, we sketch a proof of the privacy of this protocol. A more detailed formal proof is incorporated within the privacy proof for our protocol that uses the OT protocol as a sub-protocol. We observe the following:

-Alice does not get any message and hence privacy is preserved with respect to Alice. -Each of H 0 and H 1 gets a single message from Alice, which is one of her input bits xored with r; it also received from Bob a bit which is either 0 or 1, depending on the value s ⊕ p; since r and p are uniformly random and independent, then privacy is preserved with respect to each one of the helper players H 0 and H 1 . -Bob receives p and r from Alice. Then, given the value of p and the value of s, known to Bob, it receives a constant message from one of H 0 or H 1 , and the message b s ⊕ r from the other (if s ⊕ p = 1 Bob receives the constant message from H 0 , and if s⊕p = 0 Bob receives the constant message from H 1 .) Hence, given the value of b s , the transcript of Bob is distributed uniformly.

The AND protocol

We first present a protocol, Π odd , applicable to an odd number of players; this protocol uses 8 random bits. This protocol serves to introduce the main ideas of our protocols, and is also the basis for a somewhat improved protocol for n = 3, that uses 7 random bits. Extending Π odd to work also for even number of players and keeping the 8 random bits bound requires some more effort, and we give such a protocol in Subsection 4.2.2, applicable to any n ≥ 4.

Odd number of players

We describe our protocol Π odd for odd number of players, n, denoted P 0 , P 1 , . . . , P n-1 .

initialization phase. In the initialization phase player P 0 tosses 3 random bits and plays the role of the helper player of implementation 1 of OT for all pairs of players where Alice is an odd player and Bob is the successive even player. Player P n-1 does the same for all pairs of players where Alice is an even player and Bob is the successive odd player. Specifically: Player P 0 tosses 3 random bits r 1 0 , r 1 1 , and p 1 . It sends the bits r 1 0 , r 1 1 to all odd players, and sends the bits p 1 and r 1 p 1 to all even players. Player P n-1 tosses 3 random bits r 0 0 , r 0 1 , and p 0 . It sends the bits r 0 0 , r 0 1 to all even players, and sends the bits p 0 and r 0 p 0 to all odd players. In addition, player P 0 tosses 2 additional random bits q 0 and q 1 . It sends q 0 to all odd players, and q 1 to all even players. P 0 also locally computes y 0 = q 0 ⊕q 1 ⊕x 0 . computation phase. This phase runs in n -1 rounds. The inductive invariant that we maintain is that at the end of round i ≥ 1 player P i has the value y i = q 0 ⊕ q 1 ⊕ Π i j=0 x j . In each round, the protocol will run an OT protocol. We give a detailed description of the rounds below. final phase. At the end of the computation phase, player P n-1 has (by the inductive invariant) the value y n-1 = q 0 ⊕ q 1 ⊕ Π n-1 j=0 x j . It sends this value to P 0 who xors it with q 0 ⊕ q 1 to obtain Π n-1 j=0 x j = AN D(x 0 , x 1 , . . . , x n-1 ). Player P 0 then sends this value to all other players. We now define how the computation phase is implemented so as to maintain the inductive invariant (and privacy, as we prove later). The invariant clearly holds at the end of round 0 (i.e., before the computation phase starts) since player P 0 has x 0 , q 0 , and q 1 and hence can compute y 0 . Now, in round i ≥ 1 players P i-1 and P i engage in a 1-2 OT protocol, using Implementation 1 described above. The values that Alice (i.e., player P i-1 ) holds for the OT protocol are b 0 = q i mod 2 and b 1 = y i-1 . Observe that Alice has b 0 from the initialization phase, and b 1 by the inductive invariant. The selection bit of Bob (i.e., player P i ) is s = x i . The random bits used for the OT protocol are r k 0 , r k 1 , and p k , where k = (i + 1) mod 2. Observe that P i and P i-1 receive in the initialization phase the random bits needed in order to simulate Alice and Bob of the OT protocol (i.e., r k 0 , r k 1 for Alice and p k , r k p k for Bob). Let v i denote the output (i.e., the bit learned by Bob) of the OT protocol run in the i-th round.

It follows that at the end of the OT protocol, if the value that player P i holds is x i = 0, then it gets from player P i-1 the value v i = q i mod 2 , and if x i = 1 then it gets the value v i = y i-1 = q 0 ⊕ q 1 ⊕ Π i-1 j=0 x j . Now, if x i = 0 then Π i j=0 x j = 0, and player P i has y i by calculating q i mod 2 ⊕ q (i+1) mod 2 , where the former is just v i and the latter is received from P 0 in the initialization phase. If x i = 1 then Π i j=0 x j = Π i-1 j=0 x j and player P i just sets y i = v i . The total number of random bits used in this protocol is 8: the protocol uses 3 bits for each of the two sets of OT protocols, and 2 additional masking bits, q 0 and q 1 .

It remains to prove that privacy is preserved with respect to all players. Intuitively, there are n -1 invocations of the OT protocol. Each internal player (i.e., all players except P 0 and P n-1 ) participates in two OT invocations, once as Alice (with the following player) and once as Bob (with the preceding player), each of these two invocations using different sets of random bits, one set from P 0 and one set from P n-1 . Players P 0 and P n-1 participate each in a single invocation of the OT protocol, P 0 as Alice with P 1 and P n-1 as Bob with P n-2 . Hence the number of players must be odd (to guarantee that the random bits used by the OT protocol of P n-1 and P n-2 come from P 0 and not from P n-1 ). Formally, Theorem 8. The AND protocol Π odd is private for n odd, n ≥ 3.

Proof. We first prove the claim for players P i , 0 < i < n -1, and then for P 0 and for P n-1 .

For 0 < i < n -1, observe that player P i receives messages pertaining to exactly two OT invocations, one in which it plays the role of Alice, and one where it plays the role of Bob. In addition, P i receives from player P 0 either the bit q 0 or the bit q 1 and, at the end of the protocol, the computed value of the function.

We prove the claim for i even (the case of i odd is analogous, switching the roles of the random bits, i.e., flipping their superscripts, and switching q 0 and q 1 ). The messages that such player P i receives are:

1. During the initialization phase: bits r 0 0 , r 0 1 , p 1 , r 1 p 1 , q 0 . 2. During the OT protocol with player P i-1 (i.e., when playing the role of Bob):

q 1 ⊕ r 1 j and y i-1 ⊕ r 1 1⊕j , where j = x i ⊕ p 1 . 3. During the OT protocol with player P i+1 (i.e., when playing the role of Alice):

x i+1 ⊕ p 0 . 4. In the final phase, from player P 0 , AN D(x 0 , x 1 , . . . , x n-1 ).

Observing the nine messages received by P i , one can verify that:

1. The messages received in Stage 1 are just the random bits r 0 0 , r 0 1 , p 1 , r 1 p 1 , q 0 . 2. For the messages of Stage 2 we distinguish between two cases depending on the value of x i . If x i = 0 then the first message is q 1 ⊕ r 1 p 1 and the second one is y i-1 ⊕ r 1 1⊕p 1 . We have that the first message includes a xor operation with q 1 , and the second one a xor with r 1 1⊕p 1 . If x i = 1 then the first message is q 1 ⊕ r 1 1⊕p 1 and the second one is y i-1 ⊕ r 1 p 1 . In that case, the first message includes a xor operation with r 1 1⊕p 1 and the second one a xor with q 1 (since by the inductive invariant, y i-1 = q 0 ⊕ q 1 ⊕ Π i-1 j=0 x j .) 3. The message received in Stage 3 includes a xor operation with p 0 . 4. The message received in Stage 4 is the value of the function.

Inspecting the distribution of the above messages, the last message (Stage 4) is, by definition, the value of the function; all other 8 messages are independent and uniformly distributed (in correspondence with the 8 random bits that are used): the bits r 0 0 , r 0 1 , p 1 , r 1 p 1 , q 0 in Stage 1, the two messages of Stage 2 one includes a xor operation with r 1 1⊕p 1 and the other with q 1 , and the message received in Stage 3 which includes a xor operation with p 0 . Hence, the privacy with respect to P i follows.

Almost the same argument applies to player P n-1 as well. It receives a subset of the messages received by players P i , 0 < i < n -1, namely, those of Stages 1, 2, 4 above. In addition it knows the value of the random bit p 0 . But, since the message of Stage 3 is not received by P n-1 , the privacy with respect to P n-1 holds.

As to player P 0 , it receives the messages listed under Stages 1 and 3 above, and (from player P n-1 at the final phase) the message y n-1 = q 0 ⊕ q 1 ⊕ Π n-1 j=0 x j .

In addition, player P 0 knows the values of the random bits r 1 0 , r 1 1 , q 0 and q 1 . We have that the messages received in Stages 1 and 3 each includes a xor operation with an independent (uniformly distributed) random bit not known to P 0 . The message received in the final phase is determined by the value of the function, q 0 and q 1 . Hence, privacy with respect to player P 0 holds as well.

At least 4 players

If one attempts to apply the above protocol Π odd to an even number of players then privacy will not be preserved. This is because when players P n-2 and P n-1 engage in their OT protocol, they will do that with the random bits tossed by player P n-1 (while in the case of odd n these bits are tossed by the "helper" P 0 ).

To remedy this problem, we stop the computation phase one round earlier, that is, we run it for n -2 rounds only, at the end of which player P n-2 has, as in Π odd , the value y n-2 = q 0 ⊕ q 1 ⊕ Π n-2 j=0 x j . We then perform the last OT protocol of the computation phase using Implementation 2 defined above and fresh random bits. This, however, increases the total number of random bits used, and further requires that the total number of players is at least 4 (as required by Implementation 2 of OT ). While requiring at least 4 players is not an issue since we have another variant of the protocol for odd number of players, in order not to increase the total number of random bits used, we generate and distribute the random bits needed for the various OT invocations in a more efficient way. That is, while each internal player still participates in 2 OT invocations, we do not need totally separate 2 sets of random bits. Rather, it is sufficient to ensure that no player will receive two messages (of two different OT invocations) that "use" the same random bit. The resulting protocol uses a total of 8 random bits and is applicable to any n ≥ 4.

We now formally describe our protocol for n ≥ 4 players, denoted P 0 , P 1 , . . . , P n-1 . As indicated above, the high level structure of the protocol is the same as that of Π odd , with some modifications, most notably a different way to produce and distribute the random bits. initialization phase. In the initialization phase player P n-1 tosses 4 random bits u 0 , u 1 , u 2 , u 4 and defines a sequence of bits r 0 , r 1 , . . . , r , for = 2(n -2), recursively as follows: 11 r 0 = u 0 , r 1 = u 1 , r 2 = u 2 , r 4 = u 4 , and

r j = r j-3+rj-1 j > 1, j odd r j-6+(1⊕rj-4) j > 4, j even . (1)
Player P n-1 then sends to each player P i , 0 ≤ i ≤ n -2 the two bits r 2i , r 2i+1 .

11 Here and in the following we sometimes abuse notation and consider indices that involve summations over both N and F2 (denoted with the operands + and ⊕, respectively).

In addition, player P 0 tosses 2 additional random bits q 0 and q 1 . It sends q 0 to all odd players, and q 1 to all even players. P 0 also locally computes y 0 = q 0 ⊕ q 1 ⊕ x 0 . computation phase. This phase runs in n -1 rounds. The inductive invariant that we maintain is that at the end of round i ≥ 1 player P i has the value y i = q 0 ⊕ q 1 ⊕ Π i j=0 x j . In each round, the protocol will run an OT protocol. We give a detailed description of the rounds below. final phase. At the end of the computation phase, player P n-1 has (by the inductive invariant) the value y n-1 = q 0 ⊕ q 1 ⊕ Π n-1 j=0 x j . It sends this value to P 0 who xors it with q 0 ⊕ q 1 to obtain Π n-1 j=0 x j = AN D(x 0 , x 1 , . . . , x n-1 ). Player P 0 then sends this value to all other players.

The following lemma gives the properties of the sequence of bits r j , necessary both for the correctness of the protocol and for its privacy. The proof of this lemma is quite technical and the reader may wish to skip this proof. Lemma 9. For any 1 ≤ i ≤ n -2, the five bits r j , 2(i -1) ≤ j ≤ 2(i + 1), are such that 1. r 2i+1 = r 2(i-1)+r2i . 2. The four bits r 2(i-1) , r 2(i-1)+1 , r 2i , r 2(i+1) are independent and uniformly distributed.

Proof. We prove the lemma by induction on i. For the base of the induction (i = 1), observe that Point (2) is satisfied since r 0 , r 1 , r 2 , r 4 are set to be u 0 , u 1 , u 2 , u 4 , respectively, and these are independent and uniformly distributed random bits tossed by Player P n-1 . As to Point (1), r 3 is set to be equal to r r2 according to Equation (1) (first part, with j = 3). We now prove the lemma for i + 1 assuming it is correct for i. Note that the 5-tuple that corresponds to i + 1 partially overlaps the 5-tuple that corresponds to i.

Point (1) holds for i + 1 because by the first part of Equation (1) (taking j to be 2(i + 1) + 1) r 2(i+1)+1 = r 2i+1+r 2(i+1) .

As to Point (2), we consider both parts of Equation ( 1) and the value of r 2i . There are two cases:

1. If r 2i = 0:

r 2i+1 = r 2(i-1) (taking j = 2i + 1 for the first part of Equation ( 1)). r 2(i+2) = r 2(i-1)+1 (taking j = 2(i + 2) for the second part of Equation (1)).

If r 2i = 1:

r 2i+1 = r 2(i-1)+1 (taking j = 2i + 1 for the first part of Equation ( 1)).

r 2(i+2) = r 2(i-1) (taking j = 2(i + 2) for the second part of Equation (1)).

It follows that the 4-tuple of bits with indices 2i, 2i+1, 2(i+1) and 2(i+2), i.e., the 4-tuple (r 2i , r 2i+1 , r 2(i+1) , r 2(i+2 ) is equal to either the 4-tuple (r 2i , r 2(i-1) , r 2(i+1) , r 2(i-1)+1 ) (if r 2i = 0) or to (r 2i , r 2(i-1)+1 , r 2(i+1) , r 2(i-1) ) (if r 2i = 1), which are two permutations of the same 4 bits. By the induction hypothesis, these 4 bits are independent and uniformly distributed. Hence also Point (2) holds for i + 1.

We now define how the computation phase is implemented so as to maintain the inductive invariant (and privacy, as we prove later). The invariant clearly holds at the end of round 0 (i.e., before the computation phase starts) since player P 0 has x 0 , q 0 , and q 1 and hence can compute y 0 .

Similarly to protocol Π odd , in round 1 ≤ i ≤ n -2 (but not in round n -1, as is the case for Π odd ) players P i-1 and P i engage in a 1-2 OT protocol, using Implementation 1 described above. The values that Alice (i.e., player P i-1 ) holds for the OT protocol are b 0 = q i mod 2 and b 1 = y i-1 . Observe that Alice has b 0 from the initialization phase, and b 1 by the inductive invariant. The selection bit of Bob (i.e., player P i ) is s = x i . The random bits used for the OT protocol are r 2(i-1) and r 2(i-1)+1 held by Alice (player P i-1 ) and r 2i held by Bob (player P i ). Observe that P i and P i-1 receive these bits from P n-1 during the initialization phase. Further, by Lemma 9 held by player P i , all satisfy the properties required for the OT protocol to be correct (and private).

Finally, in round i = n -1, players P n-2 and P n-1 engage in an OT protocol as in previous rounds, but using Implementation 2 and using additional new random bits. 12 Specifically, P n-1 is Bob of the OT protocol and P n-2 is Alice; the helper players are P 0 (H 0 ) and P 1 (H 1 ), and we denote the two fresh random bits tossed by P n-2 by u 5 and u 6 (see Section 4.1.2). The use of Implementation 2 of the OT protocol in this round is the reason that the protocol described here works only for n ≥ 4.

As in protocol Π odd , let v i denote the output (i.e., the bit learned by Bob) of the OT protocol run in the i-th round, 1 ≤ i ≤ n -1. It follows that at the end of the OT protocol, if the value that player P i holds as input is x i = 0, then it gets from player P i-1 the value v i = q i mod 2 , and if x i = 1 it gets the value v i = y i-1 = q 0 ⊕ q 1 ⊕ Π i-1 j=0 x j . Now, if x i = 0 then Π i j=0 x j = 0, and player P i has y i by calculating q i mod 2 ⊕ q (i+1) mod 2 , where the former is just v i and the latter is received from P 0 in the initialization phase. If x i = 1 then Π i j=0 x j = Π i-1 j=0 x j and player P i just sets

y i = v i .
The total number of random bits used in this protocol is 8: u 0 , u 1 , u 2 , u 4 and q 0 , q 1 are tossed by player P 0 , and u 5 , u 6 are tossed by player P n-2 .

It remains to prove that privacy is preserved with respect to all players. Intuitively, there are n -1 invocations of the OT protocol. Each internal player (i.e., all players except P 0 and P n-1 ) participates in two OT invocations, once as Alice and once as Bob, and the privacy property with respect to these players will follow from the properties of the sequence of bits r j (Lemma 9). We now prove that the protocol is private.

Theorem 10. The AND protocol for n ≥ 4 is private.

Proof. We first prove the claim for players P i , 1 < i < n -2, and then for the players having special roles, P 0 , P 1 , P n-2 , P n-1 .

For 1 < i < n -2, observe that player P i receives messages pertaining to exactly two OT invocations, one in which it plays the role of Alice, and one where it plays the role of Bob (as implemented in Section 4.1.1). In addition, P i receives from player P 0 either the bit q 0 or the bit q 1 and, at the end of the protocol, the computed value of the function.

We prove the claim for i even (the case of i odd is analogous, switching the roles of q 0 and q 1 ). The messages player P i receives are:

1. During the initialization phase: bits r 2i , r 2i+1 , q 0 . 2. During the OT protocol with player P i-1 (i.e., when playing the role of Bob):

q 1 ⊕ r 2(i-1)+j and y i-1 ⊕ r 2(i-1)+(1⊕j) , where j = x i ⊕ r 2i . 3. During the OT protocol with player P i+1 (i.e., when playing the role of Alice):

x i+1 ⊕ r 2(i+1) . 4. In the final phase, from player P 0 , AN D(x 0 , x 1 , . . . , x n-1 ).

Observing the seven messages received by P i , one can verify that:

1. The messages received in Stage 1 are the bits r 2i , r 2i+1 , q 0 . 2. For the messages of Stage 2, we distinguish between two cases depending on the value of x i . If x i = 0 then the first message is q 1 ⊕ r 2(i-1)+r2i and the second one is y i-1 ⊕ r 2(i-1)+(1⊕r2i) . In this case, the first message includes a xor operation with q 1 , and the second one a xor operation with r 2(i-1)+(1⊕r2i) . If x i = 1 then the first message is q 1 ⊕ r 2(i-1)+(1⊕r2i) and the second one is y i-1 ⊕ r 2(i-1)+r2i . In this case, the first message includes a xor operation with r 2(i-1)+(1⊕r2i) and the second one a xor operation with q 1 (since by the inductive invariant, y i-1 = q 0 ⊕ q 1 ⊕ Π i-1 j=0 x j ). 3. The message received in Stage 3 includes a xor operation with r 2(i+1) . 4. The message received in Stage 4 is the value of the function.

The last message (Stage 4) is, by definition, the value of the function. From the observations above, it follows that the distribution of the other 6 messages is the same as the distribution of the tuple r 2i , r 2i+1 , q 0 , q 1 , r 2(i-1)+(1⊕r2i) , r 2(i+1) (if x i = 0) or the tuple r 2i , r 2i+1 , q 0 , r 2(i-1)+(1⊕r2i) , q 1 , r 2(i+1) (if x i = 1). But, using Lemma 9, we can conclude that both of these 6-tuples are uniformly distributed over the 2 6 possible binary vectors. Thus, privacy is preserved for all players P i , 1 < i < n -2.

Similar arguments apply to the remaining four players. Let b0 = q (n-1) mod 2 ⊕ u 6 and let b1 = y n-2 ⊕ u 6 (recall that player P n-2 tosses two random bits u 5 , u 6 , to be used by the OT protocol, Implementation 2, in round n -1). Player P 0 : Player P 0 receives the following messages: those listed under Stages 1 and 3 above; in round n -1 of the computation phase, when Implementation 2 of OT is invoked, P 0 receives from P n-2 either the message b0 = q n-1 mod 2 ⊕ u 6 or the message b1 = y n-2 ⊕ u 6 and from P n-1 the message x n-1 ⊕ u 5 ⊕ 1; and from P n-1 , at the final phase, the message y n-1 = q 0 ⊕q 1 ⊕Π n-1 j=0 x j . In addition, player P 0 has the values of the random bits q 0 and q 1 tossed by itself. Therefore, the messages received in Stages 1 and 3, as well as the messages received from P n-2 and P n-1 , each includes a xor operation with an independent (uniformly distributed) random bit not known to P 0 . The message received in the final phase is (together with q 0 and q 1 ) the value of the function. Hence, privacy with respect to P 0 holds. Player P 1 : Player P 1 receives the following messages: the messages listed under Stages 1, 3 and 4 above; In round n -1 of the computation phase, when Implementation 2 of OT is invoked, P 1 receives from P n-2 either the message b0 = q n-1 mod 2 ⊕ u 6 or the message b1 = y n-2 ⊕ u 6 and from P n-1 the message x n-1 ⊕ u 5 . Therefore, the messages received in Stages 1 and 3, as well as the messages received from P n-2 and P n-1 , each includes a xor operation with an independent (uniformly distributed) random bit not known to P 1 . The message received in Stage 4 is the value of the function. Hence privacy with respect to P 1 holds. Player P n-2 : The set of messages that player P n-2 receives is a subset of the messages received by players P i , 1 < i < n -2. None of these messages depend on u 5 or u 6 tossed by P n-2 . The privacy with respect to player P n-2 thus follows from the proof for P i , 1 < i < n -2. Player P n-1 : Player P n-1 receives a subset of the messages received by the players P i , 1 < i < n -2, namely those of Stage 1 and of Stage 4. In addition, it receives, while engaging in Implementation 2 of the OT protocol with player P n-2 and helpers P 0 , P 1 , the following messages:

(1) the messages u 5 and u 6 from player P n-2 , (2) the message M 0 • (x n-1 ⊕ u 5 ⊕ 1) from player P 0 , where M 0 is the message P 0 receives from P n-2 in the OT protocol, Implementation 2, (3) the message M 1 • (x n-1 ⊕ u 5 ) from player P 1 , where M 1 is the message P 1 receives from P n-2 in the OT protocol, Implementation 2. We now have four cases depending on the values of x n-1 and u 5 . In each of the four cases, the two messages received from P 0 and P 1 can be written as follows:

x n-1 = 0, u 5 = 0: P n-1 receives from P 1 the message 0, and from P 0 the message M 0 = b0 = q (n-1) mod 2 ⊕ u 6 . x n-1 = 0, u 5 = 1: P n-1 receives from P 0 the message 0, and from P 1 the message M 1 = b0 = q (n-1) mod 2 ⊕ u 6 . x n-1 = 1, u 5 = 0: P n-1 receives from P 0 the message 0, and from P 1 the message M 1 = b1 = y n-2 ⊕ u 6 . x n-1 = 1, u 5 = 1: P n-1 receives from P 1 the message 0, and from P 0 the message M 0 = b1 = y n-2 ⊕ u 6 .

It can be verified that, given the values of x n-1 and of AN D(x 0 , x 1 , . . . , x n-1 ), the distribution of the messages received by P n-1 is identical in all four cases. Indeed, given the value x n-1 , the value of u 5 determines which of the two messages above is a constant, and which includes a xor operation with q (n-1) mod 2 . Now recall that y n-2 = q 0 ⊕ q 1 ⊕ Π n-2 j=0 x j , thus the rest of the messages (except AN D(x 0 , x 1 , . . . , x n-1 )) include a xor operation with a distinct random bit, other than q (n-1) mod 2 , all are uniformly distributed and independent. Hence, privacy is preserved with respect to P n-1 .

4.2.3

The case of n = 3. This case can be slightly improved compared to the general case. We can privately compute the and of 3 players using 7 random bits instead of 8.

The protocol is simple to define: run the protocol Π odd , but fix the bit q 1 to be 0 (rather than it being a random bit).

The correctness of the protocol clearly holds since it holds for Π odd with any choice of random bits. To see that privacy is still preserved with respect to all three players, observe that both player P 0 and player P 1 get q 1 in the original protocol (P 0 tosses it, and P 1 gets it in the initialization phase). Therefore, fixing it to 0 leaves the privacy with respect to these two players intact. As to player P 2 , note that the OT protocol performed between P 1 and P 2 does not change in the modified protocol. Therefore, if x 2 = 0 then P 2 gets q 1 (which is fixed to 0), and no other information. If x 2 = 1 then the only information P 2 gets is q 0 ⊕ q 1 ⊕ Π 1 j=0 x j = q 0 ⊕ Π 1 j=0 x j , from which it can compute, using the bit q 0 that it got in the initialization phase, the value of Π 1 j=0 x j . But this value can be inferred, in the case of n = 3 and x 2 = 1 from the value of the function and x 2 , so privacy is preserved with respect to P 2 too.

Conclusions

We consider the randomness complexity of the information-theoretic multi-party private computation of the function and. We show that this computation cannot be done using a single random bit, thus giving the first non-trivial lower bound on the randomness complexity of the private computation of an explicit boolean function. We further give an improved upper bound on the randomness complexity of the private computation of and, thus approaching the exact determination of that measure for and. To the best of our knowledge, for no explicit function f is the exact randomness complexity of the private computation of f known (except for xor, which is trivially 1-random, and degenerate functions). We leave the exact determination of the randomness complexity of private computations of and for further research.

7

  By inspection for each of the 8 subsets of 1, xi, and m (represented by {0, 1} 3 in the natural way): (000, 100) -0, 1: constants, not in protocol; (010, 110) -xi, 1 ⊕ xi: violates privacy; (001, 101) -m, 1 ⊕ m: of the desired form; (011, 111) -xi ⊕ m, 1 ⊕ xi ⊕ m: of the desired form.

3 .

 3 Bob sends to Alice the message i = s ⊕ p. 4. Alice sends to Bob the two bits m 0 = b 0 ⊕ r i and m 1 = b 1 ⊕ r 1⊕i . 5. Bob "deciphers" the value of the bit he wants to learn (i.e., b s ) by computing m s ⊕ r * .

The two-party case, n =

2, is known to be qualitatively different[START_REF] Chor | A zero-one law for boolean privacy[END_REF].[START_REF] Beaver | Precomputing oblivious transfer[END_REF] Recently, a lower bound on the number of random bits necessary for the private computation of the Disjointness function was obtained[START_REF] Rosén | A new approach to multi-party peer-to-peer communication complexity[END_REF]. However, for the Disjointness function each player has m ≥ 1 bits of input. Furthermore, the obtained lower bound is of Ω(m), and the hidden constant is less than 1. Thus, for the special

In the literature, a more general notion of privacy, called t-privacy, is often considered, where any set of players of size at most t cannot learn anything from the messages received by all of them. In this paper we consider only 1-privacy, and call it "privacy" for simplicity.

Not to be confused with the j-th unit vector.

If S = {x0} then P0 can compute the message itself. If there exists a k = 0, k ∈ S, consider the two inputs e0, e 0,k to see that the privacy property is violated.

Formally, consider the two inputs e j,k and ej, for some k ∈ S , k = j. These two inputs agree on xj as well as on the value of the function, but the distributions of the messages that Pj receives on these two inputs are not identical.

It is also possible to perform the OT protocol of this round using Implementation 1 with a separate set of 3 random bits, tossed by another player, say player P0, but this results in a larger total number of random bits for the protocol.

Acknowledgements We would like to thank an anonymous reviewer of an earlier version of this paper for comments which helped us reduce the upper bound for even number of players from 10 random bits to 8 random bits, and hence also the general upper bound from 10 to 8.

is not known for any Research of E. Kushilevitz is supported by ISF grant 1709/14, BSF grant 2012378, NSF-BSF grant 2015782, and a grant from the Ministry of Science and Technology, Israel, and the Dept. of Science and Technology, Government of India. Research of R. Ostrovsky is supported in part by NSF-BSF grant 1619348, DARPA SafeWare subcontract to Galois Inc., DARPA SPAWAR contract N66001-15-1C-4065, US-Israel BSF grant 2012366, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. The views expressed are those of the author and do not reflect the position of the Department of Defense or the U.S. Government.


Damien Vergnaud

Secure Outsourcing in Discrete-Logarithm-Based and Pairing-Based Cryptography (Invited Talk)

Cryptographic operations are performed everywhere, from standard laptop to smart cards. Some devices computational resources can be very limited and it is natural to delegate costly operations to another device capable of carrying out cryptographic algorithms. In this setting, it is obviously important to ensure the limited device that the computation is carried out correctly and that the powerful device does not learn anything about what is actually computing (including the secret inputs and outputs). We briefly review the recent advances on secure outsourcing of group exponentiation (in groups of known prime order as well as in groups of unknown order) and pairing computation.

Introduction

Many widely used public-key cryptographic systems and protocols relies on the (supposed) computational hardness of the discrete-logarithm or the discrete-root problems. The core operation of these cryptosystems is group exponentiation in a finite Abelian group, i.e., computing u a from a group element u and an exponent a. Besides, since their introduction in cryptography [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF][START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF], pairings proved to be an amazingly flexible and useful tool for the construction of cryptosystems with unique features (e.g. efficient identity based cryptography [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]). In this setting, the core operation is the computation of pairings which is the most expensive operation in pairing-based cryptographic protocols.

We consider the problem of "outsourcing" group exponentiation and pairing computation from a weak computational device to a more powerful one. Indeed, some devices computational resources can be very limited and it is natural, as most of the devices are online or directly connected to a powerful device (like a SIM card in a smart phone) to securely delegate sensitive and costly operations to a device capable of carrying out cryptographic algorithms. Outsourcing cryptographic computations is a classical problem which was formalized in [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF] by Hohenberger and Lysyanskaya. In this scenario, the powerful device 1 can, po-tentially, be operated by a malicious adversary and it is obviously important to ensure the limited device that the computation is carried out correctly and that the powerful device does not learn anything about what is actually computing (including the secret inputs and outputs).

Group Exponentiation

In the last 30 years, the question of how a computationally limited device may outsource group exponentiation to another, potentially malicious, but much more computationally powerful device has been a very active research topic (e.g. [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[END_REF][START_REF] Laih | Two efficient server-aided secret computation protocols based on the addition sequence[END_REF][START_REF] Béguin | Fast server-aided RSA signatures secure against active attacks[END_REF][START_REF] Wang | Securely outsourcing exponentiations with single untrusted program for cloud storage[END_REF][START_REF] Cavallo | Efficient and secure delegation of group exponentiation to a single server[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF]). Many solutions have been proposed and then cryptanalyzed in follow-up papers (e.g. [START_REF] Phong | On the insecurity of a server-aided RSA protocol[END_REF][START_REF] Merkle | Multi-round passive attacks on server-aided RSA protocols[END_REF][START_REF] Pfitzmann | Attacks on protocols for server-aided RSA computation[END_REF][START_REF] Jakobsson | Secure server-aided signature generation[END_REF][START_REF] Merkle | On the security of server-aided RSA protocols[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF]). We briefly review the recent advances on secure outsourcing of group exponentiation.

Recently, Chevalier, Laguillaumie and Vergnaud [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF] proposed a taxonomy of private exponentiation delegation protocols (to a single untrusted computational resource) in groups of known prime order. Their taxonomy covers all the practical situations: the group element u can be secret or public, variable or fixed, the exponent a can be secret or public, and the result of the exponentiation u a can also be either public or secret. They provided simple constructions in all different settings and proved that these protocols cannot be significantly improved if one wants to use a single untrusted computational resource and to limit the computational cost of the delegating device to a small number of (generic) group operations. Aguilar-Melchor, Deneuville, Gaborit, Lepoint and Ricosset later showed [START_REF] Aguilar Melchor | Delegating elliptic-curve operations with homomorphic encryption[END_REF] that using homomorphic encryption, it is sometimes possible to reduce the computational costs for privately delegating elliptic-curve operations (but at the cost of a very large communication complexity).

Another important use case is the setting of RSA exponentiation: a device wants to delegate the computation of a signature given a public key (N, e), a public message (or hash value of a message) m and the secret signing exponent d. By outsourcing some exponentiations to a powerful device, the delegation protocol outputs a (public) signature σ = m d mod N . Most proposed protocols are variants of two protocols (named RSA-S1 and RSA-S2) that were proposed by Matsumoto, Kato and Imai in 1988 [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[END_REF]. Both schemes use a random linear decomposition of the RSA private exponent d. Several attacks were proposed on the protocols RSA-S1 and its variants (e.g. [START_REF] Phong | On the insecurity of a server-aided RSA protocol[END_REF]). Recently, Mefenza and Vergnaud [START_REF] Mefenza | Cryptanalysis of server-aided RSA protocols with private-key splitting[END_REF] proposed an improved lattice-based attack on RSA-S1 and a simple variant of this protocol that provides better efficiency for the same security level. They also presented the first attacks on the protocol RSA-S2.

A cryptographic delegation protocol that does not ensure verifiability may cause severe security problems (in particular if the computation occurs in the verification algorithm of some authentication protocol). Di Crescenzo, Khodjaeva, Kahrobaei and Shpilrain [START_REF] Di Crescenzo | Practical and secure outsourcing of discrete log group exponentiation to a single malicious server[END_REF] proposed recently private and verifiable protocols in a large class of cyclic groups. In the presented protocols, the probability that a cheating server convinces the client of an incorrect computation result can be proved to be exponentially small (whereas previous best results could only achieve a constant probability). Their protocols need some pre-computation depending on the base u and cannot be used easily in practice if this group element is variable. The different proposals for verifiable group exponentiation where precomputation does not depend on the base u are very inefficient and it is actually better in practice to directly perform the computation on the restricted device rather than using these solutions. A challenging problem is to study secure and verifiable outsourcing protocols for group exponentiation that covers all the practical situations as in [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF].

Pairings

Pairings (or bilinear maps) were introduced in cryptography in 2000 by Joux [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] and Boneh-Franklin [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]. A pairing is a bilinear, non-degenerate and computable map e : G 1 × G 2 → G T where, in practice, G 1 and G 2 are subgroups (of primeorder r) of the group of points of an elliptic curve defined over a finite field F q and some finite field extension F q k (respectively) and the so-called target group G T is the order r subgroup of F q k . The pairing computation is more resource consuming compared to a scalar multiplication on the elliptic curve E(F q ). In 2005, Girault and Lefranc [START_REF] Girault | Server-aided verification: Theory and practice[END_REF] introduced the first secure pairing delegation protocol via the notion of Server-Aided Verification, which consists in speeding up the verification step of an authentication/signature scheme. Chevallier-Mames, Coron, McCullagh, Naccache and Scott [START_REF] Chevallier-Mames | Secure delegation of elliptic-curve pairing[END_REF][START_REF] Chevallier-Mames | Secure delegation of elliptic-curve pairing[END_REF] introduced the security notions of verifiable pairing delegation protocol and proposed the first verifiable pairing delegation protocol. Later in 2014, Canard, Devigne and Sanders [START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF] improved their construction and proposed a much more efficient verifiable delegation protocol. Canard, Devigne and Sanders showed that their construction is more efficient for the client than computing a pairing himself on the so-called KSS-18 curve [START_REF] Ezekiel | Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. Later, Guillevic and Vergnaud [START_REF] Guillevic | Algorithms for outsourcing pairing computation[END_REF] showed that Canard, Devigne and Sanders protocol is actually less efficient than computing a pairing for the state-of-the-art optimal Ate pairing on a Barreto-Naehrig curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] and it remains open to propose an efficient verifiable delegation protocol for pairing computation on these curves.

Due to the inefficiency of the known protocols for delegation of a unique pairing, another approach is to propose efficient protocols when the client wants to compute several pairings at the same time. In 2007, Tsang, Chow and Smith [START_REF] Patrick | Batch pairing delegation[END_REF] introduced the security notion of batch pairing delegation protocols and propose the first verifiable batch pairing delegation protocols when the client wants to compute several pairings e(P i , Q i ) where P i ∈ G 1 and Q i ∈ G 2 for i ∈ {1, . . . , n} and n ≥ 2. In [START_REF] Mefenza | Verifiable outsourcing of pairing computations[END_REF], Mefenza and Vergnaud recently proposed four new efficient batch pairing delegation protocols in different settings but it remains open to construct a generic verifiable batch pairing delegation protocol when both inputs of the pairing are variable and secret. Another interesting open problem is to provide lower bounds on the efficiency of verifiable pairing delegation protocols (as it was done in [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF] for private delegation of group exponentiation).

Hohenberger and Lysyanskaya also considered delegation protocols to two devices that are physically separated (and do not communicate) that achieve security as long as one of them is honest. Since this separation of the two devices is a strong assumption hard to be met in practice, we consider only protocols to outsource cryptographic operations to a single untrusted server.

Acknowledgments. The author would like to thank his co-authors on this active and interesting research area: Céline Chevalier, Aurore Guillevic, Fabien Laguillaumie and Thierry Mefenza. The author is supported in part by the French ANR ALAMBIC project (ANR16-CE39-0006) and the French ANR IDFIX project (ANR-16-CE39-0004).


Karine Langlois
email: karine.langlois@ensam.eu

Hélène Pillet

François Lavaste

Goulven Rochcongar

Philippe Rouch

Patricia Thoreux

Wafa Skalli

Assessing the accuracy and precision of manual registration of both femur and tibia using EOS

Keywords: Biplanar low dose, knee flexion, registering, lower limb

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The EOS imaging system produces two simultaneous X-rays of a subject. Both views are used for the generation of a subject-specific 3D skeletal model. This model then allows to obtain quantitative parameters concerning the morphology and the positioning of bones. Furthermore, thanks to the low dose of the EOS imaging, it is possible to take several stereoradiographies of the same subjects in order to study different positions of the femoro-patellar joint [START_REF] Dagneaux | Analyse 3D de la cinématique séquentielle des troubles fémoro-patellaires à partir de radiographies biplanaires [3D pseudo-kinematic analysis of patellofemoral diseases by using biplanar radiographs[END_REF] or to analyze different positions of the subjects. Also, it can be a way to compare tibia and femur relative positions without and with an orthotic device such as a brace for example. For that, the 3D model, obtained from the reference standing position, is registered across the different pairs of X-rays for the other positions. The goals of this study are 1/ to evaluate the reproducibility of the registration of both in vitro and in vivo and 2/ to assess the accuracy of this manual method using in vitro data.

Methods

Protocol

Twelve lower extremities (femur and tibia) were used: six cadaveric lower limbs of six healthy subjects who signed an approved consent form before participating in this study. In vitro analysis: for each cadaveric lower limb, an experimental device allows to capture three pairs of views of the specimen, the femur being fixed to the device (0°, 20°, and 40° of knee flexion) [START_REF] Rochcongar | Assessment of kinematics, anatomy and variation of ligaments length during a passive knee flexion[END_REF]). In addition, clusters of markers were rigidly fixed in each bone to get reference value of the bone position in different knee flexion positions. For each healthy subject, the protocol consisted in performing four pairs of views in standing (0°) and knee flexion positions (20°, 40°, and 90°). Here, femur and tibia were mobile. For both in vitro and in vivo analyses, three qualified operators performed 1/ the lower limb reconstruction using the standing position pair of views and 2/ the manual registration of the 3D skeletal models of the femur and the tibia on each pair of views for each position of knee flexion (Figure 1). Each operator performed three repetitions of this process for each lower limb.

Parameters computation process

From femur and tibia 3D models, anatomical frames were computed according to the definition proposed by Schlaterer et al. (2009) for each knee position and each repetition. Then, the position and the orientation of each bone relatively to the EOS coordinate system was assessed for each knee flexion position and expressed by six parameters: anteroposterior (x), longitudinal (y), and mediolateral (z) translations (T x , T y , and T z ) and rotations (R x , R y , and R z ). The relative position of the tibia and the femur was also calculated.

Data analysis

The precision of the method was assessed according to NF ISO-5725-1, 1994, andNF ISO-5725-2, 1994. Inter-operator reproducibility and intra-operator repeatability of femur and tibia regarding the six parameters were determined to estimate the uncertainty of the registering method concerning femur and tibia. The uncertainty of manual positioning was estimated by the IC 95% for both cadaveric and healthy groups for each position and each parameter. IC 95% reliability was considered as 2σR. Furthermore, from in vitro data, an average position of each bone was assessed from the repetitions of the three operators and used to evaluate the accuracy of the method by comparing the resulting variation of positions between each pair of views and the true value given by the clusters embedded in the bones and visibles on the radios. and R z were, respectively, -0.7°, -0.8°, and 0°. For the translation parameters T x , T y , and T z , the deviations were, respectively, -0.2, 0.6, and 0.2 mm. In vitro, these values demonstrated high accuracy for sagittal and coronal planes.

Accuracy and precision of this current method can be compared to fluoroscopic approach, which also uses the registration of the 3D model on a 2D view. Regarding out of plane registration in these studies, our results are in agreement with the parameters R x and T z . Registration from EOS is easier for R z .

Conclusions

The purpose of this study was to assess the manual registration of 3D skeletal models of the femur and the tibia for different positions of knee flexion. This method allows to obtain body segments displacements which could improve measurements of knee kinematics or evaluate the effect of an orthotic device. Results of this study may be considered in research for protocols including several views of the lower limb.

shown for each knee flexion and for each translation and rotation parameter.

No results are presented for the femur bone in vitro conditions since the bone was fixed on the experimental device.

The precision of the femur registration was better than the one of the tibia. The precision of the registration was less than 0.6° along the mediolateral (z) axis and 2.8° along the anteroposterior (x) axis for both femur and tibia.

In this study, maximum degrees of uncertainty for the knee (ranging from 3.6° to 5.5° according to positions of knee flexion) were found along the longitudinal axis (y). These results are mainly related to the tibia registration error and are in favor of a stereoradiographic protocol in which the tibia would remain fixed throughout the different views. In comparison, [START_REF] Chaibi | Fast 3D reconstruction of the lower limb using a parametric model and statistical inferences and clinical measurements calculation from biplanar X-rays[END_REF] reported an uncertainty inferior to 2.7° for reconstruction parameters of both femur and tibia except for torsion parameters (<5°) which is consistent with our results.

Regarding the accuracy of tibia registration (in vitro data), for the 20° knee flexion position, the deviations between the values from the registration of bones and the true values for the R x , R y ,

Figure 1 .

 1 Figure 1. illustration of the process on the sagittal view: 1/ the lower limb reconstruction on the standing position view and 2/ the manual registration of the 3d skeletal models of the femur and the tibia on each position of knee flexion.

Table 1 .

 1 iC 95% of the interoperator reliability for each position and orientation parameter.

	In vivo	Parameter	20°40°90°In vitro	Parameter	20°40°i
	C 95% reliability Femur healthy subjects iC 95% reliability tibia healthy subjects iC 95% reliability knee healthy subjects	T x (mm) T y (mm) T z (mm) R x (°) R y (°) R z (°) T x (mm) T y (mm) T z (mm) R x (°) R y (°) R z (°) tx (mm) ty (mm) tz (mm) rx (°) ry (°)	1.1 1.0 1.3 0.7 3.7 0.4 1.2 1.5 1.7 0.9 5.1 0.4 1.8 2.0 2.4 1.9 5.5	1.1 1.2 1.4 0.9 2.9 0.5 1.6 1.5 2.2 1.9 4.4 0.4 2.3 2.3 2.9 2.8 4.8	1.1 1.2 1.8 1.4 3.2 0.6 1.5 1.9 2.7 2.8 4.8 0.3 2.4 3.3 3.6 4.2 3.6	iC 95% reliability tibia cadaveric iC 95% reliability knee cadaveric	T x (mm) T y (mm) T z (mm) R x (°) R y (°) R z (°) T x (mm) T y (mm) T z (mm) R x (°) R y (°)	1.6 1.6 1.6 1.6 5.4 0.4 1.6 1.8 1.8 1.8 5.6	2 2 2 3.2 5.4 0.6 2 2 2.4 3 5.6
		rz (°)	0.6	0.5	0.7		R z (°)	0.4	0.6