Proof of knowledge

In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds in 'convincing' a verifier that the prover knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs[1]) a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP.

Let be a statement of language in NP, and the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: .

A proof of knowledge for relation with knowledge error is a two party protocol with a prover and a verifier with the following two properties:

  1. Completeness: If , then the prover who knows witness for succeeds in convincing the verifier of his knowledge. More formally: , i.e. given the interaction between the prover P and the verifier V, the probability that the verifier is convinced is 1.
  2. Validity: Validity requires that the success probability of a knowledge extractor in extracting the witness, given oracle access to a possibly malicious prover , must be at least as high as the success probability of the prover in convincing the verifier. This property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier.

Details on the definition

This is a more rigorous definition of Validity:[2]

Let be a witness relation, the set of all witnesses for public value , and the knowledge error. A proof of knowledge is -valid if there exists a polynomial-time machine , given oracle access to , such that for every , it is the case that and

The result signifies that the Turing machine did not come to a conclusion.

The knowledge error denotes the probability that the verifier might accept , even though the prover does in fact not know a witness . The knowledge extractor is used to express what is meant by the knowledge of a Turing machine. If can extract from , we say that knows the value of .

This definition of the validity property is a combination of the validity and strong validity properties.[2] For small knowledge errors , such as e.g. or it can be seen as being stronger than the soundness of ordinary interactive proofs.

Relation to general interactive proofs

In order to define a specific proof of knowledge, one need not only define the language, but also the witnesses the verifier should know. In some cases proving membership in a language may be easy, while computing a specific witness may be hard. This is best explained using an example:

Let be a cyclic group with generator in which solving the discrete logarithm problem is believed to be hard. Deciding membership of the language is trivial, as every is in . However, finding the witness such that holds corresponds to solving the discrete logarithm problem.

Protocols

Schnorr protocol

One of the simplest and frequently used proofs of knowledge, the proof of knowledge of a discrete logarithm, is due to Schnorr.[3] The protocol is defined for a cyclic group of order with generator .

In order to prove knowledge of , the prover interacts with the verifier as follows:

  1. In the first round the prover commits himself to randomness ; therefore the first message is also called commitment.
  2. The verifier replies with a challenge chosen at random.
  3. After receiving , the prover sends the third and last message (the response) reduced modulo the order of the group.

The verifier accepts, if .

We can see this is a valid proof of knowledge because it has an extractor that works as follows:

  1. Simulate the prover to output . The prover is now in state .
  2. Generate random value and input it to the prover. It outputs .
  3. Rewind the prover to state . Now generate a different random value and input it to the prover to get .
  4. Output .

Since , the output of the extractor is precisely .

This protocol happens to be zero-knowledge, though that property is not required for a proof of knowledge.

Sigma protocols

Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocols.[4] The naming originates from Sig, referring to the zig-zag symbolizing the three moves of the protocol, and MA, an abbreviation of "Merlin-Arthur".[5] Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of and with respect to bases and are equal or fulfill some other linear relation. For a and b elements of , we say that the prover proves knowledge of and such that and . Equality corresponds to the special case where a = 1 and b = 0. As can be trivially computed from this is equivalent to proving knowledge of an x such that .

This is the intuition behind the following notation,[6] which is commonly used to express what exactly is proven by a proof of knowledge.

states that the prover knows an x that fulfills the relation above.

Applications

Proofs of knowledge are useful tool for the construction of identification protocols, and in their non-interactive variant, signature schemes. Such schemes are:

They are also used in the construction of group signature and anonymous digital credential systems.

See also

References

  1. ^ Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Draft. Extended abstract
  2. ^ a b Mihir Bellare, Oded Goldreich: On Defining Proofs of Knowledge. CRYPTO 1992: 390–420
  3. ^ C P Schnorr, Efficient identification and signatures for smart cards, in G Brassard, ed. Advances in Cryptology – Crypto '89, 239–252, Springer-Verlag, 1990. Lecture Notes in Computer Science, nr 435
  4. ^ [1] On Sigma protocols
  5. ^ [2] Modular Design of Secure yet Practical Cryptographic Protocols
  6. ^ Proof Systems for General Statements about Discrete Logarithms

Read other articles:

سنة كبيسةمعلومات عامةالنوع وحدة زمن — year type (en) جزء من تقويم يولياني — تقويم ميلادي تستخدم لقياس المدة الزمنية تحويلات الوحدةإلى النظام الدولي 31622400 ثانية الوحدة القياسية 366 يوم تعديل - تعديل مصدري - تعديل ويكي بيانات السنة الكبيسة هي سنة عدد أيامها 366 يوما مع العلم أن السنة ...

 

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Condon USFS Airport – news · newspapers · books · scholar · JSTOR (October 2023) AirportCondon USFS AirportIATA: noneICAO: noneFAA LID: S04SummaryAirport typePublicOwnerUnited States Forest Service (USFS)ServesCondon, MontanaElevation AMSL3,686&#...

 

Monasterio Celeste Entrada del MonasterioLocalizaciónPaís  ChileLocalidad Parcela San José, Santa Lucila s/n Requínoa, ChileCoordenadas 34°15′06″S 70°49′59″O / -34.25164722, -70.83316111Detalles generalesSuperficie 16.000 m²Propietario O'HigginsConstrucciónCoste US$ 7.500.000Inicio 2 de febrero de 2013Apertura 8 de mayo de 2014Equipo local Club Deportivo O'HigginsFútbol Joven de O'Higgins de Rancagua Club Deportivo O'Higgins (femenino)Acontecimientos...

Pinacoteca nazionale di SienaPalazzo Buonsignori - Brigidi, sede della Pinacoteca UbicazioneStato Italia Località Siena IndirizzoVia San Pietro, 29 Coordinate43°18′56″N 11°19′50″E / 43.315556°N 11.330556°E43.315556; 11.330556Coordinate: 43°18′56″N 11°19′50″E / 43.315556°N 11.330556°E43.315556; 11.330556 CaratteristicheTipoPittura Istituzione1932 Apertura1932 GestioneMinistero della Cultura DirettoreAxel Hémery Visitatori21...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2019) روب ميدوز   معلومات شخصية الميلاد 26 ديسمبر 1976 (47 سنة)  طارازانا  مواطنة الولايات المتحدة  الحياة العملية المهنة رائد أعمال  تعديل مصدري - تعديل ...

 

1941 non-aggression agreement between the USSR and Imperial Japan Soviet–Japanese Neutrality PactJapanese Foreign Minister Matsuoka signing the pactTypeBilateral treatySignedApril 13, 1941 (1941-04-13)LocationMoscow, Russian SFSR, USSRExpirationApril 13, 1946 (1946-04-13)[a]Signatories Vyacheslav Molotov Yōsuke Matsuoka Yoshitsugu TatekawaParties  Soviet Union  Japan ^ Denounced by the USSR on April 5, 1945 (1945-04-05) Soviet-...

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。(2020年5月) この記事で示されている出典について、該当する記述が具体的にその文献の何ページあるいはどの章節にあるのか、特定が求められています。ご存知の方は加筆をお願いします。...

 

Australian netball team Melbourne VixensFounded2007; 16 years ago (2007)Based inMelbourneRegionsVictoriaHome venueJohn Cain ArenaMargaret Court ArenaHead coachSimone McKinnisCaptainKate MoloneyLiz WatsonPremierships3 (2009, 2014, 2020)LeagueSuncorp Super NetballANZ Championship2022 placing1stWebsitemelbournevixens.com.au Uniform Melbourne Vixens is an Australian professional netball team based in Melbourne, Victoria. Since 2017 they have represented Netball Victoria in Sunco...

 

Book by David Lewis-Williams Inside the Neolithic Mind: Consciousness, Cosmos and the Realm of the Gods Cover of the first editionAuthorDavid Lewis-Williams and David PearceCountryUnited KingdomLanguageEnglishSubjectArchaeologyReligious studiesPublisherThames and HudsonPublication date2005Media typePrint (Hardcover and paperback)Pages320ISBN9780500288276Dewey Decimal930.14 Inside the Neolithic Mind: Consciousness, Cosmos and the Realm of the Gods is a cognitive archaeological study of Ne...

A pioneer artist of Assam India Asu Dev আশু দেবBornAshutosh Deb(1917-12-13)December 13, 1917 13 December 1917Dhubri, Assam, IndiaDiedFebruary 6, 1983(1983-02-06) (aged 65)EducationCotton Collegiate H.S School, GuwahatiKnown forPainter, sculptor, art EducatorChildrenAnutosh Deb (son)Parent(s)Kadambini Deb, Umesh Chandra DebWebsiteartofasudev.org Asu Dev (আশু দেব), born as Ashutosh Deb Dhubri, Assam, India (13 December 1917 – 6 February 1983)[1][2...

 

Simulation video game 2000 video gameCaesars Palace 2000North American Dreamcast cover artDeveloper(s)RunecraftPublisher(s)Interplay EntertainmentPlatform(s)PlayStationDreamcastMicrosoft WindowsReleasePlayStationEU: June 16, 2000NA: June 29, 2000Dreamcast EU: June 16, 2000NA: September 24, 2000Microsoft WindowsNA: June 2000Genre(s)Gambling simulationMode(s)Single-player multiplayer Caesars Palace 2000 is a gambling simulation video game developed by Runecraft and published by Interplay Entert...

 

MinoritenkircheMinoritenkirche, Vienna, AustriaReligionAffiliationSociety of Saint Pius XLeadershipCongregazione Italiana Madonna della NeveLocationLocationVienna, AustriaShown within ViennaShow map of ViennaMinoritenkirche (Vienna) (Austria)Show map of AustriaGeographic coordinates48°12′34″N 16°21′49″E / 48.2094°N 16.3636°E / 48.2094; 16.3636ArchitectureArchitect(s)Jacobus ParisiensisTypeChurch[1]StyleGothicGroundbreaking1276Completed1350Specificat...

Ministry of JusticeFinnish: oikeusministeriöSwedish: justitieministerietMinistry overviewFormedAugust 1809 (1809-08)JurisdictionFinnish GovernmentHeadquartersEteläesplanadi 10, HelsinkiAnnual budget€0.941 billion (2018)Minister responsibleLeena Meri, Minister of JusticeWebsiteoikeusministerio.fi/en/ Politics of Finland State Constitution Declaration of Independence Human rights Law enforcement Military Executive President (list) Sauli Niinistö Prime Minister (list) Petteri Orpo...

 

Caesium chromate Names IUPAC name Dicaesium dioxido(dioxo)chromium Other names Dicaesium chromate Identifiers CAS Number 13454-78-9 3D model (JSmol) Interactive image ChemSpider 55521 ECHA InfoCard 100.033.296 EC Number 236-640-4 PubChem CID 61613 CompTox Dashboard (EPA) DTXSID20894903 InChI InChI=1/Cr.2Cs.4O/q;2*+1;;;2*-1/rCrO4.2Cs/c2-1(3,4)5;;/q-2;2*+1Key: BROHICCPQMHYFY-UICSPCLAAP SMILES [Cs+].[Cs+].[O-][Cr]([O-])(=O)=O Properties[1] Chemical formula Cs2CrO4 Appearance Y...

 

Фантастическая симфонияфр. La Symphonie fantastique Жанры драматический фильм[1] и биографический фильм Режиссёр Кристиан-Жак[1] Продюсер Alfred Greven[d] Авторысценария Жан-Пьер Фейдо Андре Легран Шарль Эксбрайя Андре дю Доньон В главныхролях Жан-Луи Барро Рене Сен-Сир ...

United States historic placeU.S. Military AcademyU.S. National Register of Historic PlacesU.S. National Historic Landmark District Cadet ChapelLocationNY 218, West Point, New YorkCoordinates41°23′34″N 73°57′30″W / 41.3927°N 73.9584°W / 41.3927; -73.9584Area2,500 acres (1,000 ha)Built1775ArchitectMultipleArchitectural styleClassical Revival, Tudor Revival, FederalNRHP reference No.66000562[1]Significant datesAdded to NRHP15 Octobe...

 

Royal Spanish trading ships, 1565–1815 Galeón de ManilaManila galleon (c. 1590 Boxer Codex)Native name Spanish: Galeón de Manila, Filipino: Galyon ng MaynilaEnglish nameManila galleonDurationFrom 1565 to 1815 (250 years)VenueBetween Manila and AcapulcoLocationNew Spain (Spanish Empire) (current Mexico)Also known asNao de China or Galeón de AcapulcoMotiveTrading maritime route from East Indies to the AmericasOrganised bySpanish Crown The Manila galleon (Spanish: Galeón de Mani...

 

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

Серия телесериала «Легенда о Корре»Когда встречаются крайностиангл. When Extremes Meet Тарлок применяет на Корре магию крови Основная информация Номер серии Сезон 1Серия 8 Режиссёры Хоаким Дос СантосКи Хьюн Рю Авторы сценария Майкл Данте ДимартиноБрайан Кониецко Дата ...

 

vteLists of United Kingdom locations Aa-Ak Al Am-Ar As-Az Bab-Bal Bam-Bap Bar Bas-Baz Bea-Bem Ben-Bez Bi Bla-Blac Blad-Bly Boa-Bot Bou-Boz Bra Bre-Bri Bro-Bron Broo-Brt Bru-Bun Bur-Bz Ca-Cap Car-Cd Ce-Chap Char-Che Chi-Ck Cl-Cn Co-Col Com-Cor Cos-Cou Cov-Coy Cra Cre-Croc Croe-Cros Crot-Croz Cru-Cu Cw-Cz Da-Dam Dan-Ddu De-Dee Deo-Dn Do-Dor Dos-Doz Dr Ds-Dz Ea-Eass East A-D East E-L East M-Y Eat-Ee Ef-El Em-Ez Fa-Fe Ff-Fn Fo Fr-Fz Gab-Gan Gao-Gar Gas-Gaz Ge-Gl Gm-Gq Gr-Gred Gree-Gz Ha-Ham Han-H...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!