Pejman Iravani Nick Hockings

Pejman Iravani

Chris R Bowen

Artificial ligamentous joints : methods, materials and characteristics

Keywords:

published or not. The documents may come

I. INTRODUCTION

Locomotion and manipulation require interaction with an uncertain physical world. Consequently robotic limbs and hands need robust joints, with good range of motion. Vertebrate anatomy provides evidence of one physical solutionligamentous synovial joints -that remains superior to other methods. This is highlighted by the work of Melchorri et al (2013) who stated, "The replication of the human hand's functionality and appearance is one of the main reasons for the development of robot hands. Despite 40 years of research in the field, the reproduction of human capabilities, in terms of dexterous manipulation, still seems unachievable by the state-of-the-art technologies." [START_REF] Melchiorri | On the development of the ub-hand iv: an overview of design solutions and enabling technologies[END_REF] and of [START_REF] Grebenstein | Methodology. In Approaching Human Performance: The Functionality-Driven Awiwi Robot Hand[END_REF], "The gap between the basic principles and solutions of bio-mechanical systems and the capabilities of technical systems is too wide to develop a proper hand design by simply copying the human hand using methods and solutions of the current robotics state of the art. It is currently still not possible to construct an exact copy of the human hand." [START_REF] Grebenstein | Methodology. In Approaching Human Performance: The Functionality-Driven Awiwi Robot Hand[END_REF] The challenge is how to reproduce the material properties of the soft tissues involved, and how to layup those materials to reproduce the mechanism of anatomical joints. This is commonly considered a difficult task, e.g.

"many joints are held together ... by ligaments or tough soft tissues which are almost impossible to duplicate" [START_REF] Diamond | Anthropomimetic robots: concept, construction and modelling[END_REF] This paper presents a method for making ligamentous articulations for robots, using 3D printing, tow laying and thermoplastic welding.

The approach applied here is to examine the established anatomical and histological knowledge of the structures being emulated and ask -what properties of these materials and structures are sufficient to predict the useful behaviour that we wish to reproduce?

Specifically, histology reveals that anatomical tissues are fibrous composites. Most of these tissues are hyperelastic and anisotropic, as such they cannot be approximated in a simple way by rigid body models. The behaviour of such *This work was supported by UK EPSRC DTA 1 Department of Mechanical Engineering, University of Bath, BA2 7AY, The United Kingdom. N.C.Hockings@bath.ac.uk materials is determined by the arrangement and properties of their constituent materials : the diameter and stiffness of the fibres, the elasticity and hysteresis of the matrix, and the adhesion between the fibres and matrix. The kinematics are largely dependent on the topology and length of the fibres. The structure of anatomical tissues is known through all scales down to molecular structure. The choice of scale at which to emulate the materials determines the design.

A. Review of quasi-ligamentous joints in robots, machines and orthopaedics

In robotics flexural joints have been used in 3D printed structures, notably the iRobot-Harvard-Yale hand [START_REF] Lael U Odhner | A compliant, underactuated hand for robust manipulation[END_REF]. These allow buckling and axial twisting of the joint, and can be built into a shape deposition cast skeleton. The flexible mechanism is robust to collisions, but this flexibility limits the ability to stably transmit force along the column of bones.

Another example of fibrous joints are the ribbon joints of the "Kilck-Klack" or "Jacobs Ladder" falling blocks illusion toy, [START_REF] Anon | Jacob's ladder[END_REF] [START_REF] Simanek | Toys, tricks and teasers[END_REF]. The mechanism is close to that of a four bar linkage, and to the cruciate ligaments of knees. The fibrous constraint is very stable, but the contact area between the blocks is minimal for all but one point in the range of motion. Consequently the motion is well constrained, but any compressive force would produce high pressure loadings at the contact surfaces.

Etoundi et al [START_REF] Appolinaire C Etoundi | A bio-inspired condylar hinge joint for mobile robots[END_REF] [7] produced a condylar knee mechanism that used nylon cord ligaments in a four bar linkage, emulating the cruciate ligament mechanism of knees. Cords were also used as ligaments in ECCE Robot [START_REF] Gravato | Ecce1: the first of a series of anthropomimetic musculoskeletal upper torsos[END_REF] to prevent dislocation of the shoulder joint. These were composed of stiff cords of ultra high molecular weight polyethylene (UHMWPE), or series combination of elastic and stiff cords. While these cord-ligaments reproduce some of the topology of anatomical ligaments, they lack the broad attachment and integration with the bones that make anatomical joints robust.

Van den Broek et al [START_REF] Peter R Van Den Broek | Design of next generation total disk replacements[END_REF] [21] developed a prototype artificial inter-vertebral disk (AID) emulating the structure of anatomical inter-vertebral disks. The AID was composed of an ionized hydrogel core, wrapped in a hydrophobic membrane, enveloped by five layers of UHMWPE fibre, reproducing the nucleus pulposus constrained by the annulus fibrosus. Loading and fatigue testing showed that the prototype could withstand the maximum biological loading and fatigue, while providing stiffness and hysteresis close to that of healthy anatomical inter-vertebral disks.

The closest approximation of a ligamentous joint in a robot may be the silicone rubber joint capsule tested on the Anatomically Correct Testbed (ACT) hand [START_REF] Xu | Design and analysis of an artificial finger joint for anthropomorphic robotic hands[END_REF]. This

II. TECHNIQUE

A. Anatomical structures

This section describes the scale level at which the anatomical structures were emulated, and provides the keywords for roboticists to access the relevant anatomical literature.

The anatomy of human hands and dogs paws were used as the template for the demonstration specimens. Despite their differences of proportion, these are composed of the same tissues and share the same basic topology of bones and ligaments.

The variation in anatomy of healthy individuals shows that the material properties may vary by an order of magnitude without altering the function. Developmental anatomy shows that ligamentous joints are formed by progressive differentiation of tissues, and are fully functional whilst entirely soft prior to calcification of the bones. What is critical is sufficient strain tolerance and the ratio of stiffness between the different materials.

Ligaments do not generally provide the stiffness of constraint provided by engineering joints in rigid materials. For example for any given ligament it is generally possible to manipulate the joint to a position where the ligament is slack enough to pass a probe under it.

The stability of ligamentous joints is also dependent on direction of the load and the action of the tendons/muscles around the joint. By itself the joint capsule, including ligaments, prevents dislocation of the compression bearing articular surfaces, but commonly does allow some separation of the joint surfaces if tension is not opposed by muscle contraction. Ligaments are generally much less substantial than the principal tendons of the joint and usually have less leverage. Further, the series arrangement and under-actuation of joints is such that a load not supported by a tendon will commonly cause rotation of other joints that either transfers the load onto a tendon, or releases the load altogether. The exception to this being the function of suspensory and check ligaments which act on tendons in parallel with muscles in "passive stay" mechanisms.

1) Tissues of synovial joints: Articular cartilage is a thin layer of tough hyaline hydrogel with collagen fibre reinforcement in the plane. Synovial fluid is a viscous shear thinning fluid that acts as a boundary lubricant between the articular surfaces, and between the joint capsule and articular convex surface [START_REF] Fam | Rheological properties of synovial fluids[END_REF].

The joint capsule is continuous with the articular cartilage of the concave side of the joint. The hyaline content of the matrix is progressively replaced by hyper-elastic elastin. The capsule is reinforced with dense orientated collagen fibres. The matrix allows the capsule to stretch orthogonal to the collagen, and lubricates relative movement of the fibres in shear motions. The articular ligaments are dense bundles of collagen fibres in the joint capsule.

2) Structure of finger joints: The joints of the fingerdistal inter phalangeal (DIP) [START_REF] Ioannis | The distal interphalangeal joints of human fingers[END_REF], proximal inter phalangeal (PIP) [START_REF] William | The proximal interphalangeal joint volar plate. i. an anatomical and biomechanical study[END_REF] and metacarpophalangeal (MCP) -are of very similar construction. In the MCP the extensor tendon slip is replaced by the extrinsic extensor tendon, which does not insert on the distal margin of the joint but joins the extensor hood instead.

Figure 1 shows the PIP. Note the fibrocartilaginous dorsal [START_REF] Slattery | The dorsal plate of the proximal interphalangeal joint[END_REF] and volar plates, and the buckling motion of the volar plate aided by the recess between its distal margin and the proximal phalanx [START_REF] William | The proximal interphalangeal joint volar plate. i. an anatomical and biomechanical study[END_REF]. The check ligament and the distal part of the accessory ligament limit the maximum extension of the joint.

The collateral ligaments are much thicker and stronger than the accessory collateral ligaments, and form the primary constraint on the motion of the joint. In the MCP the collateral ligaments are attached and the joint faces shaped, such that the collateral ligaments are slack if and only if the joint is extended, allowing medio-lateral swinging of the joint. [START_REF] Minami | Ligament stability of the metacarpophalangeal joint: a biomechanical study[END_REF] 3) Structure of the palm: The palm is a complex structure, that provides critical load bearing and balancing in both paws and hands. Reproducing these functions by rigid mechatronic parts has been particularly difficult.

Figure .2 shows the ligamentous tissues of the palm. There is no synovial articular surface at the distal inter-metacarpal joints. Other soft tissue structures separate the bones including the sagital bands of the metacarpophalangeal joints and the tendons of the interosseous muscles. The metacarpals are held to each other by (i) the inter-palmar-plate ligaments [START_REF] Karl | The septa of legueu and juvara: an anatomic study[END_REF] that link the volar plates of the metacarpophalangeal joints to each other, collectively called the transverse metacarpal ligament, (ii) the natatory ligament which connects the proximal margin of the second annular ligaments of the first phalanges, (iii) the transverse fibres of the palmar aponeurosis [START_REF] James R Doyle | Anatomy and function of the palmar aponeurosis pulley[END_REF] which are connected to the deep transverse metacarpal ligament by the septae of Legueu and Juvara [START_REF] James R Doyle | Anatomy and function of the palmar aponeurosis pulley[END_REF] [START_REF] Karl | The septa of legueu and juvara: an anatomic study[END_REF].

The proximal inter-metacarpal joints have small articular facets, and three sets of ligaments -dorsal, palmar and interosseous -which allow minimal rotation of adjacent bones about each other [START_REF] William W Dzwierzynski | Anatomy of the intermetacarpal ligaments of the carpometacarpal joints of the fingers[END_REF]. The carpometacarpal joints have short ligaments that allow very little movement.

4) Structure of carpus:

The carpal mechanism of ungulates (mammals with hoof feet) (fig. 3) was used rather than that of dogs because it has a simpler motion and was easier to construct. The carpal bones are arranged in two horizontal rows and flex by hinge motion about their palmar ligaments. As such it is close to a flexural joint when flexing, but bears compression on a continuous column of bones when extended. On the dorsal side the intercarpal ligaments connect only between bones on the same row. On the palmar side long ligaments from proximal row accessory carpal and radial carpal bones to the metacarpals limit the maximum extension of the intercarpal joint.

B. Materials

1) Compatible thermoplastics: Three different thermoplastics, polycaprolactone (PCL), polylactic acid (PLA), polyamide (PA), were selected with different softening temperatures, table(I) and compatible inter-molecular bonding. PCL and PLA have the same intermolecular bonding based on ketone groups which form dipole attractions, consequently they are miscible when molten. Softened PCL wets very well to solid PLA forming a high surface area of contact with 3D printed PLA parts, (fig. 4c). PCL-PLA adhesion approaches the strength of pure PCL or PLA.

Polyamides(PA) including polyaramide(PAr) have amide links between their monomers. These present both ketone groups and hydrogen bearing amide groups. The ketone groups of PCL or PLA can form N-H"O hydrogen bonds with the PA, which are stronger than the ketone dipole attractions within either PCL or PLA. This strong intermolecular bonding allows the PA ligaments to be firmly attached to the bones.

Glycerol (propane-1,2,3-triol) is a short chain polyalcohol which is miscible with PCL and can be used as a plasticising agent. PCL softened with glycerol was used to make some joint faces more compliant.

Styrene-ethylene-butadtiene-styrene (SEBS) is a block copolymer that forms very soft (0 Shore-A [23]) hyperelastic oil-gels (SEBS-gel) with alkane oils. SEBS-gel is used as a hyperelastic matrix for soft tissues. SEBS-gel does not adhere to polar polymers but can be mechanically blended with PCL, or infused between PA fibres as a matrix. Varying the ratio of SEBS-gel:PCL produces blends of intermediate stiffness and elastic limit. A stack of rolled films of blends of SEBS and PCL of progressively varied ratios can be rolled together on a hotplate to produce a composite film with pure PCL on one face and pure SEBS-gel on the opposite face. These composite films were used both to adhere SEBS to PCL and to prevent adhesion between PCL surfaces in contact.

2) Low temperature thermoplastic welding: PCL undergoes transition from opaque rigid semicrystaline state to transparent amorphous glassy plastic state at around 60C. In this state it is viscoelastic with substantial surface tension. This allows PCL to be molded by hand and causes it to form a smooth surface if allowed to relax in the plastic state. Small spots in PCL material a few millimetres in diameter can be heated above the phase change with a soldering iron. This allows spot welding of PCL to itself and other compatible materials without softening adjacent structures, and for such welds to be resoftened and their position adjusted. Spot welding is used to precisely position ligament attachment points.

Tows of parallel non-spun polyamide (PA) fibres, either polyamide-6,6 (PA66) or polyaramide (PAr), approximately 25 microns in diameter, (fig. 4a), were used for the tendons and ligaments. The combination of high surface area of the fine fibres, with good wetting of PCL to PA and strength of hydrogen bonding produced strong welds between PCL and PA. In pull-out tension testing PA fibres fail before their connection to PCL (fig. 4b), hence the strength of PA ligaments is limited by the strength of the fibres not the attachment to PCL.

C. Layup process 1) Bone geometry from volume imaging: The bones were 3D printed in PLA using a RepRap fused filament deposition printer [START_REF] Jones | Reprap-the replicating rapid prototyper[END_REF]. The models of the bones were segmented from MRI and CT scans using Slicer3D software [START_REF] Fedorov | 3d slicer as an image computing platform for the quantitative imaging network[END_REF]. These bones as printed in PLA approximate geometry of the calcified tissues (cortical bone, cancellous bone, and calcified cartilage) which are distinct from noncalcified tissues in The PLA printed bones were then overlaid with PCL. This provided a layer of low temperature thermoplastic firmly adhered to the PLA, that could be formed and welded without deforming the printed structure. In the region of the articular surfaces PCL softened with glycerol was used to better approximate the compliance of articular cartilage.

2) Articular surfaces -method 1: The articular surfaces were formed by forging opposing surfaces against each other with one bone chilled and the other heated above the phase transition of PCL. The cartilaginous part of the joint capsule was formed by drawing the warm PCL by hand from the concave side of the joint over the chilled convex side of the joint, (fig. 5a). During the forging process the opposing faces were lubricated with a film of oil and kept continuously in relative motion to prevent fusing between them. The flexing of the joint during forging helps to ensure that the shape formed permits the range of motion required and that the articular surfaces are congruent throughout the motion.

3) Articular surfaces -method 2: A ribbon of composite SEBS-gel-PCL film, section(II-B.1), was laminated with polyaramid fibres on the PCL side. One ribbon was placed running palmar-dorsal on the concave articular surface of the distal bone, with the SEBS side facing the proximal bone. Additional ribbons were placed on the dorsal and palmar surfaces of the distal bone and laminated to the first ribbon to form the check ligament of the volar plate and extensor tendon slip, (fig. 5b). Pads of blended PCL-SEBS-gel were added to the portions of the volar plate and extensor slip adjacent to the distal bone, to emulate the fibrocartliaginous pads of the anatomical structures (fig. 1a&5c).

4) Articular ligaments and joint capsule: Ligaments are attached by working warm PCL into a point near the end of a tow of PA66 with a soldering iron, then pressing this to the prewarmed insertion point in the PCL covering the PLA bone. This method allows good wetting of the PA66 by the PCL. The insertion point can then be adjusted by pulling on the tow either side of the attachment point. The PCL can then be cooled to solidify it and fix the attachment point.

The PA66 tow is then laid across the joint to locate the correct point for its 'origin' attachment. The fibres of the tow are worked into the attachment site and more PCL added as needed to ensure good adhesion of the fibres. The tension of the ligament can then be adjusted by pulling on the free end of the tow while flexing the joint while the attachment site is soft.

The joint capsule and the elastic matrix of the ligaments outside of the bone is applied by wrapping the joint in PCL-SEBS-gel film, then briefly melting the film with hot air from a heat gun.

III. DEMONSTRATION

A. Finger

A set of fingers for a hand were printed and laid up using method 2, section(II-C.3), for the joints, following the pattern of the anatomy, section(II-A.2). Polyaramide(PAr) was used for the ligaments, in order to provide a wide temperature tolerance for infusing PCL-SEBS-gel matrix. Polyamide deep and superficial flexor tendons and associated polyaramide flexor retinacular ligaments were fitted to the finger to assess the range of motion. Details of the tendon system are provided in [START_REF] Hockings | Tendon networks for artificial ligamentous joints : methods, materials and characteristics[END_REF].

The resulting fingers match the dimensions of the musculo-skeletal components of the hand in the MRI image, leaving the normal anatomical space for dermal and subdermal structures to be added. This is important because robot fingers are usually thicker than human fingers of the same length and lack the soft pads and other dermal structures. The joints (MCP, PIP and DIP) allow the normal anatomical range of flexion-extension, (fig. 6a&6b).

Lateral stability of the DIP and PIP was slightly slacker (7 versus 5 degrees of yaw) than that of the human hand in the MRI image. Strength of lateral stabilization was tested by loading the PIP to 0.6Nm static torque without damage. This corresponds to a lateral load of 3kg weight supported by a single finger at two centimetres distal to the joint, which exceeds the maximum loads normally exerted in this way by adult humans in a domestic setting. Note that heavy loads would normally be lifted on the palmar surface of the finger with tension borne by the digital flexor tendons, which are many times stronger than the collateral ligaments.

The MCP reproduced the cam tensioning action of the collateral ligaments, allowing wide yaw (25 degrees) in the extended position, and much reduced yaw (10 degrees) in the flexed position. This action helps to close the fingers in a cage around an object in the palm in humans.

In the extended position the MCP, PIP and DIP in series permitted a total axial roll of 45 degrees. This motion is important in allowing the finger tips to comply to the orientation of the contact surface.

Friction with the joints dry was high, as expected given the contact between soft SEBS-gel and hard PCL. When lubricated with paraffin (alkane) oil friction was very low and comparable to synovial joints. This reflects that paraffin is the solvent component of the SEBS-gel, so wets very well to that surface, while the PCL surface is very smooth having been shaped by surface tension in the glassy phase.

The joint capsule was less satisfactory. The PCL-SEBSgel film was not well fused into the ligaments. This was partly due to the heat gun being oversized and lacking fine temperature control, which made it difficult to deliver the right amount of heat without risking damage by excess heating.

B. Paw

The paw was printed and laid up using method 1, section II-C.2, for the joints, following the pattern of the anatomy described in section II-A. Polyamide-6,6 (PA66) was used for all ligaments and tendons.

The flexion of the carpus is approximately 120 degrees shown in (fig. 6c,6d) matching that of dogs. The passive supination/pronation of the paw by differential extension of the carpo-metacarpal and inter-metacarpal joints is shown in (fig. 6c,6d). This motion is important to comply with the shape of the terrain and distribute load across the paw.

The paw was based a CT scan of the front paw of a dog weighing 200N, and tolerates repeated static loads greater than 120N without flexor tendon actuation. In use the flexor tendons would bear part of the tension resisting hyperextension of the joints.

An important shortcoming of the paw is that method-1 for making the joints resulted in some of the MCP and PIP joints being unintentionally fused during the layup.

IV. DISCUSSION

The key features of the materials produced are (i) the use of multiple matrix materials of stiffness ranging from rigid to low modulus hyper-elastic (ii) stiff reinforcing fibres in soft matricies creating extreme anisotropies (iii) that fibres cross matrix boundaries creating topological connections in a deformable structure, and (iv) specific fibre paths matched to the geometric shape of the rigid matrix regions. Together these features integrate material composition with mechanical structure to produce a functional machine as a single piece deformable mechanism.

The central component of the technique is the use of thermoplastic welding of the matrix of the composite to achieve accurate fibre placement. This allows tows to be individually laid, immediately fixed and adjusted during the layup. It also points to how the process could be automated to achieve precise and repeatable construction by laying tows and thermoplastic tapes.

The strength of the weld between a fine fibre and a compatible thermoplastic matrix makes it possible to have compact attachment regions for ligaments that match the anatomy being emulated. It also makes it straightforward to estimate the quantity of ligament fibre needed to impart a given strength to a joint.

To reproduce the function of anatomical fingers and paws at 1:1 scale it was necessary to emulate the tissue structure at a scale between 300-100 microns. Human finger anatomy involves many layers of ligamentous and tendinious tissues, hence it is important that these are kept thin to achieve slender dextrous fingers.

A. Comparison to other joint types

Relative to pin-hinge joints, ligamentous joints provide a simpler path for compressive and tensile forces carried by the column of bones and the tendons respectively. In joints composed purely of rigid materials, such as pin-hinge joints there has to be a discontinuity in the tension bearing structure, and a conversion the tension to a compressive force that can be transmitted by contact between rigid parts. This requires that the force doubles back on itself around the pin or other retaining part, which requires more material and more space than a ligamentous joint made of materials of similar strength.

Compared to flexural joints, ligamentous joints have a greater capacity to bear compressive loads due to the large area of direct contact between the bones. This translates to the ability to support greater actuation force by tendons, for a given size of joint. Flexural and ligamentous joints share the ability to deflect to off axis loads, which is beneficial both for complying to unknown surfaces in grasping, and to avoid breaking in collisions.

B. Actuation

In animals both actuation and additional stabilisation is provided by tendons. Tendons in animals are held in their correct paths by a second set of ligaments known as 'retinacular ligaments'. Animal tendons are proportionally much thicker than those commonly used in robots. The load bearing fibres of tendons are parallel, held together by an elastic matrix. Bowden tubes and rotating pulleys are not found in animals. Friction of tendons is lubricated by fluid filled sheaths and hyalinized load bearing surfaces resembling synovial joints. Where lateral pressure is low, tendons are lubricated by solid hyperelastic tissue.

The methods and materials described in this paper lend themselves to emulating anatomical tendon networks. The techniques for this will be addressed in another paper.

C. Further work

Further work will involve creep and fatigue cycle testing to assess durability and repairability of structures built in this way. Materials development may include new thermoplastic blends, custom co-block polymers, and custom 3D printer G-code for emulation of gross bone structure. Thermoplastic tape and tow laying tools could improve build consistency. Given suitable CAD-CAM modelling and process monitoring it would be possible to automate the lay up process.

Further components that are needed are dermal structures (pads, dermis, nails, claws and hooves), actuators, and embeded sensors for tactile and proprioceptive sensation.

V. CONCLUSIONS Contrary to previous expectations [START_REF] Grebenstein | Methodology. In Approaching Human Performance: The Functionality-Driven Awiwi Robot Hand[END_REF] [4] direct emulation of the mechanical properties of histological tissues and anatomical structures is feasible. The key distinction is to emulate the mechanical, but not necessarily the chemical or biological properties of the materials.

The ability to produce tough ligamentous joints opens the possibility of exploiting known anatomical mechanisms whose function is hard to match with conventional mechatronic techniques.

Fig. 1 :

 1 Fig. 1: (a) Proximal interphalangeal joint extended (b) flexed, showing the movement of the ligaments, dorsal and volar plates. The flexor tendons pass through the annular pulley.

Fig. 2 :

 2 Fig. 2: (a) Palmar-oblique view of the ligamentous structures of the palm : A1-1st annular lig, A2-2nd annular lig, C-carpal bones, FT-digital flexor tendons, Mc-metacarpal bone, P1first phalanx bone. (b) Transverse section of the palm at the level of the deep transverse metacarpal ligament (DTML). Note the DTML is composed of the volar (palmar) plates and the inter palmar plate ligaments.

Fig. 3 :

 3 Fig. 3: Simplified diagram of ungulate-like carpal mechanism implemented -Flexed left, extended right. Ligaments stabilise relative dorsal-palmar movement between the bones, while allowing flexion about the palmar margin of the carpal bones. R-radius, C1 & C2-1st & 2nd row carpal bones, Aaccessory carpal bone, Mc-metacarpal bones.

Fig. 4 :

 4 Fig. 4: (a) Thickess of polyamide (PA) fibre (purple) compared to 30micron motor wire. Fine fibres confer flexibility to ligaments and provide high surface area for adhesion to the matrix. (b) PA fibres failing under tension, before a 10mm long weld into a polycaprolactone (PCL) matrix, in a pull out test (c) PCL (white) forms close key with 3D printed polylactic acid (PLA, black), reproducing the 0.3mm ridge pattern of the surface. PCL-PLA adhesion approaches the strength of pure PCL or PLA

Fig. 5 :

 5 Fig. 5: Making articular surfaces (a) Method One forging polycaprolactone (PCL) articular surfaces against each other (b) Method Two laminated joint surfaces. Materials: 1.Polylactic acid (PLA) bone, 2.PCL-SEBS graded laminate, with PCL face bonded to PLA bone, 3.PCL-Glycerol blend, forms a compliant socket, 4.Polyaramide (PAr) fibres between PCL faces of laminate, form the palmar plate and dorsal extensor slip continuous with the socket, 5.PCL coating on polylactic acid (PLA) bones. PCL of articular surface faces SEBS of laminate hence faces cannot adhere, but do require oil lubrication, (c) DIP joint Method Two with ligaments: 1.Extensor slip, 2.Collateral ligament, 3.Accessory collateral ligament, 4.Volar plate

Fig. 6 :

 6 Fig. 6: Joint motions (a) finger extended, (b) finger flexed, (c) paw carpus flexed, (d) paw carpus extended, (e)&(f) passive supination/pronation of the paw.

TABLE I :

 I

Softening temperatures of plastics, temperatures will vary with polymer chain length and compounding additives.


Ferdinand Sibleyras

Generic Attack on Iterated Tweakable FX Constructions

Keywords: Tweakable, Block Cipher, Provable Security, FX, Cryptanalysis, Optimality, XHX2

Tweakable block ciphers are increasingly becoming a common primitive to build new resilient modes as well as a concept for multiple dedicated designs. While regular block ciphers define a family of permutations indexed by a secret key, tweakable ones define a family of permutations indexed by both a secret key and a public tweak. In this work we formalize and study a generic framework for building such a tweakable block cipher based on regular block ciphers, the iterated tweakable FX construction, which includes many such previous constructions of tweakable block ciphers. Then we describe a cryptanalysis from which we can derive a provable security upper-bound for all constructions following this tweakable iterated FX strategy. Concretely, the cryptanalysis of r rounds of our generic construction based on n-bit block ciphers with κ-bit keys requires O(2 r r+1 (n+κ) ) online and offline queries. For r = 2 rounds this interestingly matches the proof of the particular case of XHX2 by Lee and Lee (ASIACRYPT 2018) thus proving for the first time its tightness. In turn, the XHX and XHX2 proofs show that our generic cryptanalysis is information theoretically optimal for 1 and 2 rounds.

Introduction

Tweakable block ciphers have been the focus of many recent works in the field of symmetric cryptography as it provides a very interesting flexibility compared to regular block ciphers. Formally, a block cipher is defined as a family of permutations indexed by a secret key, thus an n-bit block cipher E indexed by a κ-bit key is an application E : {0, 1} κ × {0, 1} n → {0, 1} n . Whereas a tweakable block cipher is a family of permutations indexed by both a secret key and a public tweak, thus an n-bit tweakable block cipher Ẽ indexed by a κ-bit secret key and a τ -bit public tweak is an application Ẽ : {0, 1} κ × {0, 1} τ × {0, 1} n → {0, 1} n . They have been formalized by Liskov,Rivest and Wagner [LRW11].

On the other hand, regular block ciphers benefit from a longer history of research which gave birth to many designs and implementations notably including the DES [DES77] and the AES [AES01]. Therefore a natural question is: how can we build a tweakable block cipher out of regular block ciphers? In fact this line of study inspired new modes of operations like OCB [RBBK01] and PMAC [BR02] that benefits from a relatively easy two-step proof: first we show that the main construction is secure when used along with a tweakable block cipher then we construct such tweakable block cipher with a regular block cipher to fully describe the mode. A first approach can be to append a tweak with the secret key such that the concatenation becomes the effective key to the regular block cipher. Given security under related key attacks this can work but at the cost of security: the size of the secret key will have to be reduced to make space for the tweak.

To go around this limitation Liskov et al. described two constructions LRW1 and LRW2 [LRW11]. In particular LRW2 is somehow remindful of the FX construction that adds an n-bit key before the input and another after the output of the underlying block cipher. The FX construction has been proposed by Killian and Rogaway [KR96] in a different context: they investigated DESX, an easy solution to protect DES against an exhaustive key search. FX consists in adding one n-bit subkey before and another one after the block cipher. With such strategy they proved that the time complexity of the best generic cryptanalysis goes from O(2 κ ) to O(2 κ+n /D) where D is the data or online query complexity. The FX construction has since been notably used in PRINCE [BCG + 12] and PRIDE [ADK + 14]. We can naturally iterate r rounds of the FX construction which requires to have r κ-bit subkeys along with (r + 1) n-bit subkeys. Then the idea to build a tweakable block cipher is to blend the tweak and the master key together in a predefined key schedule to obtain all the required subkeys for the computation.

Notations

First we formally describe the r-round tweakable iterated FX construction (Figure 2) on which our results apply. Let E 1,2,...,r (u, •) be r block ciphers with κ-bit key u and n-bit input and output. Let k be the κ-bit master key of the tweakable block cipher construction. Let t be a tweak of arbitrary length. Let γ i (k, t) be the subkey for the i th block cipher of length κ-bit for 1 ≤ i ≤ r and λ i (k, t) the n-bit subkeys to XOR in the state for 0 ≤ i ≤ r. For example the r = 2-round tweakable FX construction (Figure 1) Ẽk (t, m) is described as:

Ẽk (t, m) = E 2 ( γ 2 (k, t), E 1 ( γ 1 (k, t), m ⊕ λ 0 (k, t) ) ⊕ λ 1 (k, t) ) ⊕ λ 2 (k, t)
We will focus on generic key recovery attacks. The goal of the cryptanalysis of Ẽk (t, m) is to recover k by doing offline queries to E 1,2,...,r (•, •) and online queries to Ẽk (•, •). We don't count the number of calls to the γ and λ functions generating the subkeys as queries because we don't assume any security property for them. In fact it is common for the subkeys to assume some almost uniformity, almost universality or almost XOR-universality property with respect to the tweak (See Definition 1). This makes the analysis proper for most of the constructions we cite except for F [2] by Mennink [Men15] which can be seen as a 1-round tweakable FX where the subkey functions reuse the block cipher itself. Definition 1. Let δ > 0 and a function λ : K × T → Y for non-empty sets K, T , Y.

λ(k, t) is said to be δ-almost uniform if for any t ∈ T and any y ∈ Y,

Pr ( k ← $ K : λ(k, t) = y ) ≤ δ .
λ(k, t) is said to be δ-almost universal (AU) if for any distinct t and t ′ ∈ T ,

Pr ( k ← $ K : λ(k, t) = λ(k, t ′ ) ) ≤ δ .
λ(k, t) is said to be δ-almost XOR-universal (AXU) if for any distinct t and t ′ ∈ T and any y ∈ Y,

Pr ( k ← $ K : λ(k, t) ⊕ λ(k, t ′ ) = y ) ≤ δ .
While our results do not depend on the repartition of the tweak space, having arbitrary long tweaks is justified by the XTX transformation of Minematsu and Iwata [MI15]. Indeed XTX transforms a tweakable block cipher with a tweak of limited length to one with a tweak of arbitrary length without, in our case, affecting the general iterated tweakable FX structure as it simply affects the subkey functions.

Previous Works

In the same paper where they formalize the concept of tweakable block ciphers, Liskov, Rivest and Wagner proposed two constructions often known as LRW1 and LRW2 [LRW11]. LRW1 consists in adding the tweak between two calls of the block cipher while LRW2 evaluates a keyed universal hash function on the tweak and adds it twice: before the input and after the output of the block cipher. These modes are described as

Ẽk (t, m) = E k (t ⊕ E k (m)) and Ẽk (t, m) = E k (m ⊕ h(t)) ⊕ h(t)
respectively with the requirement that h be an almost XORuniversal function. They also provide security proofs roughly up to 2 n/2 for both schemes. Matching attacks on LRW1 and LRW2 are trivial as they both allow for an easy distinguisher after the first collision at the birthday bound. Other constructions of tweakable block cipher related to LRW2 include XE and XEX by Rogaway [Rog04] and used in the OCB mode of operation.

In the quest for optimal security Mennink proposed the constructions F [1] andF [2] [Men15]. The latter reaches a provable security of 2 n queries which is the optimal security in the standard model for regular block ciphers. Other works tried to build a tweakable block cipher based solely on public permutations in the style of Even- Mansour [EM93]. Such tweakable block ciphers includes TEM [CLS15] and XPX [Men16] that are also subject to a tight birthday bound security of O(2 n/2 ). Then Jha, List, Minematsu, Mishra and Nandi described a framework called XHX [JLM + 17] and proved its security up to 2 (n+κ)/2 . They also describe generalised XHX, GXHX. In particular this means that a provable security beyond 2 n is reachable but in the ideal cipher model where rekeying is possible. This framework uses a single-round FX framework where all 3 subkeys are derived from a universal hash function on the secret master key and an arbitrarily long tweak.

So far, with the exception of GXHX, the proofs of all schemes cited can be shown to be tight. However, things become more involved when trying to iterate those constructions. Landecker et al. [LST12] proposed to iterate two independent evaluations of LRW2 and proved a security up to 2 2n/3 queries. An attack on cascaded LRW2 (or CLRW2) has been later proposed by Mennink [Men18] in query complexity O(2 3n/4 ) not completely closing the gap. Then, recently, Lee and Lee proposed XHX2 [LL18] by iterating two independent rounds of XHX. They managed to prove a query security lower bound of min{2 2 3 (n+κ) , 2 n+κ/2 } and left the tightness of this bound as an open question which we will be able to answer positively in this work.

On the other hand, a generic cryptanalysis of the r-round iterated FX construction has already been made with the original attack by Gaži [Gaž13] in query complexity O( 2r-1 r n+κ ). Obviously this attack can be used against our tweakable version when we fix the tweak to a single value. As it is written, the attack starts by querying all the code books of the secret cipher that makes the maximum possible 2 n calls. However this natural limitation of regular block ciphers has no ground in the presence of tweaks. Much like one can have security proofs beyond 2 n calls, one could attack a tweakable cipher using more than 2 n tweak/plaintext/ciphertext triples.

Results

Our generic iterated tweakable FX framework is pertinent to all cited constructions as shown in Table 1. Using a single-round FX to blend in the tweak is the most common approach and may be considered as well understood. However there seem to be additional security to be gained in iterating those constructions. Some works [LST12] [LL18] tend to do and prove just that. The focus on 2 rounds is justified by the fact that we don't know of any constructions based on block ciphers using more than 2 rounds and the single-round ones mostly have already well understood matching attacks. However we believe it is also Table 1. Some previously proposed schemes and description of how it fits in our iterated tweakable FX generic framework. Multiplications (×) are over the finite field GF(2 n ).

Ref

Scheme r Subkey functions

[LRW11] LRW2 1 λ0(k, t) = λ1(k, t) a uniform and AXU function. γ1(k, t) = k [Men15] F [1] 1 λ0(k, t) = λ1(k, t) = t × k γ1(k, t) = t ⊕ k [Men15] F [2] 1 λ0(k, t) = λ1(k, t) = E1(2 × k, t) γ1(k, t) = t ⊕ k [Men16] XPX 1 κ = 0 so E1(•, m) = P (m) t = t11 ∥ t12 ∥ t21 ∥ t22 λ0(k, t) = t11k ⊕ t12P (k) λ1(k, t) = t21k ⊕ t22P (k) [JLM + 17] XHX 1 γ1(k, t
) a uniform and AU function. λ0(k, t) = λ1(k, t) a uniform and AXU function.

[LRW11] LRW1 2 λ0(k, t) = λ2(k, t) = 0 λ1(k, t) = t γ1(k, t) = γ2(k, t) = k [LST12] CLRW2
2 λ0(k, t) and λ2(k, t) two uniform and AXU functions.

λ1(k, t) = λ0(k, t) ⊕ λ2(k, t) γ1(k, t) = γ2(k, t) = k [LL18] XHX2 2 γ1(k, t
) and γ2(k, t) two uniform and AU functions. λ0(k, t) and λ2(k, t) two uniform and AXU functions.

λ1(k, t) = λ0(k, t) ⊕ λ2(k, t)
interesting to know what kind of security bounds we might hope to achieve by iterating even further.

So in this paper we ask ourselves what is the best security bound attainable when using the iterated FX paradigm for building tweakable block ciphers from regular block ciphers. To do this we improve on the attack described by Gaži [Gaž13] to apply it in the tweakable block cipher setting.

First we show an information theoretic attack for r = 2 rounds when κ ≤ 2n with offline and online query complexity of:

Q = O(2 2 3 (n+κ) • 3 √ κ/n) . Note that Q = O(2 2 3 (n+κ)
) under the reasonable assumption that the size of the master secret key is linear with respect to the state size, that is, κ = O(n).

The recent construction XHX2 by Lee and Lee [LL18] is a particular case of our setting where λ 1 (k, t) = λ 0 (k, t) ⊕ λ 2 (k, t). Their provable security bound is 2 2 3 (n+κ) whenever κ ≤ 2n and therefore matches our attack. Thus our results prove the tightness of their bound and their bound proves the optimality of the attack.

We then extend the attack to multiple rounds of the same construction. This gives an attack on r rounds when κ ≤ rn with query complexity:

Q = O(2 r r+1 (n+κ) • r+1 √ κ/n) . Again note that Q = O(2 r r+1 (n+κ) ) under the assumption that κ = O(n).
Table 2. Some previously proposed schemes with their known asymptotic bounds.

Ref Scheme r Proof Known Attack Our Generic Attack [LRW11] LRW2 1 2 n/2 2 n/2 2 1 2 (n+κ) [Men15] F [1] 1 2 2 3 n 2 n 2 n (as κ = n) [Men16] XPX 1 2 n/2 2 n/2 2 n/2 (as κ = 0) [JLM + 17] XHX 1 2 1 2 (n+κ) 2 1 2 (n+κ) 2 1 2 (n+κ) [JLM + 17] GXHX 1 2 1 2 (n+κ) none 2 1 2 (n+κ) [Men15] F [2] 1 2 n 2 n N.A. [LRW11] LRW1 2 2 n/2 2 n/2 2 2 3 (n+κ) [LST12] CLRW2 2 2 2n/3 2 3n/4 2 2 3 (n+κ) [LL18] XHX2 2 2 2 3 (n+κ) none 2 2 3 (n+κ)

Cryptanalysis of 2-Round Tweakable FX

In this section we give an algorithm to extract the master key of a 2-round tweakable FX construction, Algorithm 1, then we show how it works by deriving the constants used and thus deriving the total query complexity.

The Algorithm

This cryptanalysis of Algorithm 1 is a key recovery attack and follows the idea of the original cryptanalysis by Gaži [Gaž13]: we want just enough data to construct contradictory paths for each wrong key. First we do all the required offline computations under all possible κ-bit key. Input values are the sets S 1 and S 2 which can be chosen randomly and the input/output pairs under the key j are stored in L j,1 and L j,2 for E 1 and E 2 respectively. Then we store all observable tweak/plaintext/ciphertext triples in L 0 . We don't need to choose the set S 0 of inputs to the tweakable block cipher as the attack works in the known plaintext setting. At last we can test all the κ-bit keys; potential master keys k only using the stored values by reconstructing the paths round by round. Indeed sets A and B reconstruct the paths under the current key guess and the condition ∀(t, m, b) ∈ B : (t, m, b ⊕ γ 5 (k, t)) ∈ L 0 is checking whether there is a contradictory path (if not satisfied) or not (if satisfied). The additional condition |B| ≥ ν is simply here to ensure a good reduction.

For completeness we provide Algorithm 2 to show how to construct the sets A and B. To construct A is to apply Algorithm 2 with inputs S 0 , L γ1(k,t),1 , λ 0 (k, t). It is basically looking over all elements of the first set and checking if a shifted version of a value exists somewhere in the second set then, if found, it records the starting and ending values.

The constants ν and Q are derived in Section 2.2 and the algorithm already ensures that the total query complexity is of magnitude Q. Indeed once we construct the sets L j,i and L 0 we will have all the necessary queries to perform Algorithm 2 Set construction. s3)

Input: S1, S2, ℓ Output: S3 ← {( e,
: (e, s1) ∈ S1, (s1 ⊕ ℓ, s3) ∈ S2 } S3 ← ∅ for all (e, s1) ∈ S1 do if ∃s3 : (s1 ⊕ ℓ, s3) ∈ S2 then S3 ← S3 ∪ {(e, s3)} end if end for return S3 to find that in expectation |B| = Q 3 /2 2n+2κ .
With some regularity assumptions, if |B| = ν in expectation then |B| ≥ ν with constant probability. Therefore we put:

Q 3 /2 2n+2κ = ν =⇒ Q = 2 2 3 (n+κ) • 3 √ ν
The Number of Paths. The constant Q was derived so that we don't have false negatives, that is, we succeed with good probability when we guess the good key k. Now we derive the constant ν so that we don't have any false positive that means the test fails with good probability for all the wrong guesses of k.

First notice that the fact that |B| = ν in expectation is true for all guesses of k, good or wrong. If |B| < ν then the test fails as it should. If |B| ≥ ν then we need to look at the second condition that is

∀(t, m, b) ∈ B : (t, m, b ⊕ λ 3 (k, t)) ∈ L 0 . If the guess is wrong then for a given (t, m, b) ∈ B we have (b ⊕ λ 3 (k, t)) = Ẽ(t, m)
with a 2 -n probability. Since |B| ≥ ν then the second condition is satisfied with probability (2 -n ) ν = 2 -ν•n . The test must fail for all the wrong guesses and there are 2 κ -1 such wrong guesses so all the tests should fail at least with constant probability when:

2 κ • 2 -ν•n ≤ 1 =⇒ κ -ν • n ≤ 0 =⇒ ν ≥ κ/n
thus we take ν = κ/n.

Constraints

For all of this to work there are some constraints that need to be spelled out. First we require that:

1 ≤ |S i | ⇐⇒ 1 ≤ 2 2 3 n-1 3 κ • 3 √ ν ⇐⇒ κ ≤ 2n + log(ν)
which limits to possible size of κ to a multiple of the state size n. Very few block ciphers admit a key larger than 2n so this is not a strong limitation in practice.

We also need to have diverse tweakable subkeys. Indeed so far we did not require that the functions γ i (k, t) depends on t which means that the tweak can be put, or not, at any stage of the construction but we still require that the tweak changes something. Therefore we can deduce such requirement:

∀k ∈ {0, 1} κ ∀(t, m) ∈ S 0 ∀(t ′ , m ′ ) ∈ S 0 : t ̸ = t ′ =⇒ ∃i : γ i (k, t) ̸ = γ i (k, t ′ ) OR λ i (k, t) ̸ = λ i (k, t ′ )
which means that for every pairs of two different observed tweaks at least one of the respective implied subkeys must be different. This condition mostly ensure that this is a reasonable tweakable block cipher construction. Indeed in the case where two tweaks imply the exact same subkeys then one can quickly realise that it gets the same permutation for two different tweaks which is a near zero probability event for a perfect tweakable block cipher and hence it's a distinguisher.

Cryptanalysis of r-Round Tweakable FX

Starting from the attack of Section 2 we show how to generalise it to attack r ≥ 1 rounds of the same construction in

Q = O(2 r r+1 (n+κ) • r+1 √ κ/n) query complexity.
The strategy is the same, we begin by doing all the necessary queries before reconstructing paths round by round to finally check whether there is a contradictory path or not. This is Algorithm 3.

Constants and Complexity

The Query Complexity. We derive the constant Q used in Algorithm 3 in the same way as we did for the 2-round version. First we focus on what happens when we guess the correct master key k. In that case we want to make sure that |B| ≥ ν happens with good probability as contradictory paths cannot exist under the correct key. Let's look at the set A 1 :

A 1 ← {( t, m, a ) : (t, m) ∈ S 0 , (m ⊕ λ 0 (k, t), a) ∈ L γ1(k,t),1 }
probability when:

2 κ • 2 -ν•n ≤ 1 =⇒ κ -ν • n ≤ 0 =⇒ ν ≥ κ/n
thus we take ν = κ/n. For all of this to work there are again some constraints. First we require that:

1 ≤ |S i | ⇐⇒ κ ≤ rn + log(ν)
which limits to possible size of κ to a multiple of the state size n.

Then we have the condition that the tweak changes something:

∀k ∈ {0, 1} κ ∀(t, m) ∈ S 0 ∀(t ′ , m ′ ) ∈ S 0 : t ̸ = t ′ =⇒ ∃i : γ i (k, t) ̸ = γ i (k, t ′ ) OR λ i (k, t) ̸ = λ i (k, t ′ )
Notice that this condition prevents the known matching attack on XHX. Indeed, as for XHX r = 1 and λ 0 = λ 1 , a collision on the full subkeys is expected after trying O(2 (n+κ)/2 ) different tweaks. Our attack has the same complexity and also work on the generalised setting GXHX that doesn't enforce λ 0 = λ 1 . This shows that the security cannot improve even if a collision on the full subkeys is made hard by, for example, choosing many different subkey functions or by using a mode of operation that limits the amount of different observable tweaks.

Discussion

Using Tweakable Block Ciphers. If instead of regular block ciphers we use tweakable block ciphers then it is not trivial to adapt this attack. Indeed we use the fact that the master key and the tweak must be blended before computation and not separately plugged in a tweakable block cipher. Such construction of a tweakable block cipher based on another tweakable block cipher could be used to increase security and/or the size of the tweak in a way that the original FX construction builds a stronger block cipher from another block cipher. However on the cryptanalysis side what can always be done is to fix a single tweak and apply the original attack by Gaži

[Gaž13] in query complexity O(2 r-1 r n+κ ) or O(2 r r+1 (n+κ) ) when κ ≤ n r .
Weaker Constructions. This attack is generic given any reasonable key schedule represented by the λ and γ functions. However they are particular cases where better attacks are possible. In particular the cascaded LRW2 construction is a 2-round tweakable FX construction where the key in the block cipher does not vary with the tweaks (γ 1 and γ 2 don't depend on t). This construction permits an attack in O(2 3n 4 ) by Mennink [Men18] using only two different tweaks which beats our generic attack as soon as κ > n 8 .

Tweak-rekeying. In fact our generic attack being a key recovery attack it will require at least 2 κ calls to the underlying block cipher. As soon as k ≥ n this implies a complexity above 2 n . Mennink [Men17] showed that provable 2 n security is unattainable in the standard block cipher model used for the proofs of schemes without tweak-rekeying. Therefore our generic attack can only hope to be tight for schemes that use tweak-rekeying and thus that are proved in the ideal block cipher model.

Key recovery and distinguisher. The fact that the complexity of this cryptanalysis depends on the size of the master key, even if a little, makes it hardly comparable to distinguishers that are independent of the master key size. Instead of waiting for some bad event to occur we collect just enough information to completely determine the master key. In the case of XHX the known distinguisher has the same asymptotic complexity but the widely different approaches make them hard to combine: a bad event for the known distinguisher gives no information on the master key. However for XHX2, and generally for r ≥ 2 rounds of the tweakable FX construction proved in the ideal cipher model, it may well be the case that a key recovery approach is more relevant than looking for a suitable bad event for a distinguisher.

Towards Simplicity. The attack on generic 2-round tweakable FX is also tight since Lee and Lee could prove with XHX2 [LL18] that we can reach this level of security even when λ 1 (k, t) = λ 0 (k, t) ⊕ λ 2 (k, t) with some conditions on those functions. Moreover the previously known matching attack on XHX [JLM + 17] exploited the fact that λ 0 (k, t) = λ 1 (k, t) but our generic attack shows that it cannot be made more secure without this simplification. Another way to say it is that enforcing λ 0 (k, t) = λ 1 (k, t) does not affect the provable security bound. Using this iterated tweakable FX paradigm, one can therefore wonder how much it is possible to simplify the subkey functions while maintaining an optimal provable security with respect to the generic security upper bound shown in this work.

  m

Acknowledgement

The author would like to thank the 2018 Asian Symmetric Key Workshop and Gaëtan Leurent for useful discussions. This work was partially supported by the French DGA.

Algorithm 1 Cryptanalysis of 2-round tweakable FX construction.

Input: κ, n, κ ≤ 2n, Ẽ, E1, E2, γ1, γ2, λ0, λ1, λ2 Output: k : the master key of

and there are 2 κ different possible subkeys then the total number of queries to E 1 and E 2 is Q. Then we also construct L 0 so the number of online queries will also be

Deriving The Constants

The Query Complexity. To derive the constant Q used in Algorithm 1 we first focus on what happens when we guess the correct master key k. In that case we want to make sure that |B| ≥ ν happens with good probability as the other constraint is always true by construction of the scheme. First let's look at the set A:

By construction there are Q values (t, m) ∈ S 0 and, as S 1 is chosen randomly and independently, there is a |S 1 |/2 n probability that (m ⊕ λ 0 (k, t)) ∈ S 1 for each (t, m) observed and thus that there exists an a such that (m ⊕ λ 0 (k, t), a) ∈ L γ1(k,t),1 . Therefore in expectation we have |A| = Q 2 /2 n+κ . We do the same reasoning for B:

Algorithm 3 Cryptanalysis of r-round tweakable FX construction.

Input: κ, n, κ ≤ rn, Ẽ, E1, E2, ..., Er,γ1,γ2,...,γr,λ0,λ1,λ2,..., ) for all observed tweak/message pairs (t, m). Therefore, in expectation, we have

Then we can easily prove by induction that n+κ) .

With some regularity assumptions, if in expectation |A r | = ν then |A r | ≥ ν with constant probability. Therefore we put:

The Number of Paths. The constant Q was derived so that we avoid false negative when we guess the good key k. Now we derive the constant ν to avoid false positives.

If |A r | < ν then the test fails as it should. If |A r | ≥ ν then the second condition is satisfied with probability (2 -n ) ν = 2 -ν•n . The test must fail for all the 2 κ -1 wrong guesses so all the tests should fail at least with constant