In the mathematical and computer science field of cryptography, a group of three numbers (x,y,z) is said to be a claw of two permutations f0 and f1 if
- f0(x) = f1(y) = z.
A pair of permutations f0 and f1 are said to be claw-free if there is no efficient algorithm for computing a claw.
The terminology claw free was introduced by Goldwasser, Micali, and Rivest in their 1984 paper, "A Paradoxical Solution to the Signature Problem" (and later in a more complete journal paper), where they showed that the existence of claw-free pairs of trapdoor permutations implies the existence of digital signature schemes secure against adaptive chosen-message attack.[1][2] This construction was later superseded by the construction of digital signatures from any one-way trapdoor permutation.[3] The existence of trapdoor permutations does not by itself imply claw-free permutations exist;[4] however, it has been shown that claw-free permutations do exist if factoring is hard.[5]
The general notion of claw-free permutation (not necessarily trapdoor) was further studied by Ivan Damgård in his PhD thesis The Application of Claw Free Functions in Cryptography (Aarhus University, 1988), where he showed how to construct
Collision Resistant Hash Functions from claw-free permutations.[5] The notion of claw-freeness is closely related to that of collision resistance in hash functions. The distinction is that claw-free permutations are pairs of functions in which it is hard to create a collision between them, while a collision-resistant hash function is a single function in which it's hard to find a collision, i.e. a function H is collision resistant if it's hard to find a pair of distinct values x,y such that
- H(x) = H(y).
In the hash function literature, this is commonly termed a hash collision. A hash function where collisions are difficult to find is said to have collision resistance.
Bit commitment
Given a pair of claw-free permutations f0 and f1 it is straightforward to create a commitment scheme. To commit to a bit b the sender chooses a random x, and calculates fb(x). Since both f0 and f1 share the same domain (and range), the bit b is statistically hidden from the receiver. To open the commitment, the sender simply sends the randomness x to the receiver. The sender is bound to his bit because opening a commitment to 1 − b is exactly equivalent to finding a claw. Notice that like the construction of Collision Resistant Hash functions, this construction does not require that the claw-free functions have a trapdoor.
References
Шаблон:Reflist
Further reading
| Партнерские ресурсы |
|---|
| Криптовалюты |
|
|---|
| Магазины |
|
|---|
| Хостинг |
|
|---|
| Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
|---|
