Indistinguishability Obfuscation from Well-Studied Assumptions.

Format:

Book

Author/Creator:

Jain, Aayush.

Series:

ACM Bks.

Language:

English

Subjects (All):

Cryptography.

Algorithms.

Physical Description:

1 online resource (178 pages)

Edition:

1st ed.

Place of Publication:

New York : Morgan & Claypool Publishers, 2025.

Summary:

Software obfuscation is used in cryptography to transform source code to make it unintelligible without altering what it computes. The research described in this book, for which the author won the ACM Dissertation Award, establishes the feasibility of mathematically rigorous software obfuscation from well-studied hardness conjectures.

Contents:

Intro

Indistinguishability Obfuscation from Well-Studied Assumptions

Contents

Preface

Acknowledgments

1 Introduction

1.1 Definition and History

History of definition

1.2 Our Results

1.2.1 Applications

1.2.1.1 Homomorphic Encryption without Lattices

1.3 Assumptions in More Detail

The DLIN assumption

The existence of PRGs in NC0

LPN over prime fields

On search vs. decision versions of our assumptions

1.4 Prior Work on Feasibility of iO

1.5 Open Problems

1.6 Organization

2 Technical Roadmap

2.1 Preliminaries

Multilinear Representation of Polynomials and Representation over Zp

Computational Indistinguishability

2.2 High-level Approach

Sublinear Functional Encryption

Constructing Sublinear Functional Encryption

Using Degree-2 FE

Allowing Preprocessing

Partially Hiding FE

Preprocessed Randomized Encoding

2.2.1 How to Construct Preprocessed Randomized Encoding

Time Succinctness versus Size Succinctness

High-level Approach for PRE

New Tool: Preprocessed Polynomial Encoding

Constructing Preprocessed Polynomial Encoding

PPE: First Attempt

Amortization

Constructing PRE Using (Amortized) PPE

Constructing PPE

Computing Si

Computability of Si in Sublinear Time

2.2.1.1 Outline

2.3 Functional Encryption Definition

2.3.1 Bootstrapping Theorems for Functional Encryption to iO

2.4 Ingredient 1: PHFE

Function class FPHFE

2.5 Ingredient 2: Preprocessed Randomized Encoding

Function Class

2.5.1 Correctness and Security Requirements

2.5.2 The Efficiency and Complexity Requirements

2.6 Bootstrapping to Functional Encryption

Parameters

Correctness

Sublinearity

Security

2.7 Outline

3 Preprocessed Randomized Encoding

3.1 Technical Outline: Preprocessed Randomized Encoding.

3.1.1 Preprocessed Polynomial Encoding

3.1.2 Amortized Randomized Encoding

Efficiency Properties

3.1.3 Construction of Preprocessed Randomized Encoding

Ingredients:

Correctness:

Security:

Sublinear Efficiency

Complexity Requirement

Summing Up

4 Preprocessed Polynomial Encoding

Preprocessed polynomial encoding

4.1 Overview of the Construction

The LPN assumption

Encrypting x using LPN assumption

How to set S?

Correcting monomials

Functionality

Sublinear time

4.2 PPE Construction Details

Complexity of evaluation

4.2.1 Sublinear Time Preprocessing

4.2.1.1 Useful Lemmas about Circuit Implementability

4.2.1.2 Sublinear Preprocessing Efficiency

Preprocessing efficiency

Size of the circuit computing (P1,…,PkPPE)

Size of the circuit computing S0

Size of the circuit computing (flag,S1,…,SmPPE)

Circuit G1

Circuit G2

Circuit G3,r

Circuit G4

Overall circuit-size calculation

Summing up

5 Amortized Randomized Encoding

5.1 Amortized Randomized Encoding

5.1.1 Overall Approach

First Idea

Inspecting Yao

Using PRG in NC0

Fixing the Monomial Pattern Issue

5.2 Construction Details

Notation

Tool

Indistinguishability Security

Efficiency

6 Partially Hiding Functional Encryption

6.1 Notations and Bilinear Map Preliminaries

6.1.1 Prime Order Bilinear Maps

Assumptions over Bilinear Maps

6.2 Constructing PHFE

6.2.1 Overview

Recalling the requirement

6.2.1.1 Simplified Setting: Constructing Quadratic Functional Encryption

A Useful Tool

Quadratic FE, Summing Up

6.2.2 Construction Details for PHFE

Linear Efficiency

Security Proof

6.2.3 Constructing PHFE1

A Useful Tool: Partial Garbling Scheme [Ishai and Wee 2014].

Using IPE

A Note on the Function Class

7 Open Questions and Concluding Remarks

Bibliography

Author's Biography

Index.

Notes:

Description based on publisher supplied metadata and other sources.

Part of the metadata in this record was created by AI, based on the text of the resource.

ISBN:

9798400713682

OCLC:

1514636308