Scientific goal of project


Advanced search

Message boards : Science : Scientific goal of project

AuthorMessage
evatutin
Send message
Joined: Oct 11 11
Posts: 1
Credit: 8,120,604
RAC: 0
Message 2 - Posted 12 Oct 2011 8:44:36 UTC

    Last modified: 12 Oct 2011 8:51:08 UTC

    ????????? ?????? ???????, ???????? ??????????, ????? ???????? ???? ?????????? ??? ??????? ? ????? ?????????? ???????? ????? ???? ???????????? ?????????? ??????????? ?????????????? ?? ??? ????? ????????????? ??? ???? ?????? ???????? ???????????

    Dear authors of the project, please explain what the end goals pursued your project? In which application areas can be used obtained results? Whether they are limited to cryptography only or there are have other useful applications?

    PS. As you can see above russian language is not correctly working in this forum...

    Profile Oleg Zaikin [SAT@home]
    Forum moderator
    Project administrator
    Project developer
    Project scientist
    Send message
    Joined: Sep 15 11
    Posts: 133
    Credit: 4,826,453
    RAC: 0
    Message 3 - Posted 12 Oct 2011 11:46:31 UTC - in response to Message 2.

      Last modified: 12 Oct 2011 14:55:00 UTC

      Current goal in cryptographic area is to solve about 10 SAT problems for the generator A5/1 in few months. This generator is used in GSM standart for data encryption. Open scientific research of A5/1 is useful for creating new standarts. Our current results in this area you can find here and here
      About other areas I will write later.

      PS. About supporting of the russian language. Thanks for your message, we are working on it.

      Profile Oleg Zaikin [SAT@home]
      Forum moderator
      Project administrator
      Project developer
      Project scientist
      Send message
      Joined: Sep 15 11
      Posts: 133
      Credit: 4,826,453
      RAC: 0
      Message 9 - Posted 12 Oct 2011 15:03:36 UTC - in response to Message 2.


        PS. As you can see above russian language is not correctly working in this forum...


        Проблема с русской кодировкой решена.

        Profile 7ri9991 [MM]
        Avatar
        Send message
        Joined: Oct 12 11
        Posts: 2
        Credit: 107,636
        RAC: 0
        Message 14 - Posted 12 Oct 2011 23:19:13 UTC - in response to Message 9.


          PS. As you can see above russian language is not correctly working in this forum...


          Проблема с русской кодировкой решена.


          Works for me, though the question marks make almost as much sense to me.

          It amazes me when someone with a language so different learns English.

          Profile Nikolay A. Saharov
          Send message
          Joined: Oct 12 11
          Posts: 4
          Credit: 347,999
          RAC: 0
          Message 32 - Posted 14 Oct 2011 16:50:31 UTC - in response to Message 9.


            PS. As you can see above russian language is not correctly working in this forum...


            Проблема с русской кодировкой решена.


            В личных сообщениях пока еще осталась проблема с кириллицей.
            ____________

            Profile Oleg Zaikin [SAT@home]
            Forum moderator
            Project administrator
            Project developer
            Project scientist
            Send message
            Joined: Sep 15 11
            Posts: 133
            Credit: 4,826,453
            RAC: 0
            Message 33 - Posted 15 Oct 2011 0:28:05 UTC - in response to Message 32.


              PS. As you can see above russian language is not correctly working in this forum...


              Проблема с русской кодировкой решена.


              В личных сообщениях пока еще осталась проблема с кириллицей.


              Спасибо, исправим.

              Profile Oleg Zaikin [SAT@home]
              Forum moderator
              Project administrator
              Project developer
              Project scientist
              Send message
              Joined: Sep 15 11
              Posts: 133
              Credit: 4,826,453
              RAC: 0
              Message 36 - Posted 17 Oct 2011 15:52:46 UTC - in response to Message 32.


                PS. As you can see above russian language is not correctly working in this forum...


                Проблема с русской кодировкой решена.


                В личных сообщениях пока еще осталась проблема с кириллицей.


                Проблема с кириллицей в личных сообщениях решена.

                Profile Oleg Zaikin [SAT@home]
                Forum moderator
                Project administrator
                Project developer
                Project scientist
                Send message
                Joined: Sep 15 11
                Posts: 133
                Credit: 4,826,453
                RAC: 0
                Message 37 - Posted 17 Oct 2011 15:55:30 UTC - in response to Message 36.

                  Last modified: 17 Oct 2011 16:03:58 UTC

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

                  Описание
                  Проект предполагает решение разнообразных комбинаторных задач. Известно множество важных в практическом отношении задач, для решения которых на данный момент не доказано наличие эффективных (полиномиальных) алгоритмов. Большинство таких задач являются NP-трудными. Это означает, что при некоторых разумных (хоть и не доказанных) предположениях данные задачи вообще не могут быть решены за полиномиальное время. Однако решать частные случаи таких задач все равно приходится, так как это востребовано практикой: это и различные задачи дискретной оптимизации (например, задачи планирования производств), и задачи верификации дискретных устройств (возникающие, например, при разработке микросхем или доказательстве корректности программ). Поэтому крайне важно иметь для их решения методы, которые являются «эффективными» если и не в строгом понимании (то есть не обладают полиномиальной сложностью), то хотя бы на практике. Такие методы могут успешно справляться с многочисленными частными случаями NP-трудных задач огромных размерностей. Одним из наиболее простых в своей основе и поэтому наиболее эффективным в плане программных реализаций является SAT-подход. Данный подход предполагает сводимость рассматриваемой исходной задачи к некоторой SAT-задаче, то есть к задаче о выполнимости конъюнктивной нормальной формы (КНФ). SAT-задачи допускают очень естественные формы распараллеливания, позволяющие использовать для их решения распределенные вычислительные среды (в том числе Grid). Собственно сводимость к SAT осуществляется эффективно (по сути, это содержание знаменитой теоремы Кука). Крайне привлекательным классом задач, для решения которых можно использовать SAT-подход, являются задачи криптоанализа. Сразу оговоримся, что мы не решаем задачи дешифровки реальных конфиденциальных данных. Все рассматриваемые нами тесты сгенерированы случайным образом. В этом плане наша работа направлена на исследование стойкости современных систем шифрования и подразумевает реальную помощь в создании новых систем шифрования. Наиболее сильным достигнутым нами практическим результатом является успешный логический криптоанализ (то есть в форме SAT-задачи) генератора ключевого потока широко известного шифра A5/1. Данный результат был получен в 2009 году с использованием системы BNB-Grid (статья 1, статья 2). В 2010-2011 годах появились исследования (см., например, эту работу), в которых также был осуществлен реальный криптоанализ A5/1, но с использованием совершенно других методов (по сути, использовалась продвинутая техника rainbow-таблиц). Однако даже самые хорошие rainbow-таблицы не покрывают все ключевое пространство на 100%. Поэтому в ближайшей перспективе в рамках SAT@home предполагается решение задач поиска инициализирующих последовательностей для A5/1, не покрываемых лучшими известными rainbow-таблицами. В дальнейшем предполагается использовать SAT@home для исследования других криптографических функций, для решения некоторых «крайне трудных» задач дискретной оптимизации, в частности, квадратичной задачи о назначениях (QAP), а также задач из области биоинформатики (исследование поведения дискретных моделей генных сетей).

                  [small]Edited by Nauchnik on 2011-10-17 20:02.[/small]

                  [small]Edited by Nauchnik on 2011-10-17 20:06.[/small]

                  quel
                  Send message
                  Joined: Nov 21 11
                  Posts: 6
                  Credit: 10,109,026
                  RAC: 0
                  Message 68 - Posted 21 Nov 2011 20:53:26 UTC - in response to Message 37.

                    Google translate seems to do a decent job, I just had to manually set the page encoding to UTF-8 first. The problem is that you need to send the proper HTTP headers for the language/character set or it will default to the user's locale and then garbled text for many of us.

                    At least one of your referenced papers I have read in the past and have some more reading to do now. Keep us all posted on new papers, achievements, goals, etc. as this is a great area of interest for me.

                    At first when I read the news section my thought was that the rainbow tables for A5/1 already exist and this was not an interesting cipher to study. However, you are correct they are not 100% but I do not recall the success rate. I am an admin for a BOINC project that generates different rainbow tables though, Free Rainbow Tables, and we focus on 99.9% success rates normally.

                    I look forward to crunching on this project and future progress with SAT solving and ciphers!

                    Profile Oleg Zaikin [SAT@home]
                    Forum moderator
                    Project administrator
                    Project developer
                    Project scientist
                    Send message
                    Joined: Sep 15 11
                    Posts: 133
                    Credit: 4,826,453
                    RAC: 0
                    Message 69 - Posted 22 Nov 2011 9:26:17 UTC - in response to Message 68.

                      Last modified: 22 Nov 2011 10:09:26 UTC

                      Google translate seems to do a decent job, I just had to manually set the page encoding to UTF-8 first. The problem is that you need to send the proper HTTP headers for the language/character set or it will default to the user's locale and then garbled text for many of us.

                      At least one of your referenced papers I have read in the past and have some more reading to do now. Keep us all posted on new papers, achievements, goals, etc. as this is a great area of interest for me.

                      At first when I read the news section my thought was that the rainbow tables for A5/1 already exist and this was not an interesting cipher to study. However, you are correct they are not 100% but I do not recall the success rate. I am an admin for a BOINC project that generates different rainbow tables though, Free Rainbow Tables, and we focus on 99.9% success rates normally.

                      I look forward to crunching on this project and future progress with SAT solving and ciphers!


                      Hello, colleague!
                      1. About garbling - if you are talking about text in section "Science", I will try to translate it into English in few days.
                      2. About out current work. We have downloaded rainbow table (1.6 TB) form A5/1 Cracking project. Now we are trying to find keystreams that can't be processed by it. I will report the % when we will finish.
                      3. About articles - we will post here everything about SAT@home.

                      PS. Thank you for your participation! I will crunch in your project too.

                      Profile Oleg Zaikin [SAT@home]
                      Forum moderator
                      Project administrator
                      Project developer
                      Project scientist
                      Send message
                      Joined: Sep 15 11
                      Posts: 133
                      Credit: 4,826,453
                      RAC: 0
                      Message 77 - Posted 23 Nov 2011 16:14:12 UTC - in response to Message 69.

                        New section Science was prepeared http://sat.isa.ru/pdsat/science.php.

                        Profile T-Armstrong
                        Send message
                        Joined: Dec 23 11
                        Posts: 1
                        Credit: 19,611
                        RAC: 0
                        Message 138 - Posted 16 Feb 2012 21:07:14 UTC - in response to Message 77.

                          I want to create an Profile...Error.

                          Server problems ?

                          Profile ISDCT_Lab_3.2
                          Send message
                          Joined: Sep 22 11
                          Posts: 2
                          Credit: 2,230
                          RAC: 0
                          Message 139 - Posted 18 Feb 2012 11:23:39 UTC - in response to Message 138.

                            I want to create an Profile...Error.

                            Server problems ?


                            You are right, we will try to fix it.

                            Ryan
                            Send message
                            Joined: Jun 13 12
                            Posts: 2
                            Credit: 0
                            RAC: 0
                            Message 186 - Posted 14 Jun 2012 0:06:19 UTC

                              I have a BS Degree in Computer Science with a minor in math and had discrete math and Calc III (not too much math to really understand what these guys are trying to do) but I an amateur to think it's cool enough to participate. :p

                              -Ryan

                              Post to thread

                              Message boards : Science : Scientific goal of project


                              Home | My Account | Message Boards


                              Copyright © 2019 Institute for System Dynamics and Control Theory of SB RAS and Institute for Information Transmission Problems of RAS