January 28th, 2009

Вопрос про математику

Где-то когда-то видел математический метод, с помощью которого можно проделать следующее. Каждому участнику некоторой группы выдан идентификатор. Некоторым образом из него делается другой идентификатор, по которому нельзя отследить исходный, однако можно убедится, что первый идентификатор, соответствующий второму, присутствует в числе выданных.

То есть, с одной стороны проверяется, что доступ легален – его получил кто-то из группы идентифицированных, с другой стороны – нельзя вычислить, кто именно получил доступ.

Мистики в моём вопросе, сразу скажу, никакой нет. Это в статье про распространение контента зашла речь про анонимность подпсичиков, и я вспомнил про этот способ. Однако неожиданно для себя понял, что не помню ни названия, ни принципа. Помню только, что в описании метода фигурировали постоянные отсылки к шифрованию с открытым ключом.

Кто-то ещё знает про этот метод?

Или, быть может, кто-то готов его сходу вывести? Было бы весьма интересно.

UPDATE

На всякий случай приведу более конкретный пример этой общей задачи.

Проводятся серии интернет-голосований (абстрагируемся сейчас от подписок на контент и прочее).

1. Каждому желающему выдают идентификационный номер (по паспортным данным, например, дабы гарантировать, что номер у гражданина будет один).

2. В каждом голосовании гражданин может проголосовать максимум один раз. Для этого как-то используется его номер. (Вопрос: как?).

3. Обрабатывающий результаты может убедиться, что проголосовали только те, кому выдали номера. И что каждый проголосовал не более одного раза.

4. Обрабатывающий результаты не может узнать, кто именно, как проголосовал (то есть, не способен связать идентификаторы, выданные по паспортным данным, с с экземпляром ответов на вопросы голосования).

5. Бонусный вариант: владелец номера имеет возможность проверить, что его ответы в обработке соответствуют введённым им при голосовании.

6. Супербонусный вариант: владелец номера имеет возможность доказать третьим лицам, что его ответы именно такие, но не выдавать при этом свой номер, равно как и не давать третьим лицам возможность отследить свои результаты в следующих и предыдущих голосованиях.

Про равновесие и перетягивание каната

И, конечно, как всегда про рыночную экономику.

И ещё это – задача

Равновесием системы в общем случае называют такое состояние системы, при котором система находится в состоянии покоя. То есть, в ней отсутствуют изменения параметров. В частных случаях термин приобретает несколько иные значения. Так, различают «устойчивое» и «неустойчивое» равновесие. Первое характеризуется тем, что отклонения системы от состояния равновесия (для определённости, назовём такое «точкой равновесия») приводят к возникновению сил, устремляющих систему обратно в это состояние. Под вторым подразумевается, что отклонения системы от точки равновесия наоборот утягивают её ещё дальше от этой точки.

Равновесие может рассматриваться как некоторое явление в системе с жёстко заданной конфигурацией, так и явление в системе, конфигурация которой меняется в результате функционирования системы. Первый случай вполне понятен – это, например, шарик, брошенный в полусферическую ямку. Через некоторое время шарик окажется на самом дне ямки и любые его смещения после того, как он остановится на дне ямке, всё равно в конечном счёте выльются в его возвращение на самое дно.

Случай с изменяемой конфигурацией несколько сложнее. Его иллюстрацией, например, служит бросок тяжёлого шарика в бокал. Под воздействием шарика бокал будет шататься, что приведёт к постоянной смене точки равновесия в системе координат бокала. То есть, в разные моменты времени «слепок» системы будет давать разные точки равновесия в плане рассмотрения слепка системы как её стационарного состояния. Подразумевается, что если бы мы поймали в какой-то момент времени бокал рукой и удержали бы его в том положении, которое он в данный момент времени принял, то через некоторое время шарик бы оказался в некоторой точке, где у него в рамках описанной системы будет устойчивое равновесие.

Конечно, можно подобрать такую конфигурацию бокала, у которой некоторые слепки будут давать не одну точку равновесия, а некоторое их множество.

Собственно, к чему это всё? Это всё к тому, что когда вам говорят про «равновесие», надо внимательно разбираться, которое именно имеется в виду. Поскольку разные равновесия имеют разный физический смысл.

Так, в частности, в ряде случаев приходится встречаться со следующим рассуждением:

Наша система уравновешивает сама себя. Конечно, некоторые действия её составных элементов временами выводят её из равновесия, однако равномерная распределённость таких действий по противоположным направлениям неминуемо возвращает систему в то же состояние, в котором она была. Или даже в ещё более близкое к равновесию – если раньше система была ещё не в нём.

Под элементами системы обычно подразумеваются игроки в некооперативную игру. То есть, конкуренты. Каждый из них стремится изменить систему в свою пользу, однако, – как говорится в рассуждении, – поскольку к такому стремятся все, их усилия уравновешивают друг друга и система пребывает в гармонии.

Вопрос равновесия тут очень тонкий. Поскольку вопрос «уравновешивания» открыт. Неясно, про какое равновесие говорится в таком «уравновешивании». Понимается ли тут переход от одной точки равновесия к другой или же возврат всё время в одну и ту же?

Впрочем, это даже не так существенно как вопрос о поведении системы. Как себя будет такая система вести?

Collapse )