Усовершенствованный тест -мерности для булевых функций PDF

Автори:А.Н. Алексейчук, С.Н. Конюшок

А.Н. Алексейчук, С.Н. Конюшок

УДК 621.391:519.2

Усовершенствованный тест -мерности для булевых функций / Алексейчук А.Н., Конюшок С.Н. // Кибернетика и системный анализ.

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

Библиогр.: 9назв.

Ключевые слова: проверка свойств булевых функций, вероятностный алгоритм, -мерная функция, преобразование Уолша-Адамара.

УДК 621.391:519.2

Удосконалений -вимірності для булевих функцій / Олексійчук А.М., Конюшок С.М. // Кібернетика і системний аналіз.

Запропоновано ймовірнісний тест -вимірности булевих функцій, який має меншу трудомісткість та характеризується меншою ймовірністю помилки першого роду (при такій самій верхній межі ймовірності помилки другого роду) в порівнянні з аналогічним раніше відомим тестом.

Бібліогр.: 9назв.

В настоящей статье решается задача тестирования свойства -мерности булевых функций. Предлагается вероятностный алгоритм (тест -мерности), имеющий лучшие характеристики эффективности по сравнению с ранее известным тестом [1].

Для уточнения постановки задачи напомним определения основных понятий и сформулируем вспомогательные результаты о свойствах булевых функций. Более подробную информацию по этим вопросам можно найти в монографии [2].

Ниже предлагается более эффективный тест -мерности, трудоемкость которого составляет  двоичных операций. При этом верхняя граница вероятности ошибки первого рода предложенного теста не зависит от , а верхняя граница вероятности ошибки второго рода по существу та же, что и для теста из [1]. Показано также, что при некотором естественном изменении альтернативы  можно построить односторонний (с нулевой вероятностью ошибки первого рода) тест -мерности, трудоемкость которого составляет  двоичных операций.

References

1. Gopalan P., O’Donnell R., Servedio A., Shpilka A., Wimmer K. Testing Fourier dimensionality and sparsity // SIAM J. on Computing. – 2011. – Vol. 40(4). – P. 1075 – 1100.

2. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. – М.: МЦНМО, 2004. – 470 с.

3. Ященко В.В. О критерии распространения для булевых функций и бент-функциях // Проблемы передачи информации. – 1997. – Т. 33. – № 1. – С. 75 – 86.

4. Golić J., Morgari G. On the resynchronization attack // Fast Software Encryption. – FSE’03, Proceedings. – Springer-Verlag. 2003. – P. 100 – 110.

5. Алексеев Е.К. О некоторых мерах нелинейности булевых функций // Прикладная дискретная математика. – 2011. – № 2(12). – С. 5 – 16.

6. Алексеев Е.К. Об атаке на фильтрующий генератор с функцией усложнения, близкой к алгебраически вырожденной // Материалы Шестой международной научной конференции по проблемам безопасности и противодействия терроризму, 11 – 12 ноября 2010 г., Том 2. – М.: МЦНМО, 2011. – С. 114 – 123.

7. Levin L.A. Randomness and non-determinism // J. of Symbolic Logic. – 1993. – Vol. 58. – № 3. – P. 1102 – 1103.

8. Alon N., Kaufman T., Krivelevich M., Litsyn S., Ron D. Testing Reed-Muller codes // IEEE Trans. on Inform. Theory. – 2005. – Vol. 51(11). – P. 4032 – 4039.

9. Bhattacharyya A., Kopparty S., Schoenebeck G., Sudan M., Zuckerman D. Optimal testing of Reed-Muller codes // Proc. of the 51st Annual IEEE Symposium on Fundations of Computer Sci. – Las Vegas, Nevada, Oct. 23 – 26, 2010. – P.  488 – 497.

 

Сайт видання:http://www.kibernetika.org/