Возьмём два слова, "и" и "нитропропилен", возмьём также 3 документа. 3 из них содежат "и", 2 - "нитропропилен".
информацию записываем в виде индекса, то есть каждая пара слово-документ - элемент в листе. дополнительно имеется инфа (rank), сколько раз в документе слово встречается. итого получаем 3+2=5 элементов записанных в виде: документИД:слово:количество_слова_в_документе

Е1 1:и:10 
Е2 2:и:15 
Е3 3:и:9 
Е4 1:"нитропропилен":2 
Е5 3:"нитропропилен":5

У каждого элемента шифруется первая часть и список сортируется по  rank, так что получается:

Е2:15, Е1:10, Е3:9, Е5:5, Е4:2

Это то, что видит нападающий. Незашифрованная часть нужна для сортировки элементов по "важности" (rank).

Теперь вопрос, как нападающему определить, в каком элементе находится какое слово?
В вышеописанном примере всё просто, нападающий знает, что слово "и" среднестатистически встречается чаще, чем "нитропропилен", а значит rank будет у них больше. Т.е он знает, что Е2 с большей вероятностью является словом "и", чем Е4.

Есть функция, которая трансформирует rank так, чтобы элементы распределились равномерно, при этом порядок одинаковых слов не изменился то есть она даст в идеальном случае:

Е5:5, Е2:4, Е1:3, Е4:2, Е3:1

Вот теперь и вопрос, как измерить, что функция действительно "спрятала" исходные значения. Сможет ли нападающий определить, где какое слово?

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

Смысл следующего - доказать, что перемешивающая функция раскидывает элементы качественно псевдослучайно, т.е. является качественным псевдо-случайным генератором чисел.

Можно замерить dist для каждого rank, где dist - это расстояние (количество позиций) между позицией элемента в перемешанном и не перемешанном рядах, для каждого элемента с выбранным rank. Получаем список rank => [dist1, dist2...], подсчитываем одинаковые расстояния, получаем множество {dist1:n1, dist2:n2...}, рисуем гистограмму. Собственно по частотам n1, n2... смотрим хорошо ли распределились расстояния (равномерно), т.е. доказать, что перемешивающая функция это в принципе не плохой генератор псевдослучайных чисел. Повторяем для каждого rank, накладываем гистограммы друг на друга, смотрим что бы диапазоны distN для каждого rank не "кучковались" (т.е. диапазоны более-менее равны, как и функции дистрибуции). Если получили общую гистограмму как один плотный прямоугольник, то функция перемешивания идеальна.

Количественную оценку можно вывести из разности дистрибуции nN внутри гистограммы (сумма разниц по квадрату от среднего к примеру), где 1 - площадь гистограммы это идеальный прямоугольник, 0 - на гистограмме полный хаос. Помножить на "кучковатость" диапазонов distN между rank'ами, т.е. взять разницу в диапазонах (разницу во множествах, к примеру среднее по элементам, разница в длинне и т.д.), 1 - диапазоны идеентичны (пересечение всех ==  каждому из них), 0 - пересечение диапазонов всех rank это пустое множество. Получим число [0-1], где 1 - перемешивающая функция идеальна (рандомно перемешивает), 0 - перемешивающая функция распределяет dist'ы не равномерно и/или диапазоны dist'ов для всех rank'ов не пересекаются.

Если два ряда вообще не перемешивать, то результат будет 1 - идеально   Что бы этого избежать, можно представить минимальный допустимый размер диапазона dist'ов - expected_dist_domain_size; посчитать средний размер множеств dist'ов каждого rank'а - mean_dist_domain_size; тогда оценку полученную выше перемножить на (mean_dist_domain_size / expected_dist_domain_size), но в таком случае можно получить оценку качества выше 1 (т.е. функция раскидывает элементы шире чем ожидалось).


P.S. перечитал... от меня на ночь торкнуло... но по идее это за более/менее честную оценку принять можно (статистика). Посчитать конечно ресурсоёмко будет... 

Всё же не могу понять архитектуру  Сергей, после предпоследнего твоего поста было всё более-менее понятно, а после последнего у меня вообще крыша съехала. 

Если есть возможность, попробуй пояснить, как это всё работает. Без этого сложно думать о "тонких вещах" (математике). Я полагал, что архитектура системы состоит из 3 частей: владелец индекса (actor 1), поисковая машина (actor 2) и ищущий пользователь (actor 3). Давай для простоты рассмотрим модель: sergejzr (actor 3) хочет найти в NewGoogle (actor 2) информацию из Клуба Винграда. Винград (actor 1) в данном случае поставляет индекс компании NewGoogle и не хочет по той или иной причине, чтобы NewGoogle что-то смог понять по этому индексу. Но хочет, чтобы sergejzr смог что-то найти в Клубе через поисковик NewGoogle. Далее, Винград выдаёт Сергею ключ, при помощи которого он может расшифровать результаты поиска NewGoogle. Более того, так как NewGoogle не знает (и не может знать) самих, собственно, слов индекса, Сергей сначала шифрует запрос и даёт Гуглу не чистый текст ("нитропропилен"), а зашифрованный вариант (грубо говоря, "AB6BBG7890"). ((Хотя, сейчас подумал, тоже непонятно, как это архитектурно устроить...))

В первом варианте (бумажка 109), как я понял, вы мешаете слова (то есть одному хэшу AB6BBG7890 соответствует несколько слов). Качество поиска падает, но при грамотном смешении слов не сильно. ((Кстати, можешь намекнуть, как именно вы мешали слова, если это не закрытая информация? Интересно, так как вы должны были сделать объединение в группы слов из разных тематик, чтобы не потерять ранк -- этакая атникластеризация, хотя, это тоже домыслы)) При этом мне, кажется, понятно, почему информацию о количестве нельзя публиковать (см. ниже рассуждения).

Теперь ты говоришь, что индекс выглядит как Е2:15, Е1:10, Е3:9, Е5:5, Е4:2. А что тогда sergejzr передаёт в качестве запроса Гуглу? Ведь теперь одному слову соответствует сразу 2, 3 и более хэшей?

А вообще, когда я исходил из понятой мной (видимо, неверно) модели, я рассуждал так.

Для начала надо понять, какая атака для нас опасна. То есть что мы не должны рассказать атакующему. Распределение само по себе вряд ли слишком опасно. То есть да, мы будем знать, что E1 -- это более вероятно "и", чем "нитропропилен", но... что далее? Как мы сможем понять содержимое коллекции из этого? Или как ещё мы сможем использовать информацию? Гораздо интереснее модель с ненулевым начальным знанием. Например, мы (NewGoogle) выкладываем в интернет документ, посвящённый определённой тематике (бомбы, терроризм и т. п.) и "вшиваем" в него какой-нибудь новый термин, который упоминаем в тексте ровно 21 раз. После этого смотрим, кто из пользователей обновил индекс: у кого появился новый термин с количеством использования 21. 3-5 таких "тестов" смогут достаточно хорошо понять аудиторию интересующихся "терроризмом". Далее мы можем отлавливать ещё и тех, кто по этому новому термину что-то ищёт (после того как поймём, как это слово шифруется). То есть я исхожу из того, что опасно не само распределение, а его "хвост" с малым количеством использования терминов. Ты исходишь примерно из той же модели атаки? А далее, если мы приходим к выводу, что нам опасен "хвост" -- может быть, его проще... отсечь? То есть дать всем "опасным" словам одинаковый ранк. Мне кажется, твои алгоритмы со склеиванием терминов и т. п. дают не меньшее искажение результатов поиска. Таким образом, у донора индекса в настройках получим такой "бегунок": на одном конце будет "ищем по вашим документам качественно", на другом "ищем безопасно для Вас". И график распределения будет уже не просто exp(-x), а exp(-x), которая с какого-то момента не падает, а устанавливается на определённом значении.

В общем, это как вариант защиты (от той атаки, которую я понимаю). Извини, я понимаю, что в первом посте ты задал другой вопрос, об оценке, а я навязываюсь с новыми "идеями". Над тем вопросом тоже подумаю, но только если "осилю" архитектуту, сейчас я просто не понимаю, как это должно работать.

Насчёт архитектурного устройства - таблица слово-хэш открыта. То есть каждый может запрос "зашифровать", а так как одному слову может соответствовать несколько хэшей, расшифровка точной уже не получится.



Да, верно. Секрет кроется в составлении таблицы слово-хэш. "мешание" (merging) присходит по вероятностной модели. То есть частые слова практически не "смешиваются" с другими, а вот редкие наоборот со многими. 

Здесь интересным оказался тот факт, что частые слова ищутся чаще. Поэтому поиск почти не искажается. Да, при поиске редких слов приходит много мусора, но на то они и редкие.



При поиске по хэшу (например sergejzr передал "AB6BBG7890") всегда возвращаются ВСЕ элементы, относящиеся к словам с этим хэшем. Это впринципе и было слабым местом системы. (Хотя эксперименты показали, что для коллекции в 200000 документов результат составил "всего" 24 кБ при размере "Хэш-таблицы" в 30168 строк)


Да, верно абсолютно. Но распределение опасно. Это мы в бумажке опишем. Конечно нельзя будет полностью сепарировать строки, но отдельные документы - вполне. А если у нападающего уже есть подозрения, то они усилятся именно на тот фактор "непохожести", который я пытаюсь промерять В самом худшем случае вероятность увеличится до 1 по сравнению с исходной. Вот этот фактор увеличения actor 1 должен знать. Иначе он не сможет решит, использовать нашу систему, или чего нибудь ещё.



Отличная атака. Но в эту бумажку уже не ляжет. 7 Марта дедлайн. Но на будущее конечно можно просимулировать и посмотреть 


Нет, одинаковый нельзя, усилится вероятность опять же..


Да, по этому принципу построена первая бумажка. Один хэш для всего - максимум секьюрити, индекс по типу слово - документы - минимум траффа.

А качество у нас не страдает по любому, потому что после того, как клиент заберёт достаточно элементов, он их расшифрует, а там ранк правильный уже.

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


Sardar, да, я тоже сперва думал о равномерности, но равномерность != максимум непохожести. Именно разница в равномерности между разными словами - проблема. Например я могу привести распределение к любому узору. Пока он действителен для всех слов - защита максимальна. А вот если узоры разные...

Добавлено @ 21:10
В аттаче - пример распределения ранка двух разных слов. "Смешивание" произойдёт, если одну картинку на другую наложить. Из графика видно, что некоторые части, заполненые точками одного слове не совпадают с точками другого слова. Они то как раз и станут видны нападающему.

Присоединённый файл ( Кол-во скачиваний: 18 )
 verteilung2.png 34,52 Kb

А бумажка 109 вот. После 25 Марта должна официально появится на ACM.
http://www.l3s.de/~olmedilla/pub/2008/2008-EDBT-Zerber.pdf

Присоединённый файл ( Кол-во скачиваний: 5 )
 Zerber.pdf 481,71 Kb

sergejzr, пусть у нас есть индекс Е5:5, Е2:4, Е1:3, Е4:2, Е3:1 (указанный тобой выше).

Я правильно понимаю, что владелец индекса знает, что Е1, Е2 и Е3 -- это "и", а Е4 и Е5 -- это "нитропропилен"? Ведь таблица хэшей открыта?

А вот номера документов он не знает: они "зашифрованы". То есть номера документов передаются клиенту, он их расшифровывает, обрабатывает и уже сам строит релевантность поиска.

Добавлено через 1 минуту и 27 секунд
За Zerber.pdf спасибо. Попробую посмотреть.

У всех них одинаковый хэш. Это те элементы, которые смешали в одну строку. 


Да, но там не только номера, но и правильное слово к каждому Е зашифровано.