# YouTubing at Home: Media Sharing Behavior Change as Proxy for Mobility
Around COVID-19 Lockdowns

Yelena Mejova<EMAIL_ADDRESS>ISI FoundationTorinoItaly and  Nicolas
Kourtellis<EMAIL_ADDRESS>Telefonica
ResearchBarcelonaSpain

(2021)

###### Abstract.

Compliance with public health measures, such as restrictions on movement and
socialization, is paramount in limiting the spread of diseases such as the
severe acute respiratory syndrome coronavirus 2 (also referred to as COVID19).
Although large population datasets, such as phone-based mobility data, may
provide some glimpse into such compliance, it is often proprietary, and may
not be available for all locales. In this work, we examine the usefulness of
video sharing on social media as a proxy of the amount of time Internet users
spend at home. In particular, we focus on the number of people sharing YouTube
videos on Twitter before and during COVID19 lockdown measures were imposed by
109 countries. We find that the media sharing behavior differs widely between
countries, in some having immediate response to the lockdown decrees – mostly
by increasing the sharing volume dramatically – while in others having a
substantial lag. We confirm that these insights correlate strongly with
mobility, as measured using phone data. Finally, we illustrate that both media
sharing and mobility behaviors change more drastically around mandated
lockdowns, and less so around more lax recommendations. We make the media
sharing volume data available to the research community for continued
monitoring of behavior change around public health measures.

††journalyear: 2021††conference: ; ; ††doi: 10.1145/xxxx.xxxx††isbn:
978-1-4503-8312-7/21/04

##  1\. Introduction

The COVID19 pandemic has brought drastic changes in people’s lives around the
world. With respect to online activities and usage of the Internet, people
have turned to social media and other networking and messaging platforms for
socialization, networking, sharing and consumption of content (Arora et al.,
2020; Böttger et al., 2020). In particular, during the first COVID19 lockdown
(Q2-Q3 2020), popular social platforms such as Twitter (Iqbal, 2020b),
Facebook (Iqbal, 2020a), and YouTube (Iqbal, 2020c), saw an increase in daily
and monthly active users (Chaffey, 2020; Fischer, 2020), with YouTube and
Facebook-related content being among the top shared (Böttger et al., 2020;
Kemp, 2020). Such large changes in social media use may be not only due to
increased interest, but indeed due to the physical constraints of the
restrictive measures taken by the governments worldwide.

Currently, lively research is being done around misinformation that is
possibly spreading among the above channels, affecting health-related beliefs
and behaviors of their audience (Cinelli et al., 2020; Yang et al., 2020).
However, in the unique circumstances of physical lockdowns, media consumption
and sharing may be a sign of another health-related behavior: social and
physical isolation. Compliance with the social distancing measures is critical
in controlling the spread of COVID19 (European Centre for Disease Prevention
and Control, 2020), and alternative data sources have been proposed to track
it, including mobile phone GPS and traffic congestion data (Kuiper et al.,
2020). Social media may be another such resource. Already, previous studies of
social media have found daily and weekly periodicity, indicating shifts in
check-in and sharing behavior around different activities (Hasan et al.,
2013). Small-scale studies are already being published for using social media
posts to track individuals who may be associated with the spread of the
disease (Bisanzio et al., 2020; Zeng et al., 2021). In this work, we propose
to use a large language- and space-agnostic collection of YouTube video
sharing on Twitter as another tool for measuring population behavior around
the social distancing measures.

Beyond monitoring the activity of users on separate platforms, studying cross-
platform posting offers unique insights into users’ behavior, as it indicates
higher engagement on multiple platforms. Given that such behavior is more
time-consuming, and requires (higher) users’ attention to view the video on
YouTube and share it on Twitter, it could reveal tendencies of users with
respect to daily schedules such as working vs. resting hours, etc. Further, it
is an act of social or “communal” video co-consumption, which can provide
insights into community or group-focused video sharing and diffusion. Finally,
technically Twitter stream provides an easier way to monitor engagement of
users with YouTube videos, and to model those users through their posting
history, than building crawling engines for both YouTube and Twitter and
handling API-related constraints for both platforms.

Concretely, in this paper, we use a dataset of 390 million Twitter posts
mentioning YouTube videos spanning the period from July 2019 to September
2020. After geo-locating the users of these posts, we select 109 countries
which have had a COVID19-related social distancing recommendation or mandate.
We find that, indeed, the posting trend shifts dramatically around government
measures, although the precise timing may differ, depending on the
peculiarities of each government’s handling of the pandemic. We also find that
these changes in media sharing have a strong negative relationship with the
phone-based mobility data, suggesting social media may provide valuable
insights, especially where such mobility data is not available.

In particular, we make the following contributions:

  * •

We are the first to study cross-platform video posting behavior and how
COVID19-related lockdowns may have impacted it.

  * •

We study this behavior worldwide for 109 countries, and provide case studies
of countries with different governmental actions around the pandemic.

  * •

We investigate if the country-specific changes in media sharing behavior can
be used as a proxy for the detection of reduced mobility of its residents.

  * •

Finally, we provide to the research community a unique dataset with daily
aggregated per-country media sharing statistics in order to encourage
reproducibility and future research of health-related
behaviors111https://github.com/ymejova/yt-tw-covid.

##  2\. Background & Related Work

YouTube on Twitter. Twitter, as a social media platform, is frequently used to
disseminate various types of content produced and published in other
platforms, such as news, photos, videos, etc. Such cross-platform data have
been used to better understand user engagement with YouTube content, predict
the extent of its diffusion, as well as to profile its viewers. For example,
Christodoulou _et al._ (Christodoulou, George and Georgiou, Chryssis and
Pallis, George, 2012) studied Twitter users and how their properties impact
the popularity and diffusion of YouTube videos. Several papers have studied
the problem of finding the best Twitter users to promote YouTube videos to
increase engagement and viewership of said videos (Deng et al., 2015; Yan et
al., 2014, 2015). Furthermore, other papers investigated the phases that a
video goes through with respect to popularity (proxied by viewership), by
building models to predict popularity of videos using power-law fitting (Yu et
al., 2015). In addition, characteristics of YouTube videos shared on Twitter
(Abisheva et al., 2014), as well as complex graph features (Yu et al., 2014)
were employed to model video popularity. In this work, we consider a large
dataset of YouTube links diffused via Twitter posts across over a hundred
countries around the world, crucially capturing the sharing behavior before
and during the rise of COVID19 in the early 2020.

Impact of COVID19 on usage of online platforms. COVID19 has had a great impact
on many aspects of our offline and online lives. In relation to the focus of
this paper, COVID19 has affected the intensity and frequency with which we use
online platforms, including social media and digital devices. Recent studies
have measured these changes by focusing on different aspects of our online
world. For example, Lutu _et al._ (Lutu et al., 2020) performed a
characterization of the impact that the pandemic had on the traffic processed
by a mobile network operator, finding that mobile traffic was reduced due to
users’ reduced mobility during lockdown. Also, Bottger _et al._ (Böttger et
al., 2020) studied how the Facebook Edge Network reacted to COVID19 and the
traffic induced by users, which was found to be higher during and after
lockdown was imposed in different countries; in many cases this increase was
due to higher video consumption. Finally, Feldmann _et al._ (Feldmann et al.,
2020) studied how being under lockdown affected various aspects of internet
traffic around the world. On the other hand, very recent studies looked into
COVID19-related information spreading through various social media platforms.
For example, Cinelli _et al._ (Cinelli et al., 2020) studied how
(mis)information related to COVID19 spreads on Twitter, Instagram, YouTube,
Reddit and Gab, as well as differences in the diffusion of information from
questionable and reliable sources on each platform. Li _et al._ (Li et al.,
2020) studied popular YouTube videos related to COVID19 and identified that
over 25% of such videos contained misinformation regarding COVID19. In this
work, not only do we find that the focus on COVID19-related videos increases
around the onset of lockdown measures, but also that sharing of other content
also markedly increases, pointing a behavior shift beyond attention to the
ongoing events. Thus, we consider the media sharing as a proxy of offline
behavior, and specifically we compare this data to mobility.

Social media and mobility. In the previous decade, the proliferation of mobile
technology has provided researchers with unprecedented fine-grained data on
human mobility, often coming from phone records or large internet platforms,
which has been combined with more traditional sources such as air traffic and
public transit data. Geo-tagged social media posts then have been used as a
way to enrich the existing mobility information, for example by annotating
movement by content associated with it (Wu et al., 2015) or explaining traffic
events in a city (Wu et al., 2016). Quercia _et al._ (Quercia et al., 2014)
use Flickr photos as proxies of beauty to measure “happiness” of trajectories
through a city. However, going beyond annotation, attempts have been made to
derive mobility data directly from the social media activity, such as
international and national travel flows networks (Barchiesi et al., 2015;
Beiró et al., 2016) or local commuting patterns (McNeill et al., 2017). This
information then can be used to track disease (Kraemer et al., 2018),
migration patterns of refugees (Hübl et al., 2017) or as a testbed for
building mobility prediction models (Feng et al., 2018). Recently, attempts
have been made to use Twitter data for tracking the spread of COVID19. For
instance, Bisanzio _et al._ (Bisanzio et al., 2020) correlated the posting
behavior of 161 users with COVID19 cases in locales they visited, while Zeng
_et al._ (Zeng et al., 2021) used geo-tagged tweets to estimate mobility of
the U.S. state of South Carolina. However, the size of the dataset presented
in this paper allows for a much larger view of the interaction between
COVID19-related measures and media consumption. In the pages below, we both
quantify the relationship between media sharing and various stages of
lockdowns, and discuss several case studies illustrating the complex nature of
such data. Also, we provide additional visualizations and aggregated data to
the research community.

Twitter/YouTube collection |
---|---
Duration | 459 days (06/19/2019-09/20/2020)
Posts (tweets) | 390,002,678
Unique Locations | 8,436,027
Countries | 249
Languages | 66
COVID19 Policy data (Oxford’s Coronavirus Response)
Duration | 276 days (01/01/2020-10/01/2020)
Countries | 185
Lockdown states | 3
Mobility data (Apple Mobility Trends)
Duration | 231 days (01/14/2020-09/01/2020)
Countries | 63
Mobility states | driving, walking, transit
Table 1. Datasets used in our analysis, before filtering took place.

Rank | Country | % of tweets
---|---|---
1 | USA | 25.24
2 | Japan | 14.47
3 | Great Britain | 5.19
4 | Brazil | 5.11
5 | France | 4.04
6 | India | 3.53
7 | Spain | 2.76
8 | Italy | 2.60
9 | Canada | 2.16
10 | Mexico | 1.91
Table 2. Top 10 countries by number of posts.

##  3\. Data

In this section, we describe the datasets used in the present study, along
with preprocessing and selection steps. First, we detail our efforts to build
the Twitter & YouTube dataset (Sec. 3.1). Then, we briefly describe the
extraction of lockdown dates from the Oxford COVID19 regulations data (Sec.
3.2). Finally, we conclude with a description of the Apple mobility dataset
(Sec. 3.3). The various datasets used are summarized in Table 2.

###  3.1. Twitter & YouTube Data

Collection. This dataset was collected using the Twitter Streaming API with
queries “youtube” and “youtu.be” (a popular shortened URL for the platform).
Besides the query, no other constraint was applied. The collection took place
from June 19, 2019 to September 20, 2020, capturing at least a half of year
before COVID19 is discovered, and several months of worldwide lockdowns in
2020. The captured information includes tweet text, user information, metadata
about posting time, and link to the YouTube video. This collection resulted in
390,002,678 tweets.

Preprocessing. We then geo-locate the users in this dataset using the Location
field of their profiles. We use the GeoNames location database to match the
user-specified free-text location strings to a populated location.222The
optimized code for geolocation can be found at
https://sites.google.com/site/yelenamejova/resources We are able to locate
4,055,292 out of 8,436,027 unique location strings present in the data, which
covers 165,520,903 tweets (42.4% of all).

Figure 1 shows daily statistics on unique users of the top 10 countries,
sorted by volume of posts (also Table 2). We can see a handful of points in
time when, due to technical difficulties, the collection was disrupted. Also,
we can already observe that 1) there is a weekly periodicity of users’
behavior in sharing YouTube videos on Twitter, 2) there was a shift in posting
frequency between March and May 2020, and 3) USA and Japan have significantly
higher posting activity across time compared to the other countries.

Figure 1. Daily number of unique users for the top 10 countries across time
(June 2019 - October 2020.

Next, we consider three metrics for data analysis: raw number of posts per
day, unique number of users, and unique videos (figures are omitted due to
space). As expected, all three metrics have skewed distributions across
countries. For example, the median for daily number of posts, users and videos
is 82, 51 and 71, respectively, but the mean is 1491, 892 and 948,
respectively. Therefore, we apply an activity threshold and keep countries
with activity (in unique users) above the median of all countries, and across
all available dates. After applying this filter, from 249 countries, we are
left with 125 countries. Furthermore, the three available metrics we have at
hand (i.e., number of posts, unique users, and unique videos) are highly
correlated with each other: average Spearman correlation between users and
videos across all countries is 0.74, and between users and posts is 0.85.
Given that the number of posts or videos involved in this sharing activity can
be skewed by abnormal or extreme posting by any particular user, for the rest
of the study, we focus on unique users posting per day. Finally, we linearly
interpolate the values for the days in which the collection went down. We dub
the resulting time series as the $T$ dataset.

###  3.2. COVID19 Response Data

Collection. We use the University of Oxford’s Coronavirus Government response
tracker (Blavatnik School of Government, 2020; Thomas et al., 2020) to gather
the indicator variables for the levels of lockdown in the above countries. It
covers the time period from January 1, 2020 to October 2, 2020. We use the
field “C6: Stay at home requirements”, which “Records orders to “shelter-in-
place” and otherwise confine to the home”. This field has an ordinal scale of
several levels: L0: no measures, L1: recommend not leaving house, L2: require
not leaving house with exceptions for daily exercise, grocery shopping, and
’essential’ trips, and L3: require not leaving house with minimal exceptions.
Using the above scale, we define _lockdown_ ($L$) as the period of time that a
country was _requiring_ its residents to stay at home unless (minimal)
exceptions apply (i.e., L2 or L3). We also consider the days under L1 as
recommended lockdown, and we use this distinction when appropriate.

Preprocessing. The data regarding the lockdown and other related information
on COVID19 were reported for 185 countries, covering all 125 countries in our
data. For each country, we find the starting date $D_{L2}$ when it entered in
_lockdown_ mode, i.e., L2 or L3 (from here on, when referring to L2 we include
both states), and the ending date $D_{L2end}$, i.e., when the country entered
L0 or L1. In case more than one starting and ending dates are detected, we
apply a buffer time $L2_{B}=7$ to merge consecutive lockdown periods (we
experimented with $L2_{B}$ up to 28, but results changed minimally). The
median country went through $\sim$52 days of lockdown, which lasted for up to
107 days for 75% of the countries. About 10% of countries have remained in a
lockdown mode for the whole duration of observation ($\sim$200 days), while 41
countries (i.e., 33%) had 0 days in lockdown. The latter countries either did
not define any stay at home guidelines (L0, 9 countries) or did not provide
any COVID19 data (5 countries), and where subsequently removed. Finally, we
removed 2 countries which had enforced fewer than 30 days of lockdown. These
steps resulted in two lists of countries: 82 that had a (L2) lockdown, and a
more inclusive one of 109 countries that had at least a lockdown
recommendation (L1).

###  3.3. Mobility Data

Collection & Preprocessing. Finally, in order to explore the relationship
between media sharing ($T$) and mobility ($M$), we utilize the Mobility Trends
Report published by Apple, which “reflects requests for directions in Apple
Maps”333https://covid19.apple.com/mobility. The report offers normalized
mobility activity in three categories: driving, walking, and transit. For our
analysis, we use the walking estimates as the finest of granularity levels. In
the end, out of the 109 countries which have passed the activity and COVID19
lockdown thresholds, 56 had mobility data (signal $M$) provided by the
Mobility Trends Report.

##  4\. Media Sharing About COVID19

(a) Daily users mentioning COVID19 (b) Normalized volume

Figure 2. (a) Portion of daily unique users who are mentioning COVID19-related
keywords, macro-averaged over countries. Gray bars indicate standard deviation
per day. (b) Normalized volume of tweets (by volume on first day), which do/do
not mention COVID19-related keywords, macro-averaged over countries.

We begin by examining the extent to which the increase in shared media ($T$)
can be directly attributed to conversations about the pandemic, or if other
topics were also at play. We use a dictionary of 590 keywords defined by
Twitter for its multilingual COVID19
stream444https://developer.twitter.com/en/docs/labs/covid19-stream/filtering-
rules, since these keywords indicate interest in the topic of the pandemic.
Figure 2(a) shows the country macro-average of the daily unique users in our
dataset who are mentioning COVID19-related keywords. Such spike on Twitter and
Facebook-related activity has also been reported in recent works (Yang et al.,
2020). On average, the maximum contribution of COVID19-related posting is
$\sim$15%, and appears to happen in late March 2020, when most lockdowns
started across many countries. The spike tends to be higher for countries
having fewer users, with Spearman $\rho=-0.362$ ($p<0.001$) between average
volume of tweets vs. maximum contribution of COVID19-related posting.

Interestingly, Figure 2(b) shows that the volume increase around the second
half of March is not only due to the posting around COVID19. In this figure,
we normalize the volume of posting in each country by dividing it by the
volume on the first day and multiplying by 100, such that the volume increase
is standardized. We find that, despite a rise in COVID19-related volume (in
blue), there is additional volume (in orange) not attributable to the interest
in pandemic.

To check whether topics other than COVID19 are mentioned in these posts, we
take the U.S. as an example (which also has the highest volume per country),
and compute the top terms mentioned in the two months before and two months
during the lockdown. The top terms, shown in Table 3, show that, even though
COVID19-related keywords emerge in the topics during the lockdown (e.g.,
_coronavirus_ and _covid_), others remain, including _music_ , mentions of
President _Trump_ , and other general terms like _love_ , _check_ , and _day_.
Thus, we postulate that the increased media sharing behavior is not wholly
explained by the increased interest in the pandemic, but includes the habitual
use of the platform.

Rank | Popular Word Before $L$ | Popular Word During $L$ | Rank | Popular Word Before $L$ | Popular Word During $L$
---|---|---|---|---|---
1 | via (28.13%) | via (27.03%) | 11 | like (1.18%) | covid (1.56%)
2 | youtube (5.25%) | youtube (5.13%) | 12 | love (1.14%) | got (1.51%)
3 | video (5.10%) | video (4.85%) | 13 | one (1.04%) | trump (1.42%)
4 | amp (2.51&) | amp (2.37%) | 14 | full (1.00%) | like (1.05%)
5 | new (2.35%) | live (2.20%) | 15 | de (0.95%) | one (1.01%)
6 | official (2.31%) | new (2.02%) | 16 | coronavirus (0.95%) | love (1.80%)
7 | watch (2.11%) | watch (2.12%) | 17 | song (0.94%) | de (0.98%)
8 | live (2.09%) | official (2.29%) | 18 | check (0.91%) | song (0.98%)
9 | trump (1.83%) | coronavirus (1.80%) | 19 | time (0.82%) | check (0.93%)
10 | music (1.71%) | music (1.56%) | 20 | day (0.81%) | day (0.92%)
Table 3. Popular words in tweets with YouTube links. Popularity shown in % out
of top 100 words.

##  5\. Media Sharing Around COVID19 Lockdowns

(a) United States (b) Spain (c) Brazil (d) Japan

Figure 3. Hourly volume (by unique posting users) of signal $T$ in four
countries, 2 months before and 2 months after lockdown announcements
($D_{L2}$) in each country. Bars indicate standard deviations.

###  5.1. Hourly Sharing Behavior Change Before and During Lockdown

Focusing specifically on the posting behavior before and after lockdown was
announced ($D_{L2}$) by the respective governments of the studied countries,
we first examine the hourly periodicity of the posting behavior. Figure 3
shows examples of unique users posting during the hours of the day in four
countries, separately for weekdays and weekends, and before and during COVID19
lockdowns. Here, we consider 2 months before and 2 months after the lockdown
announcements, average the posting volume over the days, and show standard
deviation in vertical bars. Not only do we see a marked rise in posting volume
during L2 lockdowns, but also a shift in posting patterns, though differently
for each country. For instance, in U.S., the posting rate in the morning
increases, compared to pre-COVID19 levels, whereas in Brazil it elevates
especially around evening. Also, the difference in posting between weekdays
and weekends becomes less clear during lockdown (e.g., in Spain or Brazil),
suggesting a similar media consumption on weekdays and weekends.

###  5.2. Sharing Behavior Change at the Lockdown Start

Next, we examine the change in the media sharing behavior ($T$) around the
lockdown dates. As described in Sec. 3.2, we define the lockdown dates at
several levels. Specifically, we consider two scenarios: (1) an L1 lockdown
(with its starting date signified as $D_{L1}$), when only a recommendation to
stay at home is promoted, and (2) an L2 lockdown (with its starting date
signified as $D_{L2}$), when only essential trips are allowed. To compare the
behavior change to these days, we employ change point detection on signal $T$,
using the pruned exact linear time (PELT) algorithm (Wambui et al., 2015) that
detects change points through minimising a cost function over possible numbers
and locations, as implemented in the python ruptures library (Truong et al.,
2020). We apply this algorithm to $T$ data from each country separately,
taking the 2 months before their lockdown date ($D_{L1}$ or $D_{L2}$), and 2
months after the date, or until the studied lockdown is over (whichever comes
first). Dates of detected trend change are signified as $D_{TC(T)}$. Out of
the 109 countries having L1 and/or L2, we detected a change point for 100
countries, and for the 82 countries having L2 only, we detected change point
for 77 countries.

(a)  (b)  (c)

Figure 4. Number of countries (y-axis) having (a) a difference (x-axis)
between the change point in media posting behavior ($T$) and the starting date
of L1 or L2 lockdowns (countries with both $D_{L1}$ and $D_{L2}$ are
considered separately for each group). (b) Pearson correlation $r$ (x-axis)
between a 7-day averaged mobility ($M$) and media sharing ($T$), by country
lockdown situation (L1 vs. L2 vs. L1,L2). (c) Difference in days (x-axis)
between change points of mobility ($D_{TC(M)}$) and media sharing
($D_{TC(T)}$), by country lockdown situation (L1 vs. L2 vs. L1,L2).

Figure 4(a) shows the frequency distribution of countries having a difference
between the detected change point and the lockdown dates (i.e., $D_{TC(T)}$ \-
$D_{L1}$ or $D_{TC(T)}$ \- $D_{L2}$), such that points below 0 indicate
countries in which change point happened before the lockdown, and above 0
after lockdown. For both definitions of lockdown (L1 or L2), about half of the
time the change points happened within 5 days of the lockdown (51% for L1 and
52% for L2). And, as expected, for more strict lockdown definition (L2), more
change points happened before 0 (64%) than for less strict (51%).

(a) United States (b) Italy

(c) Japan (d) Brazil

Figure 5. Media sharing volume (blue) and mobility (green) in four countries.
Vertical lines: L1 lockdown date $D_{L1}$ (orange), L2 lockdown date $D_{L2}$
(red), media sharing change point $D_{TC(T)}$ (blue), mobility change point
$D_{TC(M)}$ (green). In grey, Interrupted Time Series model for media sharing
$T$ around its change point $D_{TC(T)}$.

Figure 5 shows four countries exemplifying the case in which the change in
behavior is detected, on the same day as the announcement (United States),
before the lockdown announcement (Japan & Brazil), and after it (Italy). The
readers are welcome to examine the plots for all countries at the end of this
paper (Appendix A). The blue line shows the normalized sharing volume (in
unique users), while the lockdown dates are shown in vertical lines – orange
for L1, and red for L2. We explain the other lines in the next sections.
United States (as well as Serbia, New Zealand, Spain, and others) show changes
in posting behavior that correspond precisely to the lockdown announcements.
In the case of the U.S., on March 16, President Trump announced “15 Days to
Slow the Spread” with a series of guidelines on physical distancing and self-
isolation, and recommendations to close schools and businesses (McGraw and
Oprysko, 2020). Italy’s lockdown happened gradually, first quarantining 50,000
people from 11 different municipalities in the northern region on February 22,
with gradual subsequent closures of regions (Dusi, 2020), until the Prime
Minister Giuseppe Conte announced a country-wide quarantine on March 9 (BBC,
2020). Similarly, in Japan, Prime Minister Shinzo Abe requested that all
Japanese elementary, junior high, and high schools close on February 27 (Tokyo
News, 2020), and the state of emergency declaration eventually expanded to
include every prefecture within the country on April 16 (Mainichi, 2020).
Brazil displays a notable shift in behavior around the time of the first
COVID19 related death on March 17 (Bergamo, 2020), without any official
lockdowns until some of the northern cities announced the measures on May 7
(Globo, 2020). The sudden or gradual shifts in the media sharing behavior,
thus, visibly happen around the measures being taken at the time of the
collection gathering, but not always, as in the case of Brazil. We encourage
the reader to explore these graphs for all countries, shown at the bottom of
the paper.

###  5.3. Media Sharing as a Proxy for Mobility

Thus, we find that the media sharing behavior changes around the dates of
lockdown enforcement. We hypothesize that this change reflects the physical
mobility of users, and the fact that they have more time to spend watching and
sharing media online. To explore the relationship between media sharing and
mobility, we utilize the Apple mobility dataset ($M$) as described in Sec 3.
Recall that 56 countries that have passed our selection filters appeared in
this dataset.

Figure 4(b) shows the Pearson correlation $r$ between mobility $M$ and media
sharing $T$, by the lockdown situations that happened in each country: having
only L1, right away into L2, and having first L1 and later L2 (L1,L2). Here,
we smooth both trends using a 7-day average, in order to remove weekly
periodicity (that was obvious in Figure 1). Most correlations are strongly
negative, and all those less than $-0.6$ are significant at $p<0.0001$.
Interestingly, the correlation is the weakest for countries which had only L1
lockdown (the rightmost points on the graph are Slovakia ($r=0.23$,
$p=0.011$), Cambodia ($r=-0.25$, $p=0.011$), Thailand ($r=-0.46$, $p<0.0001$),
and Hong Kong ($r=-0.56$, $p<0.0001$)). This strongly suggests that mobility
is inversely proportional to media sharing behavior, as captured in the $T$
dataset. Further, Figure 4(c) shows the difference in days between the change
point detected in the mobility and media sharing (both raw, un-smoothed). Out
of 50 countries that had a change point detected for both mobility and media
sharing, 44 are within 7 days, and for most countries the change in media
sharing change follows the change in mobility. The three countries having
largest difference in change points (ticks in the far right of the plot) are
Philippines (23), South Korea (20), and Singapore (18) – all countries close
to China that took early precautions against the virus.

If we return to the countries in Figure 5, we now can examine the media
sharing volume (in blue) in the contemporary context of the mobility score
(green), and their respective change points (vertical lines in their
respective colors). In the case of the United States, the change happens all
at once, and the change points, thus, happen within 1 day of each other. The
change points are a bit further apart in Brazil at 4 days, Italy at 5, and
Japan at 7.

Some could argue that the identified cross-platform sharing changes were more
predominant in countries with highly connected Internet users. However, when
we take the correlation of mobility and media sharing $r_{T,M}$ computed
above, and correlate it to the internet penetration in the corresponding
countries (data extracted from (Internet World Stats, 2020)), we find no
significant relationship ($r=-0.18$, $p=0.16$). This suggests that, once the
countries have a minimum volume of Twitter usage, the signal can be used as a
proxy for mobility irrespective of internet penetration. This is encouraging,
since only 56 out of 109 originally selected countries had mobility data
available, so that an alternative proxy is especially valuable for those
locales where the major technology service providers do not release their
data.

##  6\. Media Sharing Behavior Change: Interrupted Time-Series Modeling

To understand whether human behavior changes significantly around the time of
COVID-related lockdowns, we employ Interrupted Time Series analysis (ITS)
(Bernal et al., 2017), which aims to estimate the effect of an intervention
which has a well-defined starting time. Specifically, we examine both the time
series of media sharing volume ($T$), as well as the mobility data ($M$), in
order to gauge the extent of the behavior change. We employ Ordinary Least
Squares (OLS) regression to model the behavior time series of the two signals
using two variables: $P$ signifying time passage in days and $X_{t}$, an
indicator signifying the beginning of the intervention period. For example,
modeling change in the media sharing volume around a lockdown date, in
following equation:

$y_{t}=\beta_{0}+\beta_{1}P+\beta_{2}X_{t}+\beta_{3}PX_{t}$

$y_{t}$ is the volume of media sharing at the time $t$, $\beta_{0}$ is the
baseline volume at the beginning of the time series, $\beta_{1}$ is the
baseline change in volume over time before the lockdown date, $\beta_{2}$ is
the change in volume at the lockdown date, and $\beta_{3}$ is the trend
(slope) change following the lockdown date. In this paper, we focus
specifically on the $\beta_{2}$, the change in behavior around the
intervention. Visually, the ITS models are plotted in grey in Figure 5 for the
four countries.

To capture the complexity of the lockdown situations, we again examine three
groups of countries: those that only had L1, those that only had L2, and those
that went from L1 to L2 (L1=¿L2). Note that for the last group of countries,
we can test both lockdown dates. Additionally, since in the previous sections
we found that the actual behavior change often happened some days before or
after the official lockdown dates, we decided to perform ITS with 4 different
types of dates: two lockdown dates ($D_{L1}$ or $D_{L2}$), and two trend
change points ($D_{TC(T)}$ or $D_{TC(M)}$), on the groups of countries that
each applies. As in the previous section, we select 2 months before and 2
months after the selected date, and here consider only the 54 countries with
mobility data.

Table 4 shows statistics of ITS models for various scenarios. It reports the
mean ($\bar{\beta}$) and standard deviation ($\sigma_{\beta}$) of the
intervention point coefficient, and the model fit ($\bar{R^{2}}$), aggregated
over relevant countries ($n$). First, we observe that the $\bar{\beta}$
coefficients are positive across all models. Note that we z-normalize the
sharing volume ($T$), making it comparable across countries. Second, strongly
negative $\bar{\beta}$ coefficients for mobility indicate a sharp decrease
around the interruption dates, echoing the negative relationship between
sharing volume ($T$) and mobility ($M$) we have previously established. Third,
we find the model fit to be the worst for countries that had L1 lockdowns,
indicating that the behavior change, both in media sharing and in mobility,
are affected the least by policies merely recommending people to stay home.
Further, we find similar $\bar{\beta}$ values and model fit for the two levels
of lockdowns for the L1=¿L2 countries, indicating that for such scenarios it
may be difficult to discern the effect of L1 policy, as it is usually quickly
followed by a more stringent one (for 75% of the countries within 2 weeks).

Finally, we make two methodological observations. We confirm that the extent
of change of behavior (both in media sharing and mobility) is greater at
change points than at lockdown dates, suggesting that factors other than those
captured by lockdown policies – including other communication by the
authorities – may have had an effect on behavior. The better fit of the ITS
models in the case of mobility points to the quicker effect on this variable,
and a less sudden one on media sharing, pointing to a gradual behavior change
when it concerns media consumption during emergency measures. The implications
in terms of attention to public messaging, adjustment in daily routine, and
mental health maintenance are exciting future directions of research.

Model | $\bar{\beta}$ | $\sigma_{\beta}$ | $\bar{R^{2}}$ | $n$
---|---|---|---|---
media sharing & L1 date (L1) | 1.126 | 0.832 | 0.477 | 18
media sharing & L2 date (L2) | 1.349 | 0.598 | 0.650 | 24
media sharing & L1 date (L1=¿L2) | 1.158 | 0.685 | 0.652 | 14
media sharing & L2 date (L1=¿L2) | 1.044 | 0.579 | 0.651 | 14
media sharing & sharing change point (L1) | 1.667 | 0.439 | 0.580 | 15
media sharing & sharing change point (L2) | 1.659 | 0.453 | 0.701 | 23
media sharing & sharing change point (L1=¿L2) | 1.697 | 0.370 | 0.756 | 13
media sharing & mobility change point (all countries) | 1.298 | 1.084 | 0.623 | 54
mobility & L1 date (L1) | -48.767 | 30.435 | 0.751 | 18
mobility & L2 date (L2) | -64.630 | 30.556 | 0.804 | 24
mobility & L1 date (L1=¿L2) | -58.422 | 31.459 | 0.790 | 14
mobility & L2 date (L1=¿L2) | -44.808 | 25.672 | 0.760 | 14
mobility & mobility change point (L1) | -65.221 | 21.345 | 0.817 | 16
mobility & mobility change point (L2) | -82.002 | 25.618 | 0.878 | 24
mobility & mobility change point (L1=¿L2) | -53.372 | 82.838 | 0.865 | 14
mobility & sharing change point (all countries) | -67.582 | 29.810 | 0.831 | 51
Table 4. Interrupted Time Series models with the mean ($\bar{\beta}$) and
standard deviation ($\sigma_{\beta}$) of the intervention point coefficient,
and average model fit ($\bar{R^{2}}$), aggregated over relevant countries
($n$). Model specification indicates data being modeled (media sharing or
mobility) and kind of interruption point, as well as lockdown scenario (L1,
L2, or L1=¿L2).

##  7\. Discussion & Conclusions

This paper provides a large-scale evidence of individual behavioral response
to the social distancing interventions taking place around the world in the
early 2020. We find that media sharing behavior increased in the majority of
countries during the COVID19 lockdowns. However, COVID19-related activity only
accounts for 15% of the overall volume of posts. In fact, users shared with
each other content on a wide range of topics apart from COVID19. Whether this
change in behavior extends beyond volume, and impacts the media consumption
qualitatively is a fascinating question. We are open to collaborating with
researchers (as making full dataset is against Twitter Terms of Service) on
exploring, for instance, the change in quality of information being shared,
the kind of health advice people turn to in an emergency situation, and how
users may maintain social ties and communities around co-consumption of online
media.

We also established a strongly negative relationship between media sharing and
mobility, however it is not certain that this relationship will endure. We
find the spike in interest about COVID19 dissipates after several months,
whereas the sharing volume remains elevated over time. This data provides an
opportunity to study psychological adaptation during a crisis, and test
theories around, for instance, _emotional evanescence_ as individuals adjust
their emotional reactions (Wilson et al., 2003), and the role of media in
post-traumatic stress disorder after major events.

As far as the online behavior can be viewed as a proxy of mobility, it may be
especially useful in the understanding of public compliance with the public
health measures, and its implications on the spread of disease. In the post-
hoc analysis of the effectiveness of government measures, online data may
provide a window into individual behaviors that signify online and offline
socialization, as well as interest in public health messages, which may relate
to actions individuals take that may raise or lower the risk of disease
contraction. Further, country-specific cultural aspects may play a role, as
well as trust in or disobedience to authority, and individual’s relation to
society.

There are several important limitations to our study. Not only are we limited
by the users of two specific internet platforms (albeit some of the most
popular ones), the adoption of these platforms is non-uniform around the
world, allowing us to examine only some countries. Analysis of local
platforms, such as Sina Weibo in China, may provide a better coverage.
Further, as we have found, definitions of “lockdown” are highly varied, as
each country presents a unique combination of local guidance, social support
systems, and public messaging, which makes comparison across countries
approximate. Finally, a plethora of other signals should be considered when
modeling public health-related behaviors beyond lockdown measures, and future
work in understanding health belief formation and the changing of action
affordances will provide a fuller picture of this emergency.

In order to support repeatable and extensible research, we make country-
specific daily data and additional visualizations available at
https://github.com/ymejova/yt-tw-covid.

##  8\. Acknowledgments

The research leading to these results received partial funding from the EU
H2020 Research and Innovation programme under grant agreements No 830927
(Concordia). These results reflect only the authors’ view and the Commission
is not responsible for any use that may be made of the information it
contains.

## References

  * (1)
  * Abisheva et al. (2014) Adiya Abisheva, Venkata Rama Kiran Garimella, David Garcia, and Ingmar Weber. 2014.  Who watches (and shares) what on youtube? and when? using twitter to understand youtube viewership. In _Proceedings of the 7th ACM international conference on Web search and data mining_. 593–602.
  * Arora et al. (2020) Anshika Arora, Pinaki Chakraborty, M. P. S. Bhatia, and Prabhat Mittal. 2020.  Role of Emotion in Excessive Use of Twitter During COVID-19 Imposed Lockdown in India.  _Journal of Technology in Behavioral Science_ (2020).  https://doi.org/10.1007/s41347-020-00174-3
  * Barchiesi et al. (2015) Daniele Barchiesi, Helen Susannah Moat, Christian Alis, Steven Bishop, and Tobias Preis. 2015\.  Quantifying international travel flows using Flickr.  _PloS one_ 10, 7 (2015), e0128470.
  * BBC (2020) BBC. 2020.  Coronavirus: Italy extends emergency measures nationwide.  _BBC News_ (March 2020).
  * Beiró et al. (2016) Mariano G Beiró, André Panisson, Michele Tizzoni, and Ciro Cattuto. 2016.  Predicting human mobility through the assimilation of social media traces into mobility models.  _EPJ Data Science_ 5 (2016), 1–15.
  * Bergamo (2020) Monica Bergamo. 2020\.  Brasil registra primeira morte por coronavírus.  _Folha de S.Paulo_ (March 2020).
  * Bernal et al. (2017) James Lopez Bernal, Steven Cummins, and Antonio Gasparrini. 2017\.  Interrupted time series regression for the evaluation of public health interventions: a tutorial.  _International journal of epidemiology_ 46, 1 (2017), 348–355.
  * Bisanzio et al. (2020) Donal Bisanzio, Moritz UG Kraemer, Isaac I Bogoch, Thomas Brewer, John S Brownstein, and Richard Reithinger. 2020.  Use of Twitter social media activity as a proxy for human mobility to predict the spatiotemporal spread of COVID-19 at global scale.  _Geospatial health_ 15, 1 (2020).
  * Blavatnik School of Government (2020) Blavatnik School of Government. 2020\.  Oxford COVID-19 Government Response Tracker.  Available at https://www.bsg.ox.ac.uk/research/research-projects/coronavirus-government-response-tracker, accessed on 03 December 2020.
  * Böttger et al. (2020) Timm Böttger, Ghida Ibrahim, and Ben Vallis. 2020\.  How the Internet Reacted to Covid-19: A Perspective from Facebook’s Edge Network. In _Proceedings of the ACM Internet Measurement Conference_ (Virtual Event, USA) _(IMC ’20)_. 34–41.
  * Chaffey (2020) Dave Chaffey. 2020\.  Global social media research summary August 2020.  Available at https://www.smartinsights.com/social-media-marketing/social-media-strategy/new-global-social-media-research/, accessed on 08 February 2021.
  * Christodoulou, George and Georgiou, Chryssis and Pallis, George (2012) Christodoulou, George and Georgiou, Chryssis and Pallis, George. 2012.  The Role of Twitter in YouTube Videos Diffusion. In _Web Information Systems Engineering - (WISE)_ , Wang, X. Sean and Cruz, Isabel and Delis, Alex and Huang, Guangyan (Ed.). 426–439.
  * Cinelli et al. (2020) Matteo Cinelli, Walter Quattrociocchi, Alessandro Galeazzi, Carlo Michele Valensise, Emanuele Brugnoli, Ana Lucia Schmidt, Paola Zola, Fabiana Zollo, and Antonio Scala. 2020\.  The COVID-19 social media infodemic.  _Scientific Reports_ 10 (October 2020).  Issue 1.
  * Deng et al. (2015) Zhengyu Deng, Ming Yan, Jitao Sang, and Changsheng Xu. 2015\.  Twitter is Faster: Personalized Time-Aware Video Recommendation from Twitter to YouTube.  _ACM Trans. Multimedia Comput. Commun. Appl._ 11, 2, Article 31 (January 2015), 23 pages.
  * Dusi (2020) Elena Dusi. 2020\.  Coronavirus, in dieci comuni lombardi: 50 mila persone costrette a restare in casa. Quarantena all’ospedale milanese di Baggio.  _La Repubblica_ (February 2020).
  * European Centre for Disease Prevention and Control (2020) European Centre for Disease Prevention and Control. 2020.  Considerations relating to social distancing measures in response to COVID-19 – second update.  _ECDC_ (March 2020).
  * Feldmann et al. (2020) Anja Feldmann, Oliver Gasser, Franziska Lichtblau, Enric Pujol, Ingmar Poese, Christoph Dietzel, Daniel Wagner, Matthias Wichtlhuber, Juan Tapiador, Narseo Vallina-Rodriguez, Oliver Hohlfeld, and Georgios Smaragdakis. 2020.  The Lockdown Effect: Implications of the COVID-19 Pandemic on Internet Traffic. In _Proceedings of the ACM Internet Measurement Conference_ (Virtual Event, USA) _(IMC ’20)_. 1–18.
  * Feng et al. (2018) Jie Feng, Yong Li, Chao Zhang, Funing Sun, Fanchao Meng, Ang Guo, and Depeng Jin. 2018.  Deepmove: Predicting human mobility with attentional recurrent networks. In _Proceedings of the 2018 world wide web conference_. 1459–1468.
  * Fischer (2020) Sara Fischer. 2020\.  Social media use spikes during pandemic.  Available at https://www.axios.com/social-media-overuse-spikes-in-coronavirus-pandemic-764b384d-a0ee-4787-bd19-7e7297f6d6ec.html, accessed on 08 February 2021.
  * Globo (2020) Globo. 2020.  Belem e mais 9 cidades do Para entram em ’lockdown’; estado e o 2 do país a adotar a medida contra o coronavirus.  _Globo.com_ (May 2020).
  * Hasan et al. (2013) Samiul Hasan, Xianyuan Zhan, and Satish V Ukkusuri. 2013\.  Understanding urban human activity and mobility patterns using large-scale location-based data from online social media. In _Proceedings of the 2nd ACM SIGKDD international workshop on urban computing_. 1–8.
  * Hübl et al. (2017) Franziska Hübl, Sreten Cvetojevic, Hartwig Hochmair, and Gernot Paulus. 2017.  Analyzing refugee migration patterns using geo-tagged tweets.  _ISPRS International Journal of Geo-Information_ 6, 10 (2017), 302.
  * Internet World Stats (2020) Internet World Stats. 2020\.  Alphabetic List of Countries.  Available at https://www.internetworldstats.com/list2.htm, accessed on 25 February 2021.
  * Iqbal (2020a) Mansoor Iqbal. 2020a.  Facebook Revenue and Usage Statistics (2020).  Available at https://www.businessofapps.com/data/facebook-statistics/, accessed on 08 February 2021.
  * Iqbal (2020b) Mansoor Iqbal. 2020b.  Twitter Revenue and Usage Statistics (2020).  Available at https://www.businessofapps.com/data/twitter-statistics/, accessed on 08 February 2021.
  * Iqbal (2020c) Mansoor Iqbal. 2020c.  YouTube Revenue and Usage Statistics (2020).  Available at https://www.businessofapps.com/data/youtube-statistics/, accessed on 08 February 2021.
  * Kemp (2020) Simon Kemp. 2020\.  Digital 2020: July Global Statshot.  Available at https://datareportal.com/reports/digital-2020-july-global-statshot, accessed on 08 February 2021.
  * Kraemer et al. (2018) Moritz UG Kraemer, Donal Bisanzio, RC Reiner, R Zakar, Jared B Hawkins, Clark C Freifeld, David L Smith, Simon I Hay, John S Brownstein, and T Alex Perkins. 2018\.  Inferences about spatiotemporal variation in dengue virus transmission are sensitive to assumptions about human mobility: a case study using geolocated tweets from Lahore, Pakistan.  _EPJ Data Science_ 7 (2018), 1–17.
  * Kuiper et al. (2020) Malouke Esra Kuiper, Anne Leonore de Bruijn, Chris Reinders Folmer, Elke Olthuis, Megan Brownlee, Emmeke Barbara Kooistra, Adam Fine, and Benjamin Van Rooij. 2020\.  The intelligent lockdown: Compliance with COVID-19 mitigation measures in the Netherlands.  _Available at SSRN 3598215_ (2020).
  * Li et al. (2020) Heidi Oi-Yee Li, Adrian Bailey, David Huynh, and James Chan. 2020\.  YouTube as a source of information on COVID-19: a pandemic of misinformation?  _BMJ Global Health_ 5, 5 (2020).  https://doi.org/10.1136/bmjgh-2020-002604
  * Lutu et al. (2020) Andra Lutu, Diego Perino, Marcelo Bagnulo, Enrique Frias-Martinez, and Javad Khangosstar. 2020.  A Characterization of the COVID-19 Pandemic Impact on a Mobile Network Operator Traffic. In _Proceedings of the ACM Internet Measurement Conference_ (Virtual Event, USA) _(IMC ’20)_. 19–33.
  * Mainichi (2020) Mainichi. 2020\.  Japan to declare nationwide state of emergency amid virus spread.  _The Mainichi_ (April 2020).
  * McGraw and Oprysko (2020) Meridith McGraw and Caitlin Oprysko. 2020.  Inside the White House during ’15 Days to Slow the Spread’.  _Politico_ (March 2020).
  * McNeill et al. (2017) Graham McNeill, Jonathan Bright, and Scott A Hale. 2017\.  Estimating local commuting patterns from geolocated Twitter data.  _EPJ Data Science_ 6 (2017).
  * Quercia et al. (2014) Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello. 2014\.  The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city. In _Proceedings of the 25th ACM conference on Hypertext and social media_. 116–125.
  * Thomas et al. (2020) Hale Thomas, Noam Angrist, Emily Cameron-Blake, Laura Hallas, Beatriz Kira, Saptarshi Majumdar, Anna Petherick, Toby Phillips, Helen Tatlow, and Samuel Webster. 2020\.  Oxford COVID-19 Government Response Tracker.  Available at https://github.com/OxCGRT/covid-policy-tracker.
  * Tokyo News (2020) Tokyo News. 2020\.  PM Abe asks all schools in Japan to temporarily close over coronavirus.  _Tokyo News_ (February 2020).
  * Truong et al. (2020) Charles Truong, Laurent Oudre, and Nicolas Vayatis. 2020\.  Selective review of offline change point detection methods.  _Signal Processing_ 167 (2020).
  * Wambui et al. (2015) G Dorcas Wambui, Gichuhi Anthony Waititu, and Anthony Wanjoya. 2015.  The power of the pruned exact linear time (PELT) test in multiple changepoint detection.  _Am. J. Theor. Appl. Stat_ 4, 6 (2015), 581–586.
  * Wilson et al. (2003) Timothy D Wilson, Daniel T Gilbert, and David B Centerbar. 2003\.  Making sense: The causes of emotional evanescence.  _The psychology of economic decisions_ 1 (2003), 209–233.
  * Wu et al. (2015) Fei Wu, Zhenhui Li, Wang-Chien Lee, Hongjian Wang, and Zhuojie Huang. 2015.  Semantic annotation of mobility data using social media. In _Proceedings of the 24th International Conference on World Wide Web_. 1253–1263.
  * Wu et al. (2016) Fei Wu, Hongjian Wang, and Zhenhui Li. 2016.  Interpreting traffic dynamics using ubiquitous urban data. In _Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 1–4.
  * Yan et al. (2014) Ming Yan, Jitao Sang, and Changsheng Xu. 2014.  Mining Cross-Network Association for YouTube Video Promotion. In _Proceedings of the 22nd ACM International Conference on Multimedia_ (Orlando, Florida, USA) _(MM ’14)_. 557–566.
  * Yan et al. (2015) Ming Yan, Jitao Sang, and Changsheng Xu. 2015.  Unified YouTube Video Recommendation via Cross-Network Collaboration. In _Proceedings of the 5th ACM on International Conference on Multimedia Retrieval_ (Shanghai, China) _(ICMR ’15)_. 19–26.
  * Yang et al. (2020) Kai-Cheng Yang, Francesco Pierri, Pik-Mai Hui, David Axelrod, Christopher Torres-Lugo, John Bryden, and Filippo Menczer. 2020.  The COVID-19 Infodemic: Twitter versus Facebook.  arXiv:2012.09353 [cs.SI]
  * Yu et al. (2014) Honglin Yu, Lexing Xie, and Scott Sanner. 2014.  Twitter-driven youtube views: Beyond individual influencers. In _Proceedings of the 22nd ACM international conference on Multimedia_. 869–872.
  * Yu et al. (2015) Honglin Yu, Lexing Xie, and Scott Sanner. 2015.  The lifecyle of a youtube video: Phases, content and popularity. In _Ninth International AAAI Conference on Web and Social Media_.
  * Zeng et al. (2021) Chengbo Zeng, Jiajia Zhang, Zhenlong Li, Xiaowen Sun, Bankole Olatosi, Sharon Weissman, and Xiaoming Li. 2021.  Spatial-temporal relationship between population mobility and COVID-19 outbreaks in South Carolina: A time series forecasting analysis.  _medRxiv_ (2021).

##  Appendix A Media sharing, mobility, lockdowns, and ITS model for select
countries


assignment for $P_{1}$ (i.e. we never define $P^{\prime}_{1}$); thus the
objective function value remains unchanged., which intuitively makes it easier
to guess feasible solutions to $\Gamma$. We also omitted the positive
semidefinite constraints on all $P_{i}$, since141414In our particular setting,
it is clear that $Q_{1}\succeq 0$. However, more generally in the GW
framework, the operators ${\left\\{Q_{a}\right\\}}$ defining a measuring co-
strategy all satisfy $Q_{a}\succeq 0$. $P_{4}\succeq Q_{1}\succeq 0$ implies
$P_{i}\succeq 0$ for all $i$. We now follow the standard Lagrange approach for
deriving the dual SDP (see, e.g. [BV04]). Labelling equations
(60),(61),(62),(63) with dual variables $Y_{1},\ldots,Y_{4}$, respectively,
the primal variables in the Lagrange dual function can be isolated as follows:

Primal variable | Factor
---|---
$P_{4}$ | $-Y_{1}+Y_{2}\otimes I_{\mathcal{X}_{4}}$
$P_{3}$ | $-{\rm Tr}_{\mathcal{Y}_{3}}(Y_{2})+Y_{3}\otimes I_{\mathcal{X}_{3}}$
$P_{2}$ | $-{\rm Tr}_{\mathcal{Y}_{2}}(Y_{3})+Y_{4}\otimes I_{\mathcal{X}_{2}}$
$P_{1}$ | $I_{\mathcal{X}_{1}}-{\rm Tr}_{\mathcal{Y}_{1}}(Y_{4})$

For clarity and as an example, this says the term $P_{4}(-Y_{1}+Y_{2}\otimes
I_{\mathcal{X}_{4}})$ appears in the dual function. This yields dual SDP:

max: $\displaystyle{\rm Tr}(Y_{1}Q_{1})$ (64) subject to: $\displaystyle-
Y_{1}+Y_{2}\otimes I_{\mathcal{X}_{4}}=0$ (65) $\displaystyle-{\rm
Tr}_{\mathcal{Y}_{3}}(Y_{2})+Y_{3}\otimes I_{\mathcal{X}_{3}}=0$ (66)
$\displaystyle-{\rm Tr}_{\mathcal{Y}_{2}}(Y_{3})+Y_{4}\otimes
I_{\mathcal{X}_{2}}=0$ (67) $\displaystyle I_{\mathcal{X}_{1}}-{\rm
Tr}_{\mathcal{Y}_{1}}(Y_{4})=0$ (68) $\displaystyle
Y_{1},Y_{2},Y_{3},Y_{4}\succeq 0$ (69)

Now we make the following simplifications: (1) Replace $Y_{1}$ with
$Y_{2}\otimes I_{\mathcal{X}_{4}}$ (follows from Equation (65)), (2) drop the
constraints $Y_{3},Y_{4}\succeq 0$ (since they are implied by $Y_{2}\succeq
0$), and (3) relax the equalities to inequalities (which follows similar to
the argument for the primal, except here we also require that we are
maximizing with respect to $Y_{2}$ below). Hence, we obtain:

max: $\displaystyle{\rm Tr}(Y_{2}{\rm Tr}_{\mathcal{X}_{4}}(Q_{1}))$ (70)
subject to: $\displaystyle-{\rm Tr}_{\mathcal{Y}_{3}}(Y_{2})+Y_{3}\otimes
I_{\mathcal{X}_{3}}\succeq 0$ (71) $\displaystyle-{\rm
Tr}_{\mathcal{Y}_{2}}(Y_{3})+Y_{4}\otimes I_{\mathcal{X}_{2}}\succeq 0$ (72)
$\displaystyle I_{\mathcal{X}_{1}}-{\rm Tr}_{\mathcal{Y}_{1}}(Y_{4})\succeq 0$
(73) $\displaystyle Y_{2}\succeq 0$ (74)

Note the $Y_{2}\succeq 0$ _cannot_ be removed. Intuitively, this is because
the constraint $I_{\mathcal{X}_{1}}-{\rm Tr}_{\mathcal{Y}_{1}}(Y_{4})\succeq
0$ alone does not imply $Y_{4}\succeq 0$. Rather, it is the constraint
$Y_{2}\succeq 0$ which forces $Y_{4}\succeq 0$ here. Indeed, a sanity check in
CVX for Matlab reveals removing the $Y_{2}\succeq 0$ incorrectly yields an
unbounded SDP.

We now repeat the process by taking the dual of the dual to arrive at a
simplified primal as follows. (Note that the inequalities above now go in the
other direction, since we are starting from the dual SDP.) Labelling the
constraints above $R_{1},\ldots,R_{4}$, we have factor table:

Dual variable | Factor
---|---
$Y_{2}$ | ${\rm Tr}_{\mathcal{X}_{4}}(Q_{1})-R_{1}\otimes I_{\mathcal{Y}_{3}}+R_{4}$
$Y_{3}$ | ${\rm Tr}_{\mathcal{X}_{3}}(R_{1})-R_{2}\otimes I_{\mathcal{Y}_{2}}$
$Y_{4}$ | ${\rm Tr}_{\mathcal{X}_{2}}(R_{2})-R_{3}\otimes I_{\mathcal{Y}_{1}}$

This yields primal SDP (after omitting the redundant constraints
$R_{1},R_{2},R_{3},R_{4}\succeq 0$):

min: $\displaystyle{\rm Tr}(R_{3})$ (75) subject to: $\displaystyle{\rm
Tr}_{\mathcal{X}_{4}}(Q_{1})-R_{1}\otimes I_{\mathcal{Y}_{3}}\preceq 0$ (76)
$\displaystyle{\rm Tr}_{\mathcal{X}_{3}}(R_{1})-R_{2}\otimes
I_{\mathcal{Y}_{2}}\preceq 0$ (77) $\displaystyle{\rm
Tr}_{\mathcal{X}_{2}}(R_{2})-R_{3}\otimes I_{\mathcal{Y}_{1}}\preceq 0$ (78)

Taking the dual of the primal now yields the previous dual; so it seems we are
done. Relabelling variables for the primal and dual, we obtain the final $m=3$
primal and dual SDPs, respectively:

min: $\displaystyle{\rm Tr}(P_{1})$ subject to: $\displaystyle{\rm
Tr}_{\mathcal{X}_{4}}(Q_{1})-P_{3}\otimes I_{\mathcal{Y}_{3}}\preceq 0$
$\displaystyle{\rm Tr}_{\mathcal{X}_{3}}(P_{3})-P_{2}\otimes
I_{\mathcal{Y}_{2}}\preceq 0$ $\displaystyle{\rm
Tr}_{\mathcal{X}_{2}}(P_{2})-P_{1}\otimes I_{\mathcal{Y}_{1}}\preceq 0$

max: $\displaystyle\langle Y_{1},{\rm Tr}_{\mathcal{X}_{4}}(Q_{1})\rangle$
subject to: $\displaystyle-{\rm Tr}_{\mathcal{Y}_{3}}(Y_{1})+Y_{2}\otimes
I_{\mathcal{X}_{3}}\succeq 0$ $\displaystyle-{\rm
Tr}_{\mathcal{Y}_{2}}(Y_{2})+Y_{3}\otimes I_{\mathcal{X}_{2}}\succeq 0$
$\displaystyle-{\rm Tr}_{\mathcal{Y}_{1}}(Y_{3})+I_{\mathcal{X}_{1}}\succeq 0$
$\displaystyle Y_{1}\succeq 0$

##### General case.

The derivation above straightforwardly extends to the case of arbitrary $m\geq
2$, yielding primal and dual SDPs:

Primal SDP

min: $\displaystyle{\rm Tr}(P_{1})$ (79) s.t. $\displaystyle{\rm
Tr}_{\mathcal{X}_{m+1}}(Q_{1})-P_{m}\otimes I_{\mathcal{Y}_{m}}\preceq 0$ (80)
$\displaystyle{\rm Tr}_{\mathcal{X}_{i+1}}(P_{i+1})-P_{i}\otimes
I_{\mathcal{Y}_{i}}\preceq 0$ $\displaystyle\forall
i\in{\left\\{1,\ldots,m-1\right\\}}$ (81)

Dual SDP

max: $\displaystyle\langle Y_{1},{\rm Tr}_{\mathcal{X}_{m+1}}(Q_{1})\rangle$
(83) s.t. $\displaystyle-{\rm Tr}_{\mathcal{Y}_{m-i+1}}(Y_{i})+Y_{i+1}\otimes
I_{\mathcal{X}_{m-i+1}}\succeq 0$ $\displaystyle\forall
i\in{\left\\{1,\ldots,m\right\\}}$ (84) $\displaystyle Y_{1}\succeq 0$ (85)

where note for uniformity in stating the dual constraints, we define
$Y_{m+1}:=1$ in the dual SDP.

###  D.2 An approximately optimal dual solution?

We now give a simple feasible solution $Y:={\left\\{Y_{i}\right\\}}$ to the
dual SDP, whose objective function value appears to scale essentially as one
might expect, _if_ security were to hold for our OTM construction. While we
can explicitly prove $Y$ is _not_ dual optimal (thus, it only yields a lower
bound on the best cheating probability), we conjecture it is optimal up to a
polynomial multiplicative factor (Conjecture D.2), which would in turn imply
security against subexponentially many queries to the token, as desired.

##### A candidate dual solution.

Recall that each $\mathcal{Y}_{i}$ registers encodes a message from the
receiver to the token, consisting of $n+1$ qubits. Let $d:=2^{n+1}$ denote the
dimension of this space. Define solution
$Y:={\left\\{Y_{1},\ldots,Y_{m}\right\\}}$ via:

$Y_{i}=\frac{1}{d^{m-i+1}}I_{\mathcal{Y}_{1\cdots m},\mathcal{X}_{1\cdots
m}}.$ (86)

Note that $Y_{1}\succeq 0$ trivially, and that Equation (84) holds with
equality for all $i\in{\left\\{1,\ldots,m\right\\}}$. Thus, $Y$ is a dual
feasible solution. Moreover, it obtains objective function value

$\beta:=\frac{{\rm Tr}(Q_{1})}{d^{m}}=\frac{\left\lvert
R\right\rvert}{4^{n}d^{m}},$ (87)

where recall we defined relation $R$ in Equation (30) via

$(t,\widetilde{y},z)\in R\text{ if and only if }\left[t\in T\text{ and
}(\widetilde{y},z)\in Y_{t}\right].$

##### The cardinality of $R$.

To analyze $\beta$, we require an expression for $\left\lvert R\right\rvert$,
given as follows.

######  Lemma D.1.

$\left\lvert
R\right\rvert=\left(2^{m(n+1)+n}\right)\sum_{\alpha=0}^{n}\binom{n}{\alpha}\left[1-\left(1-\frac{1}{2^{\alpha+1}}\right)^{m}-\left(1-\frac{1}{2^{n-\alpha+1}}\right)^{m}+\left(1-\frac{1}{2^{\alpha+1}}-\frac{1}{2^{n-\alpha+1}}\right)^{m}\right]$

###### Proof.

Recall again from Equation (30) that $R$ is defined via

$(t,\widetilde{y},z)\in R\text{ if and only if }\left[t\in T\text{ and
}(\widetilde{y},z)\in Y_{t}\right],$

where $T$ is the set of successful query responses. For any quantum key
$|\psi_{z}\rangle$, let $\alpha$ denote the number of qubits in
$|\psi_{z}\rangle$ which are encoded in the $Z$ basis. Note that fixing
$\alpha$ partitions $R$ into $n+1$ sets; let $R_{\alpha}$ denote the set in
this partition corresponding to $\alpha$ $Z$-bits. We analyze each
$R_{\alpha}$ independently first.

##### Computing $\left\lvert R_{\alpha}\right\rvert$ for fixed $\alpha$.

Fix any $0\leq\alpha\leq n$, and any secret key
$z\in{\left\\{0,1\right\\}}^{2n}$ with precisely $\alpha$ bits in the
$Z$-basis; denote the resulting subset of $R_{\alpha}$ by $R_{\alpha,z}$. We
now ask: Conditioned on secret key $z$ and token response
$t\in\Sigma={\left\\{0,1,\overline{0},\overline{1}\right\\}}$, how many query
strings $\widetilde{y}$ are consistent with $t$?

  * •

Case 1: $t=0$. Since we have to get precisely all $\alpha$ bits correctly
(i.e. those in the $Z$ basis), and we can get up to $n-\alpha$ bits in the $X$
basis incorrect, we have $2^{n-\alpha}$ choices for $\widetilde{y}$. (Note
that the choice bit for $\widetilde{y}$ is forced to be $0$ since $t=0$.)

  * •

Case 2: $t=1$. This is analogous to $t=0$, except now we can get the $\alpha$
$Z$-bits incorrect and the $X$-bits must be correct. Thus, there are
$2^{\alpha}$ strings $\widetilde{y}$.

  * •

Case 3: $t=\overline{0}$. Since the $X$ bits can be anything, and there is
precisely one correct setting to the $Z$ basis bits, we have
$2^{n-\alpha}(2^{\alpha}-1)=2^{n}-2^{n-\alpha}$ choices for $\widetilde{y}$.

  * •

Case 4: $t=\overline{1}$. Analogous to the $t=\overline{0}$ case, we have
$2^{\alpha}(2^{n-\alpha}-1)=2^{n}-2^{\alpha}$ strings $\widetilde{y}$.

As a sanity check, note that summing the four values obtained above yields
precisely $d=2^{n+1}$ strings $\widetilde{y}$, which is the dimension of each
register $\mathcal{Y}_{i}$, as desired.

To now obtain an expression for $\left\lvert R_{\alpha,z}\right\rvert$, recall
that any set of $m$ queries is successful if it contains at least one
successful $0$-query and one successful $1$-query. Thus, using the inclusion-
exclusion formula (intuition to follow):

$\displaystyle\left\lvert R_{\alpha,z}\right\rvert=2^{m(n+1)}$
$\displaystyle-$
$\displaystyle\sum_{a=0}^{m}\binom{m}{a}(2^{\alpha})^{a}\left[\sum_{b=0}^{m-a}\binom{m-a}{b}\left(2^{n}-2^{n-\alpha}\right)^{b}\left(2^{n}-2^{\alpha}\right)^{m-a-b}\right]$
(88) $\displaystyle-$
$\displaystyle\sum_{a=0}^{m}\binom{m}{a}(2^{n-\alpha})^{a}\left[\sum_{b=0}^{m-a}\binom{m-a}{b}\left(2^{n}-2^{n-\alpha}\right)^{b}\left(2^{n}-2^{\alpha}\right)^{m-a-b}\right]$
(89) $\displaystyle+$
$\displaystyle\sum_{b=0}^{m}\binom{m}{b}\left(2^{n}-2^{n-\alpha}\right)^{b}\left(2^{n}-2^{\alpha}\right)^{m-b}.$
(90)

Above, the first term is the set of all query strings on $m$ messages. The
negative terms count the number of query strings with no successful
$0$-queries and no successful $1$-queries, respectively. For the former, for
example, we first choose $a$ positions in which to put the successful
$1$-queries, and then distribute $\overline{0}$\- and $\overline{1}$-queries
among the remaining $m-a$ positions. The final, positive, term, counts the
number of query strings with neither a successful $0$\- nor a successful
$1$-query. Inverting the binomial expansion
$(a+b)^{k}=\sum_{l=0}^{k}\binom{k}{l}a^{l}b^{k-l}$, we can next write:

$\displaystyle\left\lvert R_{\alpha,z}\right\rvert=2^{m(n+1)}$
$\displaystyle-$
$\displaystyle\sum_{a=0}^{m}\binom{m}{a}(2^{\alpha})^{a}\left[(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m-a}$
(91) $\displaystyle-$
$\displaystyle\sum_{a=0}^{m}\binom{m}{a}(2^{n-\alpha})^{a}\left[(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m-a}$
(92) $\displaystyle+$
$\displaystyle\left[(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m}.$ (93)

Applying the binomial expansion again yields

$\displaystyle\left\lvert R_{\alpha,z}\right\rvert=2^{m(n+1)}$
$\displaystyle-$
$\displaystyle\left[2^{\alpha}+(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m}$
(94) $\displaystyle-$
$\displaystyle\left[2^{n-\alpha}+(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m}$
(95) $\displaystyle+$
$\displaystyle\left[(2^{n}-2^{n-\alpha})+(2^{n}-2^{\alpha})\right]^{m}.$ (96)

Collecting like terms and factoring out $2^{m(n+1)}$ yields

$\left\lvert
R_{\alpha,z}\right\rvert=\left(2^{m(n+1)}\right)\left[1-\left(1-\frac{1}{2^{\alpha+1}}\right)^{m}-\left(1-\frac{1}{2^{n-\alpha+1}}\right)^{m}+\left(1-\frac{1}{2^{\alpha+1}}-\frac{1}{2^{n-\alpha+1}}\right)^{m}\right].$
(97)

Recall this was for any fixed secret key $z$. But for any fixed
$0\leq\alpha\leq n$, there are precisely
$\binom{n}{\alpha}2^{\alpha}2^{n-\alpha}=\binom{n}{\alpha}2^{n}$ choices of
$z$ with $\alpha$ qubits encoded in the $Z$-basis. Thus,

$\left\lvert
R_{\alpha}\right\rvert=\binom{n}{\alpha}\left(2^{m(n+1)+n}\right)\left[1-\left(1-\frac{1}{2^{\alpha+1}}\right)^{m}-\left(1-\frac{1}{2^{n-\alpha+1}}\right)^{m}+\left(1-\frac{1}{2^{\alpha+1}}-\frac{1}{2^{n-\alpha+1}}\right)^{m}\right].$

##### The final expression.

The claim follows since the sets $R_{\alpha}$ partition $R$, and so
$\left\lvert R\right\rvert=\sum_{\alpha=0}^{n}\left\lvert
R_{\alpha}\right\rvert$. ∎

##### Using Lemma D.1 to heuristically bound $\beta$.

Recall that our goal is to understand the dual value $\beta$ from Equation
(87) obtained by our dual solution, which in turn gives us a lower bound on
the optimal cheating probability. So let us get a sense of how $\left\lvert
R\right\rvert$ might scale asymptotically by deriving a heuristic
approximation. To begin, applying the Hölder inequality to $\left\lvert
R\right\rvert$ in Lemma D.1 yields

$\displaystyle\left\lvert R\right\rvert$ $\displaystyle\leq$
$\displaystyle\left(2^{m(n+1)+2n}\right)\cdot\max_{\alpha}\left[1-\left(1-\frac{1}{2^{\alpha+1}}\right)^{m}-\left(1-\frac{1}{2^{n-\alpha+1}}\right)^{m}+\left(1-\frac{1}{2^{\alpha+1}}-\frac{1}{2^{n-\alpha+1}}\right)^{m}\right]$

We shall assume the maximum is attained for $\alpha=n/2$. For this choice of
$\alpha$, recalling that for large $x$,

$\left(1-\frac{1}{x}\right)^{m}\approx{e^{-\frac{m}{x}}},$

in the large $n$ limit the term in the square brackets above is approximately
$\left[1-2e^{-\frac{m}{2^{n/2+1}}}+e^{-\frac{m}{2^{n/2}}}\right].$ Hence, we
may bound

$\displaystyle\left\lvert R\right\rvert$ $\displaystyle\leq$
$\displaystyle\left(2^{m(n+1)+2n}\right)\left[1-2e^{-\frac{m}{2^{n/2+1}}}+e^{-\frac{m}{2^{n/2}}}\right]$
$\displaystyle\leq$
$\displaystyle\left(2^{m(n+1)}\right)4^{n}\left[1-e^{-\frac{m}{2^{n/2}}}\right]$
$\displaystyle\approx$ $\displaystyle d^{m}4^{n}\frac{m}{2^{n/2}},$

for $m\ll n$, and where in the last line we used $d=2^{n+1}$. Plugging this
into Equation (87), we get precisely the type of behavior we want:

$\beta=\frac{\left\lvert R\right\rvert}{4^{n}d^{m}}\lesssim\frac{m}{2^{n/2}}.$
(98)

Thus, for polynomial $m$, the objective function value obtained by our dual
solution from Equation (86)is exponentially small in the number of key bits,
$n$ (under the heuristic approximations made in this derivation).

##### The dual solution is not optimal.

Naturally, this raises the question of whether our dual solution $Y$ from
Equation (86) is optimal. If it were, then a matching primal solution can in
principle be found (it is easy to see that Slater’s constraint qualification
holds for the primal and dual, and so strong duality holds), and thus the
optimal cheating probability would be approximately that given in Equation
(98). Unfortunately, $Y$ is provably not dual optimal. In particular, for
$m=2$ and $n=1$ ($2$ queries, $1$ key bit), the primal optimal value is
$\approx 0.85$ and for $m=3,n=1$, it is151515With $m=3$ and $n=1$, it is
trivial to break the OTM construction. Namely, first measure the quantum key
$|\psi_{z}\rangle$ in the standard basis and make an honest $0$-query to
extract the first secret bit. Then, since $|\psi_{z}\rangle$ is only $1$
qubit, we can use brute force to make two $1$-queries to the token with the
only two possible candidate keys in the $X$-basis, $0$, or $1$. $1$ (both
numerical values calculated via CVX in Matlab). However, evaluating Lemma D.1
for these values of $m$ and $n$ yields $\beta=0.25$ and $\beta=0.46875$,
respectively. Thus, the dual solution $Y$ of Equation (86) is not optimal.
However, as the heuristic derivation of $\beta$ from Equation (98) rather
naturally led to precisely the desired type of bound on the cheating
probability, we conjecture that $Y$ is _approximately_ optimal, in the
following sense.

######  Conjecture D.2.

The optimal values for the primal and dual SDPs of Section D.1 are, up to
multiplicative scaling by some fixed polynomial in $m$, equal to
$\beta=\frac{\left\lvert R\right\rvert}{4^{n}d^{m}}$.

##  Appendix E Proof of Lemma 4.3

###### Proof.

Observe first that an honest receiver Alice wishing to extract $s_{i}$ acts as
follows. She applies a unitary $U_{i}\in\mathcal{U}({A}\otimes{B})$ to get
state

$|\phi_{1}\rangle:=U_{i}|\psi\rangle_{{A}{B}}|0\rangle_{{C}}.$ (99)

She then measures ${B}$ in the computational basis and postselects on result
$y\in{\left\\{0,1\right\\}}^{n}$, obtaining state

$|\phi_{2}\rangle:=|\phi_{y}\rangle_{{A}}|y\rangle_{{B}}|0\rangle_{{C}}.$
(100)

She now treats $y$ as a “key” for $s_{i}$, _i.e._ , she applies $O_{f}$ to
${B}\otimes{C}$ to obtain her desired bit $s_{i}$, _i.e._ ,

$|\phi_{3}\rangle:=|\phi_{y}\rangle_{{A}}|y\rangle_{{B}}|s_{i}\rangle_{{C}}.$
(101)

A malicious receiver Bob wishing to extract $s_{0}$ and $s_{1}$ now acts
similarly to the rewinding strategy for superposition queries. Suppose without
loss of generality that $s_{0}$ has at most $\Delta$ keys. Then, Bob first
applies $U_{0}$ to prepare $|\phi_{1}\rangle$ from Equation (99), which we can
express as

$|\phi_{1}\rangle=\sum_{y\in{\left\\{0,1\right\\}}^{n}}\alpha_{y}|\psi_{y}\rangle_{{A}}|y\rangle_{{B}}|0\rangle_{{C}}.$
(102)

for $\sum_{y}\left\lvert\alpha_{y}\right\rvert^{2}=1$. Since measuring ${B}$
next would allow us to retrieve $s_{0}$ in register $C$ with certainty, we
have that all $y$ appearing in the expansion above satisfy $f(y)=s_{0}$.
Moreover, since $s_{0}$ has at most $\Delta$ keys, there exists a key
$y^{\prime}$ such that $\left\lvert\alpha_{y^{\prime}}\right\rvert^{2}\geq
1/\Delta$. Bob now measures $B$ in the computational basis to obtain
$|\phi_{2}\rangle$ from Equation (100), obtaining $y^{\prime}$ with
probability at least $1/\Delta$. Feeding $y^{\prime}$ into $O_{f}$ yields
$s_{0}$. Having obtained $y^{\prime}$, we have that
$\left\lvert\langle\phi_{1}|\phi_{2}\rangle\right\rvert^{2}\geq 1/\Delta,$
implying

$\left\lvert\langle\psi|U_{0}^{\dagger}|\phi_{y^{\prime}}\rangle|y^{\prime}\rangle\right\rvert^{2}\geq
1/\Delta,$ (103)

_i.e._ , Bob now applies $U_{0}^{\dagger}$ to recover a state with “large”
overlap with initial state $|\psi\rangle$.

To next recover $s_{1}$, define $|\psi_{\rm good}\rangle:=U_{1}|\psi\rangle$
and $|\psi_{\rm
approx}\rangle:=U_{1}U_{0}^{\dagger}|\phi_{y^{\prime}}\rangle|y^{\prime}\rangle$.
Bob applies $U_{1}$ to obtain

$|\psi_{\rm approx}\rangle=\beta_{1}|\psi_{\rm
good}\rangle+\beta_{2}|\psi_{\rm good}^{\perp}\rangle,$ (104)

where $\sum_{i}\left\lvert\beta_{i}\right\rvert^{2}=1$, $\langle\psi_{\rm
good}|\psi_{\rm good}^{\perp}\rangle=0$, and
$\left\lvert\beta_{1}\right\rvert^{2}\geq 1/\Delta$. Define $\Pi_{\rm
good}:=\sum_{y\in{\left\\{0,1\right\\}}^{n}\text{ s.t.
}f(y)=s_{1}}|y\rangle{\langle y|}$. Then, the probability that measuring $B$
in the computational basis now yields a valid key for $s_{1}$ is

$\langle\psi_{\rm approx}|\Pi_{\rm good}|\psi_{\rm
approx}\rangle\geq\left\lvert\beta_{1}\right\rvert^{2}\geq\frac{1}{\Delta},$
(105)

where we have used the fact that $\Pi_{\rm good}|\psi_{\rm
good}\rangle=|\psi_{\rm good}\rangle$ (since an honest receiver can extract
$s_{1}$ with certainty). We conclude that Bob can extract both $s_{0}$ and
$s_{1}$ with probability at least $1/\Delta^{2}$. ∎

## References

  * [AC12] Scott Aaronson and Paul Christiano.  Quantum money from hidden subspaces.  In Proc. 44th Symposium on Theory of Computing (STOC) 2012, pages 41–60, 2012.  Full version available as arXiv:1203.4740.
  * [BB84] Charles H. Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  International Conference on Computers, Systems and Signal Processing, pages 175–179, 1984.
  * [BBCS92] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Marie-Hélène Skubiszewska.  Practical quantum oblivious transfer.  In Joan Feigenbaum, editor, CRYPTO’91, volume 576 of LNCS, pages 351–366. Springer, August 1992.
  * [BDS18] Shalev Ben-David and Or Sattath.  Quantum tokens for digital signatures.  arXiv:1609.09047, 2018.
  * [Bea91] Donald Beaver.  Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority.  Journal of Cryptology, 4(2):75–122, 1991.
  * [BFM88] Manuel Blum, Paul Feldman, and Silvio Micali.  Non-interactive zero-knowledge and its applications.  In 20th ACM STOC, pages 103–112. ACM Press, May 1988.
  * [BGS13] Anne Broadbent, Gus Gutoski, and Douglas Stebila.  Quantum one-time programs.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 344–360. Springer, August 2013.
  * [BGZ15] Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou.  Quantum one-time memories from stateless hardware.  arXiv:1511.01363, November 2015.
  * [BM82] Manuel Blum and Silvio Micali.  How to generate cryptographically strong sequences of pseudo random bits.  In 23rd FOCS, pages 112–117. IEEE Computer Society Press, November 1982.
  * [BS16] Anne Broadbent and Christian Schaffner.  Quantum cryptography beyond quantum key distribution.  Designs, Codes and Cryptography, 78(1):351–382, 2016.
  * [BV04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * [Can00a] Ran Canetti.  Security and composition of multiparty cryptographic protocols.  Journal of Cryptology, 13(1):143–202, 2000.
  * [Can00b] Ran Canetti.  Universally composable security: A new paradigm for cryptographic protocols.  Cryptology ePrint Archive, Report 2000/067, 2000.  http://eprint.iacr.org/2000/067.
  * [Can01] Ran Canetti.  Universally composable security: A new paradigm for cryptographic protocols.  In 42nd FOCS, pages 136–145. IEEE Computer Society Press, October 2001.
  * [CDPW07] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish.  Universally composable security with global setup.  In Salil P. Vadhan, editor, TCC 2007, volume 4392 of LNCS, pages 61–85. Springer, February 2007.
  * [CGLZ19] Kai-Min Chung, Marios Georgiou, Ching-Yi Lai, and Vassilis Zikas.  Cryptography with disposable backdoors.  Cryptography, 3(3):22, 2019.
  * [CGS08] Nishanth Chandran, Vipul Goyal, and Amit Sahai.  New constructions for UC secure computation using tamper-proof hardware.  In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 545–562. Springer, April 2008.
  * [Cho75] Man-Duen Choi.  Completely positive linear maps on complex matrices.  Linear Alg. Appl., 10:285, 1975.
  * [CKS+14] Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich, and Hong-Sheng Zhou.  (efficient) universally composable oblivious transfer using a minimal number of stateless tokens.  In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 638–662. Springer, February 2014.
  * [CLOS02] Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai.  Universally composable two-party and multi-party secure computation.  In 34th ACM STOC, pages 494–503. ACM Press, May 2002.
  * [CM97] Christian Cachin and Ueli Maurer.  Unconditional security against memory-bounded adversaries.  In Advances in Cryptology - CRYPTO 1997, LNCS, pages 292–306. Springer, 1997.
  * [DFL+09] Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner.  Improving the security of quantum protocols via commit-and-open.  In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 408–427. Springer, August 2009.
  * [DFSS05] Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner.  Cryptography in the bounded quantum-storage model.  In Symposium on Foundations of Computer Science - FOCS 2005, pages 449–458. IEEE, 2005.
  * [DNS10] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail.  Secure two-party quantum evaluation of unitaries against specious adversaries.  In Advances in Cryptology – Proc. CRYPTO 2010, LNCS, pages 685–706. Springer, 2010.
  * [DNS12] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail.  Actively secure two-party evaluation of any quantum operation.  In Advances in Cryptology – Proc. CRYPTO 2012, volume 7417 of LNCS, pages 794–811. Springer, 2012.
  * [DS13] Ivan Damgård and Alessandra Scafuro.  Unconditionally secure and universally composable commitments from physical assumptions.  In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 100–119. Springer, December 2013.
  * [FK18] Bill Fefferman and Shelby Kimmel.  Quantum vs. Classical Proofs and Subset Verification.  In Igor Potapov, Paul Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:23, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [FKS+13] Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou, and Vassilis Zikas.  Feasibility and completeness of cryptographic tasks in the quantum world.  In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 281–296. Springer, March 2013.
  * [Gav12] Dmitry Gavinsky.  Quantum money with classical verification.  In Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, pages 42–52, June 2012.
  * [GIS+10] Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia.  Founding cryptography on tamper-proof hardware tokens.  In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 308–326. Springer, February 2010.
  * [GKR08] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum.  One-time programs.  In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 39–56. Springer, August 2008.
  * [GL91] Shafi Goldwasser and Leonid A. Levin.  Fair computation of general functions in presence of immoral majority.  In Alfred J. Menezes and Scott A. Vanstone, editors, CRYPTO’90, volume 537 of LNCS, pages 77–93. Springer, August 1991.
  * [GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson.  How to play any mental game or A completeness theorem for protocols with honest majority.  In Alfred Aho, editor, 19th ACM STOC, pages 218–229. ACM Press, May 1987.
  * [GW07] Gus Gutoski and John Watrous.  Toward a general theory of quantum games.  In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565–574, 2007.
  * [Hei27] Werner Heisenberg.  Schwankungserscheinungen und quantenmechanik.  Zeitschrift fuer Physik, 40(7):501–506, July 1927.
  * [HSS11] Sean Hallgren, Adam Smith, and Fang Song.  Classical cryptographic protocols in a quantum world.  In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 411–428. Springer, August 2011.
  * [IPS08] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai.  Founding cryptography on oblivious transfer - efficiently.  In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 572–591. Springer, August 2008.
  * [Jam72] Andrzej Jamiołkowski.  Linear transformations which preserve trace and positive semi-definiteness of operators.  Rep. Math. Phys., 3:275, 1972.
  * [Kat07] Jonathan Katz.  Universally composable multi-party computation using tamper-proof hardware.  In Moni Naor, editor, EUROCRYPT 2007, volume 4515 of LNCS, pages 115–128. Springer, May 2007.
  * [Kil88] Joe Kilian.  Founding cryptography on oblivious transfer.  In 20th ACM STOC, pages 20–31. ACM Press, May 1988.
  * [KMPS14] Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai.  A full characterization of completeness for two-party randomized function evaluation.  In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 659–676. Springer, May 2014\.
  * [KMQ11] Daniel Kraschewski and Jörn Müller-Quade.  Completeness theorems with constructive proofs for finite deterministic 2-party functions.  In Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS, pages 364–381. Springer, March 2011.
  * [Liu14a] Yi-Kai Liu.  Building one-time memories from isolated qubits.  In Moni Naor, editor, ITCS 2014, pages 269–286. ACM, January 2014\.
  * [Liu14b] Yi-Kai Liu.  Single-shot security for one-time memories in the isolated qubits model.  In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS, pages 19–36. Springer, August 2014.
  * [Liu15] Yi-Kai Liu.  Privacy amplification in the isolated qubits model.  In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 785–814. Springer, April 2015.
  * [LPV09] Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam.  A unified framework for concurrent security: universal composability from stand-alone non-malleability.  In Michael Mitzenmacher, editor, 41st ACM STOC, pages 179–188. ACM Press, May / June 2009.
  * [Mau92] Ueli M. Maurer.  Protocols for secret key agreement by public discussion based on common information.  In Advances in Cryptology - CRYPTO 1992, volume 740 of LNCS, pages 461–470. Springer, 1992.
  * [MPR09] Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek.  Complexity of multi-party computation problems: The case of 2-party symmetric secure function evaluation.  In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 256–273. Springer, March 2009.
  * [MPR10] Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek.  A zero-one law for cryptographic complexity with respect to computational UC security.  In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 595–612. Springer, August 2010.
  * [MR92] Silvio Micali and Phillip Rogaway.  Secure computation (abstract).  In Joan Feigenbaum, editor, CRYPTO’91, volume 576 of LNCS, pages 392–404. Springer, August 1992.
  * [MR11] Ueli Maurer and Renato Renner.  Abstract cryptography.  In Bernard Chazelle, editor, ICS 2011, pages 1–21. Tsinghua University Press, January 2011.
  * [MVW13] Abel Molina, Thomas Vidick, and John Watrous.  Optimal counterfeiting attacks and generalizations for wiesner’s quantum money.  In Kazuo Iwama, Yasuhito Kawano, and Mio Murao, editors, Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer Science, pages 45–64. Springer Berlin Heidelberg, 2013\.
  * [NC00] M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [PR08] Manoj Prabhakaran and Mike Rosulek.  Cryptographic complexity of multi-party computation problems: Classifications and separations.  In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 262–279. Springer, August 2008.
  * [PS04] Manoj Prabhakaran and Amit Sahai.  New notions of security: Achieving universal composability without trusted setup.  In László Babai, editor, 36th ACM STOC, pages 242–251. ACM Press, June 2004.
  * [PW01] Birgit Pfitzmann and Michael Waidner.  A model for asynchronous reactive systems and its application to secure message transmission.  In Proc. 22nd IEEE Symposium on Security & Privacy (S&P) 2001, pages 184–200. IEEE, 2001.  Full version available at http://eprint.iacr.org/2000/066.
  * [PYJ+12] Fernando Pastawski, Norman Y Yao, Liang Jiang, Mikhail D Lukin, and J Ignacio Cirac.  Unforgeable noise-tolerant quantum tokens.  Proceedings of the National Academy of Sciences, 109(40):16079 –16082, 2012.
  * [QDS+19] Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda, and Mio Murao.  Reversing unknown quantum transformations: Universal quantum circuit for inverting general unitary operations.  Phys. Rev. Lett., 123:210502, Nov 2019.
  * [Ren08] Renato Renner.  Security of Quantum Key Distribution.  PhD thesis, ETH Zürich (Switzerland), September 2008.
  * [Unr10] Dominique Unruh.  Universally composable quantum multi-party computation.  In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 486–505. Springer, May 2010.
  * [Unr13] Dominique Unruh.  Everlasting multi-party computation.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 380–397. Springer, August 2013.
  * [Unr14] Dominique Unruh.  Revocable quantum timed-release encryption.  In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 129–146. Springer, May 2014\.
  * [Wat11] John Watrous.  Lecture 7: Semidefinite programming, 2011.  Latest version available at: https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  ACM SIGACT News, 15(1):78–88, 1983.  Original article written circa 1970.
  * [Win99] Andreas Winter.  Coding theorem and strong converse for quantum channels.  IEEE Transactions on Information Theory, 45:2481–2485, 1999.
  * [WST08] Stephanie Wehner, Christian Schaffner, and Barbara M. Terhal.  Cryptography from noisy storage.  Physical Review Letters, 100(22):220502, June 2008.
  * [WW10] Stephanie Wehner and Andreas Winter.  Entropic uncertainty relations—a survey.  New J. Phys., 12(2):025009, Feb 2010.
  * [WZ82] William K. Wootters and Wojciech H. Zurek.  A single quantum cannot be cloned.  Nature, 299(5886):802–803, 1982.
  * [Yao82] Andrew Chi-Chih Yao.  Theory and applications of trapdoor functions.  In 23rd FOCS, pages 80–91. IEEE Computer Society Press, November 1982.