자료유형  

 학위논문

Control Number  

0016932804

International Standard Book Number  

9798379847777

Dewey Decimal Classification Number  

519.4

Main Entry-Personal Name  

Block, Alexander R.

Publication, Distribution, etc. (Imprint  

[S.l.] : Purdue University., 2022

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2022

Physical Description  

1 online resource(278 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-01, Section: B.

General Note  

Advisor: Blocki, Jeremiah.

Dissertation Note  

Thesis (Ph.D.)--Purdue University, 2022.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약We examine new ways in which coding theory and cryptography continue to be composed together, and show that the composition of these two fields yield new constructions in the areas of Secure Computation Protocols, Succinct Interactive Arguments, and Locally Decodable Codes. This dissertation is a continuation of several decades of research in composing coding theory and cryptography; examples include secret sharing, encryption schemes, randomness extraction, pseudo-random number generation, and the PCP theorem, to name a few.In Part I of this dissertation, we examine the composition of coding theory with cryptography, explicitly and implicitly. On the explicit side, we construct a new family of linear error-correcting codes, based on algebraic geometric codes, and use this family to construct new correlation extractors (Ishai et al., FOCS 2009). Correlation extractors are two-party secure computation protocols for distilling samples of a leaky correlation (e.g., pre-processed secret shares that have been exposed to side-channel attacks) into secure and fresh shares of another correlation (e.g., shares of oblivious transfer). Our correlation extractors are (nearly) optimal in all parameters. On the implicit side, we use coding theoretic arguments to show the security of succinct interactive arguments(Micali, FOCS 1994). Succinct interactive arguments are a restriction of interactive proofs (Goldwasser, Micali, Rackoff, STOC 1985) for which security only holds against computationally bounded provers (i.e., probabilistic polynomial time), and where the proofs are sub-linear in the size of the statement being proven. Our new succinct interactive arguments are the first public-coin, zero-knowledge arguments with time and space efficient provers: we give two protocols where any NP statement that is verifiable by a time-T space-S RAM program in is provable time O˜(T) and space S · polylog(T).In Part II of this dissertation, we examine the composition of cryptography with coding theory, again explicitly and implicitly, focusing specifically on locally decodable codes (Katz and Trevisan, STOC 2000). Locally decodable codes, or LDCs, are error-correcting codes with super-efficient probabilistic decoding procedures that allow for decoding individual symbols of the encoded message, without decoding the entire codeword. On the implicit side, we utilize cryptographic analysis tools to give a conceptually simpler proof of the so-called "Hamming-to-InsDel" compiler (Ostrovsky and Paskin-Cherniavsky, ITS 2015). This compiler transforms any Hamming LDC (i.e., a code that is resilient to bit-flip errors) to another LDC that is resilient to the broad class of insertion-deletion errors, approximately preserving the rate and error-tolerance of the code at the cost of a poly-logarithmic increase in the query complexity. We further extend this compiler to both the private LDC setting (Ostrovsky, Pandey, and Sahai, ICALP 2007), where the encoder and decoder are assumed to share a secret key unknown to the adversarial channel, and the resource-bounded LDC setting (Blocki, Kulkarni, and Zhou, ITC 2020), where the adversarial channel is assumed to be resource constrained. On the explicit side, we utilize two cryptographic primitives to give new constructions of alternative notions of LDCs. First, we use cryptographic puzzles(Bitansky et al., ITCS 2016) to construct resource-bounded Hamming LDCs in the standard model without random oracles, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020); we then naturally extend these LDCs to the InsDel setting via our previously mentioned compiler.

Subject Added Entry-Topical Term  

Coding theory.

Subject Added Entry-Topical Term  

Polynomials.

Subject Added Entry-Topical Term  

Codes.

Subject Added Entry-Topical Term  

Digital signatures.

Subject Added Entry-Topical Term  

Linear codes.

Subject Added Entry-Topical Term  

Mathematics.

Added Entry-Corporate Name  

Purdue University.

Host Item Entry  

Dissertations Abstracts International. 85-01B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:643775