Pull to refresh
132
0
vimmer @vimmer

User

Send message

Опубликовано доказательство P ≠ NP?

Reading time 1 min
Views 22K
Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.

Само доказательство на ~100 страницах.

Можно почитать более или менее адекватный комментарий на ycombinator.

Добавить нечего, читаем и/или ждем мнений специалистов в этой области.

P.S. На всякий случай, ссылка о том, что такое NP и P. (спасибо, SMiX)
Total votes 311: ↑294 and ↓17 +277
Comments 127

ACM Turing Award 2009 — Charles P. Thacker

Reading time 1 min
Views 473
Ежегодная премия Тьюринга за 2009 год была присуждена доктору Чарльзу Тэкеру (Charles P. Thacker).



awards.acm.org/2010/turing-award.cfm

Award Citation

For the pioneering design and realization of the first modern personal computer—the Alto at Xerox PARC— and seminal inventions and contributions to local area networks (including the Ethernet), multiprocessor workstations, snooping cache coherence protocols, and tablet personal computers.

Charles P. Thacker — один из основоположников многих направлений в архитектуре современных персональных компьютеров, графического (GUI) дизайна в 70-80 годах, работал в исследовательской лаборатории Xerox (Xerox Palo Alto Research Center).

Кроме того, он разработал протоколы кэширования (snooping cache coherence), некоторые сетевые протоколы, а также спроектировал и сконструировал прототип tablet PC.
Total votes 7: ↑6 and ↓1 +5
Comments 0

«Распределенное управление информационными потоками»/«Distributed Information Flow Control»

Reading time 5 min
Views 3.5K
Недавно по просьбе своего научного руководителя делал компиляцию и обзор для своей группы некоторых актуальных топиков в сфере безопасности ОС и систем в целом: automated trust negotiation (автоматическое «обсуждение» прав доступа — не знаю как правильно перевести) и information flow control (контроль потоков информации). Хотел запостить эту компиляцию, но к своему удивлению нашел, на мой взгляд, необоснованно мало сведений о DIFC (distributed information flow control/распределенном управлении инфромационными потоками) в .RU и поэтому решил написать эту небольшую статью по DIFC.

Мотивация
Практически единственным способом обеспечивать безопасность и приватность данных в системе принято считать аутенификацию (отвечает на вопрос: «Кто это сказал?») и авторизацию («Что он имеет право делать с этими данными»). Т.е. если программе необходим доступ к некоторым данным, мы фактически имеем 2 варианта: отказать или поверить. Если мы не доверяем этой программе, то теряем возможность работать с ней и возможно лишаемся важной функциональности. Если же мы решаем, что доверяем программе (и/или ее разработчикам), то программа фактически становится «полновластным хозяином» этой информации (или копии). Такой принцип в литературе называют All-Or-Nothing — «Все или ничего».

Естественно, что этот принцип недостаточно гибок и кроме того является основной причиной многих уязвимостей в системах, таких как переполнение буфера. В общем случае, этот принцип не позволяет создавать более интересные приложения, где права доступа не ограничиваются традиционными: «no access», «read only» и «read/write». Оказывается, что существуют системы, которые позволяют намного более гибкие разграничения прав доступа к данным — системы с поддержкой управления информационными потоками. Самой главной особенностью этих систем является то, что они следят за данными на всем протяжении их жизненного цикла в системе. Вспомним, что традиционно система ответственна только за начальный доступ к данным, например, проверку имеет ли программа доступ к файлу, а что после этого программа делает с этими данными систему уже не интересует.

Классический пример. Допустим, что в системе есть 2 пользователя Алиса и Боб. Они хотят назначить встречу, но так чтобы не раскрывать слишком много информации о своем расписании недели. Можно ли в многопользовательской системе Linux/Unix/Windows написать программу таким образом, чтобы она имела одновременный доступ к календарям и Алисы, и Боба и гарантировала конфиденциальность обоих пользователей системы?
И можно ли?!
Total votes 23: ↑19 and ↓4 +15
Comments 16

Гомоморфное шифрование/ (Fully) Homomorphic Encryption

Reading time 2 min
Views 6.9K
Так и подмывало озаглавить тему: «Закат компании Гугл близок!», но все-таки слишком уж «желто» было бы.

Теперь к делу. Что такое «гомоморфное шифрование» и причем тут Гугл?

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

Удивительно, но до недавних пор не существовало криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption), т.к. суммы и умножения хватит, чтобы выразить любую математическую функцию. Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст (посмотрите на формулу RSA и вспомните определение mod), поэтому через некоторое количество шагов накопленный шум делает расшифровку невозможной. Насколько я помню из презентации, говорилось, что подобные схему все же существуют, но они экспоненциональны по «эффективности».

Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации. Не вдаваясь в подробности (да и не буду делать вид, что на 100% понял все математические выкладки), смысл его решения заключается в том, что он использует двойное шифрование. Т.е. через определенное количество шагов он «снимает верхний слой» (первое шифрование) и «убирает» накопившийся «шум».

Как это работает, я расскажу общими словами и примерами, которые он сам использовал в своей презентации. Кому интересна математика и более формальное объяснение — читать диссертацию.
Остальным под кат
Total votes 118: ↑110 and ↓8 +102
Comments 58

Еще раз о феномене YouTube (Сюзан Бойл — более 30 миллионов просмотров)

Reading time 2 min
Views 601
Настоящей сенсацией стала 47-летняя участница британского проекта «Britain's Got Talent» (аналог «Народного Артиста»)

Когда она появилась в зале, то буквально все были настроены против Сюзан Бойл — простоватой не слишком красивой участницы из небольшой деревеньки в Шотландии. После короткого и немного саркастичного интервью зрители узнали, что 47-летняя женщина всегда мечатала быть певицей, и вот сегодня ее шанс проявить себя. Зал свистел и улюлюкал, а жюри с некоторой жалостью и сочувствием смотрело на нее и ждало начало выступления.

Читать дальше →
Total votes 57: ↑44 and ↓13 +31
Comments 31

«Шестое Чувство» MIT

Reading time 1 min
Views 936
по следам:
habrahabr.ru/blogs/gadgets/51633
(решил, что все-таки главная презентация может быть интересна)

оригинал
www.ted.com/index.php/talks/pattie_maes_demos_the_sixth_sense.html

Студенты Медиа Лаборатории MIT разработали компьютерную систему, которую можно носить, и которая позволяет создавать тачскрин на любой поверхности. Система автоматически адаптируется и позволяет «предугадывать», что именно хочет видеть человек на поверхности книги, туалетной бумаги, газеты и т.д.

Это один из тех случаев, когда лучше один раз увидеть, чем 100 раз услышать =)

Проект назван довольно амбициозно «Шестое Чувство». По словам Pattie Maes — с группы Fluid Interfaces — традиционные 5 чувств человека не позволяют адекватно реагировать на многие проблемы современного мира. Для этого нужно обрабатывать огромное количество информации, искать в глобальной сети и т.д.

Т.е. по сути Интернет и есть — Шестое Чувство!

Видео по катом
Читать дальше →
Total votes 37: ↑32 and ↓5 +27
Comments 52

Information

Rating
Does not participate
Registered
Activity