text:
Marit Hvalsøe Schou
email: maritschou@imada.sdu.dk

Using manipulatives in upper secondary math education -a semiotic analysis

Keywords: Upper secondary mathematics education, manipulatives, semiotics, conceptualizing, objectification. Thematic Working Group 24

The use of manipulatives in upper secondary education is not common, although they hold learning potential in contributing to students' conceptualizing and establishing of relations. In this case study it is investigated how the concept of recursive sequences as a description of growth can be seen in the written reflections from students having engaged in activities with manipulatives like matches and LEGO ® and with only minor teacher interference. The analysis of students' answers is carried out by a combination of Radford's Theory of Objectification and Peirce's Theory of Signs. By interpreting the type of signs, the kind of arguing and the nature of the words used by students in various activities involving manipulatives, it is possible to acquire knowledge of the significance of the manipulatives in students' conceptualizing.

Introduction

For centuries manipulatives have been used in mathematics education as a pedagogical means for learning at all levels. A visit to the Institute of Mathematics at the University of Göttingen, Germany reveals an entire floor display of manipulatives used in university teaching [START_REF] Stewart | Riemann surfacecrocheted in four colors[END_REF]. Today the use of manipulatives is still common in primary and lower secondary school as a way of making the teaching concrete and meaningful. On higher levels where deduction and generalisation are important issues, manipulatives are rarely seen and research on their use is scarce [START_REF] Bartolini | Manipulatives in Mathematics Education Encyclopedia of Mathematics Education[END_REF]. Previous studies show that manipulatives can help students perform algebraic reflections and actions in pattern-generalizing tasks in primary and lower secondary school by joint student-teacher interaction [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF]. Here it will be investigated how the use of manipulatives can be seen in student reflections on the concept of growth in this upper secondary education.

Theoretical framework

Generalisation depends on symbolization [START_REF] Otte | Mathematical epistemology from a Peircean semiotic point of view[END_REF] and many teachers use symbolic representations extensively without connecting them to other representations thereby preventing their students the chance to explore or reflect on these relations [START_REF] Steinbring | The construction of new mathematical knowledge in classroom interaction: An epistemological perspective[END_REF]. The use of manipulatives is an alternative way of bringing in abstraction and generalisation in teaching, enhancing the development of mathematical knowledge [START_REF] Mitchelmore | The Role of Abstraction and Generalisation in the Development of Mathematical Knowledge[END_REF]. In his Theory of Objectification, Radford (2013, p. 26) states: "Learning […] is the noticing of something that is revealed in the emerging intention projected onto the signs […] in the course of practical concrete activity […] and is hence transformed into knowledge."

A semiotic analysis of the representations and the communication about these representations, i.e. the signs the students produce, is used to investigate the mathematical knowledge developed. Each observation of student work is treated as a semiotic bundle, a system of signs produced by a student or a group of students while they solve a problem or discuss a mathematical question. [START_REF] Arzarello | Gestures as semiotic resources in the mathematics classroom[END_REF]. [START_REF] Presmeg | Semiotics in Theory and Practice in Mathematics Education Semiotics in Mathematics Education[END_REF] demonstrate the usefulness of Peirce's semiotics in analyzing students' work with representations. Peirce defines:

A sign, or representamen, is something, which stands to somebody or something in some respect or capacity. It addresses somebody, that is, creates in the mind of that person an equivalent sign, or perhaps a more developed sign. That sign which it creates I call the interpretant of the first sign. The sign stands for something, its object. [Peirce 1965, 2.228, italics in original] A sign to Peirce thus consists of a triad (representamenobjectsign). Each of these can be interpreted in terms of his categories (of which there are three: "possibility, existence and law"). Here I use in particular two trichotomies: icon, index and symbol referring to how the sign stands for its object, and the token-type distinction (omitting quali-sign).

An icon is a sign that shares a likeness with the object it represents either as an image, a diagram or a metaphor. An image has a resemblance or a simple quality in common with the objecta drawing of a real thing; a diagram is a sign representing relations, e.g., x 2 + y 2 = r 2 represents the points of a circle. A metaphor represents a parallelism where the character of one sign is expressed in a law-like manner in the other, like when a symptom, fever, of illness is seen as an increased temperature at a thermometer. An index is related to the object it represents by either a causal connection or by 'a purposeful act of connecting the signs' like using 'f' as the name of a certain mathematical function. Finally a symbol is connected to its object by habit or law, e.g. designating π to refer to the ratio between the circumference and the diameter of a circle.

The token-type distinction applies to the sign alone. A token refers to the sign itself; consider the letter 'e', this letter appears many timesas a tokenon this page. It is also possible to refer to 'e' as a generalas a type, stating that 'e' appears a particular number of times on this page. A thorough explanation of Peirce's trichotomies of signs is offered in [START_REF] Short | Peirce's theory of signs[END_REF] whereas mathematical examples can be found in [START_REF] Otte | Mathematical epistemology from a Peircean semiotic point of view[END_REF] and [START_REF] Sáenz-Ludlow | Semiotics as a Tool for Learning Mathematics[END_REF].

The teaching design rests on the Theory of Didactical Situations, TDS [START_REF] Brousseau | Theory of didactical situations in mathematics: Didactique des mathématiques, 1970-1990[END_REF]. The epistemological foundation of TDS is that new knowledge is obtained in two steps: first as personal knowledge connaissance in working with a given problem and second as formal, scientific knowledge savoir, which can be share with and understood by others.

TDS distinguishes between didactical situations where the teacher participates, and a-didactical situations where students engage in activities on their own. Devolution, where the teacher introduces and hands over the problem, validation and institutionalisation, where the ideas and results are tested and then related to the scientific knowledge of the solution, are all didactical situations. The main focus of this case study is, however, the a-didactical situation where students interact with the milieu, which contains the tools that the students have at their disposal (symbolic or material as well as the other students in the group). An important issue in designing the milieu is to ensure that it provides feedback on how the students progress in order to solve the problem.

Within this framework the study will try to answer the question: How does the use of manipulatives in teaching reflect in students' answers about growth, exemplified by recursive sequences?

Method

The case study considers one lesson (100 min.) of a ten-week teaching sequence about differential equations in an upper secondary mathematics class with 25 students. The aim of the lesson was to enhance the students' understanding of the concept "growth" using recursive sequences. After a short devolution where the purpose of the lesson, describing the growth of certain patterns, and the milieu containing worksheets and manipulatives like matches and LEGO ® were introduced, the students worked in groups of 4 for 60 min. During this period teacher intervention was very sparse. Figure 1 shows an example of an activity/worksheet. As preparation for the validation and institutionalisation the students were asked to share results, ideas and reflections with their fellow group members in a logbook prompted by questions given by the teacher. Part of the logbook writing was done in class and the rest at home using a Google Docs document shared by the group members. The empirical data consists of the logbooks and field notes from classroom observations. The logbook entries were analysed through a qualitative content analysis [START_REF] Hsieh | Three approaches to qualitative content analysis[END_REF] for words indicating the concept of growth, like 'grow' and 'rise' (coded with underscore in the statements). In addition, words referring to the manipulatives (coded in bold) were noted.

To describe the patterns and how they evolved, the students introduced a 'sequence of signs'. They explained each sign and how they came on to it, and they used the sign as a starting point for the next sign they introduced. In order to examine the knowledge obtained by the students during the teaching sequence, data was analysed with respect to (1) the type of sign, applying Peirce's categories, (2) how the use of manipulatives show, according to the nature of the marked words, and (3) mathematical reasoning, according to Radford's definition of generalizing patterns [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF].

Results

In this section, we will look at two logbook entries and one episode observed in class that show how the use of manipulatives contributes to obtaining knowledge of growth.

Figure 2 shows the first logbook entry on the question: Choose the pattern from one of the activities and explain how the pattern developed. Use drawings/pictures/symbols describing the growth.

For a start we observed how the number of matches grew. We found that there was a rise on two matches in every step. You can almost say that in each step a new triangle is mirrored on to the right side of the figure. We also considered other ways of describing the growth after having discussed our results in class.

Here we noticed the constant rise with 2. This was the constant change between the earlier and the next figure. Therefore we could write down the relations: The semiotic bundle in figure 2 shows how the students, based on the pattern they have built of matches, introduce three signs: a table inclusive a drawing of the pattern, a 'formula' written in words and a list of the first four terms of the recursive sequence describing the pattern. On figure 3 one can see how any one sign evolves from a previous sign. The photo on the left shows the pattern build of matches.

Figure 3: Signs introduced by the first group

The students begin by describing what they notice in the pattern they have built from matches, and they draw the pattern as the first line in a table. There is no explanation on the rest of the table but

T (1) = 3 T (2) = T (1) + 2 T (3) = T (2) + 2 T (4) = T (3) + 2
Thematic Working Group 24 my interpretation is that this is 'a conditioned reflex' as the students have made many tables like this with an independent variable (figure no.) and a dependent variable (no. of matches) when working with growth as a continuous function. The table is iconic: the previous text indicates that the students partly take it diagrammatic as it describes the relation between two subsequent figures. It also works in part as an image as the drawn pattern looks like the pattern made of matches.

In the table, the students also state the difference between two subsequent figures and this number is used for producing the next sign, a 'formula', from which they can calculate the number of matches in figure no. 37. The students notice that the increase is constant 2, which leads them to the first term of the expression. Using Radford's definition of pattern generalization [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF] we see that they use naïve inductions for producing their formula. Instead of arguing for the y-intercept, they guess and test the value. The formula itself is a partial translation of the previous arguments to a semimathematical language. This sign is partly diagrammatic stating a relation between the figure number and the number of matches and containing the symbols '+' and '*'. It is interesting that the students do not finish the translation to a conventional formula (e.g.

) introducing indices f and

x. Most groups did at this stage. Instead they keep the original iconical terms 'figure no.' and 'no. of matches' closely related to the manipulatives.

Finally, after a validation and institutionalisation where the idea of explaining growth as a recursive sequence was discussed, the students decide to include this view as, not mentioning the important issue, though, that every new term is built on the previous term. They introduce an index T to stand for the number of matches but do not find a general expression using the symbol n for the figure number like seen in other logbook entries.

We see that the signs used for representing the object Growth include various kinds of icons as well as indices and symbols. In many of the icons there is a close link to the use of manipulatives i.e. the way the students obtain their 'data' and how they explain relations in the pattern. The manipulatives are not clearly visible in their reasoning, though. As a result of the analysis we may conclude that the understanding of growth for this group of students now includes some very concrete conceptions based on activities with manipulatives (matches), and these are pointing towards a more abstract understanding that has not yet been reached. The relations produced indicate that they take the pattern as a token. They have not yet reached the stage of considering the pattern as a type in order to produce general relations.

In some of the worksheets the use of manipulatives were not explicitly mentioned but replaced by drawings of squares, dots etc. Some groups, though, were using the manipulatives mentally, which in figure 4 is shown as a mixture of the terms 'squares'/'LEGO ® blocks' in their explanations.

f (x) = 2 × x + 1 T(n) = T(n -1) + 2 T (1) = 1
Thematic Working Group 24

The group has not built this pattern physically, but in the context of other activities with manipulatives they use a mental picture made of LEGO ® . Figure 5 shows the squares from the worksheet and the mentally evoked manipulatives. Like in the entry in figure 2, the text indicates that the iconic sign is partly diagrammatic as it describes the relation between two subsequent figures and at the same time works as an image as the drawn pattern looks like the pattern made of LEGO ® blocks, which the students have evoked in their mind. As in figure 3, this group bring in various words describing growth; several terms refer to the manipulatives thereby showing the importance of the artefacts in the learning process.

The last example does not directly refer to the manipulatives from the activities but shows how a student seizes the idea of applying a concrete artefact in explaining a mathematical concept. The episode happened during the validation of the results from the activities described above. During the discussion it became obvious that many students had great difficulties with this new and different way of looking at the concept of growth. Their prior knowledge, connected to continuous functions, seemed very persistent. During the discussion one of the students reacted:

"No, no. We talk about the growth, the change -not the actual number. Look… [she jumps up from her chair, looks around and grabs a pile of books from the neighbouring table] …If we start with, say 1 book, [she puts one book on the table] and then in the first step we put 2 books on top of it, and then in the next step 2 more books and 2 more books and so on. [For every step she places 2 books on top of the stack on the table, see figure 6]. It doesn't matter if there are 1 or 3 or 5 books in the pile. The important thing is that it grows with two books every time. The difference is two." The student makes use of concrete artefacts in order to explain to her peers how to understand growth. She applies what is easily accessible in a classroom: books! As a representation of growth, the sign contain qualities of all three kinds of icons: the growing stable of books is an image, the relation of adding two more books in each step is a diagram, and by insisting on seeing the difference in each step (two more books every time) instead of the height of the stable, it becomes a metaphor. The student clearly states that this is just one way of visualizing how something grows. From the many different words used to indicate growth she demonstrates a wide understanding. It is an example of how manipulatives can be used as visualising a challenging concept rather than a starting point for general, symbolic expressions, which we saw in the logbook entries.

Discussion and conclusion

The case study demonstrates how the use of manipulatives shows in students' answers and reflections when describing a mathematical activity, e.g. building of patterns. By using concrete artefacts they are able to describe how patterns develop and translate this description to an expression of how the number of parts in each figure of the pattern grows. In the logbook entry (figure 2) the students use an intermediate stage mixing words and symbols, not reaching the final stage expressing the formula in formal mathematical language. Other groups, not considered here, argue for an algebraic expression.

Students use various words referring to different aspects of growth. Some are everyday language e.g. sticking out, broader, bigger, grow, rise and extra; whereas others are mathematical terms like add, multiply, change, growth etc. Often the everyday language is linked with the manipulatives, and the words might not have been evoked in a purely abstract context without the artefacts present. The semiotic analysis reveals that the signs introduced by students are predominantly iconic, many of these images. [START_REF] Otte | Mathematical epistemology from a Peircean semiotic point of view[END_REF] argues "[…] iconic representations and perceptions are essential to introduce anything new into mathematical discourse", and he notices, "Mathematics teachers very often dislike iconic representations and perceptions, believing them to be confusing and not controllable with respect to their impact" [START_REF] Otte | Textual strategies[END_REF]. This case study shows how students benefit from the use of artefacts by bringing in numerous iconic representations.

While figure 3 shows that very simple patterns can be visualized as drawings without actual physical materials, classroom observations, not treated here, reveal that patterns in 3D demand the use of actual building blocks. In both cases students use the names of the manipulative i.e. "matches" or "LEGO ® ". Even when the physical artefact is not needed, students can apply a mental image of the artefact in their mathematical reasoning.

In former research results about the use of manipulatives in lower secondary education, [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF] emphasizes the importance of joined-labour between students and teacher. In this study, the students were expected to be much more self-reliant as they were soon to end their upper secondary education, hence the use of a-didactical situations. The results, though, show that even students in the last year of upper secondary school need guidance in order to make their procedures and ideas converging with the mathematics curriculum as stated in the Theory of Objectification [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF].

There are reasons to be somewhat cautious of the results. Using Peirce's categories of the relationship between object and sign is complicated as [START_REF] Presmeg | Semiotics in Theory and Practice in Mathematics Education Semiotics in Mathematics Education[END_REF] state: "the distinctions are subtle because they depend on the interpretation of the learner". They continue: "the distinctions may be useful to researchers or teachers for the purpose of identifying the subtlety of a learner's mathematical conceptions if differences in interpretation are taken into account." Thus, there are reasons to be careful in the interpretation. Earlier work of, among others, [START_REF] Radford | Students' processes of symbolizing in algebra[END_REF] shows comparable results indicating that the result of this case study is veridical. The semiotic analysis is based on students' statements, and it cannot always be taken for granted that students are conscious about the precise meaning of the words they use. The fact, though, that the analysis of most logbook entries share the features exemplified here indicates that the approach used in this study is rather robust with respect to the lack of carefulness in student language.

The results points towards several areas worth further investigation. In his study [START_REF] Radford | Iconicity and contraction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF] shows how students can be led to algebraic generalisation, introducing mathematical symbols for unknown quantities. This can be taken further by studying how students make sense in already evolved algebraic expression, and whether manipulatives can be supportive. In upper secondary education students are presented with a large number of such algebraic expressions, which they are expected to manipulate and use but often fail to understand. Another interesting aspect is the significance of prior knowledge. In figure 2 we saw how the students were led to look at the relation between a figure number in the pattern and the total amount of matches in that figure resulting in a functional expression. This behaviour was even more apparent in other entries, not shown here, and could very well originate from their knowledge of continuous functions. Although prior knowledge often helps students in new contexts, it can also prevent them from going in the desired direction.

  The sequence of figures shown is made of matches. The first is made of 3 matches, the second of 5 matches etc. The sequence can be continued with figure no. 5, 6, 7, 8 … Build and describe the next figures and tell how many matches you need to build them.

Figure

  Figure no. 2 has been made by adding matches to figure no. 1 in a specific way. Figure no. 2 has been made from no. 3 etc. Explain how you move from one figure to the next in the sequence. Describe the pattern for adding new matches. Explain how this pattern affects the number of matches, you need, to go from one figure to the next in the sequence. That is how can the number of matches in one figure be found from the number of matches in the previous figure?If you want to know how many matches you need to build figure no. 37 it is rather time consuming to build and count the number. Use the pattern you have described above to predict how many matches you need for figure no. 37.

Figure 1 :

 1 Figure 1: An example of an activity

  Figure no.

Figure 2 :

 2 Figure 2: A logbook entry with marked words

[Figure 4 :

 4 Figure 4: Logbook entry showing the use of mentally evoked manipulatives

Figure 5 :

 5 Figure 5: Alternating between to signs

Figure 6 :

 6 Figure 6: The pile of books holds many interpretations of a sign on Growth.

Proceedings of CERME10

Thematic Working Group 24Proceedings of CERME10


domain: math shs

text:
Katharina Böcherer-Linder
email: katharina.boechererlinder@ph-freiburg.de

Andreas Eichler
email: eichler@mathematik.uni-kassel.de

Markus Vogel
email: vogel@ph-heidelberg.de

Representing subset relations with tree diagrams or unit squares?

Keywords: Representation of statistical information, set relations, tree diagram, unit square

In this paper, we refer to the efficiency of different visualizations for mathematical problem solving. Particularly, we investigate how set relations that are potentially important in probability are made transparent by two different visualizations, i.e. the tree diagram and the unit square. In this paper, we use these two visualizations as representations of statistical information. First, we analyze theoretically the quality of visualizing set relations by tree diagrams and unit squares. Second, we briefly report a published study with students of mathematics education (n = 148) where the unit square outperformed the tree diagram when the perception of subset relations was regarded. A main focus of this paper is a replication of the aforementioned study with n = 58 undergraduate students. Finally, we discuss the significance of our results, specifically for the teaching and learning of conditional probabilities.

Introduction

In mathematics education, it is widely accepted that representations and visualizations could have a considerable impact on students' learning. For example, Duval claims that visualizations of mathematical concepts are "at the core of understanding in mathematics" (Duval, 2002, p. 312). However, research in mathematics education and cognitive psychology gave evidence that visualization does not necessarily foster students' understanding. For this reason, a crucial question in research in mathematics education is to identify the one of potentially different visualizations that is most efficient referring to students' learning. We refer to this question concerning competing visualizations aiming to support students' learning in statistics and probability, but also in fractions. The transparency of set relations plays a crucial role in probability [START_REF] Böcherer-Linder | The Impact of Visualizing Nested Sets. An Empirical Study on Tree Diagrams and Unit Squares[END_REF], but is also important in many other domains of mathematics education, such as the teaching and learning of fractions.

Theoretical framework

In the context of Bayesian reasoning, research in cognitive psychology has shown that the transparency of set relations in the visualization of statistical information impacts on the performance in tasks concerning the Bayes' rule: "any manipulation that increases the transparency of the nestedsets relation should increase correct responding" (Sloman, Over, Slovak, & Stibel, 2003, p. 302). Proponents of this point of view, called nested-sets account, attribute the difficulties of Bayesian reasoning to the fact that some sets of events are nested [START_REF] Lesage | Evolutionary modules and Bayesian facilitation: The role of general cognitive resources[END_REF][START_REF] Sloman | Frequency illusions and other fallacies[END_REF]. For the example of a medical diagnosis, Figure 1 illustrates the nested-sets situation. "Transparency of set relations" means that it is easy to see, how many elements are in the sets and how the sets relate. The cognitive model into which the nested-sets account has been incorporated is the dual process theory [START_REF] Barbey | Base-rate respect: From ecological rationality to dual processes[END_REF]: Representing the statistical information in a standard probability format (without visualization) obscures the nested-sets structure of the problem and, therefore, triggers the associative system which may lead to biases. Representing the statistical information with natural frequencies and / or appropriate visualizations in contrast trigger the rulebased system because nested sets relations are made transparent, enabling people to reason consciously and according to the logic of set inclusion [START_REF] Barbey | Base-rate respect: From ecological rationality to dual processes[END_REF]. For the design of effective visualizations, proponents of the nested-sets account claim that visualizations are helpful to the extent that they make the nested set structure of the problem transparent [START_REF] Barbey | Base-rate respect: From ecological rationality to dual processes[END_REF][START_REF] Sloman | Frequency illusions and other fallacies[END_REF]. There are different competing visualizations that claim to visualize efficiently set relations or situations that necessitates applying Bayes' rule and it is an open question which visualizations are the most efficient and which properties explain these visualizations' efficiencies.

In this paper, we investigate how set relations are made transparent by two competing different visualizations, i.e. the tree diagram and the unit square. We use these two visualizations as representations of statistical information (Venn diagrams are not considered in this paper because we focus on the visualization of statistical information and Venn diagrams are pure set representations but not representations of statistical information). First, we analyze theoretically the quality of visualizing set relations by tree diagrams and unit squares. Second, we briefly refer to a published study [START_REF] Böcherer-Linder | The Impact of Visualizing Nested Sets. An Empirical Study on Tree Diagrams and Unit Squares[END_REF]; n = 148 undergraduate students) where we investigate whether the tree diagram or the unit square is more efficient to support the perception of subset relations. Since we used a new approach to explain the effectiveness of visualizations of the Bayes' rule, we conducted a replication study (n = 58 undergraduate students) which results are in the main focus of this paper. Finally, we discuss the significance of our results, specifically for the teaching and learning of conditional probabilities.

Visualizing set relations

"A flower girl is selling red and white roses and carnations." We use this situation as an example to illustrate how the tree diagram and the unit square visualize set relations. In this situation, we have sets (for example the set of all roses) and subsets (for example the subset of all red roses) and subset relations (for example the red flowers among the roses). If we attribute some numerical values to the number of roses and carnations, the situation can be visualized by showing absolute numbers in the tree diagram and the unit square: Both, the tree diagram and the unit square can be seen as nested-sets representations. In the tree diagram, the logical relations between sets and subsets are visualized by lines. The subsets are on a lower level than the sets in the tree and the branches connect the subsets with the sets. For example the subset "red roses" is on a lower level than the set "roses" and the branch connecting "red roses" and "roses" visualizes the relation between both sets. The tree implies a hierarchical structure which means that subsets are always on a lower level than sets. Therefore, only those subset relations that are in line with the hierarchy are salient. For example, the subset relation of "roses among the red flowers" where the "roses" are the subset and all the "red flowers" are the including set is not visualized by a branch in the tree and thus, is not transparent.

In the unit square, subset relations are visualized by areas being embedded in other areas. For example the subset of "white roses" is represented by a partial area of the rectangle that represents all roses.

In contrast to the tree diagram, the unit square implies no hierarchy. That means that subset relations can be grasped vertically (e.g. "white roses among the roses") as well as horizontally (e.g. "roses among the red flowers"). Therefore, all subset relations that are possible in this situation are transparent in the unit square.

Because of these differences in the properties of the two visualizations, we expected a difference between the tree diagram and the unit square when the perception of different subset relations is regarded. Therefore we hypothesized:

If the subset-relation is not in line with the hierarchy of the tree diagram, the unit square is more efficient to make the subset-relation transparent (hypothesis 1). If the subset-relation is in line with the hierarchy of the tree diagram, there is no significant difference between the unit square and the tree diagram (hypothesis 2).

Method

The method in our first study and the replication study was the same. In the first study, we administered a questionnaire to 148 students who were enrolled in a course of mathematics education.

In the second study, the test was administered to 58 students who were also enrolled in a course of mathematics education. In both studies, we asked the students (among other questions concerning conditional probabilities) in one task that we indicate below to calculate proportions and to indicate the result in form of fractions:

𝑝𝑟𝑜𝑝𝑜𝑟𝑡𝑖𝑜𝑛 = #subset #set
In this way, we could analyze if the right subsets and right sets have been grasped from the visualization. The questionnaire had two versions, one showing tree diagrams, the other showing unit squares to represent the statistical information. The rest of the test-items remained constant and the participants were randomly assigned to one of the two groups. Thus, any potential difference in the results could directly be attributed to the influence of the visualizations.

To assess the influence of representation on the perception of subset relations we designed test-items that each addressed structurally different subset relations. In Figure 3, we show the questions that were accompanied by either the tree diagram or the unit square shown above. Note that the item (d) addresses a subset relation that is not in line with the hierarchy of the tree diagram and therefore a higher performance for the unit square was expected. The items a, b, c and e address subset relations that are in line with the hierarchy of the tree diagram and therefore no significant difference between the tree diagram and the unit square was expected. We rated correct answers with 1 and incorrect answers with 0.

Results

Figure 4 shows on the left side the results that we reported in Böcherer-Linder and Eichler (2017).

As we hypothesized in this study, the unit square (M = 0.66, SD = 0.44) was more efficient than the tree diagram (M = 0.38, SD = 0.48) for the item (d) that addressed a subset relation that is not in line with the hierarchy of the tree diagram. The difference for the item (d) was significant (t (146) = 3.579, p <.001) with an effect size of d = .58. In the replication study there is again a significant difference referring the item (d) that addressed a subset relation that is not in line with the hierarchy of the tree diagram (unit square: M = 0.63, SD = 0.43; tree: M = 0.31, SD = 0.39; t(54) = 3.101, p<0.01, d =.82). Thus, we replicated our result referring hypothesis 1. Further, it is interesting that the ratios of correct answers are very similar in the original study and the replication study. However, there are also unexpected differences for the items (b) and (c).

Results of the first study, n = 148 Results of the replication study, n = 58 In our first study, we investigated also the differences in the other four items that addressed subset relations within the hierarchy of the tree diagram. For these items a t-test for the accumulated score referring to these four items (α = .739) yielded no significant difference between the tree diagram (M = 3.46, SD = 1.023) and the unit square (M = 3.46, SD = 1.036), t (146) = 0.000, p = 1.000. In the same way none of the items yielded a significant difference between the unit square and the tree diagram when investigated individually. Thus, there was no reason to reject our hypothesis 2 in our first study. However, we could not replicate these results in the second study. When the items were regarded individually, a t-test yielded significant differences for item (b) (p<0.05) and (c) (p<0.01). Also, the accumulated score referring to all four items (α = .634) yielded a significant difference between the tree diagram (M = 3.01, SD = 1.11) and the unit square (M = 3.67, SD = 0.52), t (54) = 2.762, p = 0.008).

In the first study, the mean values of correct answers for the tree diagram were almost equal for all of the four items a, b, c and e addressing subset relations that were in line with the hierarchy of the tree diagram (88%, 85%, 86%, 86%). In contrast, in the second study for every item differences appeared. However, the performance for item (d) was lower for both visualizations. This might indicate that the subset relation (d) is more difficult to perceive than the other subset relations and that the visualization with the unit square is more helpful in this case.

Discussion of the results

For the situation of the flower girl, our results show a very clear effect in favor of the unit square. This was the case in the first study and, with very similar results, in our replication study. Nevertheless, we suggest for future research to prove this effect also for other contexts. In another study with 143 students of electrical engineering, we replicated the effect for subset relations that are not in line with the hierarchy of the tree diagram for two more different contexts. It is further desirable to investigate the effect of those subset relations used in the items a, b, c and e in more depth. This is especially the case since our results for this kind of items seems to be ambiguous. The replication study yielded significant differences referring to the efficiency of the tree diagram and the unit square in supporting students solutions in tasks where the subset relations are in line with the hierarchy of the tree diagram. Although this result was not expected and we further hypothesize that this result will not be replicated in further studies, it agrees with our overall hypothesis, i.e. the supremacy of the unit square to visualize situations in which the Bayes' rule has to be applied.

There are further aspects that that could be investigated in more detail. For example, there is the question of the order in the sequence in the tree diagram. It might be interesting to study the effect of the transposed order (roses / carnation on a lower level than red / white) and to compare it with a rotated unit square (roses / carnation arranged vertically and red / white arranged horizontally). This setting could be clarified if the hierarchy of the tree actually is the reason for the results in our study.

Moreover for the context of Bayesian reasoning, the results of Binder et al. (2015, p.6) suggest an advantage of the 2×2-table compared to the tree diagram, although no statistical difference between 2×2-tables and tree diagrams was reported. Thus, it is an open question if 2x2-tables are equally efficient than unit squares to make subset relations transparent or if there is an additional effect of the unit square due to the redundant geometrical and numerical representation.

Finally, there are further possibilities for visualizing set relations. One of these possibilities that was used in mathematics teaching is the double tree [START_REF] Wassner | Förderung Bayesianischen Denkens. Kognitionspsychologische Grundlagen und didaktische Analysen [Promoting Bayesian Reasoning[END_REF]. Thus, it could be interesting if a specific version of the tree diagram is able to decrease the weakness of the tree diagram to identify appropriately set relations.

Implications

The main result of our research seems nearly trivial: Visualizations have to visualize the main aspects of a mathematical concept if they aim to support students' understanding of this concept. Accordingly, a subset relation must be transparent when the aim of the visualization is to represent subset relations. However, it is by no means at all trivial to identify the crucial aspects of a mathematical concept. Actually, the tree diagram is very prominent in statistics education research [START_REF] Veaux | Intro stats[END_REF] and also psychological research [START_REF] Binder | Effects of visualizing statistical information -an empirical study on tree diagrams and 2 × 2 tables[END_REF] for visualizing Bayesian situation that necessitates applying Bayes' rule. However, our research gave evidence thatcompared to the unit square -the tree diagram is not efficient to visualize the set relation that is crucial to understand the structure of a Bayesian situation since it requires a subset relation that is not in line with the hierarchy of the tree diagram.

Our results have firstly some consequences if statistics education is regarded. [START_REF] Sloman | Frequency illusions and other fallacies[END_REF] expressed that bringing out nested set structure has been identified as being important for the improvement in Bayesian reasoning tasks. Thus, restricted to teaching and learning probability, our results imply to reconsider the role of the tree diagram to support students' learning referring to probability and Bayesian reasoning. This would be a considerable shift in statistics education (c.f. e.g. [START_REF] Gigerenzer | How I Got Started: Teaching Physicians and Judges Risk Literacy[END_REF][START_REF] Wassner | Teaching decision making and statistical thinking with natural frequencies[END_REF]. A little bit more globally, it could be considered if proportions, and in particular proportions of proportions could be appropriately visualized by a unit square to emphasize the connection between proportions of proportions and conditional probabilities. Thus, the unit square could potentially be understood as a visual connection between fractions and probabilities.

More generally, our results imply to focus the discussion of visualizations on the structure of visualization and on its relation to the structure of the represented mathematical concept. While the superiority of visualizations is a consensus in mathematics education as we outlined in the introduction, it is a crucial objective to find out which visualization best fits to a mathematical concept, especially in situations where several competing visualizations exist as it is the case for Bayesian reasoning situations. For example, [START_REF] Binder | Effects of visualizing statistical information -an empirical study on tree diagrams and 2 × 2 tables[END_REF] show that the tree diagram supports Bayesian reasoning compared to pure symbolic representation, whereas our results imply that the required subset relation is not transparent in the tree diagram. Indeed, in recent research, the unit square outperformed the tree diagram in Bayesian reasoning tasks [START_REF] Böcherer-Linder | The Impact of Visualizing Nested Sets. An Empirical Study on Tree Diagrams and Unit Squares[END_REF]Böcherer-Linder, Eichler & Vogel, in press). Therefore an ongoing task of educational research should be to precisely identify the relation of a visualization and its structure and the mathematical concept and its structure. One main message of our paper is that this relation is not sufficiently investigated, but could considerably impact on students' learning.

Figure 1 :

 1 Figure 1: Nested sets of the Bayesian situation of a medical diagnosis visualized by an Euler diagram (cf. Binder, Krauss & Bruckmaier, 2015).

Figure 2 :

 2 Figure 2: Representing statistical information with the tree diagram and the unit square

Flowers: A flower

  girl is selling red and white roses and carnations. Altogether, she has 120 flowers. Calculate the following proportions. Indicate the results in form of fractions. The proportion of a) red carnations among all carnations. b) white roses among all flowers. c) white flowers among all flowers. d) carnations among the red flowers. e) roses among all flowers.

Figure 3 :

 3 Figure 3: Items to assess the perception of subset relations

Figure 4 :

 4 Figure 4: Participants performance in the first study (left side) and in the replication study

Proceedings of CERME10


The relativistic F Q bit commitment protocol. A = Prover. Commit to a bit d ∈ {0, 1}. Non signaling condition: message 3 should be independent of message 1. André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018 13

On the binding property

wp. 1 2 , P can reveal whatever value b he wants and V will accept it. wp. 1 2 , V will always output ⊥. Still standard as a (weak) binding property. Well defined against quantum adversaries. We will present a strengthening of the sum-binding definition to avoid such behavior.

Proposition

The relativistic F Q bit commitment protocol is perfectly hiding and 2 Q sum-binding.

Hiding property: perfectly satisfied if we can enforce different randomness (here a ∈ R F Q ) at each run of the commit phase.

Sum-binding property: satisfied if message 3 is independent of message 1.

Let T be the time when B 1 sends message 1. Let T be the time when B 2 receives message 3 and let D the distance between B 1 and B 2 . If:

(T -T ) * c ≤ D then the non-signaling constraint is satisfied. Requires only to know the positions and timing of honest Bobs.

Hiding property:

After the commit phase, a is a purely random string so y = a ⊕ b • d is, from Bob's point of view, a totally random string.

Relate to a CHSH game

We consider the following game CHSH Q,2 2 player entangled game between Alice and Bob. Alice receives a uniformly random b ∈ F Q , Bob receives a random d ∈ {0, 1}. They produce respective outputs y , a ∈ F Q . They win iff. ya = x * y (x * 0 = 0 and x * 1 = x).

We can show the following:

Bit commitment to entangled games equivalence

If the relativistic F Q bit commitment scheme is ε sum-binding then ω * (CHSH Q,2 ) = 1 2 + ε 2 .

Consider a strategy S 0 = (comm * P , open * P ) for the relativistic F Q bit commitment scheme such that Let S 1 the above strategy for the CHSH Q,2 . We have ω * (CHSH Q,2 |S 1 ) = 1 2 + ε 2 . From there we have the following statement:

From bit commitment to entangled games

If the relativistic F Q bit commitment scheme is ε sum-binding then ω * (CHSH Q,2 ) ≥ 1 2 + ε 2 .
In a very similar fashion, we can transform any strategy for the game ω * (CHSH Q,2 ) into a cheating strategy for the F Q commitment. So:

Bit commitment to entangled games equivalence

If the relativistic F Q bit commitment scheme is ε sum-binding then ω * (CHSH Q,2 ) = 1 2 + ε 2 .
We can equivalently study the 2. We can show:

ω * (CHSH Q,2 ) ≤ 1 2 + 1 √ 2Q
How?, via consecutive measurements lemmata.

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Theorem

Let P and Q be two projectors and |ψ a quantum pure state. Let: p = Tr(P|ψ ψ|P) ; q := Tr(Q|ψ ψ|Q) ; E := Tr(QP|ψ ψ|PQ).

If p + q ≥ 1 then E ≥ p(p + q -1) 2 .

Idea of proof, use a geometric argument

We write |ψ = cos(α)|ψ P + sin(α)|ψ ⊥ P st. P|ψ = cos(α)|ψ P and |ψ P of norm 1.

Similarly, we write |ψ

= cos(β)|ψ Q + sin(α)|ψ ⊥ Q st. Q|ψ = cos(β)|ψ Q and |ψ Q of norm 1.
We have p = cos 2 (α) ; q = cos 2 (β) and E = pTr(Q|ψ P ψ P |Q). We now compute E = cos 2 (α)tr (Q|ψ P ψ P |Q).

Since |ψ Q ∈ Im(Q) and is of norm 1, we can construct an orthonormal basis |e 1 , . . . ,

|e k of Im(Q) with |e 1 = |ψ Q . We can write Q = k i=1 |e i e i | so Q |ψ Q ψ Q |. This implies E ≥ cos 2 (α)| ψ P |ψ Q | 2 .
To conclude, use the Angle distance

Angle Distance

Angle(|φ , |φ ) := Arccos(| φ|φ |). It's a distance (in particular, it has the triangular inequality).

Angle(|ψ , |ψ

P ) = α ; Angle(|ψ , |ψ Q ) = β. From triangle inequality: Arccos(| ψ P |ψ Q |) ≤ α + β. This implies | ψ P |ψ Q | ≥ cos(α + β). If α + β ≤ π, we get | ψ P |ψ Q | 2 ≥ cos 2 (α + β) ⇒ E ≥ cos 2 (α) cos 2 (α + β) Using the trigonometric inequality cos 2 (α + β) ≥ cos 2 (α) + cos 2 (β) -1 we can conclude that E ≥ cos 2 (α) cos 2 (α) + cos 2 (β) -1 2 = p(p + q -1) 2 .

Optimality of the bound

This bound is optimal for 1 dimensional projectors P = |ψ P ψ P | and

Q = |ψ Q ψ Q | if |ψ ∈ span(|ψ P , |ψ Q ).
If p + q = 1, we indeed have E = 0. Take for example

P = |0 0|; Q = |1 1|; |ψ = 1 √ 2 (|0 + |1
). Here: p = tr (P|ψ ψ|)q = tr (Q|ψ ψ|) = 1

2 and E = tr (PQ|ψ ψ|QP) = 0 since QP = 0(matrix).

André Chailloux (Inria, Paris)

Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Theorem

Let P and Q be two projectors and |ψ a quantum pure state. Let: p = Tr(P|ψ ψ|) ; q := Tr(Q|ψ ψ|) ; E := Tr(QP|ψ ψ|PQ).

If p + q ≥ 1 then E ≥ p(p + q -1) 2 .
Extension to mixed states:

Theorem

Let P and Q be two projectors and ρ a quantum mixed state. Let: p = Tr(Pρ) ; q := Tr(Qρ) ; E := Tr(QPρPQ).

If p + q ≥ 1 then E ≥ p(p + q -1) 2 .
ρ is in some quantum register A. Consider a purification |ψ of ρ in registers AB. By using the theorem on pure states, we can conclude.

Applications to quantum encodings 2 parties Alice and Bob, which share a quantum state

σ = x 0 ,x 1 ∈{0,1} p x 0 ,x 1 |x 0 , x 1 x 0 , x 1 | X 0 ,X 1 ⊗ σ B (x 0 , x 1 ).
Bob can guess x 0 with probability p 0 , Bob can guess x 1 with probability p 1 . We can assume wlog that this can be done via projective measurements (eventually by adding ancilla qubits to σ B (x 0 , x 1 )).

We relate p 0 ,p 1 and the probability of learning (x 0 , x 1 ).

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Proposition

Suppose Alice and Bob share a state

σ = x 0 ,x 1 ∈{0,1} p x 0 ,x 1 |x 0 , x 1 x 0 , x 1 | A ⊗ σ B (x 0 , x 1 ).
If there is a strategy for Bob to guess x 0 wp. p 0 and x 1 wp. p 1 then there exists a strategy to guess x 0 ⊕ x 1 wp. (p 0 + p 1 -1) 2 .

Proof:

Let P 0 = {P 0 x } x∈{0,1} n and P 1 = {P 1 x } x∈{0,1} n those measurements. For any b ∈ {0, 1}, each P b
x is a projector and x∈{0,1} n P b x = I (which also implies P b

x P b x = δ x,x P b x ).

Using this strategy, the probability that Bob respectively guesses x 0 and x 1 are:

p 0 = x 0 ,x 1 p x 0 ,x 1 Tr(P 0 x 0 σ B (x 0 , x 1 )) ; p 1 = x 0 ,x 1 p x 0 ,x 1 Tr(P 1 x 0 σ B (x 0 , x 1 ))

Projectors on winning subspace

Let the following 2 projectors

W 0 = x 0 ,x 1 |x 0 , x 1 x 0 , x 1 | ⊗ P 0 x 0 ; W 1 = x 0 ,x 1 |x 0 , x 1 x 0 , x 1 | ⊗ P 1 x 1 .
These are the projectors on the winning subspace. We have p 0 = tr (W 0 σ) and p 1 = tr (W 1 σ).

If Bob applies, P 0 and then P 1 , the probability of getting both outcomes correctly is

p 01 = x O ,x 1 p x 0 ,x 1 Tr(P 1 x 1 P 0 x 0 σ B (x 0 , x 1 )P 0 x 0 P 1 x 1 ).
which can be written also p 01 = Tr(W 1 W 0 σW 0 W 1 ).

Similarly, we define

p 10 = Tr(W 0 W 1 σW 1 W 0 ).
x 0 , x 1 are bits so p 0 , p 1 ≥ 1 2 . We can use the consecutive projection lemma to get

p 01 ≥ p 0 (p 0 + p 1 -1) 2 ; p 10 ≥ p 1 (p 0 + p 1 -1) 2 .
To conclude, we use the following strategy to try to learn (x 0 , x 1 ): wp. 1 2 , Bob applies measurement P 0 and gets y 0 then P 1 on the resulting state and gets y 1 , he outputs (y 0 , y 1 ). wp. 1 2 Bob applies measurement P 1 and gets y 1 then P 0 on the resulting state and gets y 0 , he outputs (y 0 , y 1 ).

Pr[Bob guesses (x 0 , x 1 )] ≥ 1 2 (p 01 + p 10 ) ≥ p(2p -1) 2 .
where recall that p = p 0 +p 1 2 . If needed:

Pr[Bob guesses (x 0 , x 1 )] ≥ max{p 0 , p 1 } • (2p -1) 2 .
Improvement: if we want to learn x 0 ⊕ x 1 .

Lemma

Let P and Q be two projectors and ρ a quantum mixed state. Let:

p = Tr(Pρ) ; q := Tr(Qρ) ; E := Tr(QPρPQ+(I -Q)(I -P)ρ(I -P)(I -Q)) If p + q ≥ 1 then E ≥ (p + q -1) 2 .

Proposition

Suppose Alice and Bob share a state

σ = x 0 ,x 1 ∈{0,1} p x 0 ,x 1 |x 0 , x 1 x 0 , x 1 | A ⊗ σ B (x 0 , x 1 ).
If there is a strategy for Bob to guess x 0 wp. p 0 and x 1 wp. p 1 then there exists a strategy to guess x 0 ⊕ x 1 wp.

(p 0 + p 1 -1) 2 .
This proposition is actually tight for non trivial examples.

Extension to x 0 , x 1 ∈ {0, 1} n .

The above arguments (for learning (x 0 , x 1 )) can be extended without problems.

But we still need the constraint

Pr[Bob can guess x 0 ] + Pr[Bob can guess x 1 ] ≥ 1.
The improvement when considering x 0 ⊕ x 1 is not known to work when x 0 , x 1 ∈ {0, 1} n .

Performing consecutive measurement doesn't seem to be the best strategy in most cases.

This bound is even worse sometimes than random guessing.

We don't of generic form to do better than consecutive measurements.

It will still be good enough for many cases, even if it's rarely tight.

Idea used several times: Idea: use the ⊕ learning lemma to bound the value of the CHSH. To do this, fix a cheating strategy S for Alice and Bob

Let Alice perform her strategy on input x to get output a. Let X 0 = a and

X 1 = x ⊕ a. Notice that X 0 ⊕ X 1 = x.
The winning condition of CHSH can be rephrased as follows

1 if y = 0, Bob must output b = a. 2 if y = 1, Bob must output b = a ⊕ y
This means that:

Pr[Alice and Bob win CHSH using S] = 1 2

From non signaling, we know that

E := Pr[Bob guesses x] = 1 2 . If we define V := 1 2 y ∈{0,1} (Pr[Bob guesses X y ]) =
Pr[Alice and Bob win CHSH using S]., we have Again, fix a cheating strategy S for Alice and Bob. Let X 0 = a and X 1 = x + a. Again, notice that X 1 -X 0 = x so if Bob learns (X 0 , X 1 ), he can learn x. We write again

1 2 = E ≥ (2V -1) 2 ⇒ V ≤ cos 2 (π/8). André Chailloux (Inria,
E := Pr[Bob guesses x]
and Applying the consecutive measurements lemma, we have

V := 1 2 y ∈{0,1} (
1 Q = E ≥ V (2V -1) 2 ≥ 1 2 (2V -1) 2 .
From there, we get

V ≤ 1 2 + 1 √ 2Q .
Since this is true for any cheating strategy S, we conclude that

ω * (CHSH Q,2 ) ≤ 1 2 + 1 √ 2Q
Used crucially the fact that there is a single possible opening for each d. Cases where we know the value:

ω * (CHSH Q,Q ) ≤ O( 1 √ Q ). When Q is an even power of a prime, ω(CHSH Q,Q ) = ω * (CHSH Q,Q ) = Θ( 1 √ Q ).
When Q is an even power of a prime, the resulting Q-string commitment scheme is Θ( √ Q) sum-binding (we hoped for ε sum-binding with ε 1).

The scheme is still 1 Q special binding so in the case of string commitment, special binding doesn't imply sum-binding.

Can we say interesting things for some values of T > 2? Yes. Proposition

ω * (CHSH Q,T ) ≤ 1 T + 4 Q 1/3 .
Idea, use a generalization of the consecutive measurement lemma.

Corollary

The F Q based T -string commitment is 4T

Q 1/3 sum-binding. If we want an 2 -k sum-binding protocol for some k ∈ N, we can take Q = 64T 3 2 3k .

Recall that each message in the protocol is log(Q) so we can achieve an n-bit string commitment (i.e. T = 2 n ) with the F Q protocol where each message is 3n + 3k + 8 bits. Now we need to prove the proposition and dive into the generalization of consecutive measurements.

Again, the most generic way to look at this is to go back through the notion of encodings.

Proposition

Let P 1 , . . . , P T be projectors and |ψ a quantum pure state. Let:

p i = Tr(P i |ψ ψ|P i ) ; V := 1 T i p i and E := 1 T (T -1)
i,j =i Tr(P j P i |ψ ψ|P i P j ). We have

E ≥ 1 64 (V - 1 T ) 3 .
Notice that this is an average case statement and not a worst case statement. Also, the bound is useful only for V > 1 T .

Tight in the sense that we can find an example with V = 1 T and E = 0. Take |ψ = 1 √ T T i=1 |i and P i = |i i|.

Known similar results?

Yes, proven for the study of sigma protocols with special soundness (i.e. in a similar context)

Proposition (Unr12)

Let P 1 , . . . , P T be projectors and |ψ a quantum pure state. Let:

p i = Tr(P i |ψ ψ|P i ) ; V := 1 T i p i and E := 1 T (T -1) i,j =i Tr(P j P i |ψ ψ|P i P j ). If V ≥ 1 √ T then E ≥ T (T -1) V (V 2 - 1 T ).

Proposition

Let P 1 , . . . , P T be projectors and |ψ a quantum pure state. Let:

p i = Tr(P i |ψ ψ|P i ) ; V := 1 T i p i and E := 1 T (T -1)
i,j =i Tr(P j P i |ψ ψ|P i P j ). We have

E ≥ 1 64 (V - 1 T ) 3 .
We define |ψ i = P i |ψ √ p i . One can check that the |ψ i are of norm 1 and that | ψ|ψ i | 2 = p i . Fix any i, j = i. As in the T = 2, we get

E i,j := Tr(P j P i |ψ ψ|P i P j ) = p i Tr(P j |ψ i ψ i |P j ) ≥ p i | ψ i |ψ j | 2 . with E = 1 T (T -1) i,j =i E i,j .
Extremal case: when can we get E = 0? If for any i, j = i, we have

ψ i |ψ j = 0. OR ψ|ψ i = 0. a quick analysis gives V = 1 T i | ψ|ψ i | 2 ≤ 1 T . By a counterpositive, if V > 1 T then E > 0.
So we need to show that the | ψ i |ψ j | 2 are not too small on average. We show the following

Lemma Let S = T • V = i | ψ|ψ i | 2 ; C = i,j =i | φ i |φ j | 2 .
We have

S ≤ 1 + (n -1)C n .
Proof of the lemma

Let M = T i=1 |ψ i ψ i |. Let λ 1 ≥ λ 2 ≥ . . . λ T the T (not necessarily distinct) eigenvalues of M. We first have T i=1 λ i = Tr(M) = T i=1 Tr(|ψ i ψ i |) = T . Notice that λ 1 = max |Ω T i=1 | ψ|Ω | 2 ≥ S.
Next we write M 2 = T i,j=1 ψ i |ψ j |ψ i ψ j | and

T i=1 λ 2 i = tr (M 2 ) = T i,j=1 ψ i |ψ j 2 ≤ T i,j=1 | ψ i |ψ j | 2 = T + C
This gives us

T + C ≥ T i=1 λ 2 i = λ 2 1 + T i=2 λ 2 i ≥ S 2 + (T -S) 2 T -1
From there, we can conclude S ≤ 1 + (T -1)C T or equivalently

V ≤ 1 T + T -1 T 1 T (T -1) i,j =i | φ i |φ j | 2 .
(1)

Recall that we want to relate

V = 1 T i | φ|φ i | 2 and E = 1 T (T -1) i,j =i | φ|φ i | 2 | φ i |φ j | 2 . Easy case: if ∀i, | φ|φ i | 2 = V (symmetric case), we can rewrite E = V T (T -1) i,j =i | φ i |φ j | 2
and plugging this in Eq 1:

V ≤ 1 T + T -1 T E V ⇒ E ≥ T T -1 2 V (V - 1 T ) 2
General case, more cumbersome calculations.

Let Z = {i : p i ≥ V κ } for a parameter κ > 1 that will be fixed later.

S Z := i∈Z p i ≥ 1 (1+ 1 κ-1 ) S. C Z = i,j =i∈Z | φ i |φ j | 2 . S Z ≤ 1 + C Z . E = 1 T (T -1) i,j =i | φ|φ i | 2 | φ i |φ j | 2 ≥ 1 T (T -1) i,j =i∈Z | φ|φ i | 2 | φ i |φ j | 2 ≥ 1 T (T -1) i,j =i∈Z V κ | φ i |φ j | 2 = VC Z κT (T -1) S Z ≤ 1 + κET (T -1) V ≤ 1 + T κE V . S ≤ (1 + 1 κ -1 )S Z ≤ (1 + 1 κ -1 )(1 + T κE V ). V ≤ (1 + 1 κ -1 )( 1 T + κE V ).
Optimization in κ, relation between E and V . κ = max 2, ( V T 2 E ) 1/3 . We get

E ≥ 1 64 (V - 1 T ) 3 .
The generic F Q Q-string commitment scheme is not sum-binding even though it is special binding.

Can we still say something about its security as a string commitment?

Yes: distributionally + sum-binding.

Using the F Q relativistic bit commitment in order to transform a Σ-protocol into a relativistic protocol.

In order to analyze cheating provers, the relativistic protocol can then be directyl transformed into an entangled 2 player game between P 1 and P 2 .

A zero-knowledge protocol for a language L is an interactive protocol between a prover P and verifier V , parametrized by a security parameter k, with the following properties:

Completeness: ∀x ∈ L, Pr[V accepts] ≥ 1 -negl(k). Soundness: ∀x / ∈ L, Pr[V accepts] ≤ negl(k).
Zero-knowledge: there is polynomial time simulator S st. ∀x ∈ L, ∀ cheating V * and ∀ρ (auxiliary state),

StatDiff (S V * (x, ρ), view V * (x, ρ)) ≤ negl(k).
where view V * (x, ρ) is verifier's view of the protocol (the transcript as well as his quantum and classical registers).

The adjacency matrix

M G of G is a V × V st. M G (i, j) = 1iff .(i, j) ∈ E .
For our example: The adjacency matrix

M G =           0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0           André Chailloux (Inria,
M G of G is a V × V st. M G (i, j) = 1 iff. (i, j) ∈ E . M G =           0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0          
If you are given the corresponding to a Hamiltonian cycle, one can check whether it indeed forms such a cycle or not. We don't need to look at the rest of the matrix to determine this.

The relativistic zero-knowledge protocol for Hamiltonian cycle will exactly be plugging in the F Q parallel relativistic bit commitment in the zero-knowledge protocol.

Relativistic zero knowledge protocol for Hamiltonian cycle

Input -The provers and the verifiers are given a graph G = (V , E ). Auxiliary Input -The provers P 1 and P 2 know a Hamiltonian cycle C of G . Preprocessing -P 1 and P 2 agree beforehand on a random permutation Π : V → V and on an n × n random matrix A ∈ M

F Q n . 1 Commitment to each bit of M Π(G ) : V 1 sends a matrix B ∈ M F Q n where each element of B is chosen uniformly at random in F Q . P 1 outputs the matrix Y ∈ M F Q n such that ∀i, j ∈ [n], Y i,j = A i,j + (B i,j * (M Π(G ) ) i,j ). 2
The verifier sends a random bit chall ∈ {0, 1} to the prover.

What do we need to prove?

Completeness: The single prover/verifier zero-knowledge protocol for Hamiltonian cycle is perfectly complete and so is the F Q bit commitment scheme. If both parties are honest and we are in a yes instance, the protocol always succeeds.

Soundness: This will be the hardest part. An extra difficulty will arise because there are several valid openings.

Zero-knowledge:

The commitment is perfectly hiding and the original zero-knowledge protocol is perfectly zero-knowledge. We will show that this relativistic zero-knowledge protocol remains perfectly zero-knowledge.

All the CHSH type games we considered were projective (even unique) so the argument worked well.

In terms of commitment, given a fixed transcript for the commit phase and a fixed string s, there is a unique opening string for s.

However, in the zero-knowledge protocol, there are many valid strings that can be opened (one for each permutation).

Consider a graph G with no Hamiltonian cycle. The cheating provers must win the following entangled game in order to convince the verifiers.

RZK-HAM game

P 1 receives a matrix B ∈ M F Q
n where each element of B is chosen uniformly at random in F Q . P 2 receives a random input bit chall.

P 1 outputs a matrix Y ∈ M F Q n . If chall = 0 then P 2 outputs a permutation Π and a matrix A ∈ M F Q n . If chall = 1 then P 2 outputs a cycle C and n strings {A (u,v ) } (u,v )∈C in F Q . If chall = 0, the two players win if ∀i, j ∈ [n], Y i,j = A i,j + (B i,j * (M Π(G ) ) i,j ). If chall = 1, the two players win if for all edges (u, v ) of C , Y u,v = A u,v + B u,v
, which corresponds to revealing 1 for each edge of the cycle C .

An entangled 2 player game G is said to be α-projective iff.

∀x, y , a |{b : A and B win G on inputs (x, y ) and ouputs (a, b)}| ≤ α.

Proposition

The RZK-HAM game is n! projective.

Proof.

When P 2 decides the string he wants to reveal, there is a unique way to open this string, this comes from the property of our F Q string commitment.

If chall = 0, there is an opening that the verifier will accept for each permutation Π, so n! valid outputs for P 2 .

If chall = 1, there is an opening that the verifier will accept for each cycle C . There are again n! such cycles. This shows that the game is n!-projective

Proposition

Let P 1 , . . . , P T be projectors that can be written as P i = α s=1 P s i where P s i are orthogonal projectors for any fixed i. Let |ψ be a quantum pure state and let

p i = Tr(P i |ψ ψ|) = α s=1 Tr(P s i |ψ ψ|) ; V := 1 T i p i and E := 1 T (T -1) α s,s =s=1 i,j =i
Tr(P s j P s i |ψ ψ|P s i P s j ).

We have

E ≥ 1 64α (V - 1 T ) 3 .
Use it to bound the value of α-projective games from special soundness

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Proof of the proposition. We can sum the outside projector to get

E = 1 T (T -1) α s=1 i
Tr(P j P s i |ψ ψ|P s i P j ).

Lemma (Pinching inequality)

For any projector P i = α s=1 P s i where P s i are orthogonal projectors and |ψ , we have

α s=1 P s i |ψ ψ|P s i P i |ψ ψ|P i .
This gives us immediately

E = 1 T (T -1) α s=1 i
Tr(P j P s i |ψ ψ|P s i P j )

≥ 1 α 1 T (T -1) i Tr(P j P i |ψ ψ|P i P j ) ≥ 1 64α (V - 1 T ) 3
This can also be extended when we only have 2 projectors with an improved bound.

Proposition

Let P 0 , P 1 be projectors that can be written as P i = α s=1 P s i where P s We have

E ≥ 2 α (V - 1 2 ) 2 .
We have the formula E ≥ 2 α (V -1 2 ) 2 . The RKZ-HAM protocol (or entangled game) has special soundness 1 Q so we can plug in E = 1 Q . We obtain

ω * (G RZK-HAM ) ≤ 1 2 + n! 2Q .
by taking Q = n! 2 k+1 , we get that the soundness of the protocol is 1 2 + 2 -k .

We just need to perform this protocol in parallel to reduce the soundness to a negligible quantity. This can be done similarly, since we know the F Q bit commitment behaves well when run in parallel.

What about the zero-knowledge property? What is the verifier's view of the protocol?

No matter what the verifier sends during the commit step, he obtains uniformly random strings from the prover.

How to include the sustain phase in the security? Give as much power as possible to the cheating parties.

The bit commitment protocol consists of comm = (comm(P), comm(V ));

Perfect hiding property

For any strategy comm * (V ), sust * (V ), the transcript of (comm(P), comm * (V ), sust(P), sust * (V )) should be independent of d. Even though the string commitment used in the sustain phase doesn't have the sum-binding property, it's still possible to prove the binding property, at least in the classical case. For r rounds:

Sum-binding property

LKB+14 : ε ≈ O(( 1 √ Q ) 1/2 r ). Proof idea, reduce to a single game. [FF15,CCL15] : ε = O( r √ Q ).
[FF15]: based on composition of relativistic bit commitment schemes. [CCL15] : recursive analysis using 2 player games.

For double-round protocol, A 1 must guess a 2 (d) = y 2 + b 2 * a 1 (d). We can reduce to the following 2 player game.

b 1 doesn't intervene directly in the winning condition (it does only in the sense that A 1 knows a 1 ) and d is known by both players.

So we can reduce to the following game: For a fixed d, they win the game if a 2 (d) -y 2 = b 2 * a 1 (d). Exactly (up to thesign) the CHSH Q,Q game. However, a 1 is not necessarily a uniform random string unknown from A 2 . If p 1 (d) = Pr[A 2 can guess a 1 (d)], we have that

p 1 (0) + p 1 (1) ≤ 1 + 2 2 Q .
from the sum-binding security of the single round protocol.

This motivates defining the game CHSH - Q,Q (p) as follows:

CHSH - Q,Q (p)
2 player entangled game between A 1 and A 2 . Alice receives a string

a 1 ∈ F Q st. max c {Pr[ a 1 = c]} = p, Bob receives a random b 2 ∈ F Q . They produce respective outputs a 2 , y 2 ∈ F Q . They win iff. y 2 -a 2 = a 1 * b 2 . Notice that ω(CHSH + Q,Q (p)) ≥ p and ω(CHSH + Q,Q ( 1 Q )) = ω(CHSH + Q,Q ( 1 Q )).
From the previous analysis, we have (for classical adversaries) that the 2-round F Q bit commitment is ε sum-binding for ε such that We can prove the following bound

ω(CHSH - Q,Q (p 1 (0))) + ω(CHSH - Q,Q (p 1 (1))) = 1 + ε. with p 1 (0) + p 1 (1) ≤ 1 + 2 Q . André Chailloux (Inria,
ω(CHSH Q,Q (p)) ≤ p + 2 Q .
Plugging this in the previous, we get

p 1 (0) + p 1 (1) + 2 2 Q = 1 + ε which gives ε ≤ 4 2 Q .
Fix a strategy S. For a fixed (x, c(x)), this strategy is deterministic (the randomness can be included in c(x). For each i, let s i (x, c(x)) ∈ {0, 1} = Pr[Bob guesses x i |S]. We use the consecutive measurement strategy to try to learn (x i , x j ) for any i, j = i. Let: V (x, c(x)) the probability of guessing x i for a random i for a fixed (x, c(x)) E (x, c(x)) the probability of guessing a random (x i , x j ) for a random i, j = i and a fixed (x, c(x)). We have

V (x, c(x)) = 1 n n i=1 s i (x, c(x)) = κ n for some κ ∈ N. E (x, c(x)) = 1 n(n -1) i,j =i s i (x, c(x))s j (x, c(x)) = κ(κ -1) n(n -1) = nV (x, c(x)) n -1 (V (x, c(x)) - 1 n ).
If we define f n (X ) = nX n-1 X -1 n we can see that f n is convex and by rewriting the above equation, we have E (x, c(x)) = f n (V (x, c(x))). We can now conclude

E = E x,c(x) [E (x, c(x))] = E x,c(x) [f n (V (x, c(x)))] ≥ f n (E x,c(x) [E (x, c(x))]) = f n (V ) = nV n -1 (V - 1 n ).
Similarly as before, we can use this to bound the value of the CHSH Q,Q (p) game. but with a subtelty. A 2 has some information about a 1 which could be of the form of a shared state |ψ a 1 with A 1 . This means that It is no longer a 2 player entangled game in the usual sense.

Our proof technique does not work here.

If we can show that the entangled value of the above game (with share state |ψ a 1 is smaller than p + f (q) then the r -round F Q protocol would be ε sum-binding secure against quantum adversaries with ε = 2rf (q).

It is possible to show a bound for the above problem of the form √ p + f (q). Behaves very poorly when considering multiple rounds.

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018 102 / 104

In the case, where the shared state is independent of the inputs, we can use the consecutive learning lemma and use the fact that A 1 can guess b 2 wp. 1 Q . This gives the bound p + 2 Q .

However, if we considered the opposite strategy i.e. trying to apply the consecutive measurements on A 2 , we would only get 1 Q + √ p which is potentially much worst. (For example, for CHSH 2,Q i.e. p = 1 2 , this would give a bound larger than 1 2 while we know a bound of 1 2 + 1 √ Q .

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018 103 / 104

In the case, where the shared state is independent of the inputs, we can use the consecutive learning lemma and use the fact that A 1 can guess b 2 wp. 1 Q . This gives the bound p + 2 Q .

If there is an entangled state that depends on a i then the above scenario doesn't make sense.

What we can do is to consider the opposite strategy i.e. trying to apply the consecutive measurements on A 2 , we would only get 1 Q + √ p which is potentially much worst. (For example, for CHSH 2,Q i.e. p = 1 2 , this would give a bound larger than 1 2 while we know a bound of

  outputs b |(comm * P , open * P )] ≤ 1 + ε Weak definition. For example, it could allow a cheating strategy comm * P such that

  succ. reveals d|comm * P , open * P (d)]) = 1 + ε. Transforming such a strategy into a strategy for the CHSH Q,2 game A 1 and A 2 share the same entangled state |ψ . On input b, Adeline performs COMM * P (b) to get outcome y . On input d, Bastian performs OPEN * P (d) to get outcome a. They win ya = b * d.

P

  and Q are projectors on A. Let P = P ⊗ I B and Q = Q ⊗ I B , which are projectors on AB. We have p = Tr(Pρ) = Tr(P |ψ ψ|) ; q = Tr(Qρ) = Tr(Q |ψ ψ|) If we define E = Tr(Q P |ψ ψ|P Q ), we can easily show that E = E .

  game between Alice and Bob. They receive respective uniformly random inputs x, y ∈ {0, 1} and produce respective outputs a, b ∈ {0, 1}. They win iff. a ⊕ b = x • y .

  Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018 Extension to CHSH Q,2 CHSH Q,2 2 player entangled game between Alice and Bob. Alice receives a uniformly random x ∈ F Q , Bob receives a random y ∈ {0, 1}. They produce respective outputs a, b ∈ F Q . They win iff. a + b = x * y (x * 0 = 0 and x * 1 = x).

  Pr[Bob guesses X y ]) = Pr[Alice and Bob win CHSH 2,Q using S ] André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

i

  are orthogonal projectors for any fixed i ∈ {0, 1}. Let |ψ be a quantum pure state and let p i = Tr(P i |ψ ψ|)

  sust = (sust(P), sust(V )); open = (open(P), open(V )).

∀

  comm * (P), b ∈{0,1} max open * (P),sust * (P) Pr[V outputs b |(comm * (P), sust * (P), open * (P))] ≤ 1 + ε

  Issue with the quantum case? We need to bound the quantum value ofCHSH - Q,Q (p)2 player entangled game between A 1 and A 2 . Alice receives a stringa 1 ∈ F Q st. Pr[A 2 can guess a 1 ] ≤ p, Bob receives a random b 2 ∈ F Q .They produce respective outputs a 2 , y 2 ∈ F Q . They win iff. y 2 -a 2 = a 1 * b 2 .

André Chailloux (Inria, Paris)

Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018 100 / 104

André Chailloux (Inria, Paris)Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

y ∈{0,1} (Pr[Bob guesses X y ]) André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

The verifier checks that these decommitments are valid and correspond, for chall = 0 to M Π(G ) and, for chall = 1, to a Hamiltonian cycle.André Chailloux (Inria, Paris)Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

If chall = 0, P 2 decommits to all the elements of M Π(G ) , i.e. he sends all the elements of A to V 2 and reveals Π. If chall = 1, P 2 reveals only the bits (of value 1) of the adjacency matrix that correspond to a Hamiltonian cycle C of Π(G ), i.e. for all edges (u, v ) of C , he sends A u,v as well as C .

The verifier checks that those decommitments are valid: if chall = 0, the prover's opening A must satisfy ∀i, j ∈[n], Y i,j = A i,j + (B i,j * (M Π(G ) ) i,j ). if chall = 1, the prover's opening A must satisfy ∀(u, v ) ∈ C , Y u,v = A u,v + B u,v .André Chailloux (Inria, Paris)Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

Relativistic string commitment

Committing to a single bit is not always enough.

We would like to commit to string of bits at the same time and say something about this commitment But the sum-binding definition is weak and is not well suited for such statements. We have also access to the special binding property Having access to those, can we manage to say something about string commitment? Yes but requires some work.

Again, we can reduce to the CHSH Q,T game.

CHSH Q,T 2 player entangled game between Alice and Bob. Alice receives a uniformly random x ∈ F Q , Bob receives a random y ∈ F T . They produce respective outputs a, b ∈ F Q . They win iff. a + b = x * y .

Again, we map a cheating strategy for the string commitment to an entangled strategy for the CHSH Q,T game.

Proposition

The above mentioned relativistic T -string commitment scheme is

Difficulty of the statement

Recall for T = 2, we could have p 1 = p 2 = 1 2 and E = 0. Idea behind this worst case:

Interpretation in terms of encodings Proposition (General learning lemma for pairs of strings)

Suppose Alice and Bob share a state

If for each i, there is a strategy for Bob to guess x i wp. p i then there exists a couple (i, j) and a strategy for Bob to guess (x i , x j ) wp. If for each i, j = i, Bob can guess

We can recognize here already the relation between the sum binding property and the special binding property. If ε ≤ 2 -3k (4n) 1/3 for some k then i Pr[Bob can guess

Bob has a random y ∈ F P and wins the game if he guesses X y .

For any y , y = y , we have x = X y -Xy y -y so if Bob can guess X y and X y then he can guess x. On average on x, a, this happens wp. 1 Q by non-signaling.

By using the special soundness lemma, we have

We deal with averaging on (x, a) similarly as for the T = 2 case.

Corollary

The

Parallel repetition of bit commitment

We proved the sum-binding property for a string commitment.

Problem: We can only reveal the whole string or nothing. In most cases, it's nice to be able to reveal some bits of the string.

With the special soundness lemma, we can also prove that the parallel repetition of the F Q bit commitment preserves the sum-binding property as a string commitment.

Definition

A bit commitment is ε distributionally + sum-binding if ∀ comm * P , there is a pr. distr. r st ∀d and ∀open * P (d), we have

Proposition

The

Sigma protocols

Consider protocols between a single prover P and a single verifier V of the following form:

1 P commits to n bits (or strings) x 1 , . . . , x n .

2 V sends a challenge chall to the prover.

3 Depending on chall, P opens some of the x i . He also sends an answer a to the verifier.

Hamiltonian cycle problem

We consider an undirected graph G = (V , E ) without self loops.

A Hamiltonian cycle is a cycle going through each vertex exactly once. Determining whether a graph contains a Hamiltonian cycle is an NP-complete problem.

Zero-knowledge protocol for Hamiltonian cycle using bit commitment

1 The prover picks a random permutation Π : V → V . He commits to each of the bits of the adjacency matrix M Π(G ) of Π(G ).

2

The verifier sends a random bit (called the challenge) chall ∈ {0, 1} to the prover.

3

If chall = 0, the prover decommits to all the elements of M Π(G ) , and reveals Π.

If chall = 1, he reveals only the bits (of value 1) of the adjacency matrix that correspond to a Hamiltonian cycle C of Π(G ).

Generic idea to use special learning lemma for bounding entangled games

A game is projective if for each x, a, y there is a unique b x,a (y ) such that the players win the game on inputs (x, y ) and outputs (a, b).

When fixing (x, a), the probability of winning the game is the probability for Bob of guessing b x,a (y ). If we can bound the probability of guessing a couple b x,a (y ), b x,a (y ) for y = y then we can use the special learning lemma to bound the value of the game.

The projective property is crucial for this argument.

Proposition

The RZK-HAM protocol has special soundness 1 Q .

Proof

Proving this is equivalent to proving that for any strategy used by P 1 , P 2 can send a valid opening for both chall = 0 and chall = 1 wp. 1 Q . We fix an input/output pair (B, Y ) for P 1 and we consider winning outputs for P 2 for both inputs. For chall = 0, we have a permutation Π and a matrix

(2)

For chall = 1, we have a cycle C of {1, . . . , |V |} as well as openings A u,v for each (u, v ) ∈ C . Because it is a winning output, the openings must satisfy

(3)

Proof continued

If the graph G (hence also Π(G )) does not contain a Hamiltonian cycle then there has to be an edge (u, v ) of C such that M Π(G ) u,v = 0. For this specific (u, v ), we combine Equations 2 and 3 and get:

This implies that A u,v -A u,v = B u,v which happens with probability at most 1 Q from non-signaling.

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

How we transformed special soundness security into sum-binding security Proposition Let P 1 , . . . , P T be projectors and |ψ a quantum pure state. Let:

i,j =i Tr(P j P i |ψ ψ|P i P j ). We have

Use it to bound the value of projective games from special soundness

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

We presented the F Q bit/string commitment protocol with an application to a zero-knowledge protocol for Hamiltonian cycle.

We could commit and immediately after perform an opening.

But the underlying bit/string commitment protocol works only for a very short of time.

Here, we show to increase the commit time.

André Chailloux (Inria, Paris) Relativistic commitment and zero-knowledge proofs Bellairs, March 4-8 2018

The relativistic F Q bit commitment protocol

Commit to a bit d ∈ {0, 1}.

If P 1 , P 2 are at a distance D, the commitment is valid for a time < D c . Idea: instead of revealing a, P 2 commits to a using a F Q string commitment scheme. 2 possibilities: make the alphabet size explode with the number of rounds or use a bad string commitment.

Multi-round F

Here, q is a prime power p n for some prime p and F q refers to the Galois field of order q.

2 Commit phase:

where d ∈ {0, 1} is the committed bit.

3 Sustain phase, starting at i = 2: at round i, B i mod 2 sends b i ∈ F q to A i mod 2 , who returns y i = a i + (a i-1 * b i ).

4 Reveal phase: A 1 reveals d and a

Timing constraints: round j finishes before any information about b j-1 reaches the other Alice.

We proved the following:

The 1 round protocol is ε-binding for ε = 2 2 Q .

The 2 round protocol is ε-binding for ε = 4 2 Q . The recursive statement actually works: the r round protocol is ε-binding for ε = 2r 2 Q .

Proof idea of the classical bound: actually very close to the quantum setting for CHSH Q .

Proposition (Classical learning lemma)

Suppose Alice has a string x = x 1 , . . . , x n and Bob has a string c(x), all given with some joint probability distribution q(x, c(x)). Suppose that Bob has a strategy to learn x i wp. p i and let V = 1 n i p i . There is a strategy to guess (x i , x j ) wp. p i,j such that


André Chailloux
email: andre.chailloux@inria.fr

A note on the quantum query complexity of permutation symmetric functions

It is known since the work of [AA14] that for any permutation symmetric function f , the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that R(f

In this paper, we improve this result and show that R(f ) = O Q 3 (f ) for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zha15].

Introduction

The black box model has been a very fruitful model for understanding the possibilities and limitations of quantum algorithms. In this model, we can prove some exponential speedups for quantum algorithms, which is notoriously hard to do in standard complexity theory. Famous examples are the Deutsch-Josza problem [START_REF] Deutsch | Rapid solution of problems by quantum computation[END_REF] and Simon's problem [START_REF] Daniel | On the power of quantum cryptography[END_REF]. There has been a great line of work to understand quantum query complexity, which developed some of the most advanced algorithms techniques. Even Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF] for factoring fundamentally relies on a black box algorithm for period finding.

We describe here the query complexity model in a nutshell. The idea is that we have to compute f (x 1 , . . . , x n ) where each x i ∈ [M ] can be accessed via a query. We consider decision problems meaning that f : S → {0, 1} with S ⊆ [M ] n . In this paper, we will consider inputs x ∈ [M ] n equivalently as functions from [n] → [M ]. We are not interested in the running time of our algorithm but only want to minimize the number of queries to x, which in the quantum setting consists of applying the unitary

O x : |i |j → |i |j + x i . D(f ), R(f ) and Q(f ) represent
the minimal amount of queries to compute f with probability greater than 2/3 (or = 1 for the case of D(f )) using respectively a deterministic algorithm with classical queries, a randomized algorithm with classical queries and a quantum algorithm with quantum queries.

As we said before, the query complexity is great for designing new quantum algortihms. It is also very useful for providing black box limitations for quantum algorithms. There are some cases in particular where we can prove that the quantum query complexity of f is at most polynomially smaller than classical (deterministic or randomized) query complexity. For example:

• for specific functions such as search [START_REF] Bennett | Strengths and weaknesses of quantum computing[END_REF] or element distinctness [AS04, Kut05, Amb05], we have respectively

Q(Search) = Θ(n 1/2 ), D(Search) = Θ(n) and Q(ED) = Θ(n 2/3 ), D(ED) = Θ(n).
• For any total function f i.e. when its domain S = [M ] n , Beals et al. [BBC + 01] proved using the polynomial method that D(f

) ≤ O(Q 6 (f )).
Another case of interest where we can lower bound the quantum query complexity is the case of permutation symmetric functions. There are several ways of defining such functions and we will be interested in the following definitions for a function

f : S → {0, 1} with S ⊆ [M ] n . Definition 1. • f permutation symmetric of the first type iff. ∀π ∈ S n , f (x) = f (x • π). • f is permutation symmetric of the second type iff. ∀π ∈ S n , ∀σ ∈ S M , f (x) = f (σ • x • π).
where S n (resp. S M ) represents the set of permutations on [n] (resp.

[M ]).

Here, recall that we consider strings

x ∈ [M ] n as functions from [n] → [M ]
. Notice also that this definition implies that S is stable by permutation, meaning that x ∈ S ⇔ ∀π ∈ S n , x • π ∈ S. We already know from the work of Aaronson and Ambainis the following result:

Theorem 1 ([AA14]). For any permutation invariant function f of the second type,

R(f ) ≤ O(Q 7 (f )).
In a recent survey on quantum query complexity and quantum algorithms [Amb17], Ambainis writes: "It has been conjectured since about 2000 that a similar result also holds for f with a symmetry of the first type."

Contribution. The contribution of this paper is to prove the above conjecture. We show the following:

Theorem 2. For any permutation invariant function f of the first type, R(f ) ≤ O(Q 3 (f )).
This result not only generalizes the result for a more general class of permutation symmetric function, but also improves the exponent from 7 to 3. In the case where M = 2, this result was already known [START_REF] Aaronson | The need for structure in quantum speedups[END_REF] with an exponent of 2, which is tight from Grover's algorithm.

The proof technique is arguably simple, constructive and relies primarily on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [START_REF] Zhandry | A note on the quantum collision and set equality problems[END_REF]. We start from a permutation symmetric function f . At high level, the proof goes as follows:

• We start from an algorithm A that outputs f (x) for all x with high (constant) probability. Let q the number of quantum queries to O x performed by A .

• Instead of running A on input x, we choose a random function

C : [n] → [n]
with small range r (from a distribution specified later in the paper) and apply the algorithm A where we replace calls to O x with calls to O x•C . We note that there is a simple procedure to compute

O x•C from O x and O C .
• If we take r = Θ(q 3 ), we can use Zhandry's lower bound, we show that for each x, the output will be close to the output of the algorithm A where we replace calls to O x•C with calls to O x•π for a random permutation π. Using the fact that f is permutation symmetric, the latter algorithm will output with high probability

f (x • π) = f (x).
In other words, if the algorithm A that calls O x•C wouldn't output f (x) for a random C and a fixed x then we would find a distinguisher between a random C and a random permutation π, which is hard from Zhandry's lower bound.

• The above tells us that applying A where we replace calls to After presenting a few notations, we dive directly into the proof of our theorem.

Preliminaries

Notations

For any function f we denote by Dom(f ) its domain and by Im(f ) its range (or image).

Query algorithms. A query algorithm A O is described by an algorithm that calls another function O in a black box fashion. We will never be interested in the running time or the size of A but only in the number of calls, or queries, to O. We will consider both the cases where the algorithm A O is classical and quantum. In the latter O will be a quantum unitary. In both cases, we only consider algorithms that output a single bit.

Oracles. We use oracles to perform black box queries to a function. For any function g, O Classical g is a black box that on input i outputs g(i) while O g (without any superscript) is the quantum unitary satisfying

O g : |i |j → |i |j + g(i) .
Query complexity. Fix a function f : S → {0, 1} where S ⊆ [M ] n . Definition 2. The randomized query complexity R(f ) of f is the smallest integer q such that there exists a classical randomized algorithm A O performing q queries to O satisfying:

∀x ∈ S, Pr[A O Classical x outputs f (x)] ≥ 2/3.
Definition 3. The quantum query complexity Q(f ) of f is the smallest integer q such that there exists a quantum algorithm A O performing q queries to O satisfying:

∀x ∈ S, Pr[A Ox outputs f (x)] ≥ 2/3.

Hardness of distinguishing a random permutation from a random function with small range

Our proof will use a quantum lower bound on distinguishing a random permutation from a random function with small range proven in [START_REF] Zhandry | A note on the quantum collision and set equality problems[END_REF]. Following this paper, we define, for any r ∈ [n], the following distribution D r on functions from [n] to [n] from which can be sampled as follows.

• Draw a random function g from [n] → [r].

• Draw a random injective function h from [r] → [n].

• Output the composition h • g.

Notice that any function f drawn from D r is of small range and satisfies |Im(f )| ≤ r. Let also D perm be the uniform distribution on permutations on [n]. Zhandry's lower bound can be stated as follows:

Proposition 1 ([Zha15]

). There exists an absolute constant Λ such that for any r ∈ [n] and any quantum query algorithm B O performing at most Λr1/3 queries to O:

∀b ∈ {0, 1}, E π←Dperm Pr[B Oπ outputs b] -E C←Dr Pr[B O C outputs b] ≤ 2 27 .
This is obtained immediately by combining Theorem 8 and Lemma 1 of [Zha15] 1 .

Proving our main theorem

The goal of this section is to prove Theorem 2. Fix a function f : S → {0, 1} where S ⊆ [M ] n with Q(f ) = q. This means there exists a quantum query algorithm A O performing q queries to O such that ∀x ∈ S, Pr[A Ox outputs f (x)] ≥ 2/3.

We first amplify the success probability to 20/27.

Lemma 1. There exists a quantum query algorithm A O 3 that performs 3q queries to

O such that ∀x ∈ S, Pr[A Ox 3 outputs f (x)] ≥ 20 27 .
Proof. A O 3 will consist of the following: run A O independently 3 times and take the output that occurs the most. For each x, each run of A Ox outputs f (x) with probability at least 2/3. The probability that the correct f (x) appears at least twice out of the 3 results is therefore greater than 8 27 + 3 • 4 27 = 20 27 .

Using the fact that f is permutation symmetric, we get the following corrolary:

Corollary 1. ∀x ∈ S, ∀π ∈ S n , Pr[A Ox•π 3 outputs f (x)] = Pr[A Ox•π 3 outputs f (x • π)] ≥ 20 27 .

Looking at a small number of indices of x

The main idea of the proof is to show that A 3 will output f (x) with high probability when replacing queries to O x with queries to O x•C for C chosen uniformly from D r for some r = Θ(Q 3 (f )). First notice that for any x : [n] → [M ] and any g : [n] → [n], it is possible to apply O x•g with 2 calls to O g and 1 call to O x with the following procedure:

|i |j |0 → |i |j |g(i) → |i |j + (x • g)(i) |g(i) → |i |j + (x • g)(i) |0
where we respectively apply O g on registers (1, 3) ; O x on registers (3, 2) and O † g on registers (1, 3).

Therefore, for any fixed (and known) x, for any function g :

[n] → [n],
we can look at A Ox•g 3 as a quantum query algorithm that queries O g . In other words, for each x ∈ S, there is a quantum query algorithm B O

x such that B Og x = A Ox•g for any function g : [n] → [n]. Notice also that since a query to O x•g is done by doing 2 queries to O g , we have that B O uses twice as many queries than A O 3 . We can now prove our main proposition that shows that we can compute f (x) by looking only at x • C meaning that we only need to look at Im(C) ≤ r random.

Proposition 2. Let f : [M ] n → {0, 1} with Q(f ) = q and r = 216q 3 Λ -3 where Λ is the absolute constant from Proposition 1.

∀x ∈ S, E C←Dr Pr[A O x•C 3 outputs f (x)] ≥ 2/3.
Proof. For each x ∈ S, we consider the algorithm B O

x described above. Recall that for all g :

[n] → [n], B Og x = A Ox•g 3 . Since A O
3 uses 3q queries, B O x uses 6q queries. We first consider the case where g is a random permutation. Using Corollary 1:

∀x ∈ S, E π←Dperm Pr[B Oπ x outputs 0] = E π←Dperm Pr[A Ox•π 3 outputs f (x)] ≥ 20 27
Using the lower bound of Proposition 1 noticing that 6q ≤ Λr 1/3 , we have

∀x ∈ S, E π←Dperm Pr[B Oπ x outputs f (x)] -E C←Dr Pr[B O C x outputs f (x)] ≤ 2 27 . which gives us ∀x ∈ S, E C←Dr Pr[B O C x outputs f (x)] ≥ 20 27 - 2 27 = 2/3. Since for each x ∈ S, B O C x = A x•C 3 , we can therefore conclude ∀x ∈ S, E C←Dr Pr[A O x•C 3 outputs f (x)] ≥ 2/3.

Constructing a classical query algorithm for f

We can now use the above proposition to prove our main theorem.

Theorem 2 (Restated). For any permutation invariant function f of the first type,

R(f ) ≤ O(Q 3 (f )).
Proof. Fix a function f : S → {0, 1} where S ⊆ [M ] n with Q(f ) = q. This means there exists a quantum query algorithm A O performing q queries to O such that

∀x ∈ S, Pr[A Ox outputs f (x)] ≥ 2/3.
We construct a randomized algorithm that performs r = 216q 3 Λ -3 classical queries to O Classical Step 4 outputs the same output distribution than the quantum algorithm A O x•C 3 . Using Proposition 2, for all x ∈ S, this algorithm outputs, f (x) with probability greater than 2/3, which implies

R(f ) ≤ r = 216Q 3 (f )Λ -3 .
Notice that after step 2, it is not possible to just compute f (x • C), and try to show that it is equal to f (x) since we don't even always have x • C ∈ S. This is yet another example in query complexity where we use the behavior of a query algorithm on inputs not necessarily in the domain of f .

  O x with calls to O x•C gives us output f (x) with high probability. Knowing C, we can construct the whole string x • C by querying x on inputs i ∈ Im(C) which can be done with Im(C) ≤ r classical queries which allows us to construct the unitary O x•C . This means we can emulate A on input x • C with r classical queries to x and this gives us f (x) with high probability.

x as follows: 1 .

 1 Choose a random C according to distribution D r . 2. Query O Classical x to get all values x i for i ∈ Im(C). This requires |Im(C)| ≤ r queries to O Classical x . These queries fully characterize the function x • C, hence the quantum unitary O x•C . 3. From A O , construct the quantum algorithm A O 3 as in Lemma 1. Recall that A O 3 just consists of applying A O independently 3 times and output the majority outcome. 4. We consider A O x•C 3 as a quantum unitary circuit acting on t qubits. At each step of the algorithm, we store the 2 t amplitudes. When O x•C is called, we use its representation from step 2 to calculate its action on the 2 t amplitudes. Other parts of A O x•C 3 are treated the same way. While this uses a lot of computing power, it does not require any queries to O Classical x or O x other than those used at step 2.

Equivalently, this is obtained immediately by combining Lemma 3.2 and Lemma 3.4 from the arXiv version quant-ph:1312.1027.