Регистрация Войти
Рейтинг:3
BlackHat18 avatar Crypto

Гибридный аргумент без эффективной выборки

флаг sy
BlackHat18

скажем, у меня есть $к$ распределения, где $к$ полиномиально велико, $D_1, D_2, \ldots, D_k$ так что каждый $D_i$ вычислительно неотличима от равномерного распределения.

Правда ли, что раздача $D_1 D_2 \ldots D_k$ также вычислительно неотличимы от $к$ копии единого дистрибутива?

Это тривиально выполняется, если каждый $D_i$ эффективно поддается выборке. Но допустим, что их нет.

Остается ли факт по-прежнему верным благодаря какому-то умному способу обойти требование выборки?

46
1 + 0
Рейтинг:3
Yehuda Lindell avatar Crypto
флаг us
Yehuda Lindell

Это очень интересный вопрос. Я осмотрелся и нашел газету под названием Вычислительная неразличимость: пример иерархии Голдрайхом и Суданом. Это содержит доказательство того, что оно не выполняется.

0 + 2
BlackHat18 avatar
флаг sy
BlackHat18
Просто уточнение. В этой статье рассказывается о двух дистрибутивах и ситуации, когда нам дается $k$ выборок из любого дистрибутива из двух.Но здесь либо дается по одной выборке из $k$ разных распределений (каждое вычислительно неотличимо от равномерного), либо нам дается $k$ выборок из равномерного распределения. Считаете ли вы, что методы, которые работают для первой настройки (в статье), также работают и для второй настройки (в моем вопросе)?
0
Ответить
Yehuda Lindell avatar
флаг us
Yehuda Lindell
В документе также есть ссылки на предыдущую работу, посвященную более основному вопросу. Моя интуиция подсказывает, что это должно привести к аналогичным настройкам, но, конечно, интуицию всегда нужно проверять.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.