text:
Michal Tabach

Chris Rasmussen
email: crasmussen@mail.sdsu.edu

Tommy Dreyfus
email: tommyd@post.tau.ac.il

Rina Hershkowitz
email: rina.hershkowitz@weizmann.ac.il

Abstraction in Context and Documenting Collective Activity

Keywords: Methodology, theories coordination, individual cognition, collective meaning making

In this report we advance the methodological and theoretical networking for documenting individual and collective mathematical progress. In particular, we draw together two approaches, Abstraction in Context (AiC) and Documenting Collective Activity (DCA). The coordination of these two approaches builds on prior analysis of grade 8 students working on probability problems to highlight the compatibility among the epistemic actions that ground each approach and drive the respective methodologies. The significance of this work lies in its contribution to coordinating what might otherwise be viewed as separate and distinct methodologies.

Background

In this report we advance the methodological and theoretical networking [START_REF] Bikner-Ahsbahs | Networking of theories as a research practice in mathematics education[END_REF] of two different approaches, the Abstraction in Context (AiC) approach with the RBC+C model commonly used for the analysis of knowledge construction by individuals or small groups; and the Documenting Collective Activity (DCA) approach with its methodology commonly used for establishing normative ways of reasoning in classrooms. In previous work related to this goal (Hershkowitz, Tabach, Rasmussen, & Dreyfus, 2014;Tabach, Hershkowitz, Rasmussen, & Dreyfus, 2014) we demonstrated how this coordination can illuminate the processes by which ideas shift from individuals and small group to the classroom community as a whole or vice versa. This combination revealed that some students functioned as "knowledge agents," meaning that they were active in shifts of knowledge among individuals in a small group, or from one group to another, or from their group to the whole class or within the whole class.

We take the coordination between AiC and DCA a step further by explicating theoretical and methodological commonalities between the two approaches. These commonalities, which we first pointed to at CERME9 [START_REF] Tabach | First steps in re-inventing Euler's method: A case for coordinating methodologies[END_REF], drives further the integration of the two approaches, including what we refer to as environmental, underlying, and internal commonalities. The analysis in the present case led us to enhance the theoretical commonalities with data driven ones. We explicate these commonalities to set the stage for the analysis of students' work, but first begin with a brief summary of the AiC and DCA approaches.

Abstraction in Context and the RBC+C model

Abstraction in Context (AiC) is a theoretical framework for investigating processes of constructing and consolidating abstract mathematical knowledge [START_REF] Hershkowitz | Abstraction in Context: Epistemic Actions[END_REF]. Abstraction is defined as an activity of vertically reorganizing previous mathematical constructs within mathematics and by mathematical means, interweaving them into a single process of Thematic Working Group 17 Proceedings of CERME10 mathematical thinking so as to lead to a construct that is new to the learner. According to AiC, the genesis of an abstraction passes through three stages (ibid): (i) the arising of the need for a new construct, (ii) the emergence of the new construct, and (iii) the consolidation of that construct. AiC includes a theoretical/methodological model, according to which the description and analysis of the emergence of a new construct and its consolidation relies on a limited number of epistemic actions: Recognizing, Building-with, Constructing, and Consolidating (RBC+C).

These epistemic actions are often observable as they are expressed by learners verbally, graphically, or otherwise. Recognizing takes place when the learner recognizes a specific previous knowledge construct as relevant to the current problem. Building-with is an action comprising the combination of recognized constructs in order to achieve a localized goal, such as the solution of a problem or the justification of a claim. The model suggests Constructing as the central epistemic action of mathematical abstraction. Constructing consists of assembling and interweaving previous constructs by vertical mathematization to produce a new construct. It refers to the first time the new construct is expressed by the learner. Recognizing actions are nested within building-with actions, and recognizing and building-with actions are nested within constructing actions. Therefore, the model is called the nested epistemic actions model of abstraction in context, or simply the RBC+C model. The second "C" stands for Consolidation. The consolidation of a new construct is evidenced by students' ability to progressively recognize its relevance more readily and to use it more flexibly in further activity.

Documenting Collective Activity

The methodological approach of documenting collective activity (DCA) is theoretically grounded in the emergent perspective (Cobb & Yackel, 1996), a basic premise of which is that mathematical progress is both an individual constructive process and a process of enculturation into the emerging norms and practices of the local classroom community. That is, the personal and collective mathematical progress can be seen as two sides of the same coin. Collective activity of a class refers to the normative ways of reasoning that develop as students work together to solve problems, explain their thinking, represent their ideas, etc. These normative ways of reasoning can be used to describe the mathematical activity of a group and may or may not be appropriate descriptions of the characteristics of each individual student in the group. A mathematical idea or way of reasoning becomes normative when there is empirical evidence that it functions in the classroom as if it is shared. The empirical approach makes use of Toulmin's model of argumentation (1958), the core of which consists of Data, Claim, and Warrant. Typically, the data consist of facts or procedures that lead to the conclusion that is made. To further improve the strength of the argument, speakers often provide more clarification that connects the data to the claim, which serves as a warrant. It is not uncommon, however, for Rebuttals or Qualifiers to arise once a claim, data, and warrant have been presented. Backing provides further support for the core of the argument.

The following three criteria are used to determine when a way of reasoning becomes normative: 1) When the backing and/or warrants for particular claim are initially present but then drop off, 2) When certain parts of an argument (the warrant, claim, data, or backing) shift position within subsequent arguments, or 3) When a particular idea is repeatedly used as either data or warrant for different claims across multiple days [START_REF] Cole | Adapting a Methodology from Mathematics Education Research to Chemistry Education Research: Documenting Collective Activity[END_REF][START_REF] Rasmussen | A methodology for documenting collective activity[END_REF].

Environmental commonalities

The use of both methodologies, RBC+C and DCA, requires quite specific classroom social norms (Yackel & Cobb, 1996). First, they require classrooms in which students routinely explain their thinking, listen to and indicate agreement or disagreement with each other's reasoning, etc. If such norms are not in place, then evidence is unlikely to be found of challenges, rebuttals, and negotiations that lead to ideas where knowledge is constructed and starts functioning as if shared by the whole class. We call such classrooms "inquiry-oriented classrooms" [START_REF] Rasmussen | An inquiry oriented approach to undergraduate mathematics[END_REF]. Second, these classrooms require the intentional use of tasks designed to offer students opportunities for constructing new knowledge by engaging them in problem solving and reflective activities allowing for vertical mathematization. Both methodologies focus on the ways in which mathematical progress is achieved and spreads in the classroom. RBC+C focuses on individuals or small groups working in the classroom and DCA focuses on group or whole class discussions. In this sense, the two methodologies complement each other in analyzing a sequence of lessons including individual and group work and learning in whole class discussion and in tracing how knowledge is constructed and becomes normative.

Underlying commonalities

Other characteristics of a classroom culture in which DCA and RBC+C methodologies might be enacted together are that the tasks are designed to afford inquiry and the emergence of new constructs from previous constructs by vertical mathematization [START_REF] Treffers | Rational analysis of realistic mathematics educationthe Wiskobas program[END_REF]; such learning materials allow for interweaving collaborative work in both small-group work and wholeclass discussions, where the teacher adopts a role that encourages inquiry in the above sense. Another underlying characteristic relates to the centrality of the shared knowledge. RBC+C characterizes shared knowledge as a common basis of knowledge which allows the students to make further progress. We find its counterpart in sociological terms, in the phrase "function as if shared" used by the DCA approach. What is common between the two constructs is the point that each operationalizes when particular ideas or ways of reasoning are, from a researcher's viewpoint, beyond justification for participants. At the collective level, ideas or ways of reasoning that function as if shared have the status of accepted mathematical truths for the group. At the individual level, consolidation results in individuals accepting something as a mathematical truth.

Internal commonalities

DCA analysis helps illuminate what is happening on the social plane, while RBC+C analysis helps illuminate what is happening on the cognitive side. To elaborate, we highlight relationship between constructs suggested by the cognitive RBC+C analysis and their sociological counterparts suggested by the DCA analysis. We do that from a theoretical perspective and from an empirical perspective.

To achieve this goal we begin with the following excerpt 1, used also in [START_REF] Hershkowitz | Knowledge shifts in probability classroom -A case study[END_REF] but for different purposes. It is a discussion between Noa and Gil, two eighth grade students working on a probability problem (see turn 95) during a group work period taken from the third lesson on this topic, and a bit of whole class discussion. This excerpt includes a DCA analysis, in particular classification of the marked parts of students talk (shaded) according to Toulmin's model as data

[D], claim [C], warrant [W], backing [B], rebuttal [R] or qualifier [Q].
In addition, RBC+C actions were identified in students' talk (italic), and marked as recognizing (R), building-with (B), end of the constructing action (C) or consolidating (CC) with respect to two knowledge elements: Exp -experiment is needed in order to determine the chances and Exdexperiment detailed.

No.

Utterance

RBC+C and DCA analysis

We begin by relating elements of the RBC+C and DCA analyses to each other, and then we relate the three criteria of the DCA approach to consolidation.

Relationship between Recognizing and Data. Theoretically, we argue that Recognizing actions are largely associated with Data. One uses some piece of information as Data because that piece of information makes sense to him/her. That is, this piece of information is relevant for the person; it is what the person selects for use (as Data). In the above excerpt, we see that Recognizing actions are primarily associated with Data. In some cases (e.g., turn 103), Recognizing actions can be associated with Warrants. In carrying out the DCA analysis, disentangling Data and Warrant is at times non-trivial, in which cases Recognizing actions can be sensibly associated with Warrants.

Relationship between Building-with and Warrants. Theoretically, Warrants establish a connection between data and claim; in order to establish such a connection, one needs to build-with what one has recognized. In the above excerpt this commonality is largely the case with some exceptions that need clarification. In turns 95/96 we had claims associated with building-with. These are the first building-with actions of this excerpt and thus the first ones of the part where the students are working on the present task. As a consequence, the building-with actions are somewhat shallow and make only claims without really warranting them. As such, this example does not pose a substantive threat to the theoretical conjecture. Similarly, turns 114 -116 and 139 do not pose a substantive threat to the conjecture. These are the final utterances belonging to a constructing action; as such, they complete the constructing by explicitly stating the claim that was constructed. As we noted above, at times data and warrant are difficult to disentangle with certainty, hence building-with can be associated with data. Empirically, this is the case for turns 114 and 115.

The relationship between Constructing and Arguments as a whole. Constructing requires vertical mathematization. Constructing actions are usually much more extended than Recognizing or Building-with actions; they incorporate sequences of interweaving Recognizing and Building-with actions (plus the 'glue' between them). Similarly, arguments interweave data-claim-warrants and backings as a whole. Hence, in a line by line coding it is not feasible to indicate the holistic nature of an argument and it is typically indicated after a line by line coding (see for example Tabach et al., 2014). Moreover, arguments are usually co-constructed by several participants over several turns. Such interaction is also frequent in constructing actions.

Consolidating and the three criteria for identifying function-as-if-shared ideas. In consolidating actions as well as across the three DCA criteria for identifying when an idea functions as if shared, repetition, reuse, revisiting, or repurposing of earlier ideas frequently occurs. To clarify, in Criterion 1 there is a repetition, but the repetition is partial in the sense that some parts of the argument (Data, Warrants) cease to be explicitly stated. In Criterion 2 there is repurposing of previous part of an argument (e.g., Claim) as either Data or Warrant. In this sense there is a repeating and reusing, but for a different purpose. In Criterion 3 there is a revisiting of either Data or Warrants to establish new Claims. In consolidation, previous constructs are recognized as relevant (i.e., revisited), and then built-with, which means they are reused, often for a new purpose such as a new constructing action. Hence there are strong parallels between consolidation and the three DCA criteria. For example, in 151, DCA analysis shows that W10 (the warrant for Claim 10) turns into D11 (i.e. the data for Claim 11); hence Criterion 2 is satisfied: the same part of the argument is reused with a different function. RBC+C analysis shows that knowledge construct xd is consolidated by being used again, and at the same time elaborated.

Further commonalities between consolidating and the DCA criteria can be seen by considering the characteristics of consolidation: awareness, self-evidence, flexibility, immediacy, and confidence [START_REF] Dreyfus | Ben's consolidation of knowledge structures about infinite sets[END_REF]. Self-evidence links to Criterion 1 because the evidence is the Data, which drops off in subsequent arguments. The subsequent argument also then relates to immediacy and confidence in the validity of the idea. Flexibility links to Criterion 2 because components of an argument are being reused and repurposed (as sign of flexibility) in subsequent arguments.

Similarly, Criterion 3 relates to flexibility, but in a different way. Here the flexibility lies in the fact that one is able to use an idea (e.g, Build-with) as Data or Warrant for a variety of different Claims.

Hence close relationships exist between the criteria and characteristics of consolidation.

We conclude this report by returning to vertical mathematization, which was highlighted as an Environmental commonality. We also see vertical mathematization as an Internal commonality. Both methodologies work from the premise that vertical mathematization is core to mathematical progress. In the RBC+C approach, consolidation is vertical mathematization and, as we argued above, the consolidation is closely linked to the three criteria.

Conclusion

We now turn to discussing some implications for research. In addition to offering a theoretically and empirically grounded approach for coordinating methodologies for individual and collective mathematical progress, there exist specific ways in which this coordination can play out. For example, one could choose an individual student within the classroom community and trace their constructing actions for the ways in which they contributed to the emergence of various normative ways of reasoning. Alternatively, when considering a normative way of reasoning, a researcher could investigate who the various individual students are that are offering the claims, data, warrants, and backing in the Toulmin analysis used to document normative ways of reasoning. How do those contributions coordinate with individual student constructions? For instance, does a student ever utilize an utterance that a different student authored as data for a new claim that they are authoring, and in what ways may that capture or be distinct from other students' individual mathematical meanings? Future research could take up more directly the role of the teacher in relation to individual and collective level mathematical progress. More generally, however, this report contributes to an emerging discourse on theories and ways in which different theoretical approaches can be profitably networked (e.g. Bikner-Ahsbahs & Prediger, 2014).

Table 1 : Excerpt 1, Transcript from the class

 1

	[DCA analysis]

R 100 Noa Right, so you take many boxes, how many, if, in the box [W1]… B 101 Gil Noa, it depends on how long you have been using the box, if you used it once then maybe it will be less … [Q1] B 102 Noa No! If it's defective! You have to take many boxes [D1] and see in each one if there is … if there are let's say 50 matches in each box and 1 is defective so it says on the box 1 out of 50 [W1], so you have to experiment! [C1, referring back to turn 95] B 103 Gil So it's 1 per the number of matches in each box [W2]. B 115 Noa No, wait! How many matches does the box contain, and see how many defective matches are in it [D4]… [Dictate together]. 141 Gil And inside you have to [check]. B 142 Noa [you need to take some] matchboxes [D11], you need to see how many matches are in each box, and how many of them are defective [W11]. 1 From this point on it is Gil who does the B and C actions

Proceedings of CERME10

Acknowledgment

This study was partially supported by the Israel Science Foundation (Grants No. 1057/12; 438/15).


Nicolas Ruty
email: nicolas.ruty@icp.inpg.fr

Annemie Van Hirtum

Xavier Pelorson
email: xavier.pelorson@icp.inpg.fr

Avraham Hirschberg
email: a.hirschberg@tue.nl

Ines Lopez
email: i.lopez@tue.nl

A preliminary study of asymmetric vocal fold vibrations: modeling and "in-vitro" validation

This paper deals with some of aspects of the influence of asymmetry on vocal folds vibrations. A theoretical model of vocal fold asymmetry is presented. The influence of asymmetry is quantitatively examined in terms of oscillation frequency and pressure threshold. The theoretical model is compared to "in-vitro" experiment on a deformable replica of vocal folds. It is found that asymmetry strongly influences the oscillation subglottal pressure threshold. Moreover, the vocal fold with the highest mechanical resonance frequency imposes the oscillation fundamental frequency. The influence of geometrical asymmetry instead of purely mechanical asymmetry is shown.

'

Introduction

Voiced sound production can be disturbed in case of vocal fold pathology. A consequence of pathologies is commonly irregular or asymmetric vibrations of the vocal folds. Voice quality is altered and voiced sounds are difficult to produce. In term of voice quality, additional in-vivo evidence is presented by [START_REF] Mergell | Irregular vocal-fold vibration -High-speed observation and modeling[END_REF], using high-speed imaging of the vocal fold during oscillations. The use of an asymmetry factor to quantify the influence of asymmetry between the two vocal fold has been proposed by [START_REF] Steinecke | Bifurcations in an asymmetric vocal-fold model[END_REF]. A more global approach has been proposed by [START_REF] Schwarz | Modeling asymmetric vocal fold vibrations[END_REF], taking into account not only the asymmetry factor Q but also other parameters like the subglottal pressure Ps. Then using an inversion procedure, it was proposed to quantify all the parameters of a modified two mass model. In this paper, we propose an asymmetric model of the vocal folds, based on a modification of the two mass model described by [START_REF] Lous | A symmetrical two mass vocal-fold model coupled to vocal tract and trachea with application to prosthesis design[END_REF]. To test its validity and to quantify the effects of asymmetry, an experimental set-up based on an asymmetric deformable replica of the vocal folds is used.

Theoretical modeling

The model used is derived from the symmetrical two-mass vocal fold model introduced by [START_REF] Lous | A symmetrical two mass vocal-fold model coupled to vocal tract and trachea with application to prosthesis design[END_REF]. Two symmetrical coupled oscillators represent each vocal fold. Each oscillator is defined by the following parameters: m/2 is the mass (m is the mass of a vocal fold), k is the spring stiffness, k c is the coupling spring stiffness, and r is the damping. In each vocal fold, the set of parameters can be different. Consequently, the model of vocal fold can be asymmetric (e.g.: figure 1).

Figure 1.

An asymmetric two-mass model of vocal folds. P sub is the subglottal pressure. P supra is the supraglottal pressure. L g is the glottal width. d is the length of glottis. A 1 , A 2 , A s are the cross-sectional areas (masses, airflow separation point). y l1 , y l2 , y r1 , y r2 are the vertical positions of the masses. k l and k r are the spring stiffnesses. k cl and k cr are the coupling spring stiffnesses. r l and r r are the damping constants.

As a result, there are two mechanical equations for each vocal fold: (1) where m i is the vibrating mass of a vocal fold (i={l,r}), y i1 and y i2 are the displacement of each mass compared to the axis of symmetry of the glottis, y i10 and y i20 are the rest position of each mass, F i1 and F i2 are the external pressure.

       + ∂ ∂ - + - - - - - = ∂ ∂ + ∂ ∂ - + - - - - - = ∂ ∂ 2 2 10 1 20 2 20 2 2 2 1 1 20 2 10 1 10 1 2 1 2 ) ( ) ) ( ) ( ( ) ) ( ( ) ( 2 ) ( ) ) ( ) ( ( ) ) ( ( ) ( 2 i i i i i i i ci i i i i i i i i i i i i ci i i i i i F t t y
The asymmetry of this mechanical model is commonly expressed by the parameter Q, used for example by Steinecke and Herzel (1993) or [START_REF] Mergell | Irregular vocal-fold vibration -High-speed observation and modeling[END_REF]:

Q m m Qk k l r l r / = = (2)
One can also take into account the asymmetry of coupling stiffness with a parameter Q c =k r /k l [START_REF] Schwarz | Modeling asymmetric vocal fold vibrations[END_REF], and the geometrical asymmetry of rest position vocal fold.

This mechanical model is coupled to an airflow description. Through the glottis geometry (figure 1), the airflow is modeled by a Poiseuille flow and a moving separation point is assumed (ad-hoc criterion). Thus, one can write the pressure distribution through the glottis (3) and the volume flow velocity (4):

∫ +         = - x x g g g sub t x A dx U L t x A U t x P P 0 ) , ( 12 ) , ( 1 2 1 ) , ( 3 2 2 2 µ ρ , if s x x < ra P t x P sup ) , ( = , if s x x > , (3)
( ) where P sub and P supra are the sub and supra glottal pressures, P(x,t) is the pressure distribution, ρ is the air density, U g is the volume flow velocity, µ is the viscosity coefficient, L g is the glottal width, A(x,t)= L g (y l (x,t)+ y r (x,t)) indicates the glottal crosssectional area, A s =1.2min(A(x,t)) is the cross-sectional area at the separation point x s .

            - +         + - = ∫ ∫ 2 2 sup 2 3 2 3 2 1 1 2 ) , ( 12
Due to the flow description, F i1 and F i2 depend on a lot of parameters

( { } { } ( ) supra sub r2 r1 l2 l1 1,2 j i, 1,2 j i, P , P , y , y , y , y F F ∈ ∈ =
). This system of four equations is mechanical asymmetric if the two vocal folds have different set of control parameters (spring stiffnesses, damping constant), and can be geometrical asymmetric (rest positions of each masses). This aeromechanical model is coupled with the vocal tract, which is assimilated to a single degree of freedom system. It is described by the following equation:

u Q Z t t t Q t t A A A A A A ω ψ ω ψ ω ψ = + ∂ ∂ + ∂ ∂ ) ( ) ( ) ( 2 2 2 (5)
where

p t t = ∂ ∂ ) ( ψ
, with p the acoustic pressure at the entrance of the vocal tract, ω A is a resonance pulsation, Q A is the quality factor of this resonance, Z A is the peak value of impedance at resonance ω A , u is the acoustic airflow velocity.

In this paper, the theoretical model is analyzed thanks to two relevant quantities in voiced-sound production: the phonation on-set pressure threshold (subglottal pressure to sustain oscillations) and the fundamental frequency of oscillations.

Experimental set-up

The aim of this study is to test the validity of the theoretical model. For reasons of control and reproducibility, a mechanical replica of the vocal folds is used. It consists in two metal pieces covered with latex (figure 2,[e]). These two pieces are encapsulated into a rigid structure (figure 2,[f]). Each vocal fold replica is filled with water, thanks to a water reservoir (figure 2 The pressure (internal pressure Pc of a vocal fold replica) of water influences the mechanical characteristics of the replica. For example, when the pressure is increased, by increasing the height of the water column, the replica is tensed. Moreover, the internal pressure can be imposed different for each vocal fold replica. Hence the replica is asymmetric. The replica is coupled to a pressure reservoir and to a downstream resonator of 17 cm length (figure 3) as described by [START_REF] Ruty | An in-vitro setup to test the relevance and the accuracy of low-order vocal folds models[END_REF]. The reservoir is fed by a compressor. The upstream pressure (up to 4000 Pa) is controlled by a Norgren regulator type 11-818-987. Thus, airflow can be forced through the vocal folds replica. Under certain conditions, self-sustained oscillations appear. The characteristics of the oscillations depend on the upstream pressure, on the internal pressure Pc of the two "vocal fold", and consequently on the asymmetry between the two "vocal folds". Several physical quantities can be measured on this experimental set-up. The movements of the replica are measured by way of an optical set-up. It is composed of a laser diode, three convergent lenses (f=100 mm and f=50 mm), and of a photodiode BPW34. Pressure measurements are performed by way of two pressure sensors (Kulite XCS-0.93-0.35-BAR-G). The first one, placed just before the replica, allows to measure the upstream pressure. The second is placed at the end of the downstream resonator. A measurement microphone Bruël and Kjaer is used to measure acoustic pressure at the end of the resonator.

Electrical signals from the sensors are filtered and amplified with a National Instruments SCXI 1121 board. This board is connected to the computer by way of a National Instruments BNC 2110 input/output card and a National Instruments PCI-6225 acquisition card.

For calibration of the sensors, one proceeds as following. The pressure sensors are calibrated using a manometer. The photodiode is calibrated using rectangular apertures with known dimensions of 0.01 mm precision. The measurement microphone is calibrated using a Bruël and Kjaer Sound Level Calibrator Type 4230, which produce a pure sinusoidal audio signal of 1000Hz frequency and 94dB amplitude.

Results and discussion

In this section, we examine the influence of vocal fold asymmetry on two relevant quantities for voiced sound production: the oscillation pressure threshold and the fundamental frequency of oscillations. A stability analysis is performed on the theoretical model. Then, mechanical parameters (masses, spring stiffness, and damping) are extracted from the frequency response of the deformable replica. Finally, experimental data and theoretical prediction are compared and discussed.

Stability Analysis

The theoretical model is examined around equilibrium. Each variable is considered as the sum of an equilibrium value and a fluctuation. For example 1) and ( 5) are written as following with (i={l,r}):

       ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ - - - - = ∂ ∂ ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ - - - - = ∂ ∂ p P F 1 2 ) ( 2 ) ( 2 (6)         ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ + ∂ ∂ = + ∂ ∂ + ∂ ∂ p P U y y U y y U y y U y y U Q Z t t t Q t t ra g r r g r r g l l g l l g A A A A A A sup ' 2 2 ' 1 1 ' 2 2 ' 1 1 2 2 2 ) ( ) ( ) ( ω ψ ω ψ ω ψ (7)
This system can be written using a state-space representation Mx x = .

where the statespace vector is

      ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ = t t y t y t y t y y y y y x r r l l r r l l ψ ψ 2 1 2 1 2 1 2 1 (8)
Then, for a given initial geometry and a set of mechanical and acoustical parameter, the subglottal pressure P sub is varied from 0 to 5000 Pa. For each subglottal pressure, the eigenvalues of the state-space matrix are calculated. The sign of the real part of the eigenvalues is analyzed. If the real part is positive, that involves the presence of oscillation. The fundamental frequency of the oscillation is determined by f0=Im(λ)/2π, where λ is an eigenvalue (Re(λ)>0). In some case, two or three eigenvalues have a positive real part. That involves the presence of more than one oscillation regime.

Extraction of the model parameters

As described in [START_REF] Ruty | An in-vitro setup to test the relevance and the accuracy of low-order vocal folds models[END_REF], the link between empirical parameters and the model parameters has to be known. For some parameters, the relationship is evident (e.g. geometrical parameters L g , d, subglottal pressure P sub ). Other parameters (spring stiffness, damping constant, and masses) need to be estimated.

The estimation is made using the experimental set-up described in section 3. For a given internal pressure, the frequency response is measured as described by [START_REF] Ruty | A mechanical experimental setup to simulate vocal folds vibrations[END_REF]. The parameters k and r are obtained using the following relationship:

r m Q m k 2 , 2 0 0 0 ω ω = = (9)
where ω 0 is a resonance pulsation and Q 0 is the quality factor of the resonance.

The mass is estimated with the relationship:

0 2 0 0 Z dQ L m g ω = (10)
where Z 0 is the amplitude of the measured resonance peak.

The coupling spring stiffness is obtained using another resonance of the frequency response (ω 1 > ω 0 ):

        -         = = 1 2 1 , 2 0 1 ω ω α α with k k c (11)

Comparison between experimental data and theoretical prediction

Using the experimental set-up described in section 3, the influence of asymmetry is analyzed. An internal pressure of 4000 Pa in the left vocal fold replica is imposed. Internal pressure of the right vocal fold replica is varied from 1500 Pa to 3000 Pa by step of 500 Pa, and from 3000 Pa to 7500 Pa by step of 250 Pa. For each internal pressure in the right vocal replica, the same protocol is followed. The frequency response of the replica is measured and the corresponding mechanical parameters are obtained. Then, the upstream pressure is increased up to 5000 Pa. Different oscillation regimes appear as the upstream pressure increases. The measured on-set pressure thresholds and the fundamental frequencies of these oscillation regimes are recapitulated and compared with the theoretical predictions in figure 4.

Discussion

Concerning the pressure threshold and oscillation fundamental frequency, one can note that the influence of asymmetry is strong. Hence, the experimental pressure thresholds are increased when Q is not close to 1. This increase is different according to whether Q is higher or lower than 1. When Q>1, the pressure increase is clear and seems to be the consequence of the higher internal pressure in the right vocal fold. When Q<1, oscillations seem to be 'controlled' by the left vocal fold replica, of which internal pressure is higher. Theoretical predictions are qualitatively in agreement with the experimental data. When Q>1, the predicted thresholds increase, but quantitatively more than in experimental data. When Q<1, two oscillation regimes are predicted by the theoretical model. The frequency F 0 of each regime corresponds to the mechanical resonance frequency of a vocal fold replica (left or right), as see figure 4b. When Q>1, only one regime remains. Its frequency is close to the mechanical resonance of the right vocal fold. Experimentally, the same phenomenon is observed, the frequency of oscillations is close to highest mechanical resonance between the two replicas.

Finally, one can note that the influence of asymmetry is different depending on the factor Q, more precisely if Q<1 or Q>1. Indeed, we have deliberately chosen to define Q=f right /f left while [START_REF] Steinecke | Bifurcations in an asymmetric vocal-fold model[END_REF] have chosen to define Q as the ratio of the lower and higher frequency (Q=f low /f high ). The reason of our choice is that in our case, the values of Q correspond to an internal pressure of the vocal fold replica. The variation of internal pressure influences not only the mechanical resonance frequency, but also the initial aperture. As shown by [START_REF] Van Hirtum | Experimental validation of some issues in lip and vocal fold physical models[END_REF] initial condition has an influence on oscillations. That's why one needs to take into account not only mechanical asymmetry but also geometrical asymmetry, or more precisely the asymmetry of the rest position of each vocal fold.

Conclusion

An asymmetric model of the vocal folds has been proposed. Asymmetry is taken into account using the asymmetry factor Q, but in addition using all the mechanical and geometrical parameters. The theoretical model is compared to experimental data obtained with an asymmetric vocal fold replica. Comparison between theoretical prediction and experimental data leads to the following conclusions:

-Asymmetry increases the oscillation pressure threshold. The increase depends on the factor Q, but also on the initial geometry.

-Experimentally, fundamental frequency of oscillations is close to the highest mechanical resonance frequency between the vocal fold replicas.

Theoretically, this result is well predicted when Q>1, whereas for Q<1 two oscillation regimes are predicted corresponding to the mechanical resonance of each vocal fold.

-The single asymmetry factor Q cannot explain the complexity of asymmetry.

One needs to take into account all the mechanical and geometrical parameters.

  , [g] and [h]).

Figure 2 .

 2 Figure 2. Deformable replica of the vocal folds made of metal, covered with latex, and filled with water. [a] screw (hollowed out) for water supply. [b] rigid part of a vocal fold replica. [c] deformable part of a replica, made of latex. [d] channel for water supply. [e] a vocal fold replica (rigid part + deformable part). [f] rigid structure maintaining the two vocal fold replicas. [g], [h] reservoir for the control of water pressure in each vocal fold replica.

Figure 3 .

 3 Figure 3. Experimental set-up producing flow induced vibration of the vocal fold replica. [a] vocal fold replica. [b] pressure reservoir. [c] downstream resonator of 17 cm length. [d], [d'] water reservoirs controlling internal pressure of each vocal fold replica. [e] air supply. [f] laser diode, optical lenses to increases the laser beam width. [g] photodiode, optical lens to focalize the beam on the sensor. [h] pressure sensors. [i] National Instruments amplifier SCXI-1121

  fluctuation. Thus, equations (

Figure 4 .

 4 Figure 4. Comparison between experimental data and theoretical predictions. [a] oscillation pressure thresholds are plotted as a function of the asymmetry factor Q=f right /f left , where f right and f left are the measured resonance frequencies of each vocal fold replica. [b] experimental and predicted frequency of oscillation as a function of the asymmetry factor Q. Full lines in blue and red indicate the mechanical resonance frequencies of each vocal fold replica (blue=left, red=right). [c] Internal pressure in the left vocal fold replica as a function of the asymmetry factor.


Majid Heidari
email: majidheidari.ie@gmail.com

Mohammad Javad Jafari

Misagh Rahbari

Modeling a Multi-Objective Location-Routing Problem for Hazardous Materials with CO2 Emissions Consideration

Keywords: Location routing problem, Green supply chain, Mixed-integer linear programming, Hazardous materials;

This paper addresses a multi-period, multi-vehicle, location routing problem (LRP) where capacitated vehicles distribute hazardous materials from multiple plants to multiple retailers to meet the given demand of hazardous materials. Also, the risk of location and routing, cost of transporting hazardous materials from plants to retailers is considered. A series of middle nodes is considered which if needed to reduce the risk and costs, use them. CO2 emissions from transport activities in a supply chain are key players in global warming. Routing decisions can help in the reduction of CO2 emissions if these emissions are taken into account by the decision makers. The proposed framework is a multi-objective deterministic programming model. The first objective function aims to minimize the expected value of the supply chain costs including CO2 emissions produced by the vehicles. The second objective function aims to minimize the total risk of establishing plants and risk of transportation. The demands associated with retailers is assumed to be time varying and deterministic. The proposed model is a mixed-integer linear program that was coded and solved in GAMS. We provide a numerical study showing the applicability of the model.

Introduction

With the rising of global warming concerns and environmental issues, many governments and researchers have begun to pay close attention to green logistics. Despite the fact that the concept of "green logistics" has recently attracted the attention of the researchers, few studies have addressed the environmental concerns in their LRP model [START_REF] Toro | A multi-objective model for the green capacitated location-routing problem considering environmental impact[END_REF]. There are few studies in this category [START_REF] Yu | A simulated annealing heuristic for the capacitated location routing problem[END_REF] under which a set of plants serve a set of retailers. Some studies on supply chain have considered CO2 emission [START_REF] Alkawaleet | Inventory routing problem with CO2 emissions consideration[END_REF][START_REF] Soysal | Modeling a green inventory routing problem for perishable products with horizontal collaboration[END_REF]. They considered CO2 emissions in the inventory-routing problem (IRP). Due to the increasing environmental concerns, the problems of locating the plants which produce hazardous materials and the transportation of these materials have become the focus of many researchers [START_REF] Ardjmand | Applying genetic algorithm to a new location and routing model of hazardous materials[END_REF]. Although, some studies on LRP have been devoted to distribute hazardous materials [START_REF] Samanlioglu | A multi-objective mathematical model for the industrial hazardous waste location routing problem[END_REF][START_REF] Ardjmand | Applying genetic algorithm to a new location and routing model of hazardous materials[END_REF] but none of these none-traditional approaches has not applied the CO2 emissions to elaborate the inherent conflict between economic aspects and environmental concerns in LRP decisions. In hazardous materials location and routing problems, in addition to cost, the risk of locating a facility should also be considered [START_REF] Ardjmand | Applying genetic algorithm to a new location and routing model of hazardous materials[END_REF]. Our problem is also classified as a many-to-many structure. The aim of this study is to present a green model of multi-period location routing problem (LRP) where capacitated vehicles distribute hazardous materials from multiple plants to multiple retailers. The proposed model can help in the reduction of CO2 emissions and risk level.

Model definition

The location routing problem (LRP) can be stated as follows: Given a set of retailers with known demand, a set of potential plants, determine the location of the plants and the vehicle routes from the plants to the retailers to minimize the sum of the costs associated with locating plants, distribution to the retailers, vehicles' fixed and CO2 emissions costs. On the other hand, determine the location of the plants and the vehicle routes taking into account the risk generated to minimize the sum of the risks associated with locating plants and distribution hazardous materials to the retailers. Each retailer is assigned to just one plant which will dispatch a vehicle to fulfil its demand. Plants have several types of vehicles, each one is characterized by its own capacity, fixed and variable transportation cost rate and its CO2 emission index. Hazardous materials distribute from plants to retailers and if the risk of the route between them exceeds the allowed level, they use a series of middle nodes to distribute hazardous materials. The notations and mathematical formulation are as follows:

Sets: {1,2,...., } fF  Set of all plants {1, 2,...., } rR  Set of all retailers {1,2,...., } nN  Set of all middle nodes f r n     Set of all nodes {1,2,....., } kK 
Set of all vehicles {1, 2,....., } tT 

Set of time periods

Parameters:

i CF  The cost of opening the plant i i RF  The risk of opening the plant i t RL  Allowed level of risk generated in each period ijt RS  Risk amount between node i and j in each period ( ,

) ij   t GHL  Allowed level of CO2 emission in each period k GHG  CO2 emission by vehicle type k per unit distance P  Price of CO2 per unit mass k Q  Capacity of vehicle k ij c  Distance between node i and j ( , ) ij   k v  Variable transportation cost per unit distance for vehicle type k k u  Fixed transportation cost for vehicle type k per trip jt D  Demand of retailer j in each period i E  Maximum throughput at plant i MA  A big number

Decision variables:

ijkt X  A binary variable that determines if arc (i, j) is visited by vehicle type k in period t ( , ) ij   ijt Z  A binary variable that determines if retailer j is allocated to plant i in period t i Y  A binary variable that determines if plant i is opened ikt W  A binary variable that determines if node i is visited by vehicle type k in period t () i   it M  Auxiliary variable for sub-tour elimination constraints in period t Mathematical model:

  1 1 1 1 1| 1 1 1 1| 1 1 1 1| 1 1 2 1 1 1| 1 1 min min F K T F K T K T i i k ij ijkt k ijkt k ij ijkt i i j i j k t i j i j k t i j i j k t F K T i i ijt ijkt i i j i j k t z CFY v c X u X P GHG c X z RFY RS X                                                        s.t:   2 1| 1 K ijkt i j i j k XY       , i f t    3 1| 1| ijkt jikt ikt j i j j i j X X W        ,, i n k t    4 1 1| R jt ijkt k i j i j D X Q       , kt    5 1 R jt ijt i i j D Z E Y    , i f t    6 1| 1 1 K ijkt i i j k X       , j r t    7 1 1 F ijt i Z    , j r t    8 1 1
(1 )

K jt it ijkt k M M MA X       , , , i j t i j       9 1 1| 1 K k ij ijkt t i j i j k GHG c X GHL          t    10 1 1| 1 K ijt ijkt t i j i j k RS X RL          t    11 1| , ( ) 1 ibkt bjkt ijt b b i j X X Z       , , , i f j r k t      12 0 ijkt X  , , , i j f k t    13 0 ijkt X  , , , i j r k t    14 , , , {0,1} 0 i ijkt ijt ikt it Y X Z W M   ( , ) , , i j k t  
The first part of the objective function (1) represents the minimization of the sum of plant opening cost, transportation cost, vehicles' fixed cost and CO2 emissions cost. The second part of the objective function (1) represents the minimization of the sum of risk of plant opening risk and transportation risk. Constraint (2) ensure that if the plant is opened, be sure to move the vehicle. Flow conservation constraints are expressed in Constraints (3). Constraint (4) guarantees that the vehicle's capacity should not be exceeded. Constraint [START_REF] Ardjmand | Applying genetic algorithm to a new location and routing model of hazardous materials[END_REF] guarantees that if plant opened, the plant's throughput should not be exceeded. Constraints [START_REF] Soysal | Modeling a green inventory routing problem for perishable products with horizontal collaboration[END_REF] ensure that each retailer belongs to exactly one route. Constraints (7) ensure that each retailer is assigned to just one plant. Constraints (8) are sub-tour elimination constraints. Constraint (9) ensures that the total amount of CO2 emissions does not exceed a certain emission capacity. Constraint (10) ensures that the total amount of risk generated does not exceed a certain emission capacity. Constraints (11) specify that a retailer can be assigned to a plant only if there is a route from that plant going through that retailer. Constraints ( 12) and (13) determine the impossible arcs. Finally, Constraint (14) defines the variable types.

Experimental result

In this section we solve a small-scale example to help understand the model. Retailer's demand is deterministic and the planning time horizon is assumed to be 3 periods. Suppose 3 plants, 2 middle nodes, 2 retailers and 3 vehicles are present. First, we want to identify the open plants then we want to determine the best route for allocation to retailers and in the end we want to determine the used vehicles. The travel distances are provided in Table 1. The information on the capacity and cost rate for 3 vehicles are summarized in Table 2. Table 3, Table 4 and Table 5 show the risks amount between nodes per period. The average permitted risk generated levels among all periods is assumed to be 15. The average permitted CO2 emission levels among all periods is assumed to be 100. We also assume that the Price of CO2 per unit mass (equal to 2). Table 6 shows the information on the risk, opening cost and throughput of each plant. The proposed model is solved by GAMS 24.1.2. We used goal programming for solve this model. In Table 7, the decision variables are reported for the 3 periods. According to the results, it is clear that in some periods the route from the plant to the retailer is direct and, if necessary, middle nodes are used. Objective value for the first objective is 1119 and for the second objective is 327 also time of run is 0.23 second.

1 f 2 f 3 f 1 n 2 n 1 r 2 r 1 f 0 2 1 4 6 5 3 2 f 2 0 2 3 5 4 2 3 f 1 2 0 1 3 4 1 1 n 4 3 1 0 2 1 4 2 n 6 5 3

Table 7 -Vehicles rout

1 t 1 f 2 f 3 f 1 n 2 n 1 r 2 r 1 f 0 1 1 5 1 1 1 2 f 1 0 5 5 1 1 1 3 f 1 1 0 1 1 5 5 1 n 1 1 1 0 5 5 5 2 n 1 1 1 1 0 1 1 1 r 1 1 1 1 1 0 1 2 r 1 1 1 1 1 1 0 2 t 1 f 2 f 3 f 1 n 2 n 1 r 2 r 1 f 0 1 1 5 5 5 20 2 f 1 0 1 1 20 20 20 3 f 1 1 0 1 1 20 20 1 n 1 1 1 0 1 20 5 2 n 1 1 1 1 0 1 1 1 r 1 1 1 1 1 0 1 2 r 1 1 1 1 1 1 0 3 t 1 f 2 f 3 f 1 n 2 n 1 r 2 r 1 f 0 1 1 5 5 20 20 2 f 1 0 5 5 5 20 20 3 f 1 1 0 1 1 5 5 1 n 1 1 1 0 1 5 5 2 n 1 1 1 1 0 1 1 1 r 1 1 1 1 1 0 1 2 r 1 1 1 1 1 1 0 Plant type (f) i CF i RF i E 1 f 200 300 100 2 f 200 200 100 3 f 300 100 100
The path is traversed Used Vehicles Opened Plant Time period

Conclusion

Routing of vehicles and location of plants are two crucial operational decisions in logistics distribution management. The efficient routing of vehicles in a company's distribution network results in economic and, in most cases, in environmental benefits. In this study, a mathematical model was presented to address a multi-period, multi-vehicle location routing problem in a many-to-many supply chain network for distribution hazardous materials. Also in this study we followed two goals, reducing amount of risk and CO2 emissions. To validate and verify the proposed model we solve a small-scale example.

Table 1 -Travel distances Table 2 -Vehicle characteristics

 1

					2	0	2	2	Vehicle type (k)	v	k	u	k	Q	k	GHG	k
	1 r	5	4	4	1	2	0	2	1 2	16 14	20 22	400 450	5 5
	2 r	3	2	1	4	2	2	0	3	12	25	500	5

Table 3 -Risk amount between nodes in period 1 Table 4 -Risk amount between nodes in period 2Table 5 -Risk amount between nodes in period 3 Table 6 -Plant characteristics

 35


Nadim Kobeissi
email: nadim.kobeissi@inria.fr

Capsule: A Protocol for Secure Collaborative Document Editing

Keywords: collaborative document editing, secure document editing protocol, formal verification, proverif, privacy enhancing technology

Today's global society strongly relies on collaborative document editing, which plays an increasingly large role in sensitive workflows. While other collaborative venues, such as secure messaging, have seen secure protocols being standardized and widely implemented, the same cannot be said for collaborative document editing. Popular tools such as Google Docs, Microsoft Office365 and Etherpad are used to collaboratively write reports and other documents which are frequently sensitive and confidential, in spite of the server having the ability to read and modify text undetected. Capsule is the first formalized and formally verified protocol that addresses secure collaborative document editing. Capsule provides confidentiality and integrity on encrypted document data, while also guaranteeing the ephemeral identity of collaborators and preventing the server from adding new collaborators to the document. Capsule also, to an extent, prevents the server from serving different versions of the document being collaborated on. In this paper, we provide a full protocol description of Capsule. We also provide formal verification results on the Capsule protocol in the symbolic model. Finally, we present a full software implementation of Capsule, which includes a novel formally verified signing primitive implementation.

Introduction

Collaborative document editing software such as Google Docs and Microsoft Office365 has become indispensable in today's work environment. In spite of no confidentiality guarantees, large working groups still find themselves depending on these services even for drafting sensitive documents. Peer pressure, a rush to agree on a working solution and the sheer lack of alternatives have created an ecosystem where a majority of sensitive drafting is currently conducted with no end-to-end encryption guarantees whatsoever. Google and Microsoft servers have full access to all documents being collaborated upon and so do any parties with read access to the internal databases used by these services.

Capsule aims to solve this problem by being the first formally specified and formally verified protocol for secure collaborative document editing. Capsule comes with security goals that are validated in the symbolic model using the ProVerif [START_REF] Cheval | Proving more observational equivalences with ProVerif[END_REF] automated protocol verifier. It is also presented with a full client and server implementation, published as open source software.

We note that Capsule does not target the much simpler problem of encrypting cloud documents that are at rest, such as files stored on Google Drive on Microsoft OneDrive. Rather, the Capsule Protocol targets files being actively, collaboratively edited in real time.

Capsule's more involved use case scenario is responsible for providing a class of security guarantees vaguely resembling that of group secure messaging but without a need for forward secrecy. Another element that Capsule has to deal with is allowing the management of a document's incremental history with a server that cannot read the document's contents. This is accomplished by storing the document as an authenticated hash chain of encrypted, signed diffs: when a new participant joins a Capsule document, they pull the entire document hash chain, decrypting and parsing every diff until the entire document is reconstructed. Once within the document, each participant pushes and pulls encrypted diff blocks into this hash chain. Utilizing a hash chain is not only more efficient than more naïve approaches, but also makes it more difficult for the server to provide differing document histories to participants, without forking the hash chain entirely and with little payoff.

Capsule uses symmetric encryption to guarantee document confidentiality and integrity. Cryptographic signatures are used for authentication, although we employ only ephemeral authentication since identities are valid for the lifetime of the document. Symmetric primitives are also used for generating a proof value that disallows the server from adding non-existent participants to the document, in spite of these fake participants already being unable to access any document plaintext.

Security Goals

Capsule aims to guarantee the following security goals. In the following, a valid participant is any entity with access to the Capsule collaborative document's shared master secret. This master secret is generated upon document creation and is shared manually by the document creator in order to allow access to the document.

-Participant List Integrity. Only participants with access to the Capsule collaborative document's shared master secret may appear as valid entries on the participant list. Illegitimate entries injected by the server or any other parties must be detectable by valid participants. -Confidentiality. Any changes made to a collaborative document may only be viewed by valid participants. -Integrity. Encrypted diffs that are appended to the Capsule document's hash chain by a particular author cannot be tampered with by any other party.

-Ephemeral Authentication. The identity keys which are generated for the lifetime of the Capsule document session must successfully identify the participant that owns them and disallow impersonation. Public identity keys must benefit from Trust on First Use logic and be verifiable out-of-band. -Transcript Consistency. A malicious server cannot selectively omit changes to the collaborative document short of entirely forking the hash chain. Furthermore, in no scenario may a malicious server maliciously append changes to the collaborative document.

Threat Model

Capsule assumes the following threat model, which is fairly standard for protocols aiming to provide end-to-end security:

-Untrusted Network. We assume that an attacker controls the network and so can intercept, tamper with and inject network messages. -Malicious Server. We assume that a Capsule server may be potentially interested in misleading users with regards to the document's history and in the apparent list of identities participating in a collaborative document editing session.

Related Work

To the best of our knowledge, the only prior existing work regarding collaborative document encryption is CryptPad [START_REF]CryptPad: Zero Knowledge, Collaborative Real Time Editing[END_REF], an open source web client. CryptPad shares similarities with Capsule especially in that both use a hash chain of encrypted diffs in order to manage document collaboration and to reconstruct the document. However, CryptPad adopts a more relaxed threat model of an "honest but curious cloud server" and does not appear to guard against a server interfering with the document's list of participants or its history. Meanwhile, Capsule explicitly guards against a server injecting false participants by requiring a certain proof from all participants. CryptPad's software implementation is also limited within a web browser and unlike Capsule's, does not employ formally verified cryptographic primitives.

Primitives

In designing the Capsule protocol, we wanted to focus on obtaining the smallest attack surface possible on an architectural cryptographic level. This is why our low-level cryptographic operations comprise of a restricted subset that is simple to illustrate. The practical details of which cipher suites are chosen to satisfy the security goals of these primitives is discussed in §5.2.

-Hashing. HASH(x) -→ y. A standard one-way cryptographic hash function.

-Hash-Based Key Derivation. HKDF(k, salt) -→ (k 0 , k 1 , k 2 , k 3 ). HKDF functions [START_REF] Krawczyk | Cryptographic extraction and key derivation: The hkdf scheme[END_REF] are proven to be pseudorandom functions under a random oracle model, which is useful for aspects of Capsule's protocol design.

-Encryption and Decryption.

• Encryption. BENC(ek, mk, p) -→ (ENC p , n). Where ek is an encryption key and mk is an authentication key. An authentication tag is generated, as is typical with authenticated symmetric ciphers. • Decryption. BDEC(ek, mk, ENC p , n) -→ {p, ⊥} depending on whether decryption can be authenticated. -Signatures.

• Key Generation. EDGEN(sk) -→ pk.

• Signing. EDSIGN(sk, x) -→ SIG x .

• Signature Verification. EDVERIF(pk, x, sig x ) -→ {⊤, ⊥} depending on whether signature verification succeeds.

Protocol Description

During the lifetime of a Capsule collaborative document, there are only two subprotocols that a participant has to follow. The first is the key generation subprotocol which produces the necessary key material to conduct the session.

The second is the hash chain [START_REF] Lamport | Password authentication with insecure communication[END_REF] protocol, which we call DiffChain. By pushing and pulling encrypted diffs to the diff chain, participants can reconstruct the document upon joining the session and then begin exchanging modifications.

Key Material

The following key material is necessary for all participants.

Client Key Materials A client A owns the following key material in relationship to collaborative document V :

-V k R ←-{0, 1}
128 , a randomly generated master secret, selected by the document creator or otherwise obtained from the document creator. Acts as the lifetime token for legitimately joining a collaborative document. 1 A set of symmetric subkeys used for encryption, message authentication, proof of being a legitimate participants and to derive the document ID used by the server for bookkeeping.

-(V ek , V mk , V sp , V id ) ←-HKDF(V k , CAPSULECORP).
-AV sk R ←-{0, 1} 256 , a signing private key. -AV pk ←-EDGEN(AV sk ). -AV pv ←-PVCALC(V sp , V id , A, AV pk ) = HMAC(V sp , A∥V id ∥AV pk )
In the above, PVCALC is simply a shorthand function for the HMAC construction following it.

Among the above values, AV pv is called a proof of participation value: Since the server does not know V sp , it cannot generate a xV pv for any possible participant x. Validating this value, therefore, protects the collaborative document editing session from containing illegitimate participants who were not given access to V k .

Server Key Materials A server S obtains access to the following key materials in relationship to collaborative document V :

-V id , used as the server-side identifier for the document.

-AV pk as Alice's ephemeral identity. Optionally, the server can also use this to validate DiffChain blocks sent in by Alice for commitment. -AV pv , used by Alice to prove that her identity is being served as a legitimate participant to the collaborative document.

Session Setup

Suppose Alice (A) wants to create a new collaborative document. She generates the keys mentioned in §3.1 and then communicates the following key material to server2 S:

A (V id ,AV pk ,AVpv) -----------→ S
The server creates the new document identified server-side as V id and stores the triple (A, AV pk , AV pv ) as the first participant to the document.

Session setup is now complete. In order to invite a fellow collaborator into the document, Alice simply shares V k . Alice can choose to encode V k as a string or QR code to make sharing easier. Once Bob obtains V k , he too can immediately generate all necessary key material to join the document, encrypt and authenticate diff information and prove to the rest of the participants that his participation is legitimate.

When Bob (B) joins the document, the following occurs (the last message is repeated for every existing participant:) ----------S At this stage, Bob may carry out several validation operations:

B (V id ,BV pk ,BVpv) -----------→ S B (V id ,AV pk ,AVpv) ← -
-Verifying that V k maps to V id .
-Depending on mutual authentication requirements, verifying that AV pk is expected for some known identity for Alice. -Verifying that HMAC(V sp , A∥V id ∥AV pk ) = AV pv .

Managing Collaborative Document History with DiffChain

As a protocol, Capsule needs to provide a fast, efficient method to allow for the continuous update of a document by an unbounded number of participants and for the constant synchronization of this document between the participants. Aside from homomorphic encryption, which currently does not appear to be ready for use in this kind of real-world system, the other clear potential solution seemed to be an encrypted, append-only authenticated log of diff information. We construct such a data structure and call it DiffChain.

Pulling a DiffChain to reconstruct a collaborative document upon joining it is very similar to pulling the Bitcoin blockchain and parsing it in order to reconstruct the currency's current value and activity by going through all transactions since the original block. A DiffChain block contains the following data:

-Encrypted Diff. Alice generates this encrypted diff using BENC(V ek , V mk , diff). -Hash of Previous Block. This is a standard element in hash chain constructions. -ID of Current Block. This is conventionally a UNIX timestamp. It is appended by the server. -ID of Previous Block. This allows for faster lookups.

-Signature. All of the above fields are included in a single signature, with the exception of the ID of the current block since it is appended by the server.

Responsible pushing and pulling. As a rule, clients should not push any new blocks before obtaining confirmation from the server that their local diff state is current. This will help avoid merge conflicts.

Diffing algorithm. The Capsule library comes equipped with an efficient diff generation algorithm that features a JSON-compatible syntax for compatibility. Independent implementations are free to adapt their own diff payload representations, as this does not strictly affect the security or operation of the cryptographic protocol itself.

Protocol Variant: Unauthenticated Encryption

We observe that if all participants accept ciphertexts signed only by identities with a valid XV pv value for any participant X, then the authentication component of the ENC becomes redundant. This observation allows potentially replacing ENC with a unauthenticated encryption cipher, which could lead to improved performance.

Proof. We assume that all clients are honest. We assume that HMAC is a oneway keyed hash function, that V k is secret and that AV pk is authenticated as a public signing identity belonging to A:

-If value AV pv is validated, this proves that generator A must possess V sp .

-Given that V k is secret, ownership of V sp in turn proves that A must possess V k .

Client -At no point in a correct execution of the protocol are the values (V ek , V mk , V sp ) leaked by any participant. -V k maps into (V ek , V mk , V sp , V id ). Therefore, proving ownership of V sp under a secret V k is equivalent to proving ownership of (V ek , V mk , V sp , V id ). This satisfies the original purpose of validating the proof of participation value. -A cannot produce AV pv without also being able to produce (V ek , V mk ). Since signature verification disallows tampering, any unauthenticated ciphertext encrypted under V ek and signed by A is equivalent to a ciphertext encrypted under V ek , authenticated using V mk and signed by A.

Symbolic Verification with ProVerif

We describe Capsule using the applied-pi calculus and, using the ProVerif symbolic protocol verifier, verify that the Capsule protocol meets its security goals under its proposed threat model. In the symbolic model, cryptographic primitives are logically perfect black boxes: hash functions are one-way mappings, encryption functions are permutations, random values are unique and perfectly indistinguishable. Processes can then be executed in parallel. In this setting, a Dolev-Yao [START_REF] Syverson | Dolev-Yao is no better than machiavelli[END_REF] active attacker exists and attempts to reconstruct inputs and outputs in such a way as to reach goals defined by queries and events.

Capsule Processes in ProVerif

In ProVerif, we describe a single public channel, pub, intending to represent regular Internet network exchanges. Then, two types of client processes are described. We illustrate them here in an abbreviated format. 3Writer Client Processes The writer process running under identity W joins a document V using a pre-shared V k . It calculates W V pk , emits a ProofSent event and sends (V id , W, W V pk , W V pv ) over the network. What follows next is an unbounded execution of the writeBlock process, with unbounded newly instantiated plaintext diff. Note that for modeling purposes, we "tag" the plaintext diff using the construction secretdiff which takes in a value of type plaintext and produces a value of type plaintext. This constructor is paired with a reductor, issecretdiff, that simply reveals whether its input value was constructed using secretdiff. l e t w r i t e r C l i e n t ( vk : key , w : p r i n c i p a l , sk : key ) = l e t pk = edgen ( sk ) in l e t ( vek : key , vmk : key , vsp : key , v i d : key ) = bkdf ( vk , c a p s u l e c o r p ) in l e t pv = p v c a l c ( vsp , vid , w, pk ) in event P r o o f S e n t (w, pv ) ; out ( pub , ( vid , w, pk , pv ) ) ; ! ( new d i f f x : p l a i n t e x t ; w r i t e B l o c k ( vk , w, sk , s e c r e t d i f f

( d i f f x ) ) ) .
The writeBlock process is self-explanatory: Reader Client Processes The reader process running under participant identity R comes equipped with a value U V f p ←-HMAC(U V pk , U ) that serves as a fingerprint for authenticating public identities and their public signing keys out of band.

Mirroring the writer processes above, the reader process begins by similarly generating the requisite values and communicating them over the network. Then, an unbounded execution of the readBlock process occurs. l e t r e a d e r C l i e n t ( vk : key , r : p r i n c i p a l , sk : key , ufp : b i t s t r i n g ) = l e t pk = edgen ( sk ) in l e t ( vek : key , vmk : key , vsp : key , v i d : key ) = bkdf ( vk , c a p s u l e c o r p ) in l e t pv = p v c a l c ( vsp , vid , r , pk ) in event P r o o f S e n t ( r , pv ) ; out ( pub , ( vid , r , pk , pv ) ) ; ! ( r e a d B l o c k ( vk , r , ufp ) ) .

The readBlock process receives over the network a triple of candidate values for (U, U V pk U V pv ) with a header matching the V id value that the reader was able to obtain using the V k the process was initialized with. Then, the internal U V f p and U V pv are checked against the candidate values received over the network. If the check succeeds, a ProofVerified event is emitted. Then, an encrypted diff along with its signature is received over the network with a header matching (V id , U, U V pk ). Once signature and authenticated encryption checks pass, the P ulled event is emitted. Attacker and Top-level Processes Before declaring the top-level process, we must declare a process where the attacker attempts to obtain the plaintext for any diff: l e t a t t a c k e r T r y i n g T o O b t a i n P l a i n t e x t ( ) = in ( pub , x : p l a i n t e x t ) ; i f ( i s s e c r e t d i f f ( x ) = true ) then ( event P l a i n t e x t O b t a i n e d B y A t t a c k e r ( x ) ) . Now, we can finally declare the top-level process. We model an unbounded number of sessions, each with a new V k and its own unbounded instantiations of reader and writer principals with their own unique signing key pairs.

Security Goals in the Symbolic Model

We apply ourselves on the security goals described in §1.1 in order to model and verify participant list integrity, confidentiality, integrity and ephemeral authentication in ProVerif. 4Participant List Integrity We assert that if a proof of participation value XV pv is verified by participant Y , then there must exist an identity X which has issued XV pv . As shown in §3.1, this means that whoever asserts identity X must also possess V sp : event ProofVerified(X, Y, XV pv ) =⇒ event ProofIssued(X, XV pv ) Confidentiality We simply query for whether the attacker can trigger the plaintext obtention event described above for any plaintext-type bitstring m: query event PlaintextObtainedByAttacker(m)

Integrity and Ephemeral Authentication

We assert that if a DiffChain block (ENC diff , SIG X∥ENCdiff∥V id ) was received by Y as part of document V , then this block will successfully authenticate and decrypt as originating from identity X if and only if it was pushed by X for document V .

event Pulled(V id , X, Y, XV pk , ENC diff , SIG X∥ENCdiff∥V id ) =⇒ event Pushed(V id , X, XV pk , ENC diff , SIG X∥ENCdiff∥V id )

Results Under a Dolev-Yao Attacker

All queries mentioned above complete successfully. By tweaking the model, we are also able to quickly test for the event where an ephemeral identity is not verified out-of-band by the other participants. Since all encryption is symmetric and no asymmetric key agreement ever occurs in the Capsule protocol, the outcome of this is minor and does not result in the compromise of confidential information.

Software Implementation

Capsule is provided with a client/server reference implementation called Capsulib. It is meant to allow for quick deployment and testing of the Capsule protocol in production.

Capsulib: a Capsule Client/Server Implementation

Capsulib Server is a Node.js application that uses Redis as a database backend but is otherwise self-contained. It achieves low latency by communicating over WebSockets. Its main purpose is to hold a DiffChain record for every document and to facilitate the exchange of encrypted blocks.

Capsulib Client is meant to be executed within an Electron runtime. It provides a user interface, the Capsulib cryptographic library and the full Capsule client protocol implementation.

Conclusion

In this paper, we have presented Capsule, the first formally verified protocol for secure collaborative document editing. We believe Capsule will address an important need in the space of privacy enhancing technologies. We have provided a full description of the Capsule protocol and symbolic verification results for its security goals under the specified threat model.

Finally, we also provide Capsulib, a reference implementation of Capsule based on modern web technologies. While Capsulib is built for web use, it is also the first software project to employ the HACL* formally verified cryptographic library by translating it into WASM. By adopting such technologies, Capsule protocol is able to be presented complete with a practical implementation that follows best practices and achieves sound practical security in deployment.

Fig. 1 .

 1 Fig.1. Capsule protocol session network messages. Here, A initiates a session with S and then communicates session key V k and her own fingerprint AV f p to B out of band. After B joins and all checks pass, A commits an example encrypted diff, diff0 and B follows up with an example diff diff1. More involved sessions can include clients C, D, etc. with a non-deterministic diff commit schedule.

l e t w

  r i t e B l o c k ( vk : key , w : p r i n c i p a l , sk : key , d i f f x : p l a i n t e x t ) = l e t pk = edgen ( sk ) in l e t ( vek : key , vmk : key , vsp : key , v i d : key ) = bkdf ( vk , c a p s u l e c o r p ) in l e t e d i f f = benc ( vek , vmk , d i f f x ) in l e t e d i f f s i g = e d s i g n ( sk , c o n c a t 3 ( p r i n 2 b i t (w) , e d i f f , k e y 2 b i t ( v i d ) ) ) in event Pushed ( vid , w, pk , e d i f f , e d i f f s i g ) ; out ( pub , ( vid , w, pk , e d i f f , e d i f f s i g ) ) .

l e t r

  e a d B l o c k ( vk : key , r : p r i n c i p a l , ufp : b i t s t r i n g ) = l e t ( vek : key , vmk : key , vsp : key , v i d : key ) = bkdf ( vk , c a p s u l e c o r p ) in in ( pub , ( =vid , u s e r 0 : p r i n c i p a l , upk0 : key , upv0 : b i t s t r i n g ) ) ; l e t ufp0 = hmac ( upk0 , p r i n 2 b i t ( u s e r 0 ) ) in l e t upv = p v c a l c ( vsp , vid , u s e r 0 , upk0 ) in i f ( ( ufp0 = ufp ) && ( upv0 = upv ) ) then ( event P r o o f V e r i f i e d ( u s e r 0 , r , upv ) ; in ( pub , ( =vid , =u s e r 0 , =upk0 , e d i f f 0 : b i t s t r i n g , e d i f f 0 s i g : b i t s t r i n g ) ) ; l e t s i g v e r 0 = e d v e r i f ( upk0 , e d i f f 0 s i g , c o n c a t 3 ( p r i n 2 b i t ( u s e r 0 ) , e d i f f 0 , k e y 2 b i t ( v i d ) )) in i f ( s i g v e r 0 = true ) then ( l e t vs0 : v a l i d = bdec ( vek , vmk , e d i f f 0 ) in l e t ( v0 : bool , s 0 : p l a i n t e x t ) = v a l i d u n p a c k ( vs0 ) in i f ( v0 = true ) then ( event P u l l e d ( vid , u s e r 0 , r , upk0 , e d i f f 0 , e d i f f 0 s i g ) ) ) ) .

CAPSULECORP represents a salt encoded as a string.

Transport layer protections for this and other communications listed below are beyond the scope of this protocol. For simplicity, we assume they are protected with a transport layer security model equivalent to a regular TLS 1.3 deployment.

Capsule models and reference implementations are available at https://symbolic. software/capsule/.

Transcript consistency, while not explicitly modeled in ProVerif, is obtained through the hash chain structure of DiffChains, as described in §3.3.

Acknowledgments

We would like to thank Karthikeyan Bhargavan, Denis Merigoux and Jonathan Protzenko for various feedback and assistance. We also thank Vitalik Buterin for encouragement to pursue this work.

Cryptographic Cipher Suite

We expose the following cryptographic functions:

-Hashing. HASH(x) -→ y. BLAKE2s is used as the hash function.

-Hash-Based Key Derivation. BKDF(k, salt) -→ (k 0 , k 1 , k 2 , k 3 ). BLAKE2s is also used for key derivation, producing four 16-byte outputs. -Encryption and Decryption. BLAKE2 is used for encryption and decryption. We hash the encryption key over a counter and a to generate a keystream. BLAKE2 is then used as a keyed hash with a MAC key to generate an HMAC value over the ciphertext.

• Encryption. BENC(ek, mk, p) -→ (ENC p , n).

• Decryption. BDEC(ek, mk, ENC p , n) -→ p. -Signatures. Ed25519 is chosen due to its speed and minimal input validation requirements.

• Key Generation. EDGEN(sk) -→ pk.

• Signing. EDSIGN(sk, x) -→ SIG x .

• Signature Verification. EDVERIF(pk, x, sig x ) -→ {⊤, ⊥}.

Formally Verified Cryptographic Primitives in WebAssembly

While Capsulib is written in JavaScript, much of the Capsulib cryptographic primitives library is automatically generated as WebAssembly (WASM) [START_REF]WebAssembly Core Specification[END_REF] code. We use a toolchain that provides strong verification guarantees, hence ruling out potentially catastrophic bugs in the cryptographic layer. Ed25519 is specified in F* [START_REF] Protzenko | Verified low-level programming embedded in F[END_REF], an ML-like programming language with support for program verification via the use of a dependent type system, effect annotations and SMT-based automation. Our specifications are executable, which allows us to run them against the RFC test vectors to ensure their correctness.

The cryptographic algorithms themselves are written in Low*, a subset of F* that enjoys an optimized compilation scheme to low-level targets. The Low* implementation of our algorithms is shown to match the original F* specification, which ensures functional correctness and memory safety.

Based on this, we rule out both incorrect math and memory errors such as buffer overflows. In addition to function correctness and memory safety, we enforce basic side-channel resistance, by restricting secrets to a very limited set of operations. In effect, this ensures that secret-manipulating code is branch-free and cannot access memory using a secret index. This helps rule out classic timing and cache attacks.

Once verified, Low* programs can be compiled to low-level targets using the Kremlin [START_REF] Wang | HACL*: A verified modern cryptographic library[END_REF] compiler, which currently supports C and WASM as backends. Compared to Emscripten, the Kremlin compiler offers a much smaller trusted computing base, smaller resulting WASM files and almost no dependencies on untrusted code, such as a libc implementation.

The cryptographic primitives that we compile into WebAssembly using this process are originally part of the HACL* [9] cryptographic library, specified in F*.