Elmokhtar Mohamed Moussa
email: elmokhtar.mohamed.moussa@myscript.com

Thibault Lelore
email: thibault.lelore@myscript.com

Harold Mouchère
email: harold.mouchere@univ-nantes.fr

Point to segment distance DTW for online handwriting signals matching

Keywords: Handwriting Matching, DTW Metric, Sampling invariance

In this paper, we propose DTW seg , a modified DTW algorithm based on a point-to-segment distance instead of the euclidean point-to-point distance. Applying DTW seg to online handwriting matching proves to be advantageous compared to other algorithms as it is less sensitive to differences between signals sampling rates occurring due to acquisition frequencies or handwriting speed. It eliminates the need for a commonly practiced resampling that omits an important dynamic part of the ductus. Experiments on IRONOFF french words dataset and FLOWCHARTS dataset show DTW seg to be least impacted by sampling rate alterations. We also propose a new benchmark of state-of-the-art methods on offline handwriting to online conversion based on our new proposed metric.

INTRODUCTION

Pen and paper have been used for hundreds of years by humans to record their activities, ideas, creations. . . The digitization and processing of documents have changed their usage: historians can access ancient material easily, and companies created Electronic Document Management Systems to improve their process. These images of documents are called offline documents. In recent years, with the emergence of digital tablets and touch screens, new usages appear and new types of documents are created with handwritten digital content: online documents. Online documents and offline documents share the same downstream processing task: document classification, document segmentation, handwriting recognition, and writer identification, etc. but often with different approaches due to the different nature of their respective input source. On the one hand, offline content is stored as matrices of pixels and on the other hand, online documents are recorded as the pen trajectory on a surface tablet represented as a time series of x and y coordinates, in addition to other motion measures (pen pressure, velocity, etc.).

This work focuses on the comparison of handwritten samples of the online domain. It is useful for many applications including handwriting trajeca https://orcid.org/0000-0002-7083-2422 b https://orcid.org/0000-0001-6220-7216 tory reconstruction from IMU-enhanced pen [START_REF] Wehbi | Surface-Free Multi-Stroke Trajectory Reconstruction and Word Recognition Using an IMU-Enhanced Digital Pen[END_REF] where synchronization between the pen and recording tablet surface is challenging due to the difference in sampling rates and acquisition start and end. Other applications include signature verification [START_REF] Sharma | On the Exploration of Information From the DTW Cost Matrix for Online Signature Verification[END_REF], template matching for content clustering, keyword (or shape) spotting [START_REF] Szoke | Comparison of keyword spotting approaches for informal continuous speech[END_REF], and due to recent advances in research topics such as online handwriting synthesis [START_REF] Graves | Generating Sequences With Recurrent Neural Networks[END_REF], offline handwriting to online conversion [START_REF] Kato | Recovery of drawing order from single-stroke handwriting images[END_REF], the need for pertinent online handwriting quality evaluation metrics of the generated online handwriting is becoming more acute. Matching of two online signals is commonly done using linear interpolation alignment which deteriorates important temporal and spatial dynamics. DTW [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] algorithm provide an elastic alignment capable of matching signals of different lengths. However, in our handwriting-specific case, it can portray a very negative matching for handwriting with similar directions and spatial arrangements as in Figure 1. We propose a new cost function based on the segment-to-point distance to compute DTW. It has the advantage to minimize the impact of the sampling rate. Our modified DTW is presented in Section 3. In Section 4, we experiment and compare our metric to classic DTW on different datasets and state-of-the-art offline handwriting to online conversion approaches.

RELATED WORKS

DTW has been used in a wide range of document analysis applications. Here we focus on recent hand-writing analysis subtopics: online handwriting synthesis and offline to online conversion. Other notable, applications such as isolated character recognition [START_REF] Bahlmann | Online handwriting recognition with support vector machines -a kernel approach[END_REF] can also be cited.

Online handwriting synthesis

This aims to generate the handwriting of a given text with neural networks [START_REF] Graves | Generating Sequences With Recurrent Neural Networks[END_REF]. The generation is usually conditioned on a given writer and outputs convincing handwriting regarding the writing style, making online handwritten documents easily editable [START_REF] Aksan | DeepWriting: Making Digital Ink Editable via Deep Generative Modeling[END_REF]. Matching the neural network predictions to ground truth online signals is essential to train such deep learning approaches. The MSE loss is ubiquitous in state-of-the-art methods, implying that the neural network has also to learn the exact correct sampling rate of the resampled ground truth signal, creating small misleading artifacts in many cases. Defining a loss function with more meaningful feedback on the general ductus rather than sampling rate artifact can help further improve the generative models. Following that line, (Ji and Chen, 2020) employed a CNN-LSTM discriminator combined with Graves Generator [START_REF] Graves | Generating Sequences With Recurrent Neural Networks[END_REF] in an adversarial training framework to obtain more realistic handwriting.

Offline conversion to online handwriting

Given a static offline handwritten document, the goal here is to recover the temporal information of the pen trajectory and thus an online document. This could be used mainly for two reasons: use the existing online tool as a recognizer; or allow the user to edit his content as a vectorized image (instead of a flat image). The retrieved trajectory should be as faithful as possible to the writer's offline document. Such systems [START_REF] Chan | Stroke Extraction for Offline Handwritten Mathematical Expression Recognition[END_REF] are often evaluated using word error rate when intended for offline recognition. WER presents a useful insight into the semantic coherence of online reconstruction. However it presents a major drawback, depending on the complexity of the recognition systems, the correct word can be recognized even if online reconstruction is unfaithful e.g. slanting and rotation don't usually affect recognizers. Root Mean Square Error (RMSE) and Dynamic Time Warping algorithm (DTW) [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] are commonly proposed as evaluation metrics [START_REF] Hassaïne | ICDAR 2013 Competition on Handwriting Stroke Recovery from Offline Data[END_REF][START_REF] Phan | Triangulation Based Skeletonization and Trajectory Recovery for Handwritten Character Patterns[END_REF][START_REF] Dinh | Recovery of drawing order from multistroke English handwritten images based on graph models and ambiguous zone analysis[END_REF][START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF][START_REF] Moussa | Applying End-to-End Trainable Approach on Stroke Extraction in Handwritten Math Expressions Images[END_REF][START_REF] Diaz | Writing Order Recovery in Complex and Long Static Handwriting[END_REF]

PROPOSED METRIC

We first present the classical DTW and then our proposed DTW-seg.

DTW

DTW algorithm computes the optimal alignment between two signals of different lengths. It allows for elastic one-to-many matching. A cumulative cost

C N×M matrix is constructed using a L2 distance func- tion f (x i , xi ) = x i -xi 2 .
DTW algorithm find a warping path w = {w p = (i, j) ∈ N N×M } P p=1 minimizing equation 2 and satisfying the following constraints:

• boundaries: w 1 = (1, 1) ∧ w P = (N, M)

• monotonicity: let w p = (i, j) and w p+1 = (i , j ) then i ≤ i ∧ j ≤ j

• continuity: i ≤ i + 1 ∧ j ≤ j + 1 This optimization is solved by recursively updating the cumulative cost matrix with equation 3.

DTW (x, x) = min w∈W P ∑ p=1 f (w p ) f (w p ) = f (x i , x j ) (2) C i j = f (x i , x j ) + min    C i, j-1 C i-1, j-1 C i-1, j (3)
DTW distance is defined as the cumulative cost of w equal to C NM normalized by the warping path length. Figure 3 shows an example of DTW algorithm output. In this work, we focus on defining a sampling rate invariant cost function f .

DTW-seg

Let x i a point and [ x j , x j+1 ] a segment between two consecutive elements, we define a point to segment cost function, as illustrated in Figure 3, by:

a = ---→ x j x j+1 , b = -→ x j x i , c = ---→ x j+1 x i g(x i , [ x j , x j+1 ]) =      a • b < 0, f (x i , x j ) ← -a • c < 0, f (x i , x j+1 ) else, pro j a b 2 (4)
Replacing f by g as a cost function in equations 2 and 3 we define DTW seg which minimizes the alignment cost changes w.r.t. variation in the sampling rate.

The special case that needs to be mentioned, as illustrated by figure 4, is that of a point distance to a segment between a stroke end and the next stroke start. In this case, the segment is considered invalid and thus omitted.

EXPERIMENTS

To demonstrate the sensitivity to resampling of RMSE, DTW and our DTW seg metric, we experiment

x i x j x j+1 - → a - → b (a) - → a • - → b < 0 x i x j x j+1 ← -a - → c (b) ← -a • - → c < 0 x i x j x j+1 - → a - → b pro j-→ a - → b (c) 0 ≤ - → a • - → b a 2 ≤ 1 Figure 3: Point to segment distance. x i x j x j+1 x j+2 x j+3
stroke 1 stroke 2

Invalid

Figure 4: Query point x j lays between two reference stroke extremities x j+1 and x j+2 . However, this segment is ignored and x j can either be aligned with valid stroke segments

[ x j , x j+1 ] or [ x j+2 , x j+3 ].
with different spatial resampling strategies:

• Equidistant linear resampling with distance d;

• Simple moving average (SMA) with previous 2 points:

x t = x t + x t-1 2 We used the validation set of IRONOFF [START_REF] Viard-Gaudin | The IRESTE On/Off (IRONOFF) dual handwriting database[END_REF] containing 19, 888 words and the FLOWCHARTS [START_REF] Awal | First experiments on a new online handwritten flowchart database[END_REF] validation set with 172 flowcharts. Table 1 shows that DTW seg is relatively small after oversampling or moving average transformations compared with classic DTW . The aforementioned transformations degrade the spatial information of the signals the least compared to subsampling yet the reported DTW and RMSE are high. DTW is observed to be the highest when subsampling IRONOFF with d = 10 in comparison, DTW seg is one and a half folds smaller. For FLOWCHARTS when subsampling with d = 15, DTW seg is 3 folds smaller than DTW .

In addition, we use our metric to benchmark stateof-the-art offline handwriting to online conversion approaches, namely, [START_REF] Chan | Stroke Extraction for Offline Handwritten Mathematical Expression Recognition[END_REF], [START_REF] Diaz | Writing Order Recovery in Complex and Long Static Handwriting[END_REF] and [START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF]. Using their public official implementations. We also include an internal rule-based method based on a smoothness criterion. Table 2 shows the results of their evaluations on the validation set of IRONOFF dataset. Synthetic offline images, with a stroke width randomly chosen rics rank the different approaches in the same manner. All of the previously mentioned approaches predict oversampled online signals therefore they have a bigger DTW alignment cost compared to DTW seg . In fact, [START_REF] Chan | Stroke Extraction for Offline Handwritten Mathematical Expression Recognition[END_REF] approach is ranked second, closely trailing behind our Internal approach. It is to be noted that [START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF] is based on a data-driven CNN-LSTM trained only on English IAM [START_REF] Marti | The IAM-database: An English sentence database for offline handwriting recognition[END_REF] 5a shows that [START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF] prediction is overall the best in this particular instance. In fact, figures 5c and 5b tend to oversim- plify small loops, the latter is also missing a portion of the last small ending. Since all of the mentioned methods infer oversampled signals, DTW seg is shown to be the metric that best evaluates the inherent signal directions and spatial arrangement with minimal regard to sampling frequencies.

DISCUSSION

This work focuses on improving the matching of similar online handwriting signals with different sampling frequencies. This variability occurs when recording simultaneously on multiple devices or due to the natural variance in human writing velocity. Another challenging extension, which is out of the scope of this paper, is the invariance to stroke direction inversion (e.g. crossing a t with a left-to-right or right-to-left stroke) and stroke permutation (e.g. letter x in Figure 2). In fact, DTW's strict continuity constraints make it such that those small handwriting preferences are assigned a very important alignment cost which can hinder the performance of downstream tasks. [START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF] employs a DTW loss function that finds the permutation of consecutive pairs of strokes and stroke direction that minimizes the alignment cost. This approach does not deal with longer-range permutations such as crossing or dotting. [START_REF] Li | A Multi-stroke Dynamic Time Warping Distance Based on A* Optimization[END_REF] proposed a more complete multi-stroke DTW based on the A* star algorithm to overcome the combinatorial explosion of alignment hypothesis. However, it is still difficult to upscale to the word level and beyond.

  (a) Query and reference online signals. Notice the sampling rate variation between the two. (b) On the left linear alignment RMSE = 0.53 which require a spatial resampling of both signal and on the right DTW alignment total 1.65, without resampling.

  (c) Proposed point to segment DTW with a total alignment cost of 0.25, without resampling.

Figure 1 :

 1 Comparison between classic online handwriting alignment methods and the proposed DTW segment method.DTW seg alignment is observed to best match the query to the reference signal.

  of the reconstructed online signal w.r.t. to the ground-truth online signal. RMSE (cf. equation 1) is a one-to-one mapping that mea-sures the distance between two temporal signals x t and xt of lengths N and M respectively. If N = M and the signals are well aligned (same frequency and in phase) RMSE is a straightforward measure of the distance between them. Nevertheless, in many cases where the signals are not perfectly aligned (stretched or compressed at different time windows, out of phase etc.) the pairing becomes far less obvious.

  (a) Accumulated cost matrix and the associated warping path in red.(b) Warped time series. The query letter x stroke order is permuted compared to the reference and its strokes don't cross.

Figure 2 :

 2 DTW algorithm output for two online words.

  (a)[START_REF] Archibald | TRACE: A Differentiable Approach to Line-Level Stroke Recovery for Offline Handwritten Text[END_REF]. RMSE = 3.09, DTW = 1.08, DTW seg = 0.58.(b)[START_REF] Chan | Stroke Extraction for Offline Handwritten Mathematical Expression Recognition[END_REF]. RMSE = 7.32, DTW = 1.88, DTW seg = 1.65 (c) Internal method inference. RMSE = 3.12, DTW = 1.36, DTW seg = 1.01 Figure5: Comparison of SoTA methods for online signal reconstruction from offline. Inferences are in black, ground truth is in blue.

Table 1 :

 1 Evaluation of different resampling strategies with DTW and DTW seg . Linear spatial interpolation resampling with distance d ∈ {2, 5, 10, 15} and SMA: simple moving average.between one and three pixels, are rendered from the ground truth online. We observe that the three met-

	Dataset	resampling RMSE ↓ DTW ↓ DTW seg ↓
		d=2	1.19	1.38	0.32
		d=5	2.43	1.64	0.76
	IRONOFF	d=10	4.35	2.87	1.90
		SMA	3.01	1.89	0.78
		d=2	29.03	8.04	0.25
		d=5	42.43	7.81	0.60
	FCs	d=10 d=15	58.46 72.43	7.66 7.73	1.29 2.04
		SMA	64.99	6.03	1.82
	Approach		DTW ↓ DTW seg ↓ RMSE ↓
	Internal [Private]	5.00	4.40	11.94
	(Chan, 2020)		5.64	5.06	12.89
	(Archibald et al., 2021) 8.10	7.45	15.77
	(Diaz et al., 2022)	22.71	21.81	33.14

Table 2 :

 2 stroke extraction SoTA evaluation on IRONOFF.

CONCLUSIONS

In this paper, we presented DTW seg , a modified DTW algorithm based on a segment-to-point cost function dedicated to online handwriting matching. We showed that classical matching approaches such as RMSE and DTW distance overstate the sampling rate's importance. DTW seg , on the other hand, matches more closely signals differing in sampling rates. We also benchmark SoTA for offline to online conversion with DTW seg . In future work, we will study the definition of a loss function (Cuturi and Blondel, 2018) based on DTW seg to train a neural network for the offline to online conversion online task. We hypothesize that DTW seg provides more meaningful information as its gradient pushes the network's predictions to be closer to the signal as a whole rather than a single point from the signal.


Christian Weymann

Salia Cherifi-Hertel

Céline Lichtensteiger

Iaroslav Gaponenko

Kokou Dodzi Dorkenoo

Aaron B Naden

Patrycja Paruch

Non-Ising domain walls in c-phase ferroelectric lead titanate thin films

Ferroelectrics are technologically important, with wide application in micromechanical systems, nonlinear optics, and information storage. Recent discoveries of exotic polarization textures in these materials, which can strongly influence their properties, have brought to the forefront questions about the nature of their domain walls: long believed to be primarily Ising, with locally null polarization. Here, combining three complementary techniques-second-harmonic generation microscopy, piezoresponse force microscopy, and transmission electron microscopy-to cover all the relevant length scales, we reveal the Néel character (non-Ising polarization oriented perpendicular to the wall) of 180 • domain walls in c-phase tetragonal ferroelectric lead titanate epitaxial thin films, for both artificial and intrinsic domains at room temperature. Furthermore, we show that variations in the domain density-detected both optically and via local piezoresponse and then quantified by radial autocorrelation analysis-can give us insight into the underlying defect potential present in these materials.

Ferroelectric materials are characterized by their spontaneous and reversible electrical polarization, with a wide variety of technological applications as microelectromechanical systems (MEMSs) and memory devices [START_REF] Setter | Ferroelectric thin films: Review of materials, properties, and applications[END_REF]. The electromechanical properties of these materials are closely linked to their domain structure. As such, understanding and controlling the arrangement of domains with different polarization orientation remains a key research objective. In addition, the boundaries between these, i.e., domain walls, can themselves present emergent properties [START_REF] Seidel | Conduction at domain walls in oxide multiferroics[END_REF][START_REF] Guyonnet | Conduction at domain walls in insulating Pb(Zr 0.2 Ti 0.8 )O 3 thin films[END_REF][START_REF] Daraktchiev | Landau theory of domain wall magnetoelectricity[END_REF] potentially attractive for domain-wall-based nanoelectronics [START_REF] Catalan | Domain wall nanoelectronics[END_REF][START_REF] Meier | Anisotropic conductance at improper ferroelectric domain walls[END_REF]. Their complex (de)pinning dynamics when driven by an electric field [START_REF] Paruch | Nanoscale studies of ferroelectric domain walls as pinned elastic interfaces[END_REF] have, in particular, given rise to varied implementations as nanoscale active device components [START_REF] Whyte | Ferroelectric domain wall injection[END_REF][START_REF] Mcgilly | Controlling domain wall motion in ferroelectric thin films[END_REF].

Ferroelectric materials were long believed to present essentially Ising-type 180 • domain walls, in which the polarization is maintained along the bulk axis, decreasing to zero and reversing its orientation at the domain wall center. However, extensive theoretical studies [START_REF] Lee | Mixed Bloch-Néel-Ising character of 180 • ferroelectric domain walls[END_REF][START_REF] Marton | Domain walls of ferroelectric BaTiO 3 within the Ginzburg-Landau-Devonshire phenomenological model[END_REF][START_REF] Stepkova | Stress-induced phase transition in ferroelectric domain walls of BaTiO 3[END_REF][START_REF] Marton | Divergence of dielectric permittivity near phase transition within ferroelectric domain boundaries[END_REF][START_REF] Wang | Chiral phase transition at 180 • domain walls in ferroelectric PbTiO 3 driven by epitaxial compressive strains[END_REF][START_REF] Wojdeł | Ferroelectric Transitions at Ferroelectric Domain Walls Found from First Principles[END_REF][START_REF] Eliseev | Structural phase transitions and electronic phenomena at 180-degree domain walls in rhombohedral BaTiO 3[END_REF] have predicted non-Ising polarization components oriented either perpendicular to the wall (Néel type) or in the plane of the wall (Bloch type). Previously, the existence of Néel-type domain walls has been demonstrated in Pb(Zr,Ti)O 3 [START_REF] Wei | Néel-like domain walls in ferroelectric Pb(Zr,Ti)O 3 single crystals[END_REF][START_REF] De Luca | Domain wall architecture in tetragonal ferroelectric thin films[END_REF][START_REF] Cherifi-Hertel | Non-Ising and chiral ferroelectric domain walls revealed by nonlinear optical microscopy[END_REF], in addition to the presence of chiral Bloch walls and Bloch lines, a particular type of ferroelectric topological structure, in LiTaO 3 [START_REF] Cherifi-Hertel | Non-Ising and chiral ferroelectric domain walls revealed by nonlinear optical microscopy[END_REF]. Additional exotic polarization structures, such as arrays of polar vortices [START_REF] Yadav | Observation of polar vortices in oxide superlattices[END_REF], "supercrystals" of highly ordered flux closure domains [START_REF] Stoica | Optical creation of a supercrystal with three-dimensional nanoscale periodicity[END_REF][START_REF] Hadjimichael | Ferroelectric domains in lead titanate heterostructures[END_REF][START_REF] Hadjimichael | Metal-ferroelectric supercrystals with periodically curved metallic layers[END_REF], and even ferroelectric skyrmions [START_REF] Gonçalves | Theoretical guidelines to create and tune electric skyrmion bubbles[END_REF][START_REF] Das | Observation of room-temperature polar skyrmions[END_REF] have also recently been reported. In the canonical tetragonal ferroelectric PbTiO 3 , hosting many of these emergent exotic polarization textures, various theoretical calculations predict either Néel walls [START_REF] Lee | Mixed Bloch-Néel-Ising character of 180 • ferroelectric domain walls[END_REF][START_REF] Behera | Structure and energetics of 180 • domain walls in PbTiO 3 by density functional theory[END_REF] such as those observed in Pb(Zr 0.2 Ti 0.8 )O 3 [START_REF] De Luca | Domain wall architecture in tetragonal ferroelectric thin films[END_REF][START_REF] Cherifi-Hertel | Non-Ising and chiral ferroelectric domain walls revealed by nonlinear optical microscopy[END_REF], of which it is one of the parent compounds, or a low-temperature Ising-to-Bloch transition at the domains walls [START_REF] Wojdeł | Ferroelectric Transitions at Ferroelectric Domain Walls Found from First Principles[END_REF]. Metastable bubble domains observed in PbTiO 3 thin films [START_REF] Zhang | Nanoscale bubble domains and topological transitions in ultrathin ferroelectric films[END_REF], with no strong delineation between the domain wall and interior, further suggest that the polarization in this material can be extremely "soft" and easy to reorient in either Bloch-or Néel-like textures under specific electrostatic and strain boundary conditions.

In this context, we set out to characterize the nature of 180 • domain walls in PbTiO 3 . Our work is based on three 50-nm PbTiO 3 thin films deposited by rf-magnetron sputtering on LaNiO 3 electrodes on single-crystal (001) SrTiO 3 substrates, with an intrinsic domain configuration governed by the interplay between mechanical and electrostatic boundary conditions [START_REF] Lichtensteiger | Tuning of the depolarization field and nanodomain structure in ferroelectric thin films[END_REF][START_REF] Lichtensteiger | Built-in voltage in thin ferroelectric PbTiO 3 films: The effect of electrostatic boundary conditions[END_REF] and additionally controlled via growth temperature defect engineering [START_REF] Weymann | Full control of polarization in ferroelectric thin films using growth temperature to modulate defects[END_REF]. Using piezoresponse force microscopy (PFM) and second-harmonic generation (SHG), we find that Néel-like behavior dominates at artificial domain walls introduced by local electric field switching of polarization. By combining PFM and careful analysis of transmission electron microscopy (TEM) data, we show that the same is true for naturally occurring domain walls in polydomain samples. Finally, we also show that it is possible to extract information on the underlying pinning potential by additional SHG and PFM image treatment and analysis based on autocorrelation.

In the out-of-plane up-oriented monodomain film, domains were patterned by applying relatively high bias to the scanning probe microscopy tip, first +10 V to switch a 6 × 6 µm 2 square and then -10 V in a 3 × 3 µm 2 square in the center, as shown in Fig. 1(a), ensuring a well-spaced square-in-square domain structure whose walls could be easily individually resolved by SHG. From the anisotropic SHG image [Fig. 1(b)], a localized second-harmonic emission is observed at the domain wall regions, demonstrating their non-Ising polar character. Additional polarimetry analysis was performed on this region for different polarizer and analyzer angle combinations. The written domain walls are clearly visible in the SHG image only when the analyzer is perpendicular to the wall plane, as shown in Figs. 1(c) and 1(d). We can thus conclude that in this case, the domain walls present an in-plane polarization component with a purely Néel-type configuration, as similarly observed in the related material Pb(Zr 0.2 Ti 0.8 )O 3 [START_REF] Cherifi-Hertel | Non-Ising and chiral ferroelectric domain walls revealed by nonlinear optical microscopy[END_REF].

For polydomain samples, vertical PFM imaging shows alternating regions with up-and down-oriented domains, of the order of a few tens of nanometers across, as can be seen in Fig. 2(a). At these length scales it impossible to individually resolve domain walls and determine their nature via SHG polarimetry, but non-negligible contrasts in the measured intensity point to the presence of in-plane polarization (as we will discuss further later). We therefore turn to scanning transmission electron microscopy (STEM) to visualize the individual atomic displacements contributing to the macroscopic polarization. TEM measurements were performed on an ≈30 nm lamella prepared with the long axis parallel to the [100] in-plane axis of the thin film, as schematically indicated by the green box in Fig. 2(a). Capturing a domain wall perfectly edge-on in such a lamella is unlikely, and we thus expect to observe a projection of the wall, in which case the TEM measurements would average over the two opposing out-of-plane polarization orientations of the domains as well as any Néel or Bloch domain wall polarization, as schematically indicated in Figs. 2(b) and 2(c), respectively.

Figure 3(a) shows a low-magnification differential phase contrast (DPC) STEM image where the color scale indicates the direction and relative magnitude of the deflection of the STEM probe due to diffraction and Lorentz deflection. Within the PbTiO 3 film, elongated linear features between regions of relatively homogeneous contrast can be identified, appearing dark red and thus indicating an increased in-plane deflection component. These features appear narrower and vertically oriented near the film surface and then gradually broaden and curve towards the interface of the film with the back electrode and substrate. We therefore focused on the near-surface region, to enhance the probability of their edge-on alignment. The red box demarcates an area imaged at atomic resolution in the high-angle annular dark-field (HAADF) image in Fig. 3(b). Here, the abrupt feature in the center can be seen to From this schematic representation, it is clear that domain walls are highly unlikely to align through the TEM lamella thickness, but will rather meander, leading to averaging over different polarization orientations in the TEM cross-section measurements. For a wall that is not imaged edge-on, i.e., orthogonal to the plane of the lamella, the two possible polarization configurations at the wall [(b) and (c)] could lead to similar projections. manifest as a distinct shift in the Pb atom positions, resulting in an apparent "kink" in the Pb lattice (the brightest atom columns). This confirms the prediction of Aguado-Puente and Junquera for 180 • domain walls in PbTiO 3 thin films [START_REF] Aguado-Puente | Structural and energetic properties of domains in PbTiO 3 /SrTiO 3 superlattices from first principles[END_REF] and is very similar to the Bi-lattice kink observed in BiFeO 3 related to the polarization rotation and accumulation of charged defects at domains walls [START_REF] Rojac | Domain-wall conduction in ferroelectric BiFeO 3 controlled by accumulation of charged defects[END_REF]. Furthermore, it can be seen from Fig. 3(b) and its cropped version shown in Fig. 3(c) that the Ti atom columns sit closer to the center of the unit cell on the left whereas they are near the bottom of the unit cell on the right. In other words, there is evidently a greater out-of-plane component of polarization on the right since this is closely linked to the B-site cation displacement from the centrosymmetric position within the unit cell [START_REF] Shirane | Soft ferroelectric modes in lead titanate[END_REF]. This observation therefore suggests the presence of a domain wall in the center of the image.

In order to accurately determine the atom positions and hence polarization, we perform two-dimensional (2D) Gaussian fitting to the Pb and Ti atom columns which offers subpixel precision [START_REF] Yankovich | Picometre-precision analysis of scanning transmission electron microscopy images of platinum nanocatalysts[END_REF][START_REF] Wang | Atomic level 1D structural modulations at the negatively charged domain walls in BiFeO 3 films[END_REF][START_REF] Bencan | Atomic scale symmetry and polar nanoclusters in the paraelectric phase of ferroelectric materials[END_REF]. From this, we can determine a number of factors that can confirm the presence of a domain wall: the c-axis d spacing and the c-a angle (the angle between the [100] and [001] directions), as shown in the averaged line profiles in Fig. 3(d), which go from left to right in Fig. 3(b). In addition, we can also determine the ellipticity of the atom columns-shown in Fig. 3(e)-which gives a measure of the disorder through the thickness of the lamella: An ideally ordered column of atoms would appear perfectly circular. From the profiles in Figs. 3(d) and 3(e), it is clear that the kink observed in Figs. 3(b) and 3(c) coincides with an increase in the c-a angle and in both the Pb and Ti ellipticities. One can also note a concomitant decrease in out-of-plane lattice parameter c, although within the error bars. Crucially, all of this occurs over approximately two to three unit cells and coincides with an increase in the in-plane component of the polarization defined by the displacement of the Ti columns from the center of the unit cell given by the Pb atoms, as shown in Fig. 3(e).

To deconvolute the different domain contributions, we fit three 2D Gaussians to each of the Ti atom columns: two corresponding to the Ti atom shifts up and down relative to the mean position given by the single Gaussian fitting and one corresponding to the "mean" position between the first two. This approach is analogous to the MPFIT algorithm proposed previously [START_REF] Mukherjee | mpfit: A robust method for fitting atomic resolution images with multiple Gaussian peaks[END_REF]. We can then reconstruct the dominant polarization from these three components, discarding extraneous effects from projection. We note, however, that the displacement of the Ti atoms only corresponds exactly to the polarization of the PbTiO 3 if the Born effective charge is constant, which may not be the case at the domain wall. For the sake of brevity, a comprehensive discussion of the procedure is detailed in Supplemental Material [START_REF]L241404 for further information about scanning transmission electron microscopy data acquisition and analysis, radially averaged autocorrelation analysis, Ising model with disorder, non-Ising structure and conductive properties of ferroelectric domain walls, second-harmonic generation, thinfilm growth, and scanning probe microscopy[END_REF] Sec. S1. Figure 3(f) shows the final result of this reconstruction where the image is an interpolated map of the c-a angle with the polarization vectors overlaid. Moving from left to right on the image, a classic Néel-like behavior is observed: The polarization rotates through 180 • from upwards on the left to downwards on the right with a predominantly in-plane orientation in the two to three unit cells at the Pb kink in the center where the c-a angle is maximized and the tetragonality is minimized.

It therefore appears that in our PbTiO 3 thin films, at room temperature, both written and intrinsic domain walls present a Néel character. For the written domain walls, tip-related interactions, e.g., electrochemical alteration of the surface [START_REF] Kalinin | The role of electrochemical phenomena in scanning probe microscopy of ferroelectric thin films[END_REF], could stabilize the polar discontinuity inherent in the Néel structure. For intrinsic domain walls, however, first-principles calculations predict a Bloch character at low temperature and, at higher temperatures, an Ising character with no in-plane component of polarization [START_REF] Wojdeł | Ferroelectric Transitions at Ferroelectric Domain Walls Found from First Principles[END_REF]. Our observations of a Néel component suggest that in real materials such structures are on the contrary at the very least metastable. The polarization discontinuity at domain walls with such a Néel component can be related to domain wall curvature or inclination [START_REF] Acevedo-Salas | Impact of 3D curvature on the polarization orientation in non-Ising domain walls[END_REF]. Such charged structures, including head-to-head or tail-to-tail polarization [START_REF] Jia | Direct observation of continuous electric dipole rotation in fluxclosure domains in ferroelectric Pb[END_REF], could contribute to a higher conductivity at the domain walls [START_REF] Morozovska | Impact of free charges on polarization and pyroelectricity in antiferrodistortive structures and surfaces induced by a flexoelectric effect[END_REF][START_REF] Eliseev | Domain wall conduction in multiaxial ferroelectrics[END_REF][START_REF] Feigl | Controlled stripes of ultrafine ferroelectric domains[END_REF][START_REF] Stolichnov | Bent ferroelectric domain walls as reconfigurable metallic-like channels[END_REF][START_REF] Cao | Role of flexoelectric coupling in polarization rotations at the a-c domain walls in ferroelectric perovskites[END_REF].

Moreover, defects and disorder are a crucial element of ferroelectric thin films, acting as nucleation sites during switching [START_REF] Jesse | Direct imaging of the spatial and energy distribution of nucleation centres in ferroelectric materials[END_REF], pinning domain walls [START_REF] Paruch | Nanoscale studies of ferroelectric domain walls as pinned elastic interfaces[END_REF][START_REF] Blaser | Minimum domain size and stability in carbon nanotube-ferroelectric devices[END_REF][START_REF] Tueckmantel | Local Probe Comparison of Ferroelectric Switching Event Statistics in the Creep and Depinning Regimes in Pb(Zr 0.2 Ti 0.8 )O 3 Thin Films[END_REF], and segregating along them to provide a path for electrical conduction [START_REF] Guyonnet | Conduction at domain walls in insulating Pb(Zr 0.2 Ti 0.8 )O 3 thin films[END_REF][START_REF] Farokhipoor | Conduction through 71 • Domain Walls in BiFeO 3 Thin Films[END_REF][START_REF] Seidel | Domain Wall Conductivity in La-Doped BiFeO 3[END_REF]. Further insight into the defect landscape can be obtained from a comparative analysis of PFM and SHG measurements in another polydomain sample (Fig. 4). The vertical PFM phase response in Fig. 4(a) reveals intrinsic domains of the order of 100 nm, well below the diffraction limit for the wavelength used in SHG measurements (∼300 nm). When comparing with the image obtained by SHG on the same sample and at the same scale [Fig. 4(b)], we nonetheless observe regions of brighter and darker SHG contrast. This signal confirms the presence of an in-plane component of polarization. However, these contrast variations appear at much larger length scales than the individual nanoscale domains imaged by PFM. Indeed, radially averaged autocorrelation for each image reveals a characteristic pseudoperiod of approximately 800 nm for the SHG contrast variations, but only about 100 nm for the PFM images, corresponding directly to the domain structure (see Supplemental Material [START_REF]L241404 for further information about scanning transmission electron microscopy data acquisition and analysis, radially averaged autocorrelation analysis, Ising model with disorder, non-Ising structure and conductive properties of ferroelectric domain walls, second-harmonic generation, thinfilm growth, and scanning probe microscopy[END_REF] Sec. S2 for details).

Nonetheless, when the microstructure of domains [Fig. 4(c)] and domain walls [Fig. 4(d)] in the PFM image is explicitly blurred to mimic the lower resolution and averaging effect of SHG, longer-range variations in density are clearly revealed. Radially averaged autocorrelation analysis of this resulting superstructure shows the same approximately 800 nm pseudoperiod as that of the intensity variations in the SHG image [Fig. 4(e)].

This superstructure in the domain density appears to be directly linked to the underlying defect landscape. To demonstrate this, we apply this radially averaged autocorrelation analysis to a simple Ising model simulation shown in Fig. 5(a), in which a disorder potential with a characteristic length scale ξ is added to the Ising Hamiltonian, and the resulting domain density fluctuations are blurred to reveal their superstructure, as for the experimental analysis (see Supplemental Material [START_REF]L241404 for further information about scanning transmission electron microscopy data acquisition and analysis, radially averaged autocorrelation analysis, Ising model with disorder, non-Ising structure and conductive properties of ferroelectric domain walls, second-harmonic generation, thinfilm growth, and scanning probe microscopy[END_REF] Sec. S3 for details). As can be seen in Fig. 5(b), we find that the typical feature size extracted from radially averaged autocorrelation analysis exactly matches the characteristic length scale ξ of the disorder potential.

While the effect of strong, localized defects can be seen in, for example, the changes in roughness at domain walls [START_REF] Guyonnet | Growing up at the nanoscale: Studies of ferroelectric domain wall functionalities, roughening, and dynamic properties by atomic force microscopy[END_REF], our observation of a characteristic length scale of 800 nm seems more compatible with variations of a collective background defect potential. This potential has been previously mapped out using spectroscopic techniques [START_REF] Jesse | Direct imaging of the spatial and energy distribution of nucleation centres in ferroelectric materials[END_REF], recently further assisted by machine learning [START_REF] Agar | Machine detection of enhanced electromechanical energy conversion in PbZr 0.2 Ti 0.8 O 3 thin films[END_REF]. We note, moreover, that the key contributions to the disorder landscape do not appear to be variations of the surface morphology (see Supplemental Material [START_REF]L241404 for further information about scanning transmission electron microscopy data acquisition and analysis, radially averaged autocorrelation analysis, Ising model with disorder, non-Ising structure and conductive properties of ferroelectric domain walls, second-harmonic generation, thinfilm growth, and scanning probe microscopy[END_REF] Fig. S10 for details). Our analysis therefore demonstrates that quantitative information on this defect potential-its characteristic length scale-can be obtained using noninvasive and nondestructive optical measurements, without the need to switch the intrinsic domains and thus modify the defect landscape of the film [START_REF] Kalinin | The role of electrochemical phenomena in scanning probe microscopy of ferroelectric thin films[END_REF][START_REF] Domingo | Surface charged species and electrochemistry of ferroelectric thin films[END_REF]. This method can be applied more generally, for example, to samples where the defect density has been engineered, to reveal the resulting change in domain density superstructure.

In summary, our complementary PFM, SHG, and TEM measurements demonstrate that both artificial and naturally occurring domain walls in PbTiO 3 thin films present components of Néel polarization at room temperature, possibly stabilized over the predicted Ising structure by defect segregation. Indeed, radially averaged autocorrelation analysis of domain density fluctuations reveals characteristic length scales which can be related to variations in the underlying disorder potential landscape. While it remains to be explored if and how such domain walls transition to a Bloch configuration at low temperature, our observations suggest potential utility in novel nanoelectronic applications, as Néel domain walls would be locally more likely to show increased electrical conductivity than their Ising counterparts (see Supplemental Material Sec. S4 for details).

The data that support the findings of this study are available at Yareta [55].

FIG. 1 .

 1 FIG. 1. Signature of Néel polarization at written domain walls at room temperature. (a) Vertical PFM phase image of the square-in-square domain structure written in an up-oriented monodomain film. (b) Isotropic SHG image (without polarization analysis) acquired at the patterned square-in-square domain structure, with red corresponding to maximum signal intensity and blue corresponding to minimum signal intensity. (c) and (d) SHG measurements of the domain structure for different polarizer and analyzer angle combinations, where the analyzer direction is represented by the double-headed arrow. SHG signal is observed at the domain walls only when the analyzer is perpendicular to the domain wall plane, consistent with a Néel character. The white scale bar in all panels represents 4 µm.

FIG. 2 .

 2 FIG. 2. Top view of nanoscale domains and domain walls. (a) Vertical PFM phase image of the domain structure of a polydomain sample. The white scale bar represents 400 nm. The typical thickness of the TEM lamella prepared from this sample (≈30 nm) is represented by the green box. (b) and (c) Schematic representation of the polarization in the black rectangle in (a), for the case of Néel-(b) or Bloch-type (c) domain walls, respectively.From this schematic representation, it is clear that domain walls are highly unlikely to align through the TEM lamella thickness, but will rather meander, leading to averaging over different polarization orientations in the TEM cross-section measurements. For a wall that is not imaged edge-on, i.e., orthogonal to the plane of the lamella, the two possible polarization configurations at the wall [(b) and (c)] could lead to similar projections.

FIG. 3 .

 3 FIG. 3. Transmission electron microscopy and cross-section polarization mapping of intrinsic domain walls at room temperature. (a) Lowmagnification differential phase contrast (DPC) TEM image of the sample, allowing visualization of the domain wall positions. (b) Highmagnification HAADF-STEM image of the region indicated by the red box in (a). The domain wall is visible as a shift in the Pb lattice close to the center of the image (see main text). (c) Cropped version of the atomic resolution HAADF shown in (b). Here the Ti atom columns are readily visible, as well as the shift in the Pb lattice, inducing a sharp change in the c-a angle highlighted by the yellow dotted lines. The domain wall position is indicated by red arrows in (a)-(c). (d) c axis and c-a angle extracted from 2D Gaussian fits to the positions of the atomic columns in (b). The position of the domain wall is clearly visible as an increase in c-a angle. (e) Ellipticities of the Pb and Ti columns, caused by the projection of different positions of the atoms throughout the thickness of the lamella. The Ti ellipticity is higher throughout, consistent with the averaging over opposite polarization directions through the thickness of the lamella. (f) Reconstructed polarization map based on a three-Gaussian fit to the position of the Ti columns in (c) (see main text). The color scale indicates the interpolated c-a angle, which we use as a marker for the position of the domain wall. The arrows represent the polarization extracted from the Ti displacement, which follows a typical Néel pattern.

FIG. 4 .

 4 FIG. 4. Characteristic length scale of domain superstructure. (a) Vertical PFM phase image of the domain structure of the polydomain sample in blue (ranging from 0 • to 180 • ), with the edges detected using the Canny edge detection algorithm in purple. (b) SHG image of the same sample. The dark and bright contrast cannot be directly related to the domain pattern or to the domain edges. (c) and (d) Local density variations revealed by blurring applied on the vertical PFM phase image of the domains in (c) and on the domain wall structure (d). These domain density variations appear to closely match the variation observed in SHG intensity. All images are shown at the same scale, indicated by the 2-µm white scale bar in (a). (e) Radially averaged autocorrelation for the SHG image and both the domain and domain wall (DW) distributions obtained from the PFM phase image, and their superstructure obtained after blurring. While only very small structures are revealed in the raw PFM images, the superstructure in the density has the same pseudoperiod as the contrast variations found in the SHG image.

  This work was supported by Division II of the Swiss National Science Foundation under Project No. 200021_178782. A.B.N. gratefully acknowledges support from the EP-SRC (Grants No. EP/R023751/1 and No. EP/L017008/1). S.C.-H. acknowledges the support of the French Agence Nationale pour la Recherche (ANR) through Grant No. ANR-18-CE92-0052 and the Programme d'Investissement d'Avenir ANR-10-IDEX-0002-02 of the University of Strasbourg under Contract No. ANR-11-LABX-0058_NIE. C.L. acknowledges the support from Division II of the Swiss National Science Foundation under Project No. 200021_200636. The authors thank S. Mohapatra for help for the domain poling. P.P. and S.C.-H. designed the experiment; C.W. and C.L. grew the samples and conducted the piezoresponse force microscopy; S.C.-H. carried out the second-harmonic generation microscopy in collaboration with K.D.D; A.B.N. performed the transmission electron microscopy and the atomic position fitting; C.W. carried out the autocorrelation analysis; I.G. performed the Monte Carlo simulations of the perturbed Ising model; C.W., C.L., A.B.N., and P.P. wrote the manuscript with contributions from all authors. All authors discussed the experimental results and models, commented on the manuscript, and agreed on its final version.

FIG. 5 .

 5 FIG. 5. Simulations of domain density variations demonstrating the importance of the disorder correlation length. Experimentally observed fluctuations of domain density were reproduced using an Ising system with a random disorder potential of characteristic length scale ξ . (a) Relaxed domain structure after randomly distributed up-and down-polarization regions, initially in equal proportion, were subjected to a random field disorder potential. (b) The radially averaged autocorrelation function of the domain superstructure, whose first minima, corresponding to the typical feature size, exactly match the disorder correlation length. Here, px, pixels.


Cyril Branciard

Eric G Cavalcanti

Stephen P Walborn

Valerio Scarani

Howard M Wiseman

One-sided Device-Independent Quantum Key Distribution: Security, feasibility, and the connection with steering

Keywords: numbers: 03.67.Dd, 03.65.Ud, 03.67.Mn

We analyze the security and feasibility of a protocol for Quantum Key Distribution (QKD), in a context where only one of the two parties trusts his measurement apparatus. This scenario lies naturally between standard QKD, where both parties trust their measurement apparatuses, and Device-Independent QKD (DI-QKD), where neither does, and can be a natural assumption in some practical situations. We show that the requirements for obtaining secure keys are much easier to meet than for DI-QKD, which opens promising experimental opportunities. We clarify the link between the security of this one-sided DI-QKD scenario and the demonstration of quantum steering, in analogy to the link between DI-QKD and the violation of Bell inequalities.

Quantum Key Distribution (QKD) allows two parties (Alice and Bob) to establish secret keys at a distance, with security guaranteed by the laws of Quantum Mechanics [1]. In standard QKD (S-QKD), the security is typically proved under the assumption that Alice and Bob can trust the physical functioning of their preparation and measurement apparatuses. For instance, standard security proofs for the BB84 protocol [START_REF] Bennett | Proc. of the IEEE International Conference on Computers, Systems and Signal Processing[END_REF] assume that Alice sends qubits to Bob, prepared in some eigenstates of the σ z or σ x Pauli operators, and that Bob measures them in one of those two bases. Recent demonstrations of hacking of the devices has shown the importance and weakness of this assumption [START_REF] Lydersen | [END_REF]. Moreover, since QKD is becoming commercially available, Alice and Bob may end up buying their devices from untrusted providers.

Remarkably, there are ways to guarantee security with fewer assumptions. The minimal set of assumptions is the one used in Device-Independent QKD (DI-QKD) [START_REF] Mayers | Proc. of the 39th IEEE Conf. on Foundations of Computer Science[END_REF][START_REF] Acín | [END_REF]. There, Alice and Bob can certify the security of QKD based only on the observed violation of Bell inequalities [6]: the measurement apparatuses are untrusted black boxes, with a knob supposedly related to the measurement settings. Alice and Bob have only to trust the random number generator with which they vary the positions of the knob, and of course the integrity of their locations. While the qualitative understanding "Bell violation implies security" is certainly true, the derivation of quantitative security bounds is challenging. The most recent results report on security against the most general attacks ("coherent attacks") under the assumption that previous measurements do not feed any information forward to subsequent ones [7,8] (or, to put it simply: that the devices are memoryless). In addition to these (hopefully temporary) limitations of the theoretical studies, DI-QKD imposes very demanding requirements on practical demonstrations. In particular, the Bell test would need to close the detection loophole [9], which requires very high detection efficiencies [10].

Intermediate scenarios between S-QKD and DI-QKD require less trust than the former and will be easier to implement than the latter [11]. Imagine for instance that a bank wants to establish secret keys with its clients; the bank could invest a lot of money to establish one trustworthy measurement device, but the clients at the other end of the channel would certainly get cheap (and insecure) detection terminals. This leads us to study one-sided DI-QKD (1sDI-QKD): we consider an entanglement-based scenario in which Bob's measurement apparatus is trusted, while Alice's is not. In the entanglementbased setup the source is also untrusted, although we will also discuss prepare-and-measure (P&M) implementations where the source is trusted. We present a security bound against coherent attacks with similar assumptions as in Refs. [7,8], in particular that the devices are memoryless, as this enables the strongest security analysis presently available. Focusing on practical implementations, we show that the detector efficiencies required for a practical implementation of 1sDI-QKD are much lower than for DI-QKD, making it feasible with existing devices. Before that, let us start by stressing a link with a hierarchy of tests of quantum nonlocality [12].

QKD and quantum nonlocality.-It is known that no secret key can be extracted in a QKD experiment if the channel between Alice and Bob is entanglement-breaking [13]. Hence, in order to demonstrate security, one must show that the channel preserves entanglement. The three different assumptions on Alice's and Bob's devices mentioned above correspond naturally to three different criteria for quantum nonlocality [12] (see Figure 1): S-QKD or DI-QKD require the observed correlations to violate a separability criterion or a Bell inequality respectively; 1sDI-QKD requires the correlations to violate an EPR-steering inequality as defined in [14]. That is, if one imagines that Bob's system has a definite (albeit unknown to him) quantum state, the protocol must prove that Alice, by her choice of measurement, can affect this state.

(i) (ii) (iii)
FIG. 1: Link between the three concepts of quantum nonlocality as classified in [12] and the three scenarios of S-QKD, 1sDI-QKD (this paper) and DI-QKD. In order to obtain a secret key, (i) if Alice and Bob trust their measurement devices (transparent boxes), then they must necessarily demonstrate entanglement; (ii) if Alice's measurement device is untrusted (black box), while Bob's is trusted, then Alice must demonstrate steering of Bob's state; (iii) if both Alice's and Bob's measurement devices are untrusted, then they must demonstrate Bell-nonlocality. In all cases, Alice and Bob must trust their random number generator (RNG), and the integrity of their location.

This sort of nonlocality, first discussed by Einstein, Podolsky and Rosen [15], was called 'steering' by Schrödinger [16]. In Ref. [12] these concepts of nonlocality arose from considering entanglement verification with untrusted parties. However, even if Alice and Bob trust each other, as in QKD, they may not trust their devices, which is an analogous situation. From this perspective, our scenario of 1sDI-QKD can thus be seen as a practical application of the concept of quantum steering.

A 1sDI-QKD protocol.-We consider the following 1sDI version of the BBM92 entanglement-based protocol [17]: Alice and Bob receive some (typically, photonic) quantum systems from an external source. Alice can choose between two binary measurements, A 1 and A 2 ; since she does not trust her measurement device, she treats it as a black box with two possible settings, yielding each time one of two possible outputs. Bob, on the other hand, trusts his device to make projective measurements B 1 or B 2 in some qubit subspace, typically corresponding to the operators σ z and σ x respectively. After publicly announcing which measurements they chose for each system, Alice and Bob will try to extract a secret key from the conclusive results of the measurements A 1 and B 1 ; as explained below, the results of measurements A 2 and B 2 will allow them to estimate Eve's information.

Alice and Bob might not always detect the photons sent by the source, because of losses or inefficient detectors. Since Bob trusts his detectors, he trusts that Eve cannot control his detections. Also, Eve cannot get any useful information from Bob's (null) result if the photons going to him are lost or if she keeps them. Cases where Bob gets ambiguous results (e.g. double clicks) can be dealt with using the techniques of Ref. [18]-see Supplemental Material [19] for details. Hence, we can safely consider only the cases where Bob gets detec-tions. On the other hand, since Alice's measurement device is untrusted, Eve could control whether her detectors click depending on the state she receives and on her choice of measurement setting. We can therefore not simply discard Alice's no-detection events. In case her detectors don't click, she records a bit value of her choice as the result of her measurement, keeps track of the fact that her detectors did not click, and tells Bob (so that they can later post-select the raw key on Alice's detections); Eve has access to that information.

We denote by A i and B i the strings of classical bits Alice and Bob get from measurements A i and B i (and where Bob got a detection, as discussed above). Among the bits of A 1 , some correspond to actual detections by Alice, and some, corresponding to non-detections, were simply chosen by Alice herself. Everyone knows which ones are which. The detected bits form a string A ps 1 (they'll be post-selected by Alice and Bob), while those that were not actually detected form a string A dis 1 (they'll be discarded for the key extraction), so that A 1 = (A ps 1 , A dis 1 ). Bob's corresponding bit strings are B ps 1 and B dis 1 , resp., so that B 1 = (B ps 1 , B dis 1 ). We denote by N the length of the strings A 1 and B 1 , and by n that of the strings A ps 1 and B ps 1 . Security proof and key rate.-Recently, Tomamichel and Renner [20], together also with Lim and Gisin [22] have developed an approach to QKD based on an uncertainty relation for smooth entropies, which enables one to prove security against coherent attacks in precisely this 1sDI-QKD scenario; note however that one also needs (as in [7,8]) the assumption that the devices are memoryless [23]. To prove the security of our protocol in realistic implementations, we extend their analysis by considering imperfect detection efficiencies [START_REF]To avoid any confusion[END_REF].

From the n-bit strings A ps 1 and B ps 1 , on which Eve may have some (possibly quantum) information E, Alice and Bob can extract, through classical error correction and privacy amplification (from Bob to Alice), a secret key of length [START_REF] Renes | [END_REF] ℓ

≈ H ǫ min (B ps 1 |E) -n h(Q ps 1 ) . (1)
Here H ǫ min (B ps 1 |E) denotes the smooth min-entropy [START_REF] Renner | Advances in Cryptology -ASI-ACRYPT[END_REF] of B ps 1 , conditioned on quantum side information E; h is the binary entropy function:

h(Q) ≡ -Q log 2 Q-(1-Q) log 2 (1- Q); and Q ps 1
is the bit error rate between A ps 1 and B ps 1 . To bound H ǫ min (B ps 1 |E), we will use the uncertainty relation introduced in [20], which bounds Eve's information on B 1 given Alice's information on the incompatible observable B 2 . However, we need to use the full strings B 1 , B 2 , as postselection may lead to an apparent violation of the uncertainty relation. Using the chain rule [START_REF] Renes | [END_REF] and the data-processing inequality [27] for smooth min-entropies, we first bound Eve's information on B ps 1 relative to her information on B 1 :

H ǫ min (B 1 |E) = H ǫ min (B ps 1 , B dis 1 |E) (2) ≤ H ǫ min (B ps 1 |B dis 1 E) + log 2 |B dis 1 | (3) ≤ H ǫ min (B ps 1 |E) + N -n . (4)
Now, consider a hypothetical run of the protocol where the bits of A 1 and B 1 would be measured in the second basis; we denote by A 2 and B 2 the corresponding hypothetical strings. From the generalized uncertainty relation of [20], one has

H ǫ min (B 1 |E) ≥ qN -H ǫ max (B 2 |A 2 ) . ( 5
)
where q is a measure of how distinct Bob's two measurements are; for orthogonal qubit measurements, q = 1. Here,

H ǫ max (B 2 |A 2 ) is the smooth max-entropy [26] of B 2 , condi- tioned on A 2 . It satisfies the following [22] H ǫ max (B 2 |A 2 ) N h(Q 2 ) , (6)
where Q 2 is the bit error rate between A 2 and B 2 . Now, since the choice of basis was made randomly, Q 2 is the same as the bit error rate observed-without post-selection-when the second basis was actually chosen (no matter how rarely) by both Alice and Bob. Substituting ( 4), ( 5) and ( 6) in Eq. ( 1), we obtain

ℓ n [1 -h(Q ps 1 )] -N [h(Q 2 ) + 1 -q] . (7)
In the asymptotic limit of infinite key lengths, the above approximate inequality becomes exact [21,22]. The fraction n/N of photons which Alice detects, given that Bob detected one, will be denoted η A . This allows us to write the secret key rate r ≡ ℓ/N (the number of secret bits obtained per photon detected by Bob, measured in the first basis), as

r ≥ η A [1 -h(Q ps 1 )] -h(Q 2 ) -(1 -q) . (8)
Relation to EPR-steering.-As we recalled before, the secret key rate above can only be positive if Alice and Bob can check that they share entanglement. In our 1sDI scenario, this amounts to demonstrating quantum steering. Hence, the in-

equality η A [1 -h(Q ps 1 )] -h(Q 2 ) -(1 -q) ≤
0 can be understood as an EPR-steering inequality [14]. In the Supplemental Material [19], we give a more direct proof of this claim, starting from the so-called Local Hidden State model [12].

Experimental prospects.-We now turn to the feasibility analysis. Consider a typical experimental setup, where a source sends maximally entangled 2-qubit states to Alice and Bob, through a depolarizing channel with visibility V , and where, as in the BBM92 protocol, A 1 = B 1 = σ z and A 2 = B 2 = σ x , with Alice's detection efficiency being η A as above. (We emphasize that this is simply a model for Alice's measurements, which are implemented in a black box.)

The secret key rate that Alice and Bob can extract is then bounded by (8), with q = 1 and

Q ps 1 = (1 -V )/2 , Q 2 = (1 -η A V )/2 .
Figure 2 shows the values of the bound (8) as a function of η A , and for different values of V . For a perfect visibility V = 1, one gets a positive secret key rate for all η A > 65.9%. This detection probability threshold is much lower than those required for DI-QKD. For instance, if Alice and Bob have the same detection efficiency η, then they require η > 94.6% for the protocol studied in [7], when they extract their 8) on the secret key rate r in a typical implementation of 1sDI-QKD, as a function of Alice's detection efficiency ηA, for visibilities V = 1, 0.99, 0.98, 0.95 (from top to bottom) and q = 1. Dashed curve: for comparison, bounds (for V = 1) for DI-QKD, obtained by adapting the security analysis of Ref. [7], when Bob has the same detection efficiency ηB = ηA as Alice (see Supplemental Material [19]). key from the non-post-selected data. If the key is extracted from the post-selected data (as we considered here for 1sDI-QKD), the threshold remains quite high, η > 91.1% (see Figure 2 and Supplemental Material [19]). The much lower efficiency threshold for 1sDI-QKD compared with DI-QKD is related to the fact that it is much easier to close the detection loophole in a steering experiment [28][29][30] than in a Bell test, for which there are no photonic detection-loophole free demonstrations to date. Heralding efficiencies of ∼ 62% have recently been reported [30], in an experiment demonstrating detection-loophole-free quantum steering; our 1sDI-QKD protocol could be demonstrated with a very similar (but slightly improved) experimental setup.

Note also that in the 1sDI-QKD case, the losses between the source and Bob's lab do not affect the security of the protocol; they only decrease the key rate proportionally to the decrease of Bob's detection rate (as long as the noise in Bob's detectors does not become prominent). Hence, long distances can in principle be reached if the source stays close to Alice; this is in contrast to the fully DI-QKD case, where the limit on the detection efficiencies imposes a limit on the allowed distance between Alice and Bob (although some proposals have been suggested to overcome this problem [31][32][33]).

Comparison of different scenarios.-Key rate bounds for entanglement-based QKD also apply to P&M schemes, as long as the preparation device can be trusted to produce a certain average state independent of Alice's (or Bob's, as the case may be) choice of preparation basis (e.g. the completely mixed state, regardless of whether σ x or σ z is the chosen basis). A preparation device with this property can be envisaged as a trusted entanglement source situated in Alice's (or Bob's) laboratory, with a trusted channel between it and the local detector. In this picture it still makes sense to consider the case where the local "hypothetical" detector is untrusted, as this is equivalent to saying that we cannot trust the preparation device to prepare the desired state. Here the efficiency (which we will denote as η * ) of the hypothetical detector models the probability that the preparation device registers to the sender which of the two states (in the chosen basis) was sent. For a well-functioning device this can be close to unity; even if the preparation does use a probabilistic photon-pair source and a detector, the sender can generate many pairs within the time window for each system, and switch out the system (one photon, ideally) only when its preparation is heralded by the detection of the other. A greater experimental challenge is the loss of the heralded photon (within the sender's lab or en route), which must be factored into the receiver's efficiency.

Considering all non-trivial permutations of device trustworthiness, there are eight P&M scenarios, and four genuine entanglement-based scenarios, whose security can be analysed using the methods of Refs. [20] or [7]. We remove mirror-image scenarios by keeping only the version which is better (or equally good) under the assumption of the privacy amplification being from Bob to Alice, as shown in Table I. Note that P&M by Bob with a fully trusted preparation device (row 3) does not improve the threshold efficiency required for Alice's untrusted detector, as compared to steering-based 1sDI-QKD with an untrusted entanglement source (row 6).

Conclusion.-We have introduced the scenario of 1sDI-QKD and analyzed its security against coherent attacks in a practical situation where losses are taken into account. Our analysis shows that the assumptions of 1sDI-QKD allow one to significantly lower the necessary detection efficiencies compared to fully DI-QKD, and that the requirements for obtaining secure key rates in an experiment are within the range of current technology.

We have also stressed that 1sDI-QKD requires the violation of an EPR-steering inequality, in analogy with the requirement of violation of a Bell inequality for security of DI-QKD. The relation between the QKD hierarchy and the nonlocality hierarchy introduces some open questions: (i) It has recently been shown that steering can be demonstrated with arbitrarily low efficiencies [28]. Can one find (and prove the security of) 1sDI-QKD protocols that would also tolerate arbitrarily low efficiencies? (ii) With 2 measurement settings per party, steering can be demonstrated for efficiencies η A > 50% [28,30]. There is a large gap between this and the threshold of ∼ 66% for our 1sDI-QKD protocol. The same situation occurs for fully DI-QKD, where there is also a gap between the threshold of η > 82.8% for a violation of the CHSH inequality [34] and that for the security of DI-QKD. How small can these be made in general? Another topic for further research is to extend our results to finite keys, for instance along the lines of Ref. [22].

Supplemental Material

Practical detectors and multiple counts.-In practical implementations with photons, Bob's detector comprises two photon counters, corresponding to his two possible outputs. Because of dark counts or imperfect state preparation (i.e. the presence of multi-photon states) there will be rare occasions where both counters click. In such cases, our protocol requires Bob to output a random result. This is a standard way to treat double clicks in the context of QKD [S1]. When Bob implements the σ z or σ x measurements, his detection scheme has a "squashing property" that should allow one to extend the present theoretical security proof for perfect qubit states (on Bob's side) to imperfect implementations [S2].

Direct proof that "r ≤ 0" is a steering inequality.-We obtained in Eq. ( 8) in the main text a bound on the secret key rate of our 1sDI-QKD protocol. As we argued, a positive secret key rate can be obtained only if Alice and Bob can demonstrate steering. That is, if they violate the inequality "r.h.s of Eq. ( 8) ≤ 0", or more explicitly

ηh(Q ps 1 ) + h(Q 2 ) + (1-η) ≥ q , (S1)
then they can conclude that they have demonstrated steering: Eq. (S1) thus defines an EPR-steering inequality [S3].

Here we show in a different way that (S1) is indeed an EPRsteering inequality, starting more directly from the Local Hidden State model [S3]-a local model whereby the statistics observed by Alice and Bob can be decomposed as [S4]

P (ã i , b j ) = λ P (λ)P (ã i |λ)P Q (b j |λ), (S2)
where ãi = (a i , s), with a i = ±1 and b j = ±1 denoting the experimental outcomes corresponding to measurements A i , B j , and s denoting whether Alice gets a detection (s = 1) or not (s = 0); recall that in case of no detection, Alice's result a i is chosen to be a pre-established bit in our 1sDI-QKD protocol and will contribute to the bit string A dis i . The subscript Q indicates that Bob's statistics are determined by quantum mechanics:

P Q (b j |λ) = Tr[E j ρ λ ]
, where ρ λ is some quantum state (in our case, a qubit state) and {E j } are the positive operators summing to unity which describe his measurements.

The variable λ fully specifies the quantum state received by Bob. As a consequence, Alice can have no more information on average about Bob's results than what one could know through λ. In terms of conditional entropies, this implies that

H(B i | Ãi ) ≥ H(B i |Λ) , (S3)
where

H(B i | Ãi ) = ãi P (ã i )H(B i |ã i )
i ) = -bi P (b i |ã i ) log 2 P (b i |ã i ) and H(B i |λ) = -bi P Q (b i |λ) log 2 P Q (b i |λ).
Now, Bob's statistics, conditioned on λ, are by assumption given by a quantum state; they must therefore satisfy all quantum uncertainty relations, and in particular

H(B 1 |λ) + H(B 2 |λ) ≥ q, ( S4
)
where q quantifies how different the measurements B 1 and B 2 are [S5]. Together with (S3), we obtain

H(B 1 | Ã1 ) + H(B 2 | Ã2 ) ≥ q. ( S5
)
Denoting A ps i for A i when s i = 1 and A dis i for A i when s i = 0, and assuming that P (s i = 1) = η A independently of A i (as should be the case if it is a detector efficiency), we have

H(B i | Ãi ) = η A H(B ps i |A ps i ) + (1-η A )H(B dis i |A dis i ). (S6)
Now, one can easily check (using for instance the concavity of the binary entropy function) that for binary variables A and B, one has

H(B|A) ≤ h(Q), ( S7
)
where Q is the bit error rate relative to A and B (the probability that A = B). Applying this to (S6) for i = 1, it follows that

H(B 1 | Ã1 ) ≤ η A h(Q ps 1 ) + (1 -η A ), (S8)
while on the other hand

H(B 2 | Ã2 ) ≤ H(B 2 |A 2 ) ≤ h(Q 2 ). (S9)
Substituting (S8) and (S9) in (S5) we finally obtain (S1), as desired.

Note that for the purpose of deriving an EPR-steering inequality, there is no need to follow the last steps of the above procedure where we treat and bound H(B 1 | Ã1 ) and H(B 2 | Ã2 ) differently. Rather we can use Eq. (S5) directly as an EPR-steering inequality. Under the usual conditions for QKD as discussed in the main text, q = 1 and Eq. (S8) becomes a tight inequality, so Eq. (S5) then becomes

η A [2 -h(Q ps 1 ) -h(Q ps 2 )] ≤ 1. (S10)
For perfect correlations (Q ps 1 = Q ps 2 = 0), this will be violated (indicating EPR-steering) provided that η A > 1 2 . This is the minimum possible efficiency threshold for EPR-steering using two settings [S6].

Comparison with DI-QKD.-In the DI-QKD case, the strongest security analysis available today is that of Masanes, Pironio and Acín [S7], who showed the security of a large class of protocols against coherent attacks (under the technical assumption that the devices are memoryless). In the simplest version, the protocol they consider involves Alice and Bob measuring in bases that enable a CHSH inequality [S8] to be tested, where one of Bob's bases is that which is used (together with a different one of Alice's bases) to yield the secret shared key. Let the CHSH polynomial have the value S (such that |S| < 2 √ 2 for quantum correlations, and |S| > 2 indicates a violation of the CHSH inequality), and let the nonpost-selected quantum bit error rate for measurements in the bases that will yield the key be Q 1 . Then Ref. [S7] shows that the final key rate can be bounded from below by

r MPA = 1 -h(Q 1 ) -log 2 1 + 2 -(S/2) 2 . (S11)
For a visibility V and inefficiencies η A and η B , we have a raw shared random key with bit error rate

Q 1 = [1 -(1 -η A )(1 - η B )-V η A η B ]/2, and a CHSH parameter S = 2 √ 2V η A η B + 2(1 -η A )(1 -η B ).
The latter is obtained if Alice and Bob use the same predetermined list of random results whenever they fail to detect a photon. With V = 1 and η A = η B = η, Eq. (S11) yields a positive key rate for η > 94.5%. In the situation of prepare-and-measure (P&M), where there is a trusted source in Bob's lab, but his detector is still untrusted, we replace η B by η * B , Bob's preparation efficiency. Taking η * B → 1, Eq. (S11) gives a lower bound η - A > 89.6%. We now show that Alice and Bob can improve their secret key rate by extracting their secret key from the data postselected on coincidence detections, as we suggested here for the case of 1sDI-QKD. Indeed, one can apply our analysis to that of Ref. [S7] to find a new secret key rate bounded from below by

r 2 = η A η B [1 -h(Q ps 1 )] -log 2 1 + 2 -(S/2) 2 . (S12)
Here S is unchanged from above (it must still be estimated from the whole non-postselected data), while Q ps 1 = (1 -V )/2. With V = 1 and η A = η B = η, this yields a positive key rate for η > 91.1%. Considering again the P&M case with η * B → 1, we obtain the lower bound η - A > 83.3%. These are the figures appearing in Table 1 in the main text. In both cases, but especially the P&M case, using our post-selection technique yields substantially better efficiency thresholds than the non-post-selected protocols. We note that somewhat lower efficiency thresholds for DI-QKD (η > 92.3% and η > 88.9% for the entanglement-based schemes, with and without post-selection, resp.) can be obtained using the analysis of Ref. [S9]. However, this analysis shows security only against collective attacks (which includes, in particular, the assumption that the devices are memoryless).

In the main text we presented only the post-selected version of 1sDI-QKD. However one can also consider a nonpost-selected version of that, in which Alice and Bob try to extract a secret key directly from the non-post-selected data A 1 , B 1 (rather than from A ps 1 , B ps 1 ; note however that we still post-select on a detection by Bob). In this case the key rate per detection by Bob is bounded from below by 1 -h(Q 1 )-h(Q 2 ) for security against coherent attacks. Here for a typical implementation the bit error rates are both given by Q i = (1 -V η A )/2, and with V = 1, we get a positive rate for η A > 78.0%. Recall that when Alice and Bob use the post-selected data, the threshold is η A > 65.9%, so the improvement is even more dramatic than in the fully DI case.

FIG. 2 :

 2 FIG.2: Solid curves: bounds(8) on the secret key rate r in a typical implementation of 1sDI-QKD, as a function of Alice's detection efficiency ηA, for visibilities V = 1, 0.99, 0.98, 0.95 (from top to bottom) and q = 1. Dashed curve: for comparison, bounds (for V = 1) for DI-QKD, obtained by adapting the security analysis of Ref.[7], when Bob has the same detection efficiency ηB = ηA as Alice (see SupplementalMaterial [19]).

  and H(B i |Λ) = λ P (λ)H(B i |λ) are the average entropies of Bob's measurement B i conditioned on the knowledge of the result of Ãi and of λ, respectively, with H(B i |ã

Acknowledgements.-This work was supported by the Australian Research Council Programs CE110001027 and DP0984863, the National Research Foundation and the Ministry of Education, Singapore, the Brazilian agencies CNPq, FAPERJ, and the INCT-Informac ¸ão Quântica.

Based on AD C S C BD Key rate bound Eff. Thresh. The second column tells which of the components-Alice's detectors (AD), the source (S), Bob's detector (BD) and each of the channels (C) between the source and the detectors-are trusted (T) or untrusted (U). Thick vertical lines in each row separate Alice's lab, the channel open to Eve, and Bob's lab. In the P&M cases, the detector plus source in a lab is a formal model for a preparation device; the efficiency η * in these cases models the probability that the preparation device registers which state is prepared, and would typically be close to unity (for details see text). In column three, the bounds on key rates (here, per photon pair produced by the source, i.e. per preparation event in the P&M cases) are given in terms of the func-

P&M T T T U T r0(

] -h(Q2)} from Eq. ( 8), and

). Here S is the value of the CHSH polynomial [34], while Q1 and Q2 are bit error rates. The superscript ps means post-selection on coincident detections; Q2 in r1(Q ps 1 , Q2) is post-selected on Bob's detections, but not on Alice's; S must be estimated from the whole non-postselected data. The Efficiency Thresholds (column four) are calculated with everything else perfect. In row 4, we assumed η * B → 1 (the threshold we quote is therefore a lower bound on the thresholds for η * B < 1), while in row 7, ηA = ηB = η.

Note added.-While finishing writing this manuscript, we became aware of a related work [35] where similar bounds on the detection efficiency thresholds are derived.