東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Learning, cryptography, and the aver...

Wan, Andrew.

FindBook

Google Book

Amazon

博客來

Learning, cryptography, and the average case.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Learning, cryptography, and the average case./
作者:	Wan, Andrew.
面頁冊數:	134 p.
附註:	Source: Dissertation Abstracts International, Volume: 71-09, Section: B, page: 5592.
Contained By:	Dissertation Abstracts International71-09B.
標題:	Applied Mathematics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3420728
ISBN:	9781124174419

Learning, cryptography, and the average case.
Wan, Andrew.

Learning, cryptography, and the average case. - 134 p.

Source: Dissertation Abstracts International, Volume: 71-09, Section: B, page: 5592.

Thesis (Ph.D.)--Columbia University, 2010.

This thesis explores problems in computational learning theory from an average-case perspective. Through this perspective we obtain a variety of new results for learning theory and cryptography.

ISBN: 9781124174419Subjects--Topical Terms:

1669109
Applied Mathematics.

Learning, cryptography, and the average case.
LDR:05227nam 2200313 4500 001 1396634
005 20110610084502.5
008 130515s2010 ||||||||||||||||| ||eng d
020 $a 9781124174419
035 $a (UMI)AAI3420728
035 $a AAI3420728
040 $a UMI $c UMI
100 1 $a Wan, Andrew. $3 1675422
245 1 0 $a Learning, cryptography, and the average case.
300 $a 134 p.
500 $a Source: Dissertation Abstracts International, Volume: 71-09, Section: B, page: 5592.
500 $a Advisers: Rocco Servedio; Tal Malkin.
502 $a Thesis (Ph.D.)--Columbia University, 2010.
520 $a This thesis explores problems in computational learning theory from an average-case perspective. Through this perspective we obtain a variety of new results for learning theory and cryptography.
520 $a Several major open questions in computational learning theory revolve around the problem of efficiently learning polynomial-size DNF formulas, which dates back to Valiant's introduction of the PAC learning model [Valiant, 1984]. We apply an average-case analysis to make progress on this problem in two ways. (1) We prove that Mansour's conjecture is true for random DNF. In 1994, Y. Mansour conjectured that for every DNF formula on n variables with t terms there exists a polynomial p with tO(log(1/epsilon)) non-zero coefficients such that Ex∈0,1 n [(p(x) - f( x))2] ≤ epsilon. We make the first progress on this conjecture and show that it is true for several natural subclasses of DNF formulas including randomly chosen DNF formulas and read-k DNF formulas. Our result yields the first polynomial-time query algorithm for agnostically learning these subclasses of DNF formulas with respect to the uniform distribution on {0, 1}n (for any constant error parameter and constant k). Applying recent work on sandwiching polynomials, our results imply that t -O(log 1/epsilon)-biased distributions fool the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work. (2) We give an efficient algortihm that learns random monotone DNF. The problem of efficiently learning the monotone subclass of polynomial-size DNF formulas from random examples was also posed in [Valiant, 1984]. This notoriously difficult question is still open, despite much study and the fact that known impediments to learning the non-monotone class (cf. [Blum et al., 1994; Blum, 2003a]) do not exist for monotone DNF formulas. We give the first algorithm that learns randomly chosen monotone DNF formulas of arbitrary polynomial size, improving results which efficiently learn n2-epsilon-size random monotone DNF formulas [Jackson and Servedio, 2005b]. Our main structural result is that most monotone DNF formulas reveal their term structure in their constant-degree Fourier coefficients.
520 $a In this thesis, we also see that connections between learning and cryptography are naturally made through average-case analysis. First, by applying techniques from average-case complexity, we demonstrate new ways of using cryptographic assumptions to prove limitations on learning. As counterpoint, we also exploit the average-case connection in the service of cryptography. Below is a more detailed description of these contributions. (1) We show that monotone polynomial-sized circuits are hard to learn if one-way functions exist. We establish the first cryptographic hardness results for learning polynomial-size classes of monotone circuits, giving a computational analogue of the information-theoretic hardness results of [Blum et al., 1998]. Some of our results show the cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2 + 1/ n ; this is close to the optimal accuracy bound, by positive results of Blum, et al. Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O'Donnell [O'Donnell, 2004a]. (2) Learning an overcomplete basis: analysis of lattice-based signatures with perturbations. Lattice-based cryptographic constructions are desirable not only because they provide security based on worst-case hardness assumptions, but also because they can be extremely efficient and practical. We propose a general technique for recovering parts of the secret key in lattice-based signature schemes that follow the Goldreich-Goldwasser-Halevi (GGH) and NTRUSign design with perturbations. Our technique is based on solving a learning problem in the average-case. To solve the average-case problem, we propose a special-purpose optimization algorithm based on higher-order cumulants of the signature distribution, and give theoretical and experimental evidence of its efficacy. Our results suggest (but do not conclusively prove) that NTRUSign is vulnerable to a polynomial-time attack.
590 $a School code: 0054.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Computer Science. $3 626642
690 $a 0364
690 $a 0984
710 2 $a Columbia University. $3 571054
773 0 $t Dissertation Abstracts International $g 71-09B.
790 1 0 $a Servedio, Rocco, $e advisor
790 1 0 $a Malkin, Tal, $e advisor
790 $a 0054
791 $a Ph.D.
792 $a 2010
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3420728