WEBVTT Kind: captions Language: en 00:00:09.240 --> 00:00:15.540 align:start position:0% [Music] 00:00:15.540 --> 00:00:15.550 align:start position:0% [Music] 00:00:15.550 --> 00:00:18.700 align:start position:0% [Music] so<00:00:16.720> this<00:00:17.720> talk<00:00:17.990> is<00:00:18.020> supposed<00:00:18.410> to<00:00:18.440> be<00:00:18.590> an 00:00:18.700 --> 00:00:18.710 align:start position:0% so this talk is supposed to be an 00:00:18.710 --> 00:00:22.300 align:start position:0% so this talk is supposed to be an introduction<00:00:19.130> to<00:00:19.310> Zika<00:00:19.580> snarks<00:00:19.910> I<00:00:20.180> will<00:00:21.310> start 00:00:22.300 --> 00:00:22.310 align:start position:0% introduction to Zika snarks I will start 00:00:22.310 --> 00:00:26.160 align:start position:0% introduction to Zika snarks I will start with<00:00:22.460> a<00:00:22.520> general<00:00:23.289> problem<00:00:24.289> setting<00:00:24.710> then 00:00:26.160 --> 00:00:26.170 align:start position:0% with a general problem setting then 00:00:26.170 --> 00:00:28.300 align:start position:0% with a general problem setting then trying<00:00:27.170> to<00:00:27.289> explain<00:00:27.590> what<00:00:27.800> Syrian<00:00:28.070> knowledge 00:00:28.300 --> 00:00:28.310 align:start position:0% trying to explain what Syrian knowledge 00:00:28.310 --> 00:00:31.029 align:start position:0% trying to explain what Syrian knowledge is<00:00:28.519> and<00:00:28.820> then<00:00:29.510> give<00:00:29.869> a<00:00:30.109> quick<00:00:30.470> walkthrough<00:00:30.769> of 00:00:31.029 --> 00:00:31.039 align:start position:0% is and then give a quick walkthrough of 00:00:31.039 --> 00:00:39.069 align:start position:0% is and then give a quick walkthrough of CK<00:00:31.849> snarks<00:00:32.530> so<00:00:36.729> seekers<00:00:37.729> narcs<00:00:38.059> are<00:00:38.239> important 00:00:39.069 --> 00:00:39.079 align:start position:0% CK snarks so seekers narcs are important 00:00:39.079 --> 00:00:41.919 align:start position:0% CK snarks so seekers narcs are important especially<00:00:39.409> for<00:00:39.799> block<00:00:40.100> chains<00:00:40.399> in<00:00:41.149> in<00:00:41.629> two 00:00:41.919 --> 00:00:41.929 align:start position:0% especially for block chains in in two 00:00:41.929 --> 00:00:44.950 align:start position:0% especially for block chains in in two aspects<00:00:42.559> the<00:00:43.129> first<00:00:43.309> aspect<00:00:43.670> is<00:00:43.940> that<00:00:43.999> block 00:00:44.950 --> 00:00:44.960 align:start position:0% aspects the first aspect is that block 00:00:44.960 --> 00:00:48.399 align:start position:0% aspects the first aspect is that block chains<00:00:45.229> scale<00:00:45.710> much<00:00:46.639> better<00:00:46.909> if<00:00:47.209> they<00:00:47.839> only<00:00:48.079> do 00:00:48.399 --> 00:00:48.409 align:start position:0% chains scale much better if they only do 00:00:48.409 --> 00:00:50.860 align:start position:0% chains scale much better if they only do if<00:00:48.949> they<00:00:49.370> only<00:00:49.579> verify<00:00:50.120> a<00:00:50.149> computation 00:00:50.860 --> 00:00:50.870 align:start position:0% if they only verify a computation 00:00:50.870 --> 00:00:52.419 align:start position:0% if they only verify a computation instead<00:00:51.229> of<00:00:51.409> actually<00:00:51.829> doing<00:00:52.129> the 00:00:52.419 --> 00:00:52.429 align:start position:0% instead of actually doing the 00:00:52.429 --> 00:00:58.479 align:start position:0% instead of actually doing the computation<00:00:53.149> so<00:00:55.569> we'll<00:00:56.569> see<00:00:57.019> later<00:00:57.350> what<00:00:58.309> that 00:00:58.479 --> 00:00:58.489 align:start position:0% computation so we'll see later what that 00:00:58.489 --> 00:01:01.359 align:start position:0% computation so we'll see later what that actually<00:00:58.789> means<00:00:58.909> and<00:00:59.709> the<00:01:00.709> great<00:01:01.069> thing<00:01:01.339> about 00:01:01.359 --> 00:01:01.369 align:start position:0% actually means and the great thing about 00:01:01.369 --> 00:01:03.939 align:start position:0% actually means and the great thing about CK<00:01:01.819> snarks<00:01:02.149> is<00:01:02.269> that<00:01:02.479> they<00:01:02.690> the<00:01:03.229> verification 00:01:03.939 --> 00:01:03.949 align:start position:0% CK snarks is that they the verification 00:01:03.949 --> 00:01:06.130 align:start position:0% CK snarks is that they the verification is<00:01:04.100> magnitudes<00:01:04.879> faster<00:01:05.330> than<00:01:05.479> the<00:01:05.689> actual 00:01:06.130 --> 00:01:06.140 align:start position:0% is magnitudes faster than the actual 00:01:06.140 --> 00:01:08.560 align:start position:0% is magnitudes faster than the actual computation<00:01:06.469> of<00:01:06.770> CK<00:01:07.070> snarks<00:01:07.369> the<00:01:07.759> downside 00:01:08.560 --> 00:01:08.570 align:start position:0% computation of CK snarks the downside 00:01:08.570 --> 00:01:10.209 align:start position:0% computation of CK snarks the downside again<00:01:08.840> is<00:01:09.079> that<00:01:09.350> sick<00:01:09.649> is<00:01:09.770> not<00:01:09.799> stem-cell 00:01:10.209 --> 00:01:10.219 align:start position:0% again is that sick is not stem-cell 00:01:10.219 --> 00:01:13.539 align:start position:0% again is that sick is not stem-cell themselves<00:01:11.119> add<00:01:11.479> an<00:01:11.930> overhead<00:01:12.350> but<00:01:12.740> we'll 00:01:13.539 --> 00:01:13.549 align:start position:0% themselves add an overhead but we'll 00:01:13.549 --> 00:01:16.630 align:start position:0% themselves add an overhead but we'll hope<00:01:13.789> that<00:01:14.500> this<00:01:15.500> balance<00:01:15.770> is<00:01:16.009> also<00:01:16.310> that<00:01:16.460> they 00:01:16.630 --> 00:01:16.640 align:start position:0% hope that this balance is also that they 00:01:16.640 --> 00:01:19.660 align:start position:0% hope that this balance is also that they can<00:01:16.850> actually<00:01:17.030> be<00:01:17.299> a<00:01:17.539> scaling<00:01:18.200> solution<00:01:18.670> in 00:01:19.660 --> 00:01:19.670 align:start position:0% can actually be a scaling solution in 00:01:19.670 --> 00:01:23.410 align:start position:0% can actually be a scaling solution in the<00:01:19.820> future<00:01:21.100> then<00:01:22.100> the<00:01:22.579> second<00:01:22.880> aspect<00:01:23.119> is 00:01:23.410 --> 00:01:23.420 align:start position:0% the future then the second aspect is 00:01:23.420 --> 00:01:24.999 align:start position:0% the future then the second aspect is that<00:01:23.479> in<00:01:23.960> block<00:01:24.229> chains<00:01:24.469> everything<00:01:24.920> is 00:01:24.999 --> 00:01:25.009 align:start position:0% that in block chains everything is 00:01:25.009 --> 00:01:26.770 align:start position:0% that in block chains everything is public<00:01:25.369> all<00:01:25.579> you<00:01:25.880> send<00:01:26.119> to<00:01:26.210> a<00:01:26.240> block<00:01:26.450> chain<00:01:26.659> is 00:01:26.770 --> 00:01:26.780 align:start position:0% public all you send to a block chain is 00:01:26.780 --> 00:01:30.880 align:start position:0% public all you send to a block chain is readable<00:01:27.020> by<00:01:27.140> the<00:01:28.009> whole<00:01:28.189> world<00:01:28.219> and<00:01:29.890> Sikhi 00:01:30.880 --> 00:01:30.890 align:start position:0% readable by the whole world and Sikhi 00:01:30.890 --> 00:01:32.770 align:start position:0% readable by the whole world and Sikhi snarks<00:01:31.219> help<00:01:31.460> there<00:01:31.820> because<00:01:32.420> they<00:01:32.600> add<00:01:32.749> a 00:01:32.770 --> 00:01:32.780 align:start position:0% snarks help there because they add a 00:01:32.780 --> 00:01:37.289 align:start position:0% snarks help there because they add a property<00:01:33.140> that<00:01:33.320> is<00:01:33.439> called<00:01:33.710> zero<00:01:33.979> knowledge 00:01:37.289 --> 00:01:37.299 align:start position:0% 00:01:37.299 --> 00:01:40.300 align:start position:0% okay<00:01:38.299> let's<00:01:38.570> start<00:01:38.810> explaining<00:01:39.259> what<00:01:40.039> zero 00:01:40.300 --> 00:01:40.310 align:start position:0% okay let's start explaining what zero 00:01:40.310 --> 00:01:44.859 align:start position:0% okay let's start explaining what zero knowledge<00:01:40.549> is<00:01:40.939> or<00:01:42.460> more<00:01:43.460> importantly<00:01:43.880> so<00:01:44.119> zero 00:01:44.859 --> 00:01:44.869 align:start position:0% knowledge is or more importantly so zero 00:01:44.869 --> 00:01:49.630 align:start position:0% knowledge is or more importantly so zero knowledge<00:01:45.140> is<00:01:45.319> a<00:01:46.569> aspect<00:01:47.569> of<00:01:48.039> that<00:01:49.039> or<00:01:49.609> a 00:01:49.630 --> 00:01:49.640 align:start position:0% knowledge is a aspect of that or a 00:01:49.640 --> 00:01:54.840 align:start position:0% knowledge is a aspect of that or a notion<00:01:50.359> that<00:01:51.460> was<00:01:52.460> defined<00:01:53.030> in<00:01:53.780> the<00:01:54.140> area<00:01:54.560> of 00:01:54.840 --> 00:01:54.850 align:start position:0% notion that was defined in the area of 00:01:54.850 --> 00:01:57.609 align:start position:0% notion that was defined in the area of interactive<00:01:55.850> protocols<00:01:56.630> and<00:01:56.840> in<00:01:57.499> an 00:01:57.609 --> 00:01:57.619 align:start position:0% interactive protocols and in an 00:01:57.619 --> 00:01:59.679 align:start position:0% interactive protocols and in an interactive<00:01:57.920> protocol<00:01:58.429> you<00:01:58.579> always<00:01:58.880> have<00:01:59.060> so 00:01:59.679 --> 00:01:59.689 align:start position:0% interactive protocol you always have so 00:01:59.689 --> 00:02:01.149 align:start position:0% interactive protocol you always have so we<00:01:59.749> have<00:01:59.780> two<00:01:59.990> parties<00:02:00.319> approver<00:02:00.889> and<00:02:00.920> the 00:02:01.149 --> 00:02:01.159 align:start position:0% we have two parties approver and the 00:02:01.159 --> 00:02:11.880 align:start position:0% we have two parties approver and the verifier<00:02:01.579> and<00:02:01.850> the<00:02:02.450> proof<00:02:02.689> of<00:02:02.780> wants<00:02:03.079> to 00:02:11.880 --> 00:02:11.890 align:start position:0% 00:02:11.890 --> 00:02:17.290 align:start position:0% so<00:02:12.890> I<00:02:13.220> so<00:02:14.180> this<00:02:14.930> is<00:02:14.990> a<00:02:15.140> quite<00:02:15.560> small<00:02:15.830> room<00:02:16.310> and<00:02:16.550> I 00:02:17.290 --> 00:02:17.300 align:start position:0% so I so this is a quite small room and I 00:02:17.300 --> 00:02:20.860 align:start position:0% so I so this is a quite small room and I think<00:02:17.390> it's<00:02:17.720> very<00:02:17.780> important<00:02:19.239> to<00:02:20.239> get<00:02:20.420> a<00:02:20.480> very 00:02:20.860 --> 00:02:20.870 align:start position:0% think it's very important to get a very 00:02:20.870 --> 00:02:22.840 align:start position:0% think it's very important to get a very high<00:02:21.140> quality<00:02:21.200> recording<00:02:21.680> of<00:02:22.130> these<00:02:22.430> talk<00:02:22.670> so 00:02:22.840 --> 00:02:22.850 align:start position:0% high quality recording of these talk so 00:02:22.850 --> 00:02:24.460 align:start position:0% high quality recording of these talk so please<00:02:22.880> don't<00:02:23.360> do<00:02:23.810> this<00:02:23.870> stuff<00:02:24.230> with<00:02:24.380> the 00:02:24.460 --> 00:02:24.470 align:start position:0% please don't do this stuff with the 00:02:24.470 --> 00:02:33.550 align:start position:0% please don't do this stuff with the lights<00:02:31.000> sorry<00:02:32.000> for<00:02:32.209> the<00:02:32.360> technical<00:02:32.660> so<00:02:33.290> we 00:02:33.550 --> 00:02:33.560 align:start position:0% lights sorry for the technical so we 00:02:33.560 --> 00:02:44.190 align:start position:0% lights sorry for the technical so we aren't<00:02:33.860> fixing<00:02:34.310> just<00:02:35.150> one<00:02:35.450> moment<00:02:35.720> please 00:02:44.190 --> 00:02:44.200 align:start position:0% 00:02:44.200 --> 00:02:46.960 align:start position:0% okay<00:02:45.230> in<00:02:45.410> protocol<00:02:46.370> you<00:02:46.519> always<00:02:46.730> have<00:02:46.850> two 00:02:46.960 --> 00:02:46.970 align:start position:0% okay in protocol you always have two 00:02:46.970 --> 00:02:48.520 align:start position:0% okay in protocol you always have two parties<00:02:47.300> the<00:02:47.480> prover<00:02:47.780> and<00:02:47.900> the<00:02:47.959> verify<00:02:48.350> and 00:02:48.520 --> 00:02:48.530 align:start position:0% parties the prover and the verify and 00:02:48.530 --> 00:02:49.870 align:start position:0% parties the prover and the verify and the<00:02:48.620> prover<00:02:48.920> wants<00:02:49.160> to<00:02:49.310> convince<00:02:49.640> the 00:02:49.870 --> 00:02:49.880 align:start position:0% the prover wants to convince the 00:02:49.880 --> 00:02:57.729 align:start position:0% the prover wants to convince the verifier<00:02:50.360> about<00:02:50.840> a<00:02:50.870> certain<00:02:51.260> effect<00:02:53.890> and<00:02:56.739> it 00:02:57.729 --> 00:02:57.739 align:start position:0% verifier about a certain effect and it 00:02:57.739 --> 00:03:00.100 align:start position:0% verifier about a certain effect and it has<00:02:57.950> this<00:02:58.610> protocol<00:02:58.970> has<00:02:59.180> the<00:02:59.690> property<00:03:00.019> of 00:03:00.100 --> 00:03:00.110 align:start position:0% has this protocol has the property of 00:03:00.110 --> 00:03:02.680 align:start position:0% has this protocol has the property of zero<00:03:00.140> knowledge<00:03:00.500> if<00:03:01.010> the<00:03:01.910> proof<00:03:02.090> can<00:03:02.360> convince 00:03:02.680 --> 00:03:02.690 align:start position:0% zero knowledge if the proof can convince 00:03:02.690 --> 00:03:05.110 align:start position:0% zero knowledge if the proof can convince the<00:03:02.810> prior<00:03:03.049> verify<00:03:03.530> that<00:03:04.310> the<00:03:04.519> fact<00:03:04.760> is<00:03:04.940> true 00:03:05.110 --> 00:03:05.120 align:start position:0% the prior verify that the fact is true 00:03:05.120 --> 00:03:07.509 align:start position:0% the prior verify that the fact is true but<00:03:05.540> without<00:03:06.080> verifying<00:03:06.560> any<00:03:06.890> detail<00:03:07.340> about 00:03:07.509 --> 00:03:07.519 align:start position:0% but without verifying any detail about 00:03:07.519 --> 00:03:09.880 align:start position:0% but without verifying any detail about why<00:03:07.760> it<00:03:07.819> is<00:03:08.060> true<00:03:08.360> this<00:03:09.019> sounds<00:03:09.440> really<00:03:09.560> weird 00:03:09.880 --> 00:03:09.890 align:start position:0% why it is true this sounds really weird 00:03:09.890 --> 00:03:17.020 align:start position:0% why it is true this sounds really weird and<00:03:14.530> examples<00:03:15.530> of<00:03:15.650> such<00:03:15.799> statements<00:03:16.400> are<00:03:16.610> that 00:03:17.020 --> 00:03:17.030 align:start position:0% and examples of such statements are that 00:03:17.030 --> 00:03:20.140 align:start position:0% and examples of such statements are that a<00:03:17.739> given<00:03:18.739> message<00:03:18.890> is<00:03:19.160> a<00:03:19.190> valid<00:03:19.579> transact<00:03:20.000> on 00:03:20.140 --> 00:03:20.150 align:start position:0% a given message is a valid transact on 00:03:20.150 --> 00:03:23.830 align:start position:0% a given message is a valid transact on the<00:03:20.239> blockchain<00:03:20.450> or<00:03:21.579> more<00:03:22.579> abstractly<00:03:23.150> there 00:03:23.830 --> 00:03:23.840 align:start position:0% the blockchain or more abstractly there 00:03:23.840 --> 00:03:27.789 align:start position:0% the blockchain or more abstractly there is<00:03:24.079> a<00:03:24.109> W<00:03:24.980> such<00:03:25.220> that<00:03:25.250> a<00:03:25.700> f<00:03:26.180> of<00:03:26.570> X<00:03:26.780> comma<00:03:26.989> W<00:03:27.440> is<00:03:27.560> why 00:03:27.789 --> 00:03:27.799 align:start position:0% is a W such that a f of X comma W is why 00:03:27.799 --> 00:03:33.759 align:start position:0% is a W such that a f of X comma W is why for<00:03:28.100> a<00:03:28.130> fixed<00:03:28.400> function<00:03:28.549> f<00:03:31.480> but<00:03:32.500> let's<00:03:33.500> take<00:03:33.739> a 00:03:33.759 --> 00:03:33.769 align:start position:0% for a fixed function f but let's take a 00:03:33.769 --> 00:03:36.880 align:start position:0% for a fixed function f but let's take a more<00:03:34.070> specific<00:03:34.489> example<00:03:34.760> and<00:03:35.359> so<00:03:35.870> one<00:03:36.739> would 00:03:36.880 --> 00:03:36.890 align:start position:0% more specific example and so one would 00:03:36.890 --> 00:03:40.660 align:start position:0% more specific example and so one would be<00:03:36.950> a<00:03:37.359> mini<00:03:38.359> Sudoku<00:03:38.959> board<00:03:39.200> is<00:03:39.530> solvable<00:03:39.950> so 00:03:40.660 --> 00:03:40.670 align:start position:0% be a mini Sudoku board is solvable so 00:03:40.670 --> 00:03:43.240 align:start position:0% be a mini Sudoku board is solvable so what<00:03:41.450> is<00:03:41.570> mini<00:03:41.810> Sudoku<00:03:42.320> you<00:03:42.590> probably<00:03:43.010> know 00:03:43.240 --> 00:03:43.250 align:start position:0% what is mini Sudoku you probably know 00:03:43.250 --> 00:03:45.280 align:start position:0% what is mini Sudoku you probably know the<00:03:43.489> regular<00:03:43.850> nine<00:03:44.120> times<00:03:44.450> nine<00:03:44.660> pseudo<00:03:45.109> ku 00:03:45.280 --> 00:03:45.290 align:start position:0% the regular nine times nine pseudo ku 00:03:45.290 --> 00:03:48.699 align:start position:0% the regular nine times nine pseudo ku and<00:03:46.209> to<00:03:47.209> fit<00:03:47.510> it<00:03:47.600> into<00:03:47.720> the<00:03:47.870> presentation<00:03:48.260> I 00:03:48.699 --> 00:03:48.709 align:start position:0% and to fit it into the presentation I 00:03:48.709 --> 00:03:50.860 align:start position:0% and to fit it into the presentation I will<00:03:49.040> I<00:03:49.250> will<00:03:49.430> talk<00:03:49.670> about<00:03:49.790> a<00:03:50.150> smaller<00:03:50.690> version 00:03:50.860 --> 00:03:50.870 align:start position:0% will I will talk about a smaller version 00:03:50.870 --> 00:03:53.430 align:start position:0% will I will talk about a smaller version a<00:03:51.320> four<00:03:51.950> times<00:03:52.130> four<00:03:52.400> Sudoku<00:03:52.820> but<00:03:53.030> which<00:03:53.209> is 00:03:53.430 --> 00:03:53.440 align:start position:0% a four times four Sudoku but which is 00:03:53.440 --> 00:03:56.470 align:start position:0% a four times four Sudoku but which is the<00:03:54.440> same<00:03:54.620> thing<00:03:54.859> in<00:03:55.130> the<00:03:55.340> end<00:03:55.459> so<00:03:56.090> you<00:03:56.120> have<00:03:56.450> a 00:03:56.470 --> 00:03:56.480 align:start position:0% the same thing in the end so you have a 00:03:56.480 --> 00:03:59.610 align:start position:0% the same thing in the end so you have a board<00:03:57.230> with<00:03:57.440> four<00:03:57.709> times<00:03:57.890> four<00:03:58.190> cells<00:03:58.940> and 00:03:59.610 --> 00:03:59.620 align:start position:0% board with four times four cells and 00:03:59.620 --> 00:04:02.259 align:start position:0% board with four times four cells and some<00:04:00.620> of<00:04:00.739> these<00:04:00.890> cells<00:04:01.190> are<00:04:01.489> pre<00:04:01.730> filled<00:04:02.030> with 00:04:02.259 --> 00:04:02.269 align:start position:0% some of these cells are pre filled with 00:04:02.269 --> 00:04:06.069 align:start position:0% some of these cells are pre filled with numbers<00:04:02.660> between<00:04:02.870> one<00:04:03.230> and<00:04:03.260> four<00:04:04.810> but<00:04:05.810> not<00:04:05.930> all 00:04:06.069 --> 00:04:06.079 align:start position:0% numbers between one and four but not all 00:04:06.079 --> 00:04:09.039 align:start position:0% numbers between one and four but not all of<00:04:06.200> them<00:04:06.350> and<00:04:06.560> the<00:04:07.280> task<00:04:07.549> is<00:04:07.880> to<00:04:07.910> fill<00:04:08.720> all<00:04:08.900> the 00:04:09.039 --> 00:04:09.049 align:start position:0% of them and the task is to fill all the 00:04:09.049 --> 00:04:11.740 align:start position:0% of them and the task is to fill all the remaining<00:04:09.440> cells<00:04:09.709> in<00:04:09.980> a<00:04:10.190> way<00:04:10.370> such<00:04:11.209> that<00:04:11.239> in 00:04:11.740 --> 00:04:11.750 align:start position:0% remaining cells in a way such that in 00:04:11.750 --> 00:04:15.130 align:start position:0% remaining cells in a way such that in each<00:04:11.959> row<00:04:12.500> there<00:04:12.859> is<00:04:12.890> exactly<00:04:13.600> so<00:04:14.600> that<00:04:14.630> one<00:04:15.049> of 00:04:15.130 --> 00:04:15.140 align:start position:0% each row there is exactly so that one of 00:04:15.140 --> 00:04:16.539 align:start position:0% each row there is exactly so that one of the<00:04:15.230> numbers<00:04:15.470> between<00:04:15.590> one<00:04:15.889> and<00:04:15.919> four<00:04:16.130> appears 00:04:16.539 --> 00:04:16.549 align:start position:0% the numbers between one and four appears 00:04:16.549 --> 00:04:18.610 align:start position:0% the numbers between one and four appears exactly<00:04:16.669> once<00:04:17.090> in<00:04:17.269> each<00:04:17.359> row<00:04:17.630> it<00:04:18.229> appears 00:04:18.610 --> 00:04:18.620 align:start position:0% exactly once in each row it appears 00:04:18.620 --> 00:04:20.890 align:start position:0% exactly once in each row it appears exactly<00:04:18.769> once<00:04:19.190> in<00:04:19.400> each<00:04:19.489> column<00:04:19.880> and<00:04:20.030> it 00:04:20.890 --> 00:04:20.900 align:start position:0% exactly once in each column and it 00:04:20.900 --> 00:04:21.740 align:start position:0% exactly once in each column and it appears<00:04:21.229> exactly 00:04:21.740 --> 00:04:21.750 align:start position:0% appears exactly 00:04:21.750 --> 00:04:25.400 align:start position:0% appears exactly in<00:04:22.049> each<00:04:22.440> of<00:04:22.500> the<00:04:22.890> two<00:04:23.520> times<00:04:23.790> two<00:04:24.140> in<00:04:25.140> each<00:04:25.260> of 00:04:25.400 --> 00:04:25.410 align:start position:0% in each of the two times two in each of 00:04:25.410 --> 00:04:28.780 align:start position:0% in each of the two times two in each of the<00:04:25.500> four<00:04:25.740> or<00:04:25.830> two<00:04:25.950> times<00:04:26.160> two<00:04:26.340> sub<00:04:26.700> squares 00:04:28.780 --> 00:04:28.790 align:start position:0% the four or two times two sub squares 00:04:28.790 --> 00:04:33.890 align:start position:0% the four or two times two sub squares and<00:04:30.590> so<00:04:31.590> of<00:04:32.160> course<00:04:32.370> the<00:04:32.790> regular<00:04:33.210> Sudoku 00:04:33.890 --> 00:04:33.900 align:start position:0% and so of course the regular Sudoku 00:04:33.900 --> 00:04:35.720 align:start position:0% and so of course the regular Sudoku games<00:04:34.170> it's<00:04:34.920> always<00:04:35.190> clear<00:04:35.430> that<00:04:35.610> it's 00:04:35.720 --> 00:04:35.730 align:start position:0% games it's always clear that it's 00:04:35.730 --> 00:04:37.040 align:start position:0% games it's always clear that it's solvable<00:04:36.060> the<00:04:36.210> question<00:04:36.480> is<00:04:36.570> how 00:04:37.040 --> 00:04:37.050 align:start position:0% solvable the question is how 00:04:37.050 --> 00:04:39.290 align:start position:0% solvable the question is how but<00:04:37.170> in<00:04:37.380> this<00:04:37.530> setting<00:04:37.890> we<00:04:38.400> want<00:04:38.640> to<00:04:38.820> so<00:04:39.150> that 00:04:39.290 --> 00:04:39.300 align:start position:0% but in this setting we want to so that 00:04:39.300 --> 00:04:41.450 align:start position:0% but in this setting we want to so that the<00:04:39.420> prover<00:04:39.810> wants<00:04:40.530> to<00:04:40.710> convince<00:04:41.250> the 00:04:41.450 --> 00:04:41.460 align:start position:0% the prover wants to convince the 00:04:41.460 --> 00:04:44.000 align:start position:0% the prover wants to convince the verifier<00:04:41.960> that<00:04:42.960> the<00:04:43.320> board<00:04:43.530> is<00:04:43.650> solvable 00:04:44.000 --> 00:04:44.010 align:start position:0% verifier that the board is solvable 00:04:44.010 --> 00:04:46.400 align:start position:0% verifier that the board is solvable without<00:04:44.400> telling<00:04:44.700> anything<00:04:44.940> about<00:04:45.350> how<00:04:46.350> the 00:04:46.400 --> 00:04:46.410 align:start position:0% without telling anything about how the 00:04:46.410 --> 00:04:49.100 align:start position:0% without telling anything about how the so<00:04:46.710> the<00:04:46.920> the<00:04:47.130> solution<00:04:47.340> looks<00:04:47.670> like<00:04:47.760> and<00:04:48.110> in 00:04:49.100 --> 00:04:49.110 align:start position:0% so the the solution looks like and in 00:04:49.110 --> 00:04:50.540 align:start position:0% so the the solution looks like and in the<00:04:49.200> general<00:04:49.500> setting<00:04:49.860> you<00:04:50.310> would<00:04:50.400> also 00:04:50.540 --> 00:04:50.550 align:start position:0% the general setting you would also 00:04:50.550 --> 00:04:52.100 align:start position:0% the general setting you would also consider<00:04:50.790> boards<00:04:51.240> which<00:04:51.420> are<00:04:51.570> not<00:04:51.750> solvable 00:04:52.100 --> 00:04:52.110 align:start position:0% consider boards which are not solvable 00:04:52.110 --> 00:04:53.390 align:start position:0% consider boards which are not solvable and<00:04:52.380> then<00:04:52.530> of<00:04:52.650> course<00:04:52.860> the<00:04:52.980> prove<00:04:53.130> it<00:04:53.250> cannot 00:04:53.390 --> 00:04:53.400 align:start position:0% and then of course the prove it cannot 00:04:53.400 --> 00:04:55.220 align:start position:0% and then of course the prove it cannot convince<00:04:53.700> the<00:04:54.000> verify<00:04:54.300> that<00:04:54.419> it's<00:04:54.570> not 00:04:55.220 --> 00:04:55.230 align:start position:0% convince the verify that it's not 00:04:55.230 --> 00:04:57.020 align:start position:0% convince the verify that it's not solvable<00:04:55.560> so<00:04:56.340> this<00:04:56.490> only<00:04:56.610> works<00:04:56.850> in<00:04:57.000> the 00:04:57.020 --> 00:04:57.030 align:start position:0% solvable so this only works in the 00:04:57.030 --> 00:05:01.370 align:start position:0% solvable so this only works in the positive<00:04:57.450> case<00:04:57.660> and<00:04:59.870> it's<00:05:00.870> important<00:05:01.140> to<00:05:01.200> note 00:05:01.370 --> 00:05:01.380 align:start position:0% positive case and it's important to note 00:05:01.380 --> 00:05:03.310 align:start position:0% positive case and it's important to note that<00:05:01.410> the<00:05:01.710> protocol<00:05:02.010> we<00:05:02.160> will<00:05:02.280> see<00:05:02.430> next<00:05:02.610> the 00:05:03.310 --> 00:05:03.320 align:start position:0% that the protocol we will see next the 00:05:03.320 --> 00:05:05.630 align:start position:0% that the protocol we will see next the size<00:05:04.320> of<00:05:04.560> the<00:05:04.650> past<00:05:04.860> is<00:05:05.010> irrelevant<00:05:05.250> for<00:05:05.520> the 00:05:05.630 --> 00:05:05.640 align:start position:0% size of the past is irrelevant for the 00:05:05.640 --> 00:05:07.520 align:start position:0% size of the past is irrelevant for the protocol<00:05:05.970> it<00:05:06.060> works<00:05:06.240> for<00:05:06.510> nine<00:05:06.810> times<00:05:06.990> nine<00:05:07.169> or 00:05:07.520 --> 00:05:07.530 align:start position:0% protocol it works for nine times nine or 00:05:07.530 --> 00:05:14.150 align:start position:0% protocol it works for nine times nine or four<00:05:08.060> 1000<00:05:09.060> times<00:05:09.240> 1000<00:05:09.840> boards<00:05:10.470> and<00:05:12.950> the<00:05:13.950> only 00:05:14.150 --> 00:05:14.160 align:start position:0% four 1000 times 1000 boards and the only 00:05:14.160 --> 00:05:17.360 align:start position:0% four 1000 times 1000 boards and the only things<00:05:14.340> we<00:05:14.400> need<00:05:14.669> are<00:05:14.970> a<00:05:15.390> table<00:05:16.080> a<00:05:16.380> sheet<00:05:17.250> of 00:05:17.360 --> 00:05:17.370 align:start position:0% things we need are a table a sheet of 00:05:17.370 --> 00:05:21.520 align:start position:0% things we need are a table a sheet of paper<00:05:17.580> and<00:05:17.940> a<00:05:18.030> pen<00:05:18.270> and<00:05:18.770> then<00:05:19.770> an<00:05:20.010> opaque 00:05:21.520 --> 00:05:21.530 align:start position:0% paper and a pen and then an opaque 00:05:21.530 --> 00:05:28.730 align:start position:0% paper and a pen and then an opaque sticky<00:05:22.530> tape<00:05:22.740> and<00:05:22.919> a<00:05:23.310> dice<00:05:24.770> okay<00:05:25.770> and<00:05:26.150> so<00:05:27.740> it 00:05:28.730 --> 00:05:28.740 align:start position:0% sticky tape and a dice okay and so it 00:05:28.740 --> 00:05:30.380 align:start position:0% sticky tape and a dice okay and so it starts<00:05:29.130> so<00:05:29.340> of<00:05:29.460> course<00:05:29.580> the<00:05:29.760> prover<00:05:30.000> has<00:05:30.030> the 00:05:30.380 --> 00:05:30.390 align:start position:0% starts so of course the prover has the 00:05:30.390 --> 00:05:31.730 align:start position:0% starts so of course the prover has the secret<00:05:30.600> solution<00:05:30.870> to<00:05:31.110> the<00:05:31.200> puzzle<00:05:31.320> it<00:05:31.590> looks 00:05:31.730 --> 00:05:31.740 align:start position:0% secret solution to the puzzle it looks 00:05:31.740 --> 00:05:36.290 align:start position:0% secret solution to the puzzle it looks like<00:05:31.890> that<00:05:32.040> and<00:05:33.860> what<00:05:34.860> the<00:05:35.010> the<00:05:35.820> first<00:05:36.060> step 00:05:36.290 --> 00:05:36.300 align:start position:0% like that and what the the first step 00:05:36.300 --> 00:05:38.719 align:start position:0% like that and what the the first step what<00:05:36.720> the<00:05:36.810> prove<00:05:36.990> it<00:05:37.080> does<00:05:37.229> is<00:05:37.440> she<00:05:38.340> shovels 00:05:38.719 --> 00:05:38.729 align:start position:0% what the prove it does is she shovels 00:05:38.729 --> 00:05:40.940 align:start position:0% what the prove it does is she shovels shuffles<00:05:39.210> the<00:05:39.300> numbers<00:05:39.600> so<00:05:39.750> uses<00:05:40.020> the<00:05:40.140> dice<00:05:40.290> to 00:05:40.940 --> 00:05:40.950 align:start position:0% shuffles the numbers so uses the dice to 00:05:40.950 --> 00:05:42.920 align:start position:0% shuffles the numbers so uses the dice to create<00:05:41.400> a<00:05:41.669> replacement<00:05:42.419> of<00:05:42.479> the<00:05:42.600> number<00:05:42.780> two 00:05:42.920 --> 00:05:42.930 align:start position:0% create a replacement of the number two 00:05:42.930 --> 00:05:45.230 align:start position:0% create a replacement of the number two she<00:05:43.410> doesn't<00:05:43.710> she<00:05:44.310> doesn't<00:05:44.340> move<00:05:44.729> the<00:05:44.910> numbers 00:05:45.230 --> 00:05:45.240 align:start position:0% she doesn't she doesn't move the numbers 00:05:45.240 --> 00:05:46.909 align:start position:0% she doesn't she doesn't move the numbers on<00:05:45.419> the<00:05:45.540> board<00:05:45.690> but<00:05:45.960> she<00:05:46.110> replaces<00:05:46.590> each 00:05:46.909 --> 00:05:46.919 align:start position:0% on the board but she replaces each 00:05:46.919 --> 00:05:49.760 align:start position:0% on the board but she replaces each number<00:05:47.310> by<00:05:47.340> a<00:05:47.460> different<00:05:47.820> one<00:05:47.940> so<00:05:48.200> each<00:05:49.200> one<00:05:49.650> is 00:05:49.760 --> 00:05:49.770 align:start position:0% number by a different one so each one is 00:05:49.770 --> 00:05:51.560 align:start position:0% number by a different one so each one is replaced<00:05:50.070> by<00:05:50.130> a<00:05:50.220> 3<00:05:50.460> h2<00:05:50.640> is<00:05:50.880> provided<00:05:51.240> by<00:05:51.300> for 00:05:51.560 --> 00:05:51.570 align:start position:0% replaced by a 3 h2 is provided by for 00:05:51.570 --> 00:05:54.770 align:start position:0% replaced by a 3 h2 is provided by for each<00:05:52.169> 3<00:05:52.650> PI<00:05:52.860> by<00:05:53.040> a<00:05:53.160> 2<00:05:53.370> and<00:05:53.640> each<00:05:53.760> four<00:05:54.120> by<00:05:54.540> one 00:05:54.770 --> 00:05:54.780 align:start position:0% each 3 PI by a 2 and each four by one 00:05:54.780 --> 00:05:57.800 align:start position:0% each 3 PI by a 2 and each four by one and<00:05:55.580> this<00:05:56.580> is<00:05:56.640> how<00:05:56.910> the<00:05:56.970> shuffled<00:05:57.450> solution 00:05:57.800 --> 00:05:57.810 align:start position:0% and this is how the shuffled solution 00:05:57.810 --> 00:06:00.620 align:start position:0% and this is how the shuffled solution looks<00:05:57.990> like<00:05:58.200> now<00:05:58.440> and<00:05:58.710> I<00:05:59.160> also<00:05:59.479> added<00:06:00.479> the 00:06:00.620 --> 00:06:00.630 align:start position:0% looks like now and I also added the 00:06:00.630 --> 00:06:03.680 align:start position:0% looks like now and I also added the replacement<00:06:01.110> here<00:06:01.260> and<00:06:02.390> because<00:06:03.390> of<00:06:03.570> the 00:06:03.680 --> 00:06:03.690 align:start position:0% replacement here and because of the 00:06:03.690 --> 00:06:05.270 align:start position:0% replacement here and because of the specific<00:06:04.140> properties<00:06:04.560> of<00:06:04.800> the<00:06:04.950> pseudocode 00:06:05.270 --> 00:06:05.280 align:start position:0% specific properties of the pseudocode 00:06:05.280 --> 00:06:07.370 align:start position:0% specific properties of the pseudocode problem<00:06:05.850> the<00:06:06.300> shuffle<00:06:06.630> solution<00:06:07.050> is<00:06:07.140> still<00:06:07.350> a 00:06:07.370 --> 00:06:07.380 align:start position:0% problem the shuffle solution is still a 00:06:07.380 --> 00:06:11.000 align:start position:0% problem the shuffle solution is still a solution<00:06:07.860> so<00:06:08.120> you<00:06:09.120> still<00:06:09.360> have<00:06:09.620> each<00:06:10.620> of<00:06:10.890> the 00:06:11.000 --> 00:06:11.010 align:start position:0% solution so you still have each of the 00:06:11.010 --> 00:06:12.710 align:start position:0% solution so you still have each of the numbers<00:06:11.280> exactly<00:06:11.430> once<00:06:11.820> in<00:06:12.000> each<00:06:12.090> row<00:06:12.300> exactly 00:06:12.710 --> 00:06:12.720 align:start position:0% numbers exactly once in each row exactly 00:06:12.720 --> 00:06:14.450 align:start position:0% numbers exactly once in each row exactly one<00:06:12.840> once<00:06:13.320> it's<00:06:13.560> called<00:06:13.800> each<00:06:14.010> column<00:06:14.370> and 00:06:14.450 --> 00:06:14.460 align:start position:0% one once it's called each column and 00:06:14.460 --> 00:06:18.230 align:start position:0% one once it's called each column and exactly<00:06:14.790> once<00:06:14.970> in<00:06:15.450> each<00:06:15.630> sub<00:06:16.229> square<00:06:16.610> but<00:06:17.610> it 00:06:18.230 --> 00:06:18.240 align:start position:0% exactly once in each sub square but it 00:06:18.240 --> 00:06:19.730 align:start position:0% exactly once in each sub square but it doesn't<00:06:18.600> it<00:06:18.690> doesn't<00:06:18.960> necessarily<00:06:19.560> fit 00:06:19.730 --> 00:06:19.740 align:start position:0% doesn't it doesn't necessarily fit 00:06:19.740 --> 00:06:21.680 align:start position:0% doesn't it doesn't necessarily fit anymore<00:06:20.010> to<00:06:20.340> this<00:06:20.460> initial<00:06:20.970> setting<00:06:21.479> of<00:06:21.570> the 00:06:21.680 --> 00:06:21.690 align:start position:0% anymore to this initial setting of the 00:06:21.690 --> 00:06:27.500 align:start position:0% anymore to this initial setting of the prefilled<00:06:22.200> cells<00:06:25.340> now<00:06:26.340> the<00:06:26.400> next<00:06:27.300> thing<00:06:27.450> that 00:06:27.500 --> 00:06:27.510 align:start position:0% prefilled cells now the next thing that 00:06:27.510 --> 00:06:30.409 align:start position:0% prefilled cells now the next thing that happens<00:06:27.960> is<00:06:28.110> that<00:06:28.700> the<00:06:29.700> the<00:06:29.729> prove<00:06:30.120> of<00:06:30.210> writes 00:06:30.409 --> 00:06:30.419 align:start position:0% happens is that the the prove of writes 00:06:30.419 --> 00:06:31.790 align:start position:0% happens is that the the prove of writes the<00:06:30.660> shuffle<00:06:30.960> puzzle<00:06:31.229> on<00:06:31.289> a<00:06:31.320> piece<00:06:31.530> of<00:06:31.680> paper 00:06:31.790 --> 00:06:31.800 align:start position:0% the shuffle puzzle on a piece of paper 00:06:31.800 --> 00:06:35.050 align:start position:0% the shuffle puzzle on a piece of paper and<00:06:32.160> covers<00:06:32.970> each<00:06:33.150> cell<00:06:33.450> individually<00:06:33.660> with 00:06:35.050 --> 00:06:35.060 align:start position:0% and covers each cell individually with 00:06:35.060 --> 00:06:37.420 align:start position:0% and covers each cell individually with piece<00:06:35.330> of<00:06:35.480> sticky<00:06:35.720> tape<00:06:35.750> and<00:06:36.200> then<00:06:36.950> the 00:06:37.420 --> 00:06:37.430 align:start position:0% piece of sticky tape and then the 00:06:37.430 --> 00:06:40.690 align:start position:0% piece of sticky tape and then the proverb<00:06:37.790> puts<00:06:38.720> the<00:06:38.990> the<00:06:39.340> paper<00:06:40.340> on<00:06:40.520> the<00:06:40.580> table 00:06:40.690 --> 00:06:40.700 align:start position:0% proverb puts the the paper on the table 00:06:40.700 --> 00:06:43.270 align:start position:0% proverb puts the the paper on the table for<00:06:41.060> the<00:06:41.450> sole<00:06:41.660> heir<00:06:41.870> for<00:06:41.990> the<00:06:42.110> verifier<00:06:42.620> to 00:06:43.270 --> 00:06:43.280 align:start position:0% for the sole heir for the verifier to 00:06:43.280 --> 00:06:47.050 align:start position:0% for the sole heir for the verifier to see<00:06:43.460> and<00:06:44.270> now<00:06:44.510> it's<00:06:44.990> the<00:06:45.139> verifier<00:06:45.470> stern<00:06:46.060> okay 00:06:47.050 --> 00:06:47.060 align:start position:0% see and now it's the verifier stern okay 00:06:47.060 --> 00:06:47.920 align:start position:0% see and now it's the verifier stern okay that's<00:06:47.240> that's<00:06:47.419> how<00:06:47.540> it<00:06:47.630> looks<00:06:47.750> like<00:06:47.810> now 00:06:47.920 --> 00:06:47.930 align:start position:0% that's that's how it looks like now 00:06:47.930 --> 00:06:49.810 align:start position:0% that's that's how it looks like now everything<00:06:48.560> is<00:06:48.650> covered<00:06:48.800> so<00:06:48.919> all<00:06:49.160> the<00:06:49.460> both 00:06:49.810 --> 00:06:49.820 align:start position:0% everything is covered so all the both 00:06:49.820 --> 00:06:52.300 align:start position:0% everything is covered so all the both the<00:06:50.120> the<00:06:50.480> cells<00:06:51.110> and<00:06:51.410> the<00:06:51.650> replacement<00:06:52.190> is 00:06:52.300 --> 00:06:52.310 align:start position:0% the the cells and the replacement is 00:06:52.310 --> 00:06:55.600 align:start position:0% the the cells and the replacement is covered<00:06:52.610> with<00:06:53.000> tape<00:06:53.180> now<00:06:54.139> the<00:06:54.680> verifier<00:06:55.190> has 00:06:55.600 --> 00:06:55.610 align:start position:0% covered with tape now the verifier has 00:06:55.610 --> 00:06:58.930 align:start position:0% covered with tape now the verifier has the<00:06:56.419> following<00:06:56.870> choices<00:06:57.380> she<00:06:58.280> can<00:06:58.430> either<00:06:58.610> ask 00:06:58.930 --> 00:06:58.940 align:start position:0% the following choices she can either ask 00:06:58.940 --> 00:07:00.550 align:start position:0% the following choices she can either ask the<00:06:59.300> prover<00:06:59.600> to<00:06:59.750> reveal<00:07:00.020> a<00:07:00.050> certain<00:07:00.380> row 00:07:00.550 --> 00:07:00.560 align:start position:0% the prover to reveal a certain row 00:07:00.560 --> 00:07:02.740 align:start position:0% the prover to reveal a certain row reveal<00:07:01.040> a<00:07:01.100> certain<00:07:01.340> column<00:07:01.610> reveal<00:07:02.389> a<00:07:02.450> certain 00:07:02.740 --> 00:07:02.750 align:start position:0% reveal a certain column reveal a certain 00:07:02.750 --> 00:07:05.650 align:start position:0% reveal a certain column reveal a certain sub<00:07:02.930> square<00:07:03.230> or<00:07:03.520> reveal<00:07:04.520> the<00:07:04.760> initially 00:07:05.650 --> 00:07:05.660 align:start position:0% sub square or reveal the initially 00:07:05.660 --> 00:07:09.879 align:start position:0% sub square or reveal the initially filled<00:07:06.139> cells<00:07:06.620> from<00:07:07.070> the<00:07:07.220> initial<00:07:08.889> setting 00:07:09.879 --> 00:07:09.889 align:start position:0% filled cells from the initial setting 00:07:09.889 --> 00:07:12.820 align:start position:0% filled cells from the initial setting and<00:07:10.160> the<00:07:10.580> shuffling<00:07:10.940> so<00:07:11.900> let's<00:07:12.229> assume<00:07:12.500> she 00:07:12.820 --> 00:07:12.830 align:start position:0% and the shuffling so let's assume she 00:07:12.830 --> 00:07:16.000 align:start position:0% and the shuffling so let's assume she chooses<00:07:13.580> to<00:07:13.810> see<00:07:14.810> the<00:07:15.080> initially<00:07:15.560> fuel<00:07:15.710> cells 00:07:16.000 --> 00:07:16.010 align:start position:0% chooses to see the initially fuel cells 00:07:16.010 --> 00:07:18.400 align:start position:0% chooses to see the initially fuel cells then<00:07:16.340> the<00:07:17.000> prover<00:07:17.270> will<00:07:17.450> just<00:07:17.660> peel<00:07:17.960> off<00:07:17.990> the 00:07:18.400 --> 00:07:18.410 align:start position:0% then the prover will just peel off the 00:07:18.410 --> 00:07:20.320 align:start position:0% then the prover will just peel off the sticky<00:07:18.680> tape<00:07:18.830> from<00:07:19.160> the<00:07:19.400> from<00:07:19.820> the<00:07:19.910> cells<00:07:20.120> from 00:07:20.320 --> 00:07:20.330 align:start position:0% sticky tape from the from the cells from 00:07:20.330 --> 00:07:22.390 align:start position:0% sticky tape from the from the cells from the<00:07:20.479> initial<00:07:21.410> solution<00:07:21.800> and<00:07:21.950> from<00:07:22.160> the 00:07:22.390 --> 00:07:22.400 align:start position:0% the initial solution and from the 00:07:22.400 --> 00:07:26.080 align:start position:0% the initial solution and from the substitution<00:07:23.380> from<00:07:24.380> the<00:07:24.530> shuffling<00:07:24.830> and<00:07:25.090> the 00:07:26.080 --> 00:07:26.090 align:start position:0% substitution from the shuffling and the 00:07:26.090 --> 00:07:30.010 align:start position:0% substitution from the shuffling and the verifier<00:07:26.570> will<00:07:27.100> check<00:07:28.100> that<00:07:28.700> this<00:07:29.240> matches 00:07:30.010 --> 00:07:30.020 align:start position:0% verifier will check that this matches 00:07:30.020 --> 00:07:32.469 align:start position:0% verifier will check that this matches the<00:07:30.320> initially<00:07:30.710> given<00:07:30.919> problem<00:07:31.910> setting<00:07:32.120> so 00:07:32.469 --> 00:07:32.479 align:start position:0% the initially given problem setting so 00:07:32.479 --> 00:07:35.590 align:start position:0% the initially given problem setting so she<00:07:33.290> looks<00:07:33.860> at<00:07:34.070> the<00:07:34.280> at<00:07:34.970> the<00:07:35.090> problem<00:07:35.360> setting 00:07:35.590 --> 00:07:35.600 align:start position:0% she looks at the at the problem setting 00:07:35.600 --> 00:07:37.629 align:start position:0% she looks at the at the problem setting here<00:07:35.750> on<00:07:35.870> the<00:07:35.930> right<00:07:36.110> for<00:07:36.350> example<00:07:37.160> the<00:07:37.250> and<00:07:37.460> in 00:07:37.629 --> 00:07:37.639 align:start position:0% here on the right for example the and in 00:07:37.639 --> 00:07:40.779 align:start position:0% here on the right for example the and in the<00:07:37.729> top<00:07:37.910> row<00:07:38.720> there's<00:07:38.990> a<00:07:39.050> three<00:07:39.400> she<00:07:40.400> looks<00:07:40.610> at 00:07:40.779 --> 00:07:40.789 align:start position:0% the top row there's a three she looks at 00:07:40.789 --> 00:07:42.580 align:start position:0% the top row there's a three she looks at the<00:07:40.910> replacement<00:07:41.330> and<00:07:41.690> the<00:07:41.750> shuffling<00:07:42.110> sees 00:07:42.580 --> 00:07:42.590 align:start position:0% the replacement and the shuffling sees 00:07:42.590 --> 00:07:44.800 align:start position:0% the replacement and the shuffling sees that<00:07:42.770> she's<00:07:43.010> read<00:07:43.640> three<00:07:44.090> is<00:07:44.240> replaced<00:07:44.570> by<00:07:44.660> two 00:07:44.800 --> 00:07:44.810 align:start position:0% that she's read three is replaced by two 00:07:44.810 --> 00:07:47.200 align:start position:0% that she's read three is replaced by two looks<00:07:45.680> at<00:07:45.860> the<00:07:46.039> cell<00:07:46.280> in<00:07:46.520> the<00:07:46.580> in<00:07:47.030> the 00:07:47.200 --> 00:07:47.210 align:start position:0% looks at the cell in the in the 00:07:47.210 --> 00:07:50.170 align:start position:0% looks at the cell in the in the partially<00:07:47.690> covered<00:07:48.760> table<00:07:49.760> and<00:07:50.000> see<00:07:50.150> that 00:07:50.170 --> 00:07:50.180 align:start position:0% partially covered table and see that 00:07:50.180 --> 00:07:51.880 align:start position:0% partially covered table and see that that<00:07:50.570> there's<00:07:50.750> a<00:07:50.810> two<00:07:51.020> so<00:07:51.229> that<00:07:51.380> that<00:07:51.560> matches 00:07:51.880 --> 00:07:51.890 align:start position:0% that there's a two so that that matches 00:07:51.890 --> 00:07:53.950 align:start position:0% that there's a two so that that matches and<00:07:52.070> she<00:07:52.160> does<00:07:52.310> that<00:07:52.460> for<00:07:52.520> all<00:07:53.000> the<00:07:53.479> cells<00:07:53.720> in 00:07:53.950 --> 00:07:53.960 align:start position:0% and she does that for all the cells in 00:07:53.960 --> 00:07:57.930 align:start position:0% and she does that for all the cells in the<00:07:54.140> initial<00:07:54.740> problem<00:07:55.100> setting<00:07:56.110> okay<00:07:57.110> and 00:07:57.930 --> 00:07:57.940 align:start position:0% the initial problem setting okay and 00:07:57.940 --> 00:08:01.630 align:start position:0% the initial problem setting okay and what<00:07:58.940> what<00:07:59.120> just<00:07:59.300> happened<00:07:59.660> so<00:08:00.220> the<00:08:01.220> prover 00:08:01.630 --> 00:08:01.640 align:start position:0% what what just happened so the prover 00:08:01.640 --> 00:08:04.360 align:start position:0% what what just happened so the prover revealed<00:08:02.210> parts<00:08:02.660> of<00:08:02.870> the<00:08:03.560> rebuild<00:08:04.250> of 00:08:04.360 --> 00:08:04.370 align:start position:0% revealed parts of the rebuild of 00:08:04.370 --> 00:08:06.420 align:start position:0% revealed parts of the rebuild of shuffling<00:08:04.639> right<00:08:04.850> doesn't<00:08:05.450> that<00:08:05.660> reveal<00:08:05.990> any 00:08:06.420 --> 00:08:06.430 align:start position:0% shuffling right doesn't that reveal any 00:08:06.430 --> 00:08:10.210 align:start position:0% shuffling right doesn't that reveal any information<00:08:07.430> I<00:08:08.289> mean<00:08:09.289> the<00:08:09.410> the<00:08:09.740> shuffling<00:08:10.070> is 00:08:10.210 --> 00:08:10.220 align:start position:0% information I mean the the shuffling is 00:08:10.220 --> 00:08:13.029 align:start position:0% information I mean the the shuffling is the<00:08:11.000> proved<00:08:11.389> it<00:08:11.510> shows<00:08:11.690> that<00:08:11.900> in<00:08:12.080> secret<00:08:12.500> but 00:08:13.029 --> 00:08:13.039 align:start position:0% the proved it shows that in secret but 00:08:13.039 --> 00:08:14.529 align:start position:0% the proved it shows that in secret but it's<00:08:13.190> not<00:08:13.340> part<00:08:13.550> of<00:08:13.580> the<00:08:13.700> solution<00:08:14.060> so<00:08:14.090> that's 00:08:14.529 --> 00:08:14.539 align:start position:0% it's not part of the solution so that's 00:08:14.539 --> 00:08:16.510 align:start position:0% it's not part of the solution so that's that's<00:08:14.840> totally<00:08:15.200> fine<00:08:15.380> and<00:08:15.680> all<00:08:15.919> the<00:08:16.100> initial 00:08:16.510 --> 00:08:16.520 align:start position:0% that's totally fine and all the initial 00:08:16.520 --> 00:08:18.400 align:start position:0% that's totally fine and all the initial cells<00:08:16.729> I<00:08:16.970> mean<00:08:17.150> that's<00:08:17.389> nothing<00:08:18.080> to<00:08:18.320> be 00:08:18.400 --> 00:08:18.410 align:start position:0% cells I mean that's nothing to be 00:08:18.410 --> 00:08:20.560 align:start position:0% cells I mean that's nothing to be learned<00:08:18.590> there<00:08:18.680> right<00:08:18.979> so<00:08:19.090> no<00:08:20.090> private 00:08:20.560 --> 00:08:20.570 align:start position:0% learned there right so no private 00:08:20.570 --> 00:08:23.080 align:start position:0% learned there right so no private information<00:08:20.720> was<00:08:21.530> shared<00:08:21.560> in<00:08:22.190> this<00:08:22.490> in<00:08:22.910> this 00:08:23.080 --> 00:08:23.090 align:start position:0% information was shared in this in this 00:08:23.090 --> 00:08:29.860 align:start position:0% information was shared in this in this turn<00:08:24.490> and<00:08:25.490> now<00:08:25.820> the<00:08:26.950> this<00:08:27.950> these<00:08:28.550> steps<00:08:29.150> 1<00:08:29.479> to<00:08:29.660> 5 00:08:29.860 --> 00:08:29.870 align:start position:0% turn and now the this these steps 1 to 5 00:08:29.870 --> 00:08:36.040 align:start position:0% turn and now the this these steps 1 to 5 are<00:08:30.340> repeated<00:08:31.340> multiple<00:08:31.789> times<00:08:31.850> and<00:08:33.700> the<00:08:35.050> one 00:08:36.040 --> 00:08:36.050 align:start position:0% are repeated multiple times and the one 00:08:36.050 --> 00:08:37.990 align:start position:0% are repeated multiple times and the one very<00:08:36.500> important<00:08:37.010> thing<00:08:37.219> here<00:08:37.459> is<00:08:37.640> that<00:08:37.669> the 00:08:37.990 --> 00:08:38.000 align:start position:0% very important thing here is that the 00:08:38.000 --> 00:08:40.180 align:start position:0% very important thing here is that the prover<00:08:38.270> always<00:08:38.599> has<00:08:38.810> to<00:08:38.990> find<00:08:39.260> a<00:08:39.500> completely 00:08:40.180 --> 00:08:40.190 align:start position:0% prover always has to find a completely 00:08:40.190 --> 00:08:42.449 align:start position:0% prover always has to find a completely random<00:08:40.700> shuffling<00:08:41.539> in<00:08:41.719> each<00:08:41.900> round 00:08:42.449 --> 00:08:42.459 align:start position:0% random shuffling in each round 00:08:42.459 --> 00:08:46.390 align:start position:0% random shuffling in each round if<00:08:43.459> the<00:08:43.700> prover<00:08:44.470> uses<00:08:45.470> the<00:08:45.709> same<00:08:45.920> shuffling 00:08:46.390 --> 00:08:46.400 align:start position:0% if the prover uses the same shuffling 00:08:46.400 --> 00:08:48.140 align:start position:0% if the prover uses the same shuffling and<00:08:46.520> the<00:08:46.670> verify<00:08:47.000> knows<00:08:47.270> the<00:08:47.540> fact<00:08:47.780> that 00:08:48.140 --> 00:08:48.150 align:start position:0% and the verify knows the fact that 00:08:48.150 --> 00:08:53.810 align:start position:0% and the verify knows the fact that information<00:08:49.020> can<00:08:49.170> be<00:08:49.290> revealed<00:08:49.790> so<00:08:52.580> yes<00:08:53.580> and 00:08:53.810 --> 00:08:53.820 align:start position:0% information can be revealed so yes and 00:08:53.820 --> 00:08:55.580 align:start position:0% information can be revealed so yes and only<00:08:54.150> if<00:08:54.390> you<00:08:54.510> choose<00:08:54.750> a<00:08:54.780> new<00:08:55.140> shuffling<00:08:55.500> in 00:08:55.580 --> 00:08:55.590 align:start position:0% only if you choose a new shuffling in 00:08:55.590 --> 00:08:57.440 align:start position:0% only if you choose a new shuffling in each<00:08:55.680> round<00:08:55.860> you<00:08:56.070> achieve<00:08:56.340> zero<00:08:56.370> knowledge<00:08:56.760> so 00:08:57.440 --> 00:08:57.450 align:start position:0% each round you achieve zero knowledge so 00:08:57.450 --> 00:09:01.250 align:start position:0% each round you achieve zero knowledge so let's<00:08:57.600> do<00:08:57.690> a<00:08:57.720> second<00:08:58.080> round<00:08:59.840> we<00:09:00.840> have<00:09:00.990> a<00:09:01.020> newly 00:09:01.250 --> 00:09:01.260 align:start position:0% let's do a second round we have a newly 00:09:01.260 --> 00:09:02.750 align:start position:0% let's do a second round we have a newly shuffle<00:09:01.650> board<00:09:01.860> with<00:09:02.040> a<00:09:02.070> newly<00:09:02.280> randomly 00:09:02.750 --> 00:09:02.760 align:start position:0% shuffle board with a newly randomly 00:09:02.760 --> 00:09:07.000 align:start position:0% shuffle board with a newly randomly chosen<00:09:03.000> shuffling<00:09:03.660> and<00:09:05.210> cover<00:09:06.210> that<00:09:06.360> again 00:09:07.000 --> 00:09:07.010 align:start position:0% chosen shuffling and cover that again 00:09:07.010 --> 00:09:09.890 align:start position:0% chosen shuffling and cover that again put<00:09:08.010> it<00:09:08.100> on<00:09:08.190> the<00:09:08.280> table<00:09:08.490> and<00:09:08.850> now<00:09:09.060> the<00:09:09.120> verify 00:09:09.890 --> 00:09:09.900 align:start position:0% put it on the table and now the verify 00:09:09.900 --> 00:09:12.770 align:start position:0% put it on the table and now the verify again<00:09:10.080> has<00:09:10.290> these<00:09:10.530> choices<00:09:10.860> she<00:09:11.820> chooses<00:09:12.360> to 00:09:12.770 --> 00:09:12.780 align:start position:0% again has these choices she chooses to 00:09:12.780 --> 00:09:16.100 align:start position:0% again has these choices she chooses to she<00:09:13.740> wants<00:09:13.920> to<00:09:14.010> see<00:09:14.160> column<00:09:14.550> two<00:09:14.760> so<00:09:15.750> the 00:09:16.100 --> 00:09:16.110 align:start position:0% she wants to see column two so the 00:09:16.110 --> 00:09:19.160 align:start position:0% she wants to see column two so the approver<00:09:16.910> peels<00:09:17.910> off<00:09:18.150> the<00:09:18.570> sticky<00:09:18.870> tape<00:09:19.020> from 00:09:19.160 --> 00:09:19.170 align:start position:0% approver peels off the sticky tape from 00:09:19.170 --> 00:09:21.050 align:start position:0% approver peels off the sticky tape from column<00:09:19.470> two<00:09:19.650> but<00:09:20.100> it's<00:09:20.220> not<00:09:20.430> peel<00:09:20.700> off<00:09:20.910> the 00:09:21.050 --> 00:09:21.060 align:start position:0% column two but it's not peel off the 00:09:21.060 --> 00:09:22.700 align:start position:0% column two but it's not peel off the sticky<00:09:21.300> tape<00:09:21.450> from<00:09:21.660> the<00:09:21.960> from<00:09:22.350> the<00:09:22.440> shuffling 00:09:22.700 --> 00:09:22.710 align:start position:0% sticky tape from the from the shuffling 00:09:22.710 --> 00:09:26.030 align:start position:0% sticky tape from the from the shuffling that's<00:09:22.890> very<00:09:23.100> important<00:09:23.520> and<00:09:24.200> now<00:09:25.200> what<00:09:25.950> the 00:09:26.030 --> 00:09:26.040 align:start position:0% that's very important and now what the 00:09:26.040 --> 00:09:29.620 align:start position:0% that's very important and now what the prove<00:09:26.220> it<00:09:26.310> does<00:09:26.490> ever<00:09:26.790> the<00:09:27.860> verifier<00:09:28.860> does<00:09:29.130> is 00:09:29.620 --> 00:09:29.630 align:start position:0% prove it does ever the verifier does is 00:09:29.630 --> 00:09:33.200 align:start position:0% prove it does ever the verifier does is she<00:09:30.630> checks<00:09:30.870> that<00:09:31.430> each<00:09:32.430> of<00:09:32.670> the<00:09:32.760> numbers<00:09:33.030> one 00:09:33.200 --> 00:09:33.210 align:start position:0% she checks that each of the numbers one 00:09:33.210 --> 00:09:35.300 align:start position:0% she checks that each of the numbers one to<00:09:33.330> four<00:09:33.570> appears<00:09:33.990> exactly<00:09:34.350> once<00:09:34.560> in<00:09:34.920> this 00:09:35.300 --> 00:09:35.310 align:start position:0% to four appears exactly once in this 00:09:35.310 --> 00:09:37.550 align:start position:0% to four appears exactly once in this column<00:09:35.640> because<00:09:36.450> that's<00:09:36.630> a<00:09:36.720> property<00:09:37.020> we<00:09:37.410> want 00:09:37.550 --> 00:09:37.560 align:start position:0% column because that's a property we want 00:09:37.560 --> 00:09:41.390 align:start position:0% column because that's a property we want to<00:09:37.650> have<00:09:37.860> and<00:09:38.100> now<00:09:39.140> you<00:09:40.140> might<00:09:40.350> say<00:09:40.590> okay<00:09:41.040> the 00:09:41.390 --> 00:09:41.400 align:start position:0% to have and now you might say okay the 00:09:41.400 --> 00:09:43.730 align:start position:0% to have and now you might say okay the proof<00:09:41.790> were<00:09:41.970> just<00:09:42.240> revealed<00:09:42.720> the<00:09:43.260> numbers<00:09:43.590> in 00:09:43.730 --> 00:09:43.740 align:start position:0% proof were just revealed the numbers in 00:09:43.740 --> 00:09:45.500 align:start position:0% proof were just revealed the numbers in the<00:09:43.830> solution<00:09:44.220> so<00:09:44.430> some<00:09:45.060> private<00:09:45.390> information 00:09:45.500 --> 00:09:45.510 align:start position:0% the solution so some private information 00:09:45.510 --> 00:09:47.000 align:start position:0% the solution so some private information was<00:09:45.990> revealed<00:09:46.290> but<00:09:46.470> that's<00:09:46.620> actually<00:09:46.710> not<00:09:46.950> the 00:09:47.000 --> 00:09:47.010 align:start position:0% was revealed but that's actually not the 00:09:47.010 --> 00:09:51.860 align:start position:0% was revealed but that's actually not the fact<00:09:47.810> because<00:09:49.040> the<00:09:50.040> this<00:09:50.940> replacement<00:09:51.450> was 00:09:51.860 --> 00:09:51.870 align:start position:0% fact because the this replacement was 00:09:51.870 --> 00:09:54.440 align:start position:0% fact because the this replacement was completely<00:09:52.350> random<00:09:52.560> any<00:09:53.030> replacement<00:09:54.030> has 00:09:54.440 --> 00:09:54.450 align:start position:0% completely random any replacement has 00:09:54.450 --> 00:09:58.910 align:start position:0% completely random any replacement has equal<00:09:55.110> probability<00:09:55.140> and<00:09:57.290> each<00:09:58.290> replacement 00:09:58.910 --> 00:09:58.920 align:start position:0% equal probability and each replacement 00:09:58.920 --> 00:10:03.950 align:start position:0% equal probability and each replacement actually<00:10:00.650> corresponds<00:10:01.650> to<00:10:01.680> a<00:10:02.840> permutation<00:10:03.840> of 00:10:03.950 --> 00:10:03.960 align:start position:0% actually corresponds to a permutation of 00:10:03.960 --> 00:10:09.320 align:start position:0% actually corresponds to a permutation of this<00:10:05.540> of<00:10:06.540> this<00:10:06.780> column<00:10:07.110> here<00:10:07.290> so<00:10:07.610> every<00:10:08.610> every 00:10:09.320 --> 00:10:09.330 align:start position:0% this of this column here so every every 00:10:09.330 --> 00:10:11.120 align:start position:0% this of this column here so every every correct<00:10:09.630> solution<00:10:10.200> inside<00:10:10.560> this<00:10:10.680> column<00:10:11.010> is 00:10:11.120 --> 00:10:11.130 align:start position:0% correct solution inside this column is 00:10:11.130 --> 00:10:13.850 align:start position:0% correct solution inside this column is equally<00:10:11.430> likely<00:10:11.460> so<00:10:11.790> no<00:10:12.180> not<00:10:13.110> a<00:10:13.140> single<00:10:13.500> bit<00:10:13.650> of 00:10:13.850 --> 00:10:13.860 align:start position:0% equally likely so no not a single bit of 00:10:13.860 --> 00:10:15.770 align:start position:0% equally likely so no not a single bit of private<00:10:14.280> information<00:10:14.760> was<00:10:15.120> revealed<00:10:15.300> here 00:10:15.770 --> 00:10:15.780 align:start position:0% private information was revealed here 00:10:15.780 --> 00:10:22.670 align:start position:0% private information was revealed here and<00:10:17.780> yeah<00:10:18.780> so<00:10:19.670> and<00:10:21.050> if<00:10:22.050> you<00:10:22.170> repeat<00:10:22.350> this 00:10:22.670 --> 00:10:22.680 align:start position:0% and yeah so and if you repeat this 00:10:22.680 --> 00:10:25.550 align:start position:0% and yeah so and if you repeat this multiple<00:10:23.100> times<00:10:23.160> then<00:10:23.960> the<00:10:24.960> prover<00:10:25.260> can<00:10:25.440> up 00:10:25.550 --> 00:10:25.560 align:start position:0% multiple times then the prover can up 00:10:25.560 --> 00:10:27.830 align:start position:0% multiple times then the prover can up cheat<00:10:25.740> or<00:10:25.860> at<00:10:25.950> least<00:10:26.160> it<00:10:26.910> becomes<00:10:27.360> less<00:10:27.660> and 00:10:27.830 --> 00:10:27.840 align:start position:0% cheat or at least it becomes less and 00:10:27.840 --> 00:10:29.210 align:start position:0% cheat or at least it becomes less and less<00:10:27.960> likely<00:10:28.230> for<00:10:28.380> the<00:10:28.620> prover<00:10:28.890> to<00:10:29.010> cheat 00:10:29.210 --> 00:10:29.220 align:start position:0% less likely for the prover to cheat 00:10:29.220 --> 00:10:32.450 align:start position:0% less likely for the prover to cheat because<00:10:29.720> the<00:10:30.720> verifier<00:10:31.110> doesn't<00:10:31.470> check 00:10:32.450 --> 00:10:32.460 align:start position:0% because the verifier doesn't check 00:10:32.460 --> 00:10:35.030 align:start position:0% because the verifier doesn't check everything<00:10:33.000> she<00:10:33.630> only<00:10:33.870> checks<00:10:34.140> a<00:10:34.380> certain 00:10:35.030 --> 00:10:35.040 align:start position:0% everything she only checks a certain 00:10:35.040 --> 00:10:37.250 align:start position:0% everything she only checks a certain part<00:10:35.250> of<00:10:35.310> the<00:10:35.370> solution<00:10:36.090> in<00:10:36.210> each<00:10:36.300> round<00:10:36.570> but 00:10:37.250 --> 00:10:37.260 align:start position:0% part of the solution in each round but 00:10:37.260 --> 00:10:39.860 align:start position:0% part of the solution in each round but there's<00:10:38.070> always<00:10:38.580> a<00:10:38.940> certain<00:10:39.270> probability 00:10:39.860 --> 00:10:39.870 align:start position:0% there's always a certain probability 00:10:39.870 --> 00:10:42.860 align:start position:0% there's always a certain probability that<00:10:40.140> she<00:10:40.860> will<00:10:41.010> find<00:10:41.310> the<00:10:41.520> error<00:10:41.670> and<00:10:42.120> this 00:10:42.860 --> 00:10:42.870 align:start position:0% that she will find the error and this 00:10:42.870 --> 00:10:47.120 align:start position:0% that she will find the error and this the<00:10:43.650> overall<00:10:44.720> chance<00:10:45.720> of<00:10:46.020> success<00:10:46.950> in 00:10:47.120 --> 00:10:47.130 align:start position:0% the overall chance of success in 00:10:47.130 --> 00:10:48.440 align:start position:0% the overall chance of success in cheating<00:10:47.520> of<00:10:47.670> course<00:10:47.700> decreases 00:10:48.440 --> 00:10:48.450 align:start position:0% cheating of course decreases 00:10:48.450 --> 00:10:50.770 align:start position:0% cheating of course decreases exponentially<00:10:48.840> with<00:10:49.200> the<00:10:49.230> number<00:10:49.410> of<00:10:49.680> rounds 00:10:50.770 --> 00:10:50.780 align:start position:0% exponentially with the number of rounds 00:10:50.780 --> 00:10:55.070 align:start position:0% exponentially with the number of rounds and<00:10:51.780> the<00:10:53.240> the<00:10:54.240> important<00:10:54.870> thing<00:10:55.050> that 00:10:55.070 --> 00:10:55.080 align:start position:0% and the the important thing that 00:10:55.080 --> 00:10:57.710 align:start position:0% and the the important thing that happened<00:10:55.560> here<00:10:55.590> is<00:10:55.890> why<00:10:56.760> this<00:10:56.820> works<00:10:57.240> is<00:10:57.480> that 00:10:57.710 --> 00:10:57.720 align:start position:0% happened here is why this works is that 00:10:57.720 --> 00:11:00.200 align:start position:0% happened here is why this works is that the<00:10:58.320> prover<00:10:58.890> actually<00:10:59.430> writes<00:10:59.700> the<00:10:59.910> numbers 00:11:00.200 --> 00:11:00.210 align:start position:0% the prover actually writes the numbers 00:11:00.210 --> 00:11:01.639 align:start position:0% the prover actually writes the numbers on<00:11:00.420> the<00:11:00.630> paper 00:11:01.639 --> 00:11:01.649 align:start position:0% on the paper 00:11:01.649 --> 00:11:04.400 align:start position:0% on the paper but<00:11:02.129> it<00:11:02.369> would<00:11:02.790> tape<00:11:02.970> with<00:11:03.269> tape<00:11:03.540> so<00:11:03.779> it's 00:11:04.400 --> 00:11:04.410 align:start position:0% but it would tape with tape so it's 00:11:04.410 --> 00:11:06.889 align:start position:0% but it would tape with tape so it's impossible<00:11:04.680> to<00:11:05.069> change<00:11:05.339> the<00:11:06.149> numbers<00:11:06.689> after 00:11:06.889 --> 00:11:06.899 align:start position:0% impossible to change the numbers after 00:11:06.899 --> 00:11:09.410 align:start position:0% impossible to change the numbers after the<00:11:07.350> verifier<00:11:07.829> has<00:11:08.100> made<00:11:08.579> her<00:11:08.759> decision<00:11:08.790> what 00:11:09.410 --> 00:11:09.420 align:start position:0% the verifier has made her decision what 00:11:09.420 --> 00:11:12.609 align:start position:0% the verifier has made her decision what to<00:11:09.449> see<00:11:09.749> that's<00:11:10.589> basically<00:11:10.980> the<00:11:11.160> the<00:11:12.149> way<00:11:12.389> we 00:11:12.609 --> 00:11:12.619 align:start position:0% to see that's basically the the way we 00:11:12.619 --> 00:11:17.540 align:start position:0% to see that's basically the the way we why<00:11:13.619> this<00:11:13.680> protocol<00:11:14.279> works<00:11:16.040> okay<00:11:17.069> this<00:11:17.369> was 00:11:17.540 --> 00:11:17.550 align:start position:0% why this protocol works okay this was 00:11:17.550 --> 00:11:24.859 align:start position:0% why this protocol works okay this was mini<00:11:17.819> Sudoku<00:11:18.300> and<00:11:23.029> from<00:11:24.029> this<00:11:24.179> example<00:11:24.540> want 00:11:24.859 --> 00:11:24.869 align:start position:0% mini Sudoku and from this example want 00:11:24.869 --> 00:11:28.150 align:start position:0% mini Sudoku and from this example want to<00:11:24.959> go<00:11:25.079> to<00:11:25.139> CK<00:11:25.559> snarks<00:11:25.889> mini<00:11:26.550> Sudoku<00:11:27.059> still<00:11:27.540> has 00:11:28.150 --> 00:11:28.160 align:start position:0% to go to CK snarks mini Sudoku still has 00:11:28.160 --> 00:11:31.009 align:start position:0% to go to CK snarks mini Sudoku still has lots<00:11:29.160> of<00:11:29.279> problems<00:11:29.429> it's<00:11:29.850> not<00:11:29.999> really<00:11:30.389> nicely 00:11:31.009 --> 00:11:31.019 align:start position:0% lots of problems it's not really nicely 00:11:31.019 --> 00:11:34.100 align:start position:0% lots of problems it's not really nicely usable<00:11:31.499> protocol<00:11:31.949> and<00:11:32.209> the<00:11:33.209> first<00:11:33.509> problem<00:11:34.050> is 00:11:34.100 --> 00:11:34.110 align:start position:0% usable protocol and the first problem is 00:11:34.110 --> 00:11:35.449 align:start position:0% usable protocol and the first problem is that<00:11:34.170> it<00:11:34.350> doesn't<00:11:34.470> use<00:11:34.589> it<00:11:34.949> doesn't<00:11:35.220> work<00:11:35.309> for 00:11:35.449 --> 00:11:35.459 align:start position:0% that it doesn't use it doesn't work for 00:11:35.459 --> 00:11:36.799 align:start position:0% that it doesn't use it doesn't work for generic<00:11:35.759> computation<00:11:36.209> it<00:11:36.300> just<00:11:36.420> works<00:11:36.629> for 00:11:36.799 --> 00:11:36.809 align:start position:0% generic computation it just works for 00:11:36.809 --> 00:11:38.419 align:start position:0% generic computation it just works for these<00:11:36.929> pseudo<00:11:37.259> keyboards<00:11:37.709> but<00:11:38.279> that's 00:11:38.419 --> 00:11:38.429 align:start position:0% these pseudo keyboards but that's 00:11:38.429 --> 00:11:43.040 align:start position:0% these pseudo keyboards but that's actually<00:11:38.519> not<00:11:38.699> true<00:11:38.910> so<00:11:40.459> you<00:11:41.459> can<00:11:42.019> you<00:11:43.019> can 00:11:43.040 --> 00:11:43.050 align:start position:0% actually not true so you can you can 00:11:43.050 --> 00:11:46.879 align:start position:0% actually not true so you can you can take<00:11:43.410> an<00:11:43.679> arbitrary<00:11:45.170> problem<00:11:46.170> in<00:11:46.259> computation 00:11:46.879 --> 00:11:46.889 align:start position:0% take an arbitrary problem in computation 00:11:46.889 --> 00:11:50.239 align:start position:0% take an arbitrary problem in computation and<00:11:47.300> transform<00:11:48.300> that<00:11:48.449> into<00:11:48.829> the<00:11:49.829> Sudoku 00:11:50.239 --> 00:11:50.249 align:start position:0% and transform that into the Sudoku 00:11:50.249 --> 00:11:52.040 align:start position:0% and transform that into the Sudoku problem<00:11:50.579> so<00:11:50.699> this<00:11:50.850> is<00:11:50.939> called<00:11:51.179> a<00:11:51.329> reduction<00:11:51.899> or 00:11:52.040 --> 00:11:52.050 align:start position:0% problem so this is called a reduction or 00:11:52.050 --> 00:11:56.059 align:start position:0% problem so this is called a reduction or you<00:11:52.920> could<00:11:53.069> also<00:11:53.189> just<00:11:53.309> see<00:11:53.639> it<00:11:53.699> as<00:11:54.589> if<00:11:55.589> you 00:11:56.059 --> 00:11:56.069 align:start position:0% you could also just see it as if you 00:11:56.069 --> 00:11:57.230 align:start position:0% you could also just see it as if you have<00:11:56.220> a<00:11:56.249> solution<00:11:56.579> written<00:11:56.850> in<00:11:57.089> one 00:11:57.230 --> 00:11:57.240 align:start position:0% have a solution written in one 00:11:57.240 --> 00:11:59.389 align:start position:0% have a solution written in one programming<00:11:57.569> language<00:11:58.019> and<00:11:58.230> you<00:11:59.189> take<00:11:59.369> a 00:11:59.389 --> 00:11:59.399 align:start position:0% programming language and you take a 00:11:59.399 --> 00:12:01.579 align:start position:0% programming language and you take a compiler<00:11:59.790> and<00:11:59.999> compile<00:12:00.389> it<00:12:00.540> into<00:12:00.720> a<00:12:01.170> machine 00:12:01.579 --> 00:12:01.589 align:start position:0% compiler and compile it into a machine 00:12:01.589 --> 00:12:03.559 align:start position:0% compiler and compile it into a machine language<00:12:01.740> this<00:12:02.129> is<00:12:02.249> also<00:12:02.610> I<00:12:02.790> mean<00:12:03.300> this<00:12:03.389> is 00:12:03.559 --> 00:12:03.569 align:start position:0% language this is also I mean this is 00:12:03.569 --> 00:12:05.629 align:start position:0% language this is also I mean this is done<00:12:03.720> all<00:12:03.899> the<00:12:04.019> time<00:12:04.199> this<00:12:04.769> is<00:12:04.949> just<00:12:05.100> these 00:12:05.629 --> 00:12:05.639 align:start position:0% done all the time this is just these 00:12:05.639 --> 00:12:09.110 align:start position:0% done all the time this is just these problems<00:12:06.360> just<00:12:06.540> look<00:12:06.990> little<00:12:07.759> less<00:12:08.759> than 00:12:09.110 --> 00:12:09.120 align:start position:0% problems just look little less than 00:12:09.120 --> 00:12:11.179 align:start position:0% problems just look little less than computers<00:12:10.019> but<00:12:10.290> they<00:12:10.439> can<00:12:10.620> actually<00:12:10.740> encode 00:12:11.179 --> 00:12:11.189 align:start position:0% computers but they can actually encode 00:12:11.189 --> 00:12:13.069 align:start position:0% computers but they can actually encode all<00:12:11.429> these<00:12:11.639> problems<00:12:12.480> you<00:12:12.540> could<00:12:12.689> think<00:12:12.779> of<00:12:12.929> so 00:12:13.069 --> 00:12:13.079 align:start position:0% all these problems you could think of so 00:12:13.079 --> 00:12:18.559 align:start position:0% all these problems you could think of so this<00:12:13.170> is<00:12:13.230> a<00:12:13.350> soft<00:12:13.620> problem<00:12:15.110> it<00:12:16.110> takes<00:12:16.439> a<00:12:17.540> lot<00:12:18.540> of 00:12:18.559 --> 00:12:18.569 align:start position:0% this is a soft problem it takes a lot of 00:12:18.569 --> 00:12:20.030 align:start position:0% this is a soft problem it takes a lot of engineering<00:12:19.050> work<00:12:19.230> to<00:12:19.350> make<00:12:19.499> that<00:12:19.620> efficient 00:12:20.030 --> 00:12:20.040 align:start position:0% engineering work to make that efficient 00:12:20.040 --> 00:12:21.860 align:start position:0% engineering work to make that efficient that<00:12:20.249> take<00:12:20.579> for<00:12:20.730> granted<00:12:20.910> but<00:12:21.149> the<00:12:21.360> general 00:12:21.860 --> 00:12:21.870 align:start position:0% that take for granted but the general 00:12:21.870 --> 00:12:24.379 align:start position:0% that take for granted but the general problem<00:12:22.290> is<00:12:22.379> solved<00:12:22.920> so<00:12:23.459> a<00:12:23.490> but<00:12:23.910> what<00:12:24.300> is 00:12:24.379 --> 00:12:24.389 align:start position:0% problem is solved so a but what is 00:12:24.389 --> 00:12:29.299 align:start position:0% problem is solved so a but what is actually<00:12:24.929> more<00:12:27.019> yeah<00:12:28.019> more<00:12:28.709> problematic<00:12:29.189> is 00:12:29.299 --> 00:12:29.309 align:start position:0% actually more yeah more problematic is 00:12:29.309 --> 00:12:31.610 align:start position:0% actually more yeah more problematic is that<00:12:29.339> mini<00:12:29.999> pseudocode<00:12:30.300> takes<00:12:30.600> many<00:12:31.319> rounds 00:12:31.610 --> 00:12:31.620 align:start position:0% that mini pseudocode takes many rounds 00:12:31.620 --> 00:12:33.619 align:start position:0% that mini pseudocode takes many rounds of<00:12:31.709> kind<00:12:31.889> of<00:12:31.980> interaction<00:12:32.610> and<00:12:32.759> this<00:12:33.480> is 00:12:33.619 --> 00:12:33.629 align:start position:0% of kind of interaction and this is 00:12:33.629 --> 00:12:35.749 align:start position:0% of kind of interaction and this is especially<00:12:34.110> problematic<00:12:34.649> for<00:12:35.220> a<00:12:35.309> block<00:12:35.519> chain 00:12:35.749 --> 00:12:35.759 align:start position:0% especially problematic for a block chain 00:12:35.759 --> 00:12:37.280 align:start position:0% especially problematic for a block chain where<00:12:35.970> we<00:12:36.029> want<00:12:36.209> to<00:12:36.329> create<00:12:36.929> a<00:12:37.019> transaction 00:12:37.280 --> 00:12:37.290 align:start position:0% where we want to create a transaction 00:12:37.290 --> 00:12:39.259 align:start position:0% where we want to create a transaction send<00:12:37.829> it<00:12:37.920> the<00:12:38.009> block<00:12:38.189> chain<00:12:38.429> and<00:12:38.670> the<00:12:39.089> block 00:12:39.259 --> 00:12:39.269 align:start position:0% send it the block chain and the block 00:12:39.269 --> 00:12:42.619 align:start position:0% send it the block chain and the block chain<00:12:39.480> should<00:12:39.959> verify<00:12:40.949> it<00:12:41.009> and<00:12:41.279> then<00:12:41.429> yeah<00:12:42.300> be 00:12:42.619 --> 00:12:42.629 align:start position:0% chain should verify it and then yeah be 00:12:42.629 --> 00:12:44.539 align:start position:0% chain should verify it and then yeah be done<00:12:42.809> with<00:12:42.959> it<00:12:43.079> instead<00:12:43.829> of<00:12:43.980> having<00:12:44.309> all<00:12:44.490> these 00:12:44.539 --> 00:12:44.549 align:start position:0% done with it instead of having all these 00:12:44.549 --> 00:12:47.559 align:start position:0% done with it instead of having all these rounds<00:12:44.910> of<00:12:44.999> interactions<00:12:45.509> and<00:12:45.629> especially 00:12:47.559 --> 00:12:47.569 align:start position:0% rounds of interactions and especially 00:12:47.569 --> 00:12:51.829 align:start position:0% rounds of interactions and especially the<00:12:48.569> verifier<00:12:49.049> is<00:12:49.319> a<00:12:50.389> person<00:12:51.389> separate<00:12:51.689> from 00:12:51.829 --> 00:12:51.839 align:start position:0% the verifier is a person separate from 00:12:51.839 --> 00:12:53.360 align:start position:0% the verifier is a person separate from the<00:12:51.929> block<00:12:52.110> chain<00:12:52.259> that<00:12:52.410> has<00:12:52.559> to<00:12:52.799> use<00:12:53.160> their 00:12:53.360 --> 00:12:53.370 align:start position:0% the block chain that has to use their 00:12:53.370 --> 00:12:55.639 align:start position:0% the block chain that has to use their own<00:12:53.429> randomness<00:12:54.360> and<00:12:54.660> that<00:12:55.019> would<00:12:55.290> also<00:12:55.439> not 00:12:55.639 --> 00:12:55.649 align:start position:0% own randomness and that would also not 00:12:55.649 --> 00:12:57.829 align:start position:0% own randomness and that would also not work<00:12:55.860> in<00:12:56.160> the<00:12:56.279> blockchain<00:12:56.569> context<00:12:57.569> so<00:12:57.720> we 00:12:57.829 --> 00:12:57.839 align:start position:0% work in the blockchain context so we 00:12:57.839 --> 00:12:59.059 align:start position:0% work in the blockchain context so we have<00:12:57.959> to<00:12:58.079> reduce<00:12:58.410> the<00:12:58.709> rounds<00:12:58.949> of<00:12:59.009> that 00:12:59.059 --> 00:12:59.069 align:start position:0% have to reduce the rounds of that 00:12:59.069 --> 00:13:01.309 align:start position:0% have to reduce the rounds of that interaction<00:12:59.429> and<00:12:59.730> at<00:13:00.509> the<00:13:00.660> best<00:13:00.809> reduce<00:13:01.139> it<00:13:01.290> to 00:13:01.309 --> 00:13:01.319 align:start position:0% interaction and at the best reduce it to 00:13:01.319 --> 00:13:04.789 align:start position:0% interaction and at the best reduce it to only<00:13:01.499> one<00:13:01.769> and<00:13:02.749> the<00:13:03.749> reason<00:13:04.110> why<00:13:04.230> we<00:13:04.439> have<00:13:04.589> this 00:13:04.789 --> 00:13:04.799 align:start position:0% only one and the reason why we have this 00:13:04.799 --> 00:13:07.090 align:start position:0% only one and the reason why we have this many<00:13:05.009> interactions<00:13:05.519> is<00:13:05.819> that<00:13:06.029> because<00:13:06.389> a 00:13:07.090 --> 00:13:07.100 align:start position:0% many interactions is that because a 00:13:07.100 --> 00:13:09.619 align:start position:0% many interactions is that because a single<00:13:08.100> tiny<00:13:08.459> error<00:13:08.730> could<00:13:08.999> be<00:13:09.149> hidden<00:13:09.329> in<00:13:09.480> any 00:13:09.619 --> 00:13:09.629 align:start position:0% single tiny error could be hidden in any 00:13:09.629 --> 00:13:12.259 align:start position:0% single tiny error could be hidden in any Cell<00:13:09.929> of<00:13:10.079> this<00:13:10.230> Sudoku<00:13:10.980> board<00:13:11.160> and<00:13:11.399> if<00:13:12.089> there 00:13:12.259 --> 00:13:12.269 align:start position:0% Cell of this Sudoku board and if there 00:13:12.269 --> 00:13:13.429 align:start position:0% Cell of this Sudoku board and if there is<00:13:12.389> a<00:13:12.420> single<00:13:12.689> error<00:13:12.959> then<00:13:13.199> the<00:13:13.290> whole 00:13:13.429 --> 00:13:13.439 align:start position:0% is a single error then the whole 00:13:13.439 --> 00:13:14.489 align:start position:0% is a single error then the whole solution<00:13:13.709> is<00:13:13.920> wrong<00:13:14.129> so<00:13:14.309> we 00:13:14.489 --> 00:13:14.499 align:start position:0% solution is wrong so we 00:13:14.499 --> 00:13:16.799 align:start position:0% solution is wrong so we have<00:13:14.589> to<00:13:14.679> do<00:13:14.829> these<00:13:15.159> many<00:13:15.879> rounds<00:13:16.329> to<00:13:16.479> increase 00:13:16.799 --> 00:13:16.809 align:start position:0% have to do these many rounds to increase 00:13:16.809 --> 00:13:18.509 align:start position:0% have to do these many rounds to increase the<00:13:17.139> likelihood<00:13:17.289> of<00:13:17.619> actually<00:13:18.009> finding<00:13:18.219> this 00:13:18.509 --> 00:13:18.519 align:start position:0% the likelihood of actually finding this 00:13:18.519 --> 00:13:20.489 align:start position:0% the likelihood of actually finding this this<00:13:18.849> tiny<00:13:19.119> error<00:13:19.329> that<00:13:19.989> is<00:13:20.079> hidden<00:13:20.259> in<00:13:20.439> a 00:13:20.489 --> 00:13:20.499 align:start position:0% this tiny error that is hidden in a 00:13:20.499 --> 00:13:25.289 align:start position:0% this tiny error that is hidden in a single<00:13:20.799> cell<00:13:21.719> but<00:13:22.719> if<00:13:23.229> we<00:13:23.439> take<00:13:23.649> a<00:13:24.299> different 00:13:25.289 --> 00:13:25.299 align:start position:0% single cell but if we take a different 00:13:25.299 --> 00:13:29.069 align:start position:0% single cell but if we take a different problem<00:13:25.809> that<00:13:26.349> does<00:13:26.559> not<00:13:26.739> have<00:13:26.979> this<00:13:27.219> this<00:13:28.149> if 00:13:29.069 --> 00:13:29.079 align:start position:0% problem that does not have this this if 00:13:29.079 --> 00:13:31.979 align:start position:0% problem that does not have this this if we<00:13:29.199> have<00:13:29.319> a<00:13:29.349> take<00:13:30.339> a<00:13:30.599> different<00:13:31.599> game<00:13:31.749> that 00:13:31.979 --> 00:13:31.989 align:start position:0% we have a take a different game that 00:13:31.989 --> 00:13:37.349 align:start position:0% we have a take a different game that doesn't<00:13:32.229> have<00:13:32.349> this<00:13:32.499> this<00:13:32.859> problem<00:13:33.549> then<00:13:36.359> okay 00:13:37.349 --> 00:13:37.359 align:start position:0% doesn't have this this problem then okay 00:13:37.359 --> 00:13:41.909 align:start position:0% doesn't have this this problem then okay let<00:13:37.659> me<00:13:37.749> stop<00:13:40.139> so<00:13:41.139> we<00:13:41.289> have<00:13:41.409> to<00:13:41.529> find<00:13:41.799> a 00:13:41.909 --> 00:13:41.919 align:start position:0% let me stop so we have to find a 00:13:41.919 --> 00:13:43.049 align:start position:0% let me stop so we have to find a different<00:13:42.219> game<00:13:42.339> that<00:13:42.519> doesn't<00:13:42.789> have<00:13:42.909> this 00:13:43.049 --> 00:13:43.059 align:start position:0% different game that doesn't have this 00:13:43.059 --> 00:13:45.899 align:start position:0% different game that doesn't have this problem<00:13:43.629> so<00:13:43.809> we<00:13:43.899> have<00:13:43.929> to<00:13:44.049> find<00:13:44.319> a<00:13:44.679> a<00:13:45.069> setting 00:13:45.899 --> 00:13:45.909 align:start position:0% problem so we have to find a a setting 00:13:45.909 --> 00:13:48.599 align:start position:0% problem so we have to find a a setting where<00:13:46.479> a<00:13:46.809> single<00:13:47.199> error<00:13:47.379> is<00:13:47.709> visible<00:13:48.189> almost 00:13:48.599 --> 00:13:48.609 align:start position:0% where a single error is visible almost 00:13:48.609 --> 00:13:52.859 align:start position:0% where a single error is visible almost everywhere<00:13:48.969> and<00:13:51.539> polynomials<00:13:52.539> have<00:13:52.659> this 00:13:52.859 --> 00:13:52.869 align:start position:0% everywhere and polynomials have this 00:13:52.869 --> 00:13:56.459 align:start position:0% everywhere and polynomials have this property<00:13:53.289> so<00:13:54.119> if<00:13:55.119> you<00:13:55.359> change<00:13:55.809> a<00:13:55.959> polynomial 00:13:56.459 --> 00:13:56.469 align:start position:0% property so if you change a polynomial 00:13:56.469 --> 00:13:58.529 align:start position:0% property so if you change a polynomial in<00:13:56.529> the<00:13:56.619> time<00:13:56.799> in<00:13:57.009> a<00:13:57.309> single<00:13:57.639> place<00:13:57.819> then<00:13:58.239> this 00:13:58.529 --> 00:13:58.539 align:start position:0% in the time in a single place then this 00:13:58.539 --> 00:14:00.809 align:start position:0% in the time in a single place then this will<00:13:58.749> usually<00:13:59.469> change<00:13:59.889> the<00:14:00.219> full<00:14:00.399> polynomial 00:14:00.809 --> 00:14:00.819 align:start position:0% will usually change the full polynomial 00:14:00.819 --> 00:14:03.299 align:start position:0% will usually change the full polynomial so<00:14:00.909> take<00:14:01.059> a<00:14:01.089> look<00:14:01.269> at<00:14:01.389> this<00:14:02.349> polynomial<00:14:02.979> here 00:14:03.299 --> 00:14:03.309 align:start position:0% so take a look at this polynomial here 00:14:03.309 --> 00:14:06.989 align:start position:0% so take a look at this polynomial here this<00:14:03.789> is<00:14:03.909> the<00:14:04.059> graph<00:14:04.089> and<00:14:05.399> now<00:14:06.399> let's<00:14:06.759> change 00:14:06.989 --> 00:14:06.999 align:start position:0% this is the graph and now let's change 00:14:06.999 --> 00:14:10.829 align:start position:0% this is the graph and now let's change this<00:14:07.329> to<00:14:07.629> X<00:14:08.229> to<00:14:08.439> the<00:14:08.559> 4<00:14:08.829> into<00:14:09.519> a<00:14:09.549> 1<00:14:10.119> X<00:14:10.329> to<00:14:10.479> the<00:14:10.509> 4 00:14:10.829 --> 00:14:10.839 align:start position:0% this to X to the 4 into a 1 X to the 4 00:14:10.839 --> 00:14:13.139 align:start position:0% this to X to the 4 into a 1 X to the 4 and<00:14:11.079> we<00:14:11.949> will<00:14:12.069> get<00:14:12.189> this<00:14:12.339> graph<00:14:12.609> here<00:14:12.849> and<00:14:13.029> you 00:14:13.139 --> 00:14:13.149 align:start position:0% and we will get this graph here and you 00:14:13.149 --> 00:14:16.919 align:start position:0% and we will get this graph here and you see<00:14:13.359> it's<00:14:13.859> different<00:14:14.859> at<00:14:15.669> almost<00:14:16.059> every<00:14:16.659> point 00:14:16.919 --> 00:14:16.929 align:start position:0% see it's different at almost every point 00:14:16.929 --> 00:14:21.960 align:start position:0% see it's different at almost every point and<00:14:19.259> there's<00:14:20.259> of<00:14:20.409> course<00:14:20.439> a<00:14:20.919> theorem<00:14:21.609> that 00:14:21.960 --> 00:14:21.970 align:start position:0% and there's of course a theorem that 00:14:21.970 --> 00:14:23.729 align:start position:0% and there's of course a theorem that says<00:14:22.029> that<00:14:22.629> two<00:14:22.899> different<00:14:23.019> polynomials<00:14:23.439> of 00:14:23.729 --> 00:14:23.739 align:start position:0% says that two different polynomials of 00:14:23.739 --> 00:14:26.909 align:start position:0% says that two different polynomials of degree<00:14:23.799> up<00:14:24.429> to<00:14:24.579> n<00:14:24.729> can<00:14:25.239> coincide<00:14:26.079> in<00:14:26.409> at<00:14:26.739> most 00:14:26.909 --> 00:14:26.919 align:start position:0% degree up to n can coincide in at most 00:14:26.919 --> 00:14:35.779 align:start position:0% degree up to n can coincide in at most endpoints<00:14:27.669> so<00:14:29.399> and<00:14:30.809> of<00:14:31.809> course<00:14:32.819> this<00:14:33.839> that<00:14:34.839> we 00:14:35.779 --> 00:14:35.789 align:start position:0% endpoints so and of course this that we 00:14:35.789 --> 00:14:39.239 align:start position:0% endpoints so and of course this that we we<00:14:36.789> take<00:14:36.999> polynomials<00:14:37.599> that<00:14:37.659> are<00:14:37.989> low<00:14:38.769> degree 00:14:39.239 --> 00:14:39.249 align:start position:0% we take polynomials that are low degree 00:14:39.249 --> 00:14:42.299 align:start position:0% we take polynomials that are low degree I<00:14:39.279> mean<00:14:39.609> it<00:14:39.729> can<00:14:39.939> still<00:14:40.239> be<00:14:40.419> quite<00:14:41.019> high<00:14:41.829> degree 00:14:42.299 --> 00:14:42.309 align:start position:0% I mean it can still be quite high degree 00:14:42.309 --> 00:14:44.729 align:start position:0% I mean it can still be quite high degree but<00:14:42.579> the<00:14:43.269> degree<00:14:43.479> is<00:14:43.629> usually<00:14:43.749> tiny<00:14:44.199> compared 00:14:44.729 --> 00:14:44.739 align:start position:0% but the degree is usually tiny compared 00:14:44.739 --> 00:14:47.399 align:start position:0% but the degree is usually tiny compared to<00:14:44.799> the<00:14:45.299> number<00:14:46.299> of<00:14:46.329> points<00:14:46.569> we<00:14:46.779> can<00:14:46.899> evaluate 00:14:47.399 --> 00:14:47.409 align:start position:0% to the number of points we can evaluate 00:14:47.409 --> 00:14:53.069 align:start position:0% to the number of points we can evaluate the<00:14:47.769> polynomial<00:14:48.009> at<00:14:49.349> so<00:14:50.349> and<00:14:51.689> with<00:14:52.689> that<00:14:52.869> we 00:14:53.069 --> 00:14:53.079 align:start position:0% the polynomial at so and with that we 00:14:53.079 --> 00:14:56.329 align:start position:0% the polynomial at so and with that we get<00:14:53.199> the<00:14:53.409> we<00:14:53.769> get<00:14:53.919> the<00:14:54.099> the<00:14:55.089> error<00:14:55.720> probability 00:14:56.329 --> 00:14:56.339 align:start position:0% get the we get the the error probability 00:14:56.339 --> 00:14:59.719 align:start position:0% get the we get the the error probability to<00:14:57.339> a<00:14:57.369> point<00:14:57.609> where<00:14:57.789> it's<00:14:57.909> negligible<00:14:58.359> okay 00:14:59.719 --> 00:14:59.729 align:start position:0% to a point where it's negligible okay 00:14:59.729 --> 00:15:03.119 align:start position:0% to a point where it's negligible okay how<00:15:00.729> do<00:15:00.789> stocks<00:15:01.179> now<00:15:01.529> work<00:15:02.529> how<00:15:02.739> do<00:15:02.799> they<00:15:02.949> use 00:15:03.119 --> 00:15:03.129 align:start position:0% how do stocks now work how do they use 00:15:03.129 --> 00:15:09.389 align:start position:0% how do stocks now work how do they use these<00:15:03.399> polynomials<00:15:05.339> we<00:15:06.339> use<00:15:07.979> yeah<00:15:08.979> special 00:15:09.389 --> 00:15:09.399 align:start position:0% these polynomials we use yeah special 00:15:09.399 --> 00:15:12.989 align:start position:0% these polynomials we use yeah special polynomial<00:15:09.579> equations<00:15:11.099> where<00:15:12.099> a<00:15:12.549> proven 00:15:12.989 --> 00:15:12.999 align:start position:0% polynomial equations where a proven 00:15:12.999 --> 00:15:15.599 align:start position:0% polynomial equations where a proven knows<00:15:13.209> a<00:15:13.599> secret<00:15:13.769> polynomial<00:15:14.769> W<00:15:15.219> such<00:15:15.579> that 00:15:15.599 --> 00:15:15.609 align:start position:0% knows a secret polynomial W such that 00:15:15.609 --> 00:15:19.319 align:start position:0% knows a secret polynomial W such that for<00:15:16.089> all<00:15:16.149> X<00:15:16.599> a<00:15:16.959> of<00:15:17.319> x<00:15:17.499> times<00:15:17.619> W<00:15:18.279> of<00:15:18.549> x<00:15:18.729> equals<00:15:19.269> B 00:15:19.319 --> 00:15:19.329 align:start position:0% for all X a of x times W of x equals B 00:15:19.329 --> 00:15:22.710 align:start position:0% for all X a of x times W of x equals B of<00:15:19.599> X<00:15:19.809> times<00:15:20.229> G<00:15:20.529> of<00:15:20.739> X<00:15:20.979> this<00:15:21.729> is<00:15:21.909> simplification 00:15:22.710 --> 00:15:22.720 align:start position:0% of X times G of X this is simplification 00:15:22.720 --> 00:15:25.109 align:start position:0% of X times G of X this is simplification usually<00:15:23.470> you<00:15:23.829> have<00:15:23.979> multiple<00:15:24.489> polynomials 00:15:25.109 --> 00:15:25.119 align:start position:0% usually you have multiple polynomials 00:15:25.119 --> 00:15:27.560 align:start position:0% usually you have multiple polynomials and<00:15:25.389> you<00:15:25.509> have<00:15:25.659> to<00:15:25.839> have<00:15:26.169> a<00:15:26.259> way<00:15:26.439> to<00:15:26.470> choose 00:15:27.560 --> 00:15:27.570 align:start position:0% and you have to have a way to choose 00:15:27.570 --> 00:15:29.390 align:start position:0% and you have to have a way to choose selection<00:15:28.260> of<00:15:28.410> polynomials<00:15:28.830> according<00:15:29.310> to 00:15:29.390 --> 00:15:29.400 align:start position:0% selection of polynomials according to 00:15:29.400 --> 00:15:30.710 align:start position:0% selection of polynomials according to some<00:15:29.550> rules<00:15:29.700> but<00:15:30.000> I<00:15:30.150> would<00:15:30.300> like<00:15:30.390> to<00:15:30.480> keep<00:15:30.600> it 00:15:30.710 --> 00:15:30.720 align:start position:0% some rules but I would like to keep it 00:15:30.720 --> 00:15:32.630 align:start position:0% some rules but I would like to keep it simple<00:15:30.750> here<00:15:31.560> and<00:15:31.830> just<00:15:32.130> take<00:15:32.370> a<00:15:32.400> single 00:15:32.630 --> 00:15:32.640 align:start position:0% simple here and just take a single 00:15:32.640 --> 00:15:38.680 align:start position:0% simple here and just take a single polynomial<00:15:35.210> so<00:15:36.210> W<00:15:36.990> is<00:15:37.260> the<00:15:37.530> secret<00:15:37.860> solution 00:15:38.680 --> 00:15:38.690 align:start position:0% polynomial so W is the secret solution 00:15:38.690 --> 00:15:41.240 align:start position:0% polynomial so W is the secret solution that<00:15:39.690> is<00:15:39.780> only<00:15:39.930> known<00:15:40.110> to<00:15:40.260> the<00:15:40.470> to<00:15:40.800> the<00:15:40.890> prover 00:15:41.240 --> 00:15:41.250 align:start position:0% that is only known to the to the prover 00:15:41.250 --> 00:15:42.470 align:start position:0% that is only known to the to the prover and<00:15:41.460> the<00:15:41.580> prover<00:15:41.790> wants<00:15:42.000> to<00:15:42.060> convince<00:15:42.270> the 00:15:42.470 --> 00:15:42.480 align:start position:0% and the prover wants to convince the 00:15:42.480 --> 00:15:45.920 align:start position:0% and the prover wants to convince the verifier<00:15:42.960> that<00:15:43.590> she<00:15:43.830> knows<00:15:44.010> this<00:15:44.280> solution<00:15:44.930> oh 00:15:45.920 --> 00:15:45.930 align:start position:0% verifier that she knows this solution oh 00:15:45.930 --> 00:15:50.060 align:start position:0% verifier that she knows this solution oh yeah<00:15:47.480> so<00:15:48.480> and<00:15:48.870> what<00:15:49.260> happens<00:15:49.500> now<00:15:49.650> is<00:15:49.770> that<00:15:49.800> the 00:15:50.060 --> 00:15:50.070 align:start position:0% yeah so and what happens now is that the 00:15:50.070 --> 00:15:52.690 align:start position:0% yeah so and what happens now is that the verify<00:15:50.400> chooses<00:15:50.790> a<00:15:50.850> secret<00:15:51.180> evaluation<00:15:51.780> point 00:15:52.690 --> 00:15:52.700 align:start position:0% verify chooses a secret evaluation point 00:15:52.700 --> 00:15:55.480 align:start position:0% verify chooses a secret evaluation point to<00:15:53.700> check<00:15:53.880> that<00:15:54.090> these<00:15:54.210> polynomials<00:15:54.570> are 00:15:55.480 --> 00:15:55.490 align:start position:0% to check that these polynomials are 00:15:55.490 --> 00:15:57.500 align:start position:0% to check that these polynomials are equal<00:15:56.490> that<00:15:56.520> this<00:15:56.730> polynomial<00:15:57.180> equation 00:15:57.500 --> 00:15:57.510 align:start position:0% equal that this polynomial equation 00:15:57.510 --> 00:16:00.950 align:start position:0% equal that this polynomial equation holds<00:15:57.690> and<00:15:57.980> asks<00:15:58.980> the<00:15:59.220> prover<00:16:00.180> to<00:16:00.330> evaluate 00:16:00.950 --> 00:16:00.960 align:start position:0% holds and asks the prover to evaluate 00:16:00.960 --> 00:16:03.650 align:start position:0% holds and asks the prover to evaluate the<00:16:01.200> secret<00:16:02.040> polynomials<00:16:02.730> and<00:16:02.970> you<00:16:03.510> already 00:16:03.650 --> 00:16:03.660 align:start position:0% the secret polynomials and you already 00:16:03.660 --> 00:16:06.080 align:start position:0% the secret polynomials and you already see<00:16:04.020> that<00:16:04.290> this<00:16:04.530> doesn't<00:16:04.980> really<00:16:05.310> work<00:16:05.520> so<00:16:05.550> the 00:16:06.080 --> 00:16:06.090 align:start position:0% see that this doesn't really work so the 00:16:06.090 --> 00:16:08.750 align:start position:0% see that this doesn't really work so the verify<00:16:06.510> a<00:16:06.540> secret<00:16:07.080> point<00:16:07.320> the<00:16:08.130> prover<00:16:08.580> has<00:16:08.610> a 00:16:08.750 --> 00:16:08.760 align:start position:0% verify a secret point the prover has a 00:16:08.760 --> 00:16:10.970 align:start position:0% verify a secret point the prover has a secret<00:16:09.060> polynomial<00:16:09.690> so<00:16:09.960> and<00:16:10.440> they<00:16:10.620> both<00:16:10.800> don't 00:16:10.970 --> 00:16:10.980 align:start position:0% secret polynomial so and they both don't 00:16:10.980 --> 00:16:15.620 align:start position:0% secret polynomial so and they both don't want<00:16:11.130> to<00:16:11.400> reveal<00:16:12.230> their<00:16:13.230> secrets<00:16:13.650> so<00:16:14.510> we<00:16:15.510> have 00:16:15.620 --> 00:16:15.630 align:start position:0% want to reveal their secrets so we have 00:16:15.630 --> 00:16:17.270 align:start position:0% want to reveal their secrets so we have to<00:16:15.750> add<00:16:15.870> another<00:16:16.020> tool<00:16:16.470> and<00:16:16.800> this<00:16:17.010> is 00:16:17.270 --> 00:16:17.280 align:start position:0% to add another tool and this is 00:16:17.280 --> 00:16:21.830 align:start position:0% to add another tool and this is homomorphic<00:16:18.000> encryption<00:16:20.840> homomorphic 00:16:21.830 --> 00:16:21.840 align:start position:0% homomorphic encryption homomorphic 00:16:21.840 --> 00:16:24.230 align:start position:0% homomorphic encryption homomorphic encryption<00:16:21.960> yeah<00:16:22.950> and<00:16:23.100> then<00:16:23.250> so<00:16:23.580> they<00:16:23.910> use<00:16:24.060> for 00:16:24.230 --> 00:16:24.240 align:start position:0% encryption yeah and then so they use for 00:16:24.240 --> 00:16:25.550 align:start position:0% encryption yeah and then so they use for morphing<00:16:24.480> encryption<00:16:24.840> some<00:16:24.990> magic<00:16:25.230> happens 00:16:25.550 --> 00:16:25.560 align:start position:0% morphing encryption some magic happens 00:16:25.560 --> 00:16:27.140 align:start position:0% morphing encryption some magic happens and<00:16:25.650> then<00:16:26.130> the<00:16:26.250> verify<00:16:26.580> can<00:16:26.790> check<00:16:26.970> whether 00:16:27.140 --> 00:16:27.150 align:start position:0% and then the verify can check whether 00:16:27.150 --> 00:16:29.660 align:start position:0% and then the verify can check whether the<00:16:27.270> two<00:16:27.510> polynomials<00:16:27.930> are<00:16:28.290> equal<00:16:28.530> or<00:16:28.620> not<00:16:28.740> so 00:16:29.660 --> 00:16:29.670 align:start position:0% the two polynomials are equal or not so 00:16:29.670 --> 00:16:33.320 align:start position:0% the two polynomials are equal or not so what<00:16:30.240> is<00:16:30.330> homomorphic<00:16:30.750> encryption<00:16:31.550> it<00:16:32.550> allows 00:16:33.320 --> 00:16:33.330 align:start position:0% what is homomorphic encryption it allows 00:16:33.330 --> 00:16:36.260 align:start position:0% what is homomorphic encryption it allows it<00:16:33.870> allows<00:16:34.140> you<00:16:34.440> to<00:16:34.650> perform<00:16:35.030> computations<00:16:36.030> on 00:16:36.260 --> 00:16:36.270 align:start position:0% it allows you to perform computations on 00:16:36.270 --> 00:16:38.450 align:start position:0% it allows you to perform computations on encrypted<00:16:36.810> data<00:16:36.990> so<00:16:37.260> you<00:16:37.350> have<00:16:37.560> a<00:16:37.770> known 00:16:38.450 --> 00:16:38.460 align:start position:0% encrypted data so you have a known 00:16:38.460 --> 00:16:40.610 align:start position:0% encrypted data so you have a known function<00:16:39.210> and<00:16:39.510> own<00:16:39.600> program<00:16:40.050> but<00:16:40.350> you<00:16:40.440> don't 00:16:40.610 --> 00:16:40.620 align:start position:0% function and own program but you don't 00:16:40.620 --> 00:16:42.020 align:start position:0% function and own program but you don't know<00:16:40.740> the<00:16:40.920> inputs<00:16:41.220> they<00:16:41.370> are<00:16:41.460> encrypted<00:16:41.820> some 00:16:42.020 --> 00:16:42.030 align:start position:0% know the inputs they are encrypted some 00:16:42.030 --> 00:16:44.390 align:start position:0% know the inputs they are encrypted some way<00:16:42.180> you<00:16:42.660> perform<00:16:43.080> the<00:16:43.200> computation<00:16:43.830> and<00:16:43.920> the 00:16:44.390 --> 00:16:44.400 align:start position:0% way you perform the computation and the 00:16:44.400 --> 00:16:47.770 align:start position:0% way you perform the computation and the result<00:16:44.760> is<00:16:44.940> the<00:16:45.270> encrypted<00:16:46.050> version<00:16:46.350> of<00:16:46.560> the 00:16:47.770 --> 00:16:47.780 align:start position:0% result is the encrypted version of the 00:16:47.780 --> 00:16:52.670 align:start position:0% result is the encrypted version of the of<00:16:48.780> the<00:16:48.990> result<00:16:50.660> this<00:16:51.660> does<00:16:51.900> not<00:16:52.050> yet<00:16:52.230> work<00:16:52.470> for 00:16:52.670 --> 00:16:52.680 align:start position:0% of the result this does not yet work for 00:16:52.680 --> 00:16:55.400 align:start position:0% of the result this does not yet work for arbitrary<00:16:53.010> computations<00:16:53.790> but<00:16:54.210> so<00:16:54.960> there<00:16:55.260> is 00:16:55.400 --> 00:16:55.410 align:start position:0% arbitrary computations but so there is 00:16:55.410 --> 00:16:57.200 align:start position:0% arbitrary computations but so there is theoretical<00:16:56.190> work<00:16:56.340> that<00:16:56.490> allows<00:16:56.700> that<00:16:57.000> but 00:16:57.200 --> 00:16:57.210 align:start position:0% theoretical work that allows that but 00:16:57.210 --> 00:17:00.290 align:start position:0% theoretical work that allows that but it's<00:16:57.330> not<00:16:57.480> really<00:16:57.540> practical<00:16:57.990> yet<00:16:58.700> but<00:16:59.700> we 00:17:00.290 --> 00:17:00.300 align:start position:0% it's not really practical yet but we 00:17:00.300 --> 00:17:03.890 align:start position:0% it's not really practical yet but we have<00:17:00.510> a<00:17:00.960> tool<00:17:01.410> called<00:17:01.440> parings<00:17:02.370> which<00:17:02.880> can<00:17:03.810> do 00:17:03.890 --> 00:17:03.900 align:start position:0% have a tool called parings which can do 00:17:03.900 --> 00:17:05.540 align:start position:0% have a tool called parings which can do it<00:17:04.020> up<00:17:04.170> to<00:17:04.199> a<00:17:04.350> certain<00:17:04.680> point<00:17:04.920> and<00:17:05.070> this<00:17:05.220> point 00:17:05.540 --> 00:17:05.550 align:start position:0% it up to a certain point and this point 00:17:05.550 --> 00:17:07.699 align:start position:0% it up to a certain point and this point is<00:17:05.730> arbitrary<00:17:06.390> sums<00:17:06.689> and<00:17:06.959> a<00:17:07.260> single 00:17:07.699 --> 00:17:07.709 align:start position:0% is arbitrary sums and a single 00:17:07.709 --> 00:17:12.800 align:start position:0% is arbitrary sums and a single multiplication<00:17:08.490> at<00:17:08.640> the<00:17:08.790> end<00:17:10.610> so<00:17:11.610> a<00:17:12.030> of<00:17:12.630> x 00:17:12.800 --> 00:17:12.810 align:start position:0% multiplication at the end so a of x 00:17:12.810 --> 00:17:16.569 align:start position:0% multiplication at the end so a of x times<00:17:13.110> W<00:17:13.560> of<00:17:13.829> X<00:17:13.980> is<00:17:14.220> a<00:17:14.250> single<00:17:14.780> multiplication 00:17:16.569 --> 00:17:16.579 align:start position:0% times W of X is a single multiplication 00:17:16.579 --> 00:17:20.990 align:start position:0% times W of X is a single multiplication so<00:17:17.579> it<00:17:17.699> works<00:17:18.390> fine<00:17:19.050> until<00:17:19.949> you<00:17:20.189> take<00:17:20.610> a<00:17:20.640> closer 00:17:20.990 --> 00:17:21.000 align:start position:0% so it works fine until you take a closer 00:17:21.000 --> 00:17:23.870 align:start position:0% so it works fine until you take a closer look<00:17:21.150> and<00:17:21.449> see<00:17:21.510> that<00:17:21.930> we<00:17:22.439> actually<00:17:22.470> have<00:17:22.880> more 00:17:23.870 --> 00:17:23.880 align:start position:0% look and see that we actually have more 00:17:23.880 --> 00:17:26.150 align:start position:0% look and see that we actually have more than<00:17:24.000> one<00:17:24.209> multiplication<00:17:24.660> here<00:17:25.110> because<00:17:25.470> X 00:17:26.150 --> 00:17:26.160 align:start position:0% than one multiplication here because X 00:17:26.160 --> 00:17:28.460 align:start position:0% than one multiplication here because X is<00:17:26.610> taken<00:17:27.060> to<00:17:27.270> certain<00:17:27.630> powers<00:17:27.990> inside<00:17:28.320> the 00:17:28.460 --> 00:17:28.470 align:start position:0% is taken to certain powers inside the 00:17:28.470 --> 00:17:33.020 align:start position:0% is taken to certain powers inside the polynomial<00:17:30.080> but<00:17:31.220> this<00:17:32.220> can<00:17:32.490> be<00:17:32.640> worked<00:17:32.880> around 00:17:33.020 --> 00:17:33.030 align:start position:0% polynomial but this can be worked around 00:17:33.030 --> 00:17:37.730 align:start position:0% polynomial but this can be worked around by<00:17:34.970> taking<00:17:35.970> a<00:17:36.060> look<00:17:36.240> at<00:17:36.390> this<00:17:36.570> separate<00:17:37.440> for 00:17:37.730 --> 00:17:37.740 align:start position:0% by taking a look at this separate for 00:17:37.740 --> 00:17:41.340 align:start position:0% by taking a look at this separate for each<00:17:37.920> power<00:17:38.580> of<00:17:38.850> X 00:17:41.340 --> 00:17:41.350 align:start position:0% 00:17:41.350 --> 00:17:45.760 align:start position:0% yeah<00:17:42.350> so<00:17:42.530> you<00:17:42.590> encrypt<00:17:42.919> X<00:17:44.289> so<00:17:45.289> you<00:17:45.350> take<00:17:45.559> X<00:17:45.710> to 00:17:45.760 --> 00:17:45.770 align:start position:0% yeah so you encrypt X so you take X to 00:17:45.770 --> 00:17:47.980 align:start position:0% yeah so you encrypt X so you take X to the<00:17:45.919> K<00:17:46.100> and<00:17:46.400> encrypt<00:17:46.730> that<00:17:46.789> and<00:17:47.120> then<00:17:47.419> perform 00:17:47.980 --> 00:17:47.990 align:start position:0% the K and encrypt that and then perform 00:17:47.990 --> 00:17:49.510 align:start position:0% the K and encrypt that and then perform the<00:17:48.020> addition<00:17:48.380> inside<00:17:48.890> the<00:17:48.980> polynomial<00:17:49.429> and 00:17:49.510 --> 00:17:49.520 align:start position:0% the addition inside the polynomial and 00:17:49.520 --> 00:17:53.620 align:start position:0% the addition inside the polynomial and the<00:17:49.610> multiplication<00:17:50.299> here<00:17:50.419> at<00:17:50.570> the<00:17:50.659> end<00:17:52.630> yeah 00:17:53.620 --> 00:17:53.630 align:start position:0% the multiplication here at the end yeah 00:17:53.630 --> 00:17:55.000 align:start position:0% the multiplication here at the end yeah and<00:17:53.750> this<00:17:53.840> allows<00:17:54.110> the<00:17:54.230> prover<00:17:54.470> to<00:17:54.559> evaluate 00:17:55.000 --> 00:17:55.010 align:start position:0% and this allows the prover to evaluate 00:17:55.010 --> 00:17:57.779 align:start position:0% and this allows the prover to evaluate the<00:17:55.100> polynomial<00:17:55.280> at<00:17:55.760> a<00:17:55.789> unknown<00:17:56.330> or<00:17:56.840> encrypted 00:17:57.779 --> 00:17:57.789 align:start position:0% the polynomial at a unknown or encrypted 00:17:57.789 --> 00:18:01.390 align:start position:0% the polynomial at a unknown or encrypted point<00:17:58.789> and<00:17:59.090> thus<00:17:59.390> the<00:17:59.809> verifier<00:18:00.380> can<00:18:01.159> check 00:18:01.390 --> 00:18:01.400 align:start position:0% point and thus the verifier can check 00:18:01.400 --> 00:18:05.169 align:start position:0% point and thus the verifier can check the<00:18:03.100> that<00:18:04.100> the<00:18:04.190> polynomials<00:18:04.429> are<00:18:04.730> equal<00:18:04.970> or 00:18:05.169 --> 00:18:05.179 align:start position:0% the that the polynomials are equal or 00:18:05.179 --> 00:18:09.760 align:start position:0% the that the polynomials are equal or whether<00:18:05.419> they<00:18:05.570> are<00:18:05.690> equal<00:18:06.820> okay<00:18:08.620> we<00:18:09.620> now 00:18:09.760 --> 00:18:09.770 align:start position:0% whether they are equal okay we now 00:18:09.770 --> 00:18:11.980 align:start position:0% whether they are equal okay we now reduce<00:18:10.220> this<00:18:10.429> whole<00:18:10.610> thing<00:18:10.909> to<00:18:11.120> a<00:18:11.150> two<00:18:11.299> round 00:18:11.980 --> 00:18:11.990 align:start position:0% reduce this whole thing to a two round 00:18:11.990 --> 00:18:14.919 align:start position:0% reduce this whole thing to a two round protocol<00:18:12.620> they<00:18:13.000> prove<00:18:14.000> a<00:18:14.090> claim<00:18:14.270> something 00:18:14.919 --> 00:18:14.929 align:start position:0% protocol they prove a claim something 00:18:14.929 --> 00:18:16.860 align:start position:0% protocol they prove a claim something the<00:18:15.169> verify<00:18:15.530> chooses<00:18:15.890> a<00:18:15.950> circuit<00:18:16.250> point 00:18:16.860 --> 00:18:16.870 align:start position:0% the verify chooses a circuit point 00:18:16.870 --> 00:18:20.230 align:start position:0% the verify chooses a circuit point prover<00:18:17.870> evaluates<00:18:18.470> the<00:18:18.590> polynomial<00:18:19.240> verifier 00:18:20.230 --> 00:18:20.240 align:start position:0% prover evaluates the polynomial verifier 00:18:20.240 --> 00:18:24.159 align:start position:0% prover evaluates the polynomial verifier checks<00:18:20.570> that<00:18:21.049> they<00:18:21.169> are<00:18:21.289> equal<00:18:22.390> but<00:18:23.390> we<00:18:24.020> would 00:18:24.159 --> 00:18:24.169 align:start position:0% checks that they are equal but we would 00:18:24.169 --> 00:18:25.750 align:start position:0% checks that they are equal but we would like<00:18:24.289> to<00:18:24.409> reduce<00:18:24.530> that<00:18:24.770> even<00:18:25.039> further<00:18:25.370> and 00:18:25.750 --> 00:18:25.760 align:start position:0% like to reduce that even further and 00:18:25.760 --> 00:18:28.659 align:start position:0% like to reduce that even further and here<00:18:26.360> is<00:18:26.510> where<00:18:26.780> this<00:18:27.039> thing<00:18:28.039> called<00:18:28.280> trusted 00:18:28.659 --> 00:18:28.669 align:start position:0% here is where this thing called trusted 00:18:28.669 --> 00:18:32.110 align:start position:0% here is where this thing called trusted setup<00:18:29.000> comes<00:18:29.780> into<00:18:30.049> play<00:18:30.700> the<00:18:31.700> way<00:18:31.820> it<00:18:31.880> works 00:18:32.110 --> 00:18:32.120 align:start position:0% setup comes into play the way it works 00:18:32.120 --> 00:18:38.260 align:start position:0% setup comes into play the way it works is<00:18:32.419> okay<00:18:35.770> sorry<00:18:36.770> I'm<00:18:37.100> out<00:18:37.789> of<00:18:37.850> sync<00:18:38.120> with<00:18:38.150> the 00:18:38.260 --> 00:18:38.270 align:start position:0% is okay sorry I'm out of sync with the 00:18:38.270 --> 00:18:41.770 align:start position:0% is okay sorry I'm out of sync with the slides<00:18:39.789> if<00:18:40.789> you<00:18:40.880> take<00:18:41.090> a<00:18:41.120> look<00:18:41.330> at<00:18:41.419> the<00:18:41.570> the 00:18:41.770 --> 00:18:41.780 align:start position:0% slides if you take a look at the the 00:18:41.780 --> 00:18:45.340 align:start position:0% slides if you take a look at the the procedure<00:18:42.140> here<00:18:42.440> you<00:18:42.620> see<00:18:42.860> that<00:18:44.080> we<00:18:45.080> don't 00:18:45.340 --> 00:18:45.350 align:start position:0% procedure here you see that we don't 00:18:45.350 --> 00:18:47.230 align:start position:0% procedure here you see that we don't really<00:18:45.590> need<00:18:45.860> to<00:18:45.919> go<00:18:46.610> from<00:18:46.850> the<00:18:46.970> encrypted 00:18:47.230 --> 00:18:47.240 align:start position:0% really need to go from the encrypted 00:18:47.240 --> 00:18:49.060 align:start position:0% really need to go from the encrypted form<00:18:47.600> to<00:18:47.750> the<00:18:47.840> decrypted<00:18:48.289> form<00:18:48.530> in<00:18:48.770> the<00:18:48.950> end 00:18:49.060 --> 00:18:49.070 align:start position:0% form to the decrypted form in the end 00:18:49.070 --> 00:18:50.680 align:start position:0% form to the decrypted form in the end again<00:18:49.340> we<00:18:49.520> can<00:18:49.640> just<00:18:49.820> check<00:18:49.970> equality<00:18:50.539> on<00:18:50.659> the 00:18:50.680 --> 00:18:50.690 align:start position:0% again we can just check equality on the 00:18:50.690 --> 00:18:52.539 align:start position:0% again we can just check equality on the encrypted<00:18:51.080> form<00:18:51.409> so<00:18:51.590> if<00:18:51.799> the<00:18:52.280> encrypted 00:18:52.539 --> 00:18:52.549 align:start position:0% encrypted form so if the encrypted 00:18:52.549 --> 00:18:53.860 align:start position:0% encrypted form so if the encrypted version<00:18:52.669> of<00:18:52.940> x<00:18:53.150> equals<00:18:53.510> the<00:18:53.570> encrypted 00:18:53.860 --> 00:18:53.870 align:start position:0% version of x equals the encrypted 00:18:53.870 --> 00:19:02.710 align:start position:0% version of x equals the encrypted version<00:18:54.020> of<00:18:54.289> X<00:18:54.500> then<00:18:54.980> x<00:18:55.309> equals<00:18:55.730> x<00:18:58.720> so<00:19:01.600> what<00:19:02.600> we 00:19:02.710 --> 00:19:02.720 align:start position:0% version of X then x equals x so what we 00:19:02.720 --> 00:19:05.590 align:start position:0% version of X then x equals x so what we actually<00:19:03.130> what<00:19:04.130> we<00:19:04.250> what<00:19:04.850> we<00:19:04.880> don't<00:19:05.270> actually 00:19:05.590 --> 00:19:05.600 align:start position:0% actually what we what we don't actually 00:19:05.600 --> 00:19:09.610 align:start position:0% actually what we what we don't actually need<00:19:06.049> is<00:19:06.380> the<00:19:06.820> is<00:19:07.820> the<00:19:08.179> decrypted<00:19:09.140> version<00:19:09.169> of 00:19:09.610 --> 00:19:09.620 align:start position:0% need is the is the decrypted version of 00:19:09.620 --> 00:19:12.580 align:start position:0% need is the is the decrypted version of X<00:19:09.830> so<00:19:10.070> this<00:19:10.190> initial<00:19:10.460> X<00:19:11.000> that<00:19:11.330> got<00:19:11.590> encrypted 00:19:12.580 --> 00:19:12.590 align:start position:0% X so this initial X that got encrypted 00:19:12.590 --> 00:19:14.890 align:start position:0% X so this initial X that got encrypted then<00:19:12.740> sent<00:19:13.010> to<00:19:13.070> the<00:19:13.130> prover<00:19:13.549> and<00:19:13.730> the<00:19:14.690> proof 00:19:14.890 --> 00:19:14.900 align:start position:0% then sent to the prover and the proof 00:19:14.900 --> 00:19:16.419 align:start position:0% then sent to the prover and the proof evaluates<00:19:15.440> the<00:19:15.559> polynomial<00:19:16.039> we<00:19:16.130> don't<00:19:16.309> need 00:19:16.419 --> 00:19:16.429 align:start position:0% evaluates the polynomial we don't need 00:19:16.429 --> 00:19:18.940 align:start position:0% evaluates the polynomial we don't need this<00:19:16.640> initial<00:19:17.120> version<00:19:17.419> anymore<00:19:18.140> we<00:19:18.770> only 00:19:18.940 --> 00:19:18.950 align:start position:0% this initial version anymore we only 00:19:18.950 --> 00:19:22.930 align:start position:0% this initial version anymore we only need<00:19:19.220> it<00:19:19.340> once<00:19:19.580> to<00:19:20.350> encrypt<00:19:21.350> it<00:19:21.500> and<00:19:21.820> this<00:19:22.820> is 00:19:22.930 --> 00:19:22.940 align:start position:0% need it once to encrypt it and this is 00:19:22.940 --> 00:19:25.390 align:start position:0% need it once to encrypt it and this is what<00:19:23.090> the<00:19:23.299> what<00:19:23.780> the<00:19:23.809> trusted<00:19:24.200> setup<00:19:24.470> does<00:19:25.070> and 00:19:25.390 --> 00:19:25.400 align:start position:0% what the what the trusted setup does and 00:19:25.400 --> 00:19:28.750 align:start position:0% what the what the trusted setup does and especially<00:19:25.909> if<00:19:26.390> nobody<00:19:26.780> knows<00:19:27.049> the<00:19:27.760> non 00:19:28.750 --> 00:19:28.760 align:start position:0% especially if nobody knows the non 00:19:28.760 --> 00:19:31.840 align:start position:0% especially if nobody knows the non encrypted<00:19:29.299> version<00:19:29.510> of<00:19:29.929> X<00:19:30.559> at<00:19:30.830> any<00:19:30.950> point<00:19:31.309> then 00:19:31.840 --> 00:19:31.850 align:start position:0% encrypted version of X at any point then 00:19:31.850 --> 00:19:33.580 align:start position:0% encrypted version of X at any point then we<00:19:32.210> can<00:19:32.360> actually<00:19:32.510> reuse<00:19:32.870> the<00:19:33.289> encrypted 00:19:33.580 --> 00:19:33.590 align:start position:0% we can actually reuse the encrypted 00:19:33.590 --> 00:19:35.620 align:start position:0% we can actually reuse the encrypted version<00:19:33.710> of<00:19:34.039> X<00:19:34.190> all<00:19:34.370> the<00:19:34.400> time<00:19:34.700> we<00:19:35.360> just<00:19:35.390> have 00:19:35.620 --> 00:19:35.630 align:start position:0% version of X all the time we just have 00:19:35.630 --> 00:19:37.360 align:start position:0% version of X all the time we just have to<00:19:35.870> generate<00:19:36.169> it<00:19:36.320> once<00:19:36.500> and<00:19:36.710> this<00:19:36.860> is<00:19:37.010> exactly 00:19:37.360 --> 00:19:37.370 align:start position:0% to generate it once and this is exactly 00:19:37.370 --> 00:19:41.830 align:start position:0% to generate it once and this is exactly what<00:19:37.580> the<00:19:38.350> trusted<00:19:39.350> setup<00:19:39.620> does<00:19:40.450> we<00:19:41.450> generate 00:19:41.830 --> 00:19:41.840 align:start position:0% what the trusted setup does we generate 00:19:41.840 --> 00:19:44.260 align:start position:0% what the trusted setup does we generate an<00:19:42.049> encrypted<00:19:42.409> version<00:19:42.770> of<00:19:43.340> X<00:19:43.520> in<00:19:44.090> a 00:19:44.260 --> 00:19:44.270 align:start position:0% an encrypted version of X in a 00:19:44.270 --> 00:19:47.680 align:start position:0% an encrypted version of X in a distributed<00:19:44.630> process<00:19:45.789> in<00:19:46.789> a<00:19:46.909> simplified<00:19:47.240> way 00:19:47.680 --> 00:19:47.690 align:start position:0% distributed process in a simplified way 00:19:47.690 --> 00:19:50.139 align:start position:0% distributed process in a simplified way you<00:19:47.750> can<00:19:48.049> think<00:19:48.320> of<00:19:48.409> that<00:19:48.559> like<00:19:48.770> so<00:19:49.159> and<00:19:49.309> why<00:19:49.760> do 00:19:50.139 --> 00:19:50.149 align:start position:0% you can think of that like so and why do 00:19:50.149 --> 00:19:52.970 align:start position:0% you can think of that like so and why do we<00:19:50.480> want<00:19:50.659> it<00:19:50.780> to<00:19:50.899> be<00:19:50.990> distributed<00:19:51.500> because 00:19:52.970 --> 00:19:52.980 align:start position:0% we want it to be distributed because 00:19:52.980 --> 00:19:55.560 align:start position:0% we want it to be distributed because we<00:19:53.980> want<00:19:54.190> to<00:19:54.280> share<00:19:54.640> the<00:19:54.850> responsibility 00:19:55.560 --> 00:19:55.570 align:start position:0% we want to share the responsibility 00:19:55.570 --> 00:20:00.450 align:start position:0% we want to share the responsibility among<00:19:56.200> multiple<00:19:57.010> persons<00:19:57.850> so<00:19:58.030> we<00:19:58.120> want<00:19:58.330> to<00:19:59.460> if 00:20:00.450 --> 00:20:00.460 align:start position:0% among multiple persons so we want to if 00:20:00.460 --> 00:20:02.490 align:start position:0% among multiple persons so we want to if anyone<00:20:00.820> publishes<00:20:01.630> this<00:20:01.780> decrypted<00:20:02.470> version 00:20:02.490 --> 00:20:02.500 align:start position:0% anyone publishes this decrypted version 00:20:02.500 --> 00:20:05.180 align:start position:0% anyone publishes this decrypted version of<00:20:02.860> X<00:20:03.070> then<00:20:03.370> we<00:20:03.730> can<00:20:03.880> create<00:20:04.090> fake<00:20:04.330> proofs<00:20:04.600> and 00:20:05.180 --> 00:20:05.190 align:start position:0% of X then we can create fake proofs and 00:20:05.190 --> 00:20:10.620 align:start position:0% of X then we can create fake proofs and if<00:20:06.190> we<00:20:06.429> do<00:20:07.000> it<00:20:07.120> in<00:20:07.240> a<00:20:07.299> way<00:20:07.450> that<00:20:08.309> the<00:20:09.630> encrypted 00:20:10.620 --> 00:20:10.630 align:start position:0% if we do it in a way that the encrypted 00:20:10.630 --> 00:20:13.850 align:start position:0% if we do it in a way that the encrypted version<00:20:10.780> of<00:20:11.080> X<00:20:11.320> is<00:20:11.559> a<00:20:11.850> combined<00:20:12.850> version<00:20:13.120> of 00:20:13.850 --> 00:20:13.860 align:start position:0% version of X is a combined version of 00:20:13.860 --> 00:20:16.770 align:start position:0% version of X is a combined version of the<00:20:14.860> the<00:20:15.160> secrets<00:20:15.580> of<00:20:15.700> all<00:20:15.820> participants<00:20:16.419> then 00:20:16.770 --> 00:20:16.780 align:start position:0% the the secrets of all participants then 00:20:16.780 --> 00:20:20.850 align:start position:0% the the secrets of all participants then we<00:20:17.640> require<00:20:18.640> all<00:20:18.940> participants<00:20:19.600> to<00:20:19.860> publish 00:20:20.850 --> 00:20:20.860 align:start position:0% we require all participants to publish 00:20:20.860 --> 00:20:23.039 align:start position:0% we require all participants to publish the<00:20:20.980> secrets<00:20:21.370> in<00:20:21.490> order<00:20:21.669> to<00:20:21.790> for<00:20:22.419> it<00:20:22.480> to<00:20:22.630> be 00:20:23.039 --> 00:20:23.049 align:start position:0% the secrets in order to for it to be 00:20:23.049 --> 00:20:27.090 align:start position:0% the secrets in order to for it to be broken<00:20:23.200> so<00:20:25.230> yeah<00:20:26.230> that's<00:20:26.440> how<00:20:26.500> the<00:20:26.770> trusted 00:20:27.090 --> 00:20:27.100 align:start position:0% broken so yeah that's how the trusted 00:20:27.100 --> 00:20:31.590 align:start position:0% broken so yeah that's how the trusted setup<00:20:27.280> works<00:20:28.919> yes<00:20:29.919> and<00:20:30.100> this<00:20:30.160> is<00:20:30.309> the<00:20:30.340> so<00:20:30.760> these 00:20:31.590 --> 00:20:31.600 align:start position:0% setup works yes and this is the so these 00:20:31.600 --> 00:20:34.799 align:start position:0% setup works yes and this is the so these seek<00:20:32.290> numbers<00:20:32.770> generated<00:20:33.520> by<00:20:33.880> the<00:20:33.940> the 00:20:34.799 --> 00:20:34.809 align:start position:0% seek numbers generated by the the 00:20:34.809 --> 00:20:36.510 align:start position:0% seek numbers generated by the the participants<00:20:35.230> of<00:20:35.470> this<00:20:35.590> setup<00:20:36.040> is<00:20:36.250> also 00:20:36.510 --> 00:20:36.520 align:start position:0% participants of this setup is also 00:20:36.520 --> 00:20:37.890 align:start position:0% participants of this setup is also called<00:20:36.700> the<00:20:36.820> toxic<00:20:37.000> waste<00:20:37.299> because<00:20:37.720> they 00:20:37.890 --> 00:20:37.900 align:start position:0% called the toxic waste because they 00:20:37.900 --> 00:20:40.350 align:start position:0% called the toxic waste because they should<00:20:38.380> not<00:20:38.530> ever<00:20:39.250> publish<00:20:39.820> it<00:20:39.970> they<00:20:40.179> should 00:20:40.350 --> 00:20:40.360 align:start position:0% should not ever publish it they should 00:20:40.360 --> 00:20:43.440 align:start position:0% should not ever publish it they should just<00:20:40.510> destroy<00:20:40.720> it<00:20:41.760> okay<00:20:42.760> do<00:20:43.059> I<00:20:43.120> have<00:20:43.150> time<00:20:43.419> for 00:20:43.440 --> 00:20:43.450 align:start position:0% just destroy it okay do I have time for 00:20:43.450 --> 00:20:46.770 align:start position:0% just destroy it okay do I have time for a<00:20:43.630> quick<00:20:43.840> wrap-up<00:20:45.240> so<00:20:46.240> we<00:20:46.419> have<00:20:46.540> to<00:20:46.630> test 00:20:46.770 --> 00:20:46.780 align:start position:0% a quick wrap-up so we have to test 00:20:46.780 --> 00:20:48.120 align:start position:0% a quick wrap-up so we have to test except<00:20:47.049> that<00:20:47.169> it<00:20:47.260> generates<00:20:47.650> a<00:20:47.799> reusable 00:20:48.120 --> 00:20:48.130 align:start position:0% except that it generates a reusable 00:20:48.130 --> 00:20:51.860 align:start position:0% except that it generates a reusable encrypted<00:20:49.020> evaluation<00:20:50.020> point<00:20:50.260> the<00:20:51.190> prover 00:20:51.860 --> 00:20:51.870 align:start position:0% encrypted evaluation point the prover 00:20:51.870 --> 00:20:54.560 align:start position:0% encrypted evaluation point the prover evaluates<00:20:52.870> the<00:20:53.049> polynomials<00:20:53.350> at<00:20:53.740> this 00:20:54.560 --> 00:20:54.570 align:start position:0% evaluates the polynomials at this 00:20:54.570 --> 00:20:56.640 align:start position:0% evaluates the polynomials at this encrypted<00:20:55.570> point<00:20:55.900> using<00:20:56.080> homomorphic 00:20:56.640 --> 00:20:56.650 align:start position:0% encrypted point using homomorphic 00:20:56.650 --> 00:20:59.430 align:start position:0% encrypted point using homomorphic encryption<00:20:56.890> using<00:20:57.460> pairings<00:20:57.820> then<00:20:58.660> verify 00:20:59.430 --> 00:20:59.440 align:start position:0% encryption using pairings then verify 00:20:59.440 --> 00:21:02.039 align:start position:0% encryption using pairings then verify checks<00:20:59.770> that<00:21:00.000> the<00:21:01.000> numbers<00:21:01.299> are<00:21:01.450> equal<00:21:01.600> in<00:21:01.929> an 00:21:02.039 --> 00:21:02.049 align:start position:0% checks that the numbers are equal in an 00:21:02.049 --> 00:21:03.570 align:start position:0% checks that the numbers are equal in an encrypted<00:21:02.230> form<00:21:02.440> this<00:21:02.740> is<00:21:02.890> all<00:21:03.070> quite 00:21:03.570 --> 00:21:03.580 align:start position:0% encrypted form this is all quite 00:21:03.580 --> 00:21:06.120 align:start position:0% encrypted form this is all quite simplified<00:21:03.940> I<00:21:04.540> hope<00:21:05.020> the<00:21:05.169> next<00:21:05.380> talks<00:21:05.620> will<00:21:05.830> go 00:21:06.120 --> 00:21:06.130 align:start position:0% simplified I hope the next talks will go 00:21:06.130 --> 00:21:09.240 align:start position:0% simplified I hope the next talks will go into<00:21:06.429> depth<00:21:07.030> there<00:21:07.240> more<00:21:07.540> and<00:21:08.100> zero<00:21:09.100> knowledge 00:21:09.240 --> 00:21:09.250 align:start position:0% into depth there more and zero knowledge 00:21:09.250 --> 00:21:11.549 align:start position:0% into depth there more and zero knowledge oh<00:21:09.549> yeah<00:21:09.790> right<00:21:10.030> we<00:21:10.929> didn't<00:21:11.110> talk<00:21:11.200> about<00:21:11.440> your 00:21:11.549 --> 00:21:11.559 align:start position:0% oh yeah right we didn't talk about your 00:21:11.559 --> 00:21:18.330 align:start position:0% oh yeah right we didn't talk about your knowledge<00:21:12.840> this<00:21:13.840> is<00:21:13.990> actually<00:21:14.380> I<00:21:16.410> mean<00:21:17.410> the 00:21:18.330 --> 00:21:18.340 align:start position:0% knowledge this is actually I mean the 00:21:18.340 --> 00:21:20.310 align:start position:0% knowledge this is actually I mean the the<00:21:18.940> interesting<00:21:19.179> point<00:21:19.540> about<00:21:19.660> snarks<00:21:20.140> is 00:21:20.310 --> 00:21:20.320 align:start position:0% the interesting point about snarks is 00:21:20.320 --> 00:21:22.289 align:start position:0% the interesting point about snarks is actually<00:21:20.830> not<00:21:21.280> that<00:21:21.610> they<00:21:21.760> allows<00:21:22.120> your 00:21:22.289 --> 00:21:22.299 align:start position:0% actually not that they allows your 00:21:22.299 --> 00:21:24.380 align:start position:0% actually not that they allows your knowledge<00:21:22.660> it's<00:21:22.780> it's<00:21:23.020> that<00:21:23.290> they<00:21:23.500> allow<00:21:23.860> this 00:21:24.380 --> 00:21:24.390 align:start position:0% knowledge it's it's that they allow this 00:21:24.390 --> 00:21:28.169 align:start position:0% knowledge it's it's that they allow this speed<00:21:25.390> up<00:21:25.540> in<00:21:25.750> verification<00:21:26.650> and<00:21:27.179> people 00:21:28.169 --> 00:21:28.179 align:start position:0% speed up in verification and people 00:21:28.179 --> 00:21:30.990 align:start position:0% speed up in verification and people people<00:21:29.020> find<00:21:29.650> your<00:21:29.950> knowledge<00:21:30.280> more 00:21:30.990 --> 00:21:31.000 align:start position:0% people find your knowledge more 00:21:31.000 --> 00:21:32.280 align:start position:0% people find your knowledge more interesting<00:21:31.570> because<00:21:31.750> it's<00:21:32.020> kind<00:21:32.200> of 00:21:32.280 --> 00:21:32.290 align:start position:0% interesting because it's kind of 00:21:32.290 --> 00:21:33.990 align:start position:0% interesting because it's kind of counterintuitive<00:21:32.679> but<00:21:33.250> actually<00:21:33.610> it's<00:21:33.760> it's 00:21:33.990 --> 00:21:34.000 align:start position:0% counterintuitive but actually it's it's 00:21:34.000 --> 00:21:36.030 align:start position:0% counterintuitive but actually it's it's a<00:21:34.120> triviality<00:21:34.390> to<00:21:34.870> add<00:21:35.020> to<00:21:35.320> the<00:21:35.410> protocol<00:21:35.799> here 00:21:36.030 --> 00:21:36.040 align:start position:0% a triviality to add to the protocol here 00:21:36.040 --> 00:21:38.850 align:start position:0% a triviality to add to the protocol here so<00:21:36.190> the<00:21:36.309> protocol<00:21:36.669> works<00:21:37.419> so<00:21:38.410> most<00:21:38.679> of<00:21:38.799> the 00:21:38.850 --> 00:21:38.860 align:start position:0% so the protocol works so most of the 00:21:38.860 --> 00:21:43.230 align:start position:0% so the protocol works so most of the work<00:21:39.040> in<00:21:39.190> the<00:21:39.280> protocol<00:21:39.960> is<00:21:40.960> to<00:21:42.059> allows<00:21:43.059> the 00:21:43.230 --> 00:21:43.240 align:start position:0% work in the protocol is to allows the 00:21:43.240 --> 00:21:45.060 align:start position:0% work in the protocol is to allows the speed-up<00:21:43.510> and<00:21:43.750> the<00:21:44.410> zero<00:21:44.650> knowledge<00:21:44.919> just 00:21:45.060 --> 00:21:45.070 align:start position:0% speed-up and the zero knowledge just 00:21:45.070 --> 00:21:47.039 align:start position:0% speed-up and the zero knowledge just basically<00:21:45.700> comes<00:21:45.910> for<00:21:46.090> free<00:21:46.240> and<00:21:46.480> this<00:21:46.780> is<00:21:46.840> how 00:21:47.039 --> 00:21:47.049 align:start position:0% basically comes for free and this is how 00:21:47.049 --> 00:21:52.190 align:start position:0% basically comes for free and this is how it<00:21:47.140> comes<00:21:47.290> for<00:21:47.740> free<00:21:49.530> the<00:21:50.530> prover<00:21:50.860> just<00:21:51.100> adds<00:21:51.309> a 00:21:52.190 --> 00:21:52.200 align:start position:0% it comes for free the prover just adds a 00:21:52.200 --> 00:21:54.870 align:start position:0% it comes for free the prover just adds a random<00:21:53.200> encrypted<00:21:53.650> number<00:21:53.980> to<00:21:54.250> both<00:21:54.400> sides<00:21:54.730> of 00:21:54.870 --> 00:21:54.880 align:start position:0% random encrypted number to both sides of 00:21:54.880 --> 00:21:57.200 align:start position:0% random encrypted number to both sides of the<00:21:55.000> equation<00:21:55.450> because<00:21:56.290> it's<00:21:56.410> all<00:21:56.500> encrypted 00:21:57.200 --> 00:21:57.210 align:start position:0% the equation because it's all encrypted 00:21:57.210 --> 00:22:00.360 align:start position:0% the equation because it's all encrypted there's<00:21:58.210> no<00:21:58.419> way<00:21:58.660> for<00:21:58.690> the<00:21:59.110> prover<00:21:59.530> to<00:22:00.160> cheat 00:22:00.360 --> 00:22:00.370 align:start position:0% there's no way for the prover to cheat 00:22:00.370 --> 00:22:02.159 align:start position:0% there's no way for the prover to cheat there<00:22:00.640> and<00:22:00.850> that's<00:22:01.630> how<00:22:01.750> you<00:22:01.809> get<00:22:01.960> zero 00:22:02.159 --> 00:22:02.169 align:start position:0% there and that's how you get zero 00:22:02.169 --> 00:22:04.470 align:start position:0% there and that's how you get zero knowledge<00:22:02.320> and<00:22:02.679> the<00:22:03.669> proof<00:22:03.880> itself<00:22:04.120> is<00:22:04.299> eight 00:22:04.470 --> 00:22:04.480 align:start position:0% knowledge and the proof itself is eight 00:22:04.480 --> 00:22:05.590 align:start position:0% knowledge and the proof itself is eight group<00:22:04.690> elements<00:22:05.080> in<00:22:05.230> an 00:22:05.590 --> 00:22:05.600 align:start position:0% group elements in an 00:22:05.600 --> 00:22:10.750 align:start position:0% group elements in an the<00:22:05.720> curve<00:22:06.910> the<00:22:07.910> verifying<00:22:09.340> iz5<00:22:10.340> pairing 00:22:10.750 --> 00:22:10.760 align:start position:0% the curve the verifying iz5 pairing 00:22:10.760 --> 00:22:12.160 align:start position:0% the curve the verifying iz5 pairing checks<00:22:11.000> plus<00:22:11.300> some<00:22:11.510> elliptic<00:22:11.930> curve 00:22:12.160 --> 00:22:12.170 align:start position:0% checks plus some elliptic curve 00:22:12.170 --> 00:22:15.520 align:start position:0% checks plus some elliptic curve arithmetic<00:22:13.040> and<00:22:13.450> I'm<00:22:14.450> Way<00:22:14.690> out<00:22:14.930> of<00:22:14.960> time<00:22:15.320> now 00:22:15.520 --> 00:22:15.530 align:start position:0% arithmetic and I'm Way out of time now 00:22:15.530 --> 00:22:18.170 align:start position:0% arithmetic and I'm Way out of time now so<00:22:15.830> thanks<00:22:16.310> for<00:22:16.430> your<00:22:16.580> attention 00:22:18.170 --> 00:22:18.180 align:start position:0% so thanks for your attention 00:22:18.180 --> 00:22:24.460 align:start position:0% so thanks for your attention [Applause] 00:22:24.460 --> 00:22:24.470 align:start position:0% 00:22:24.470 --> 00:22:32.059 align:start position:0% [Music]