Кіріспе
Цифрлық қолтаңба схемасы
Криптографияда Шнорр қолтаңбасы — Клаус Шнорр сипаттаған Шнорр қолтаңба алгоритмімен жасалған цифрлық қолтаңба. Бұл цифрлық қолтаңба схемасы қарапайымдылығымен танымал және қауіпсіздігі кейбір дискретті логарифмдік есептердің шешілмейтініне негізделген. Ол тиімді және қысқа қолтаңбаларды жасайды. Шнорр қолтаңбаларының жағдайында бұл жай ғана мәндерді азайтуды қажет етеді: Егер , бірақ , онда жай ғана оқшаулауға болады. Шындығында, тіпті мәнге кішкене қателіктер немесе жартылай ақпараттың шығуы жеке кілтті жеткілікті көп қолтаңба жинап, жасырын сан мәселесін шешкеннен кейін ашуға мүмкіндік береді. Шноррдың идентификациялық протоколына сәйкес. Сондықтан (Фиат пен Шамирдің аргументтері бойынша) егер кездейсоқ оракул ретінде модельделген болса, ол қауіпсіз. Оның қауіпсіздігі сондай-ақ "кездейсоқ префикске төзімді" және "кездейсоқ префикске екінші рет төзімді" деген болжаммен жалпы топтық модельде де дәлелденуі мүмкін. Атап айтқанда, соқтығысуға төзімді болуы міндетті емес. 2012 жылы Сеурин Шнорр қолтаңба схемасының нақты дәлелін ұсынды. Атап айтқанда, Сеурин көрсеткендей, бұтақтану леммасын қолдана отырып қауіпсіздікті дәлелдеу, Шнорр типті қолтаңбалар және Гийю-Квискатер қолтаңба схемаларын қоса алғанда, бір бағытты топтық гомоморфизмдерге негізделген кез келген қолтаңба схемалары үшін ең жақсы нәтиже болып табылады. Атап айтқанда, ROMDL болжамы бойынша, кез келген алгебралық қысқарту өзінің уақыт пен табыстылық арақатынасының бір факторын жоғалтуы керек, мұнда функция 1-ден айтарлықтай кіші болғанша 1-ге жақын болады, ал — кездейсоқ оракулға жасалған ең көптеген сұраныстарда қате жасау ықтималдығы.
In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the intractability of certain discrete logarithm problems. It is efficient and generates short signatures. In the case of Schnorr signatures, this simply requires subtracting values:
If but then can be simply isolated. In fact, even slight biases in the value or partial leakage of can reveal the private key, after collecting sufficiently many signatures and solving the hidden number problem. to Schnorr's identification protocol. Therefore, (as per Fiat and Shamir's arguments), it is secure if is modeled as a random oracle. Its security can also be argued in the generic group model, under the assumption that is "random prefix preimage resistant" and "random prefix second preimage resistant". In particular, does not need to be collision resistant. In 2012, Seurin provided an exact proof of the Schnorr signature scheme. In particular, Seurin shows that the security proof using the forking lemma is the best possible result for any signature schemes based on one way group homomorphisms including Schnorr type signatures and the Guillou–Quisquater signature schemes. Namely, under the ROMDL assumption, any algebraic reduction must lose a factor in its time to success ratio, where is a function that remains close to 1 as long as " is noticeably smaller than 1", where is the probability of forging an error making at most queries to the random oracle.
Қысқа Шнорр қолтаңбалары
Жоғарыда аталған процесс 4t биттік қолтаңбалармен t биттік қауіпсіздік деңгейіне жетеді. Мысалы, 128 биттік қауіпсіздік деңгейіне 512 биттік (64 байттық) қолтаңбалар қажет. Қауіпсіздік, топтың мөлшерінің квадрат түбірімен сипатталатын күрделілікке ие топқа қарсы дискретті логарифм шабуылдарымен шектеледі. 1991 жылғы Schnorr-дың бастапқы мақаласында хэш функциясының соқтығысу төзімділігі қажет емес болғандықтан, қысқа хэш функциялары да дәл сондай қауіпсіз болуы мүмкін екені айтылды. Шындығында, соңғы жетістіктер t биттік қауіпсіздік деңгейіне 3t биттік қолтаңбалармен қол жеткізуге болатынын көрсетеді. Осылайша, 128 биттік қауіпсіздік деңгейі үшін тек 384 биттік (48 байттық) қолтаңбалар жеткілікті, және бұл s биттік өрістің жартысына дейін e өлшемін қысқарту арқылы қол жеткізілуі мүмкін.