pir

package
v0.0.0-...-dee1182 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 28, 2023 License: MIT Imports: 21 Imported by: 6

Documentation

Index

Constants

View Source 
const COMP_RATIO = uint64(64)

Ratio between first-level DB and second-level DB

Variables

This section is empty.

Functions

func ApproxDatabaseDims 

func ApproxDatabaseDims(N, row_length, p, lower_bound_m uint64) (uint64, uint64)

Find smallest l, m such that l*m >= N*ne and ne divides l, where ne is the number of Z_p elements per DB entry determined by row_length and p, and m >= lower_bound_m.

func ApproxSquareDatabaseDims 

func ApproxSquareDatabaseDims(N, row_length, p uint64) (uint64, uint64)

Find smallest l, m such that l*m >= N*ne and ne divides l, where ne is the number of Z_p elements per DB entry determined by row_length and p.

func ApproxSquareStrDatabaseDims 

func ApproxSquareStrDatabaseDims(N, row_length, p uint64, Item_bits uint64) (uint64, uint64)

func Base_p 

func Base_p(p, m, i uint64) uint64

Returns the i-th elem in the representation of m in base p.

func Compute_num_entries_base_p 

func Compute_num_entries_base_p(p, log_q uint64) uint64

Returns how many entries in Z_p are needed to represent an element in Z_q

func Compute_num_str_entries_base_p 

func Compute_num_str_entries_base_p(p, log_q uint64, Item_bits uint64) uint64

Returns how many entries in Z_p are needed to represent an element in Z_q

func FindLongestElement 

func FindLongestElement(slice []string) string

func GaussSample 

func GaussSample() int64

The function below is modeled on Martin Albrecht's discrete-Gaussian sampler included in his dgs library: 

https://github.com/malb/dgs

func LoadFile 

func LoadFile(filepath, col_name string) []string

func MathRand 

func MathRand() *mrand.Rand

func Num_DB_entries 

func Num_DB_entries(N, row_length, p uint64) (uint64, uint64, uint64)

Returns how many Z_p elements are needed to represent a database of N entries, each consisting of row_length bits.

func Num_StrDB_entries 

func Num_StrDB_entries(N, row_length, p uint64, Item_bits uint64) (uint64, uint64, uint64)

func PrintTime 

func PrintTime(start time.Time) time.Duration

func RandInt 

func RandInt(mod *big.Int) *big.Int

Produce a random integer in Z_p where mod is the value p.

func ReconstructElem 

func ReconstructElem(vals []uint64, index uint64, info DBinfo) uint64

Store the database with entries decomposed into Z_p elements, and mapped to [-p/2, p/2] Z_p elements that encode the same database entry are stacked vertically below each other.

func Reconstruct_from_base_p 

func Reconstruct_from_base_p(p uint64, vals []uint64) uint64

Returns the element whose base-p decomposition is given by the values in vals

func RunFakePIR 

func RunFakePIR(pi PIR, DB *Database, p Params, i []uint64,
	f *os.File, profile bool) (float64, float64, float64, float64)

Run PIR's online phase, with a random preprocessing (to skip the offline phase). Gives accurate bandwidth and online time measurements.

func RunMyPIR 

func RunMyPIR(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)

Run My PIR scheme (offline + online phases).

func RunPIR 

func RunPIR(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)

Run full PIR scheme (offline + online phases).

func RunPIRCompressed 

func RunPIRCompressed(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)

Run full PIR scheme (offline + online phases), where the transmission of the A matrix is compressed.

Types

type BufPRGReader 

type BufPRGReader struct {
	mrand.Source64
	Key PRGKey
	// contains filtered or unexported fields
}

func NewBufPRG 

func NewBufPRG(prg *PRGReader) *BufPRGReader

func (*BufPRGReader) Int63 

func (b *BufPRGReader) Int63() int64

func (*BufPRGReader) RandInt 

func (b *BufPRGReader) RandInt(mod *big.Int) *big.Int

func (*BufPRGReader) Seed 

func (b *BufPRGReader) Seed(int64)

func (*BufPRGReader) Uint64 

func (b *BufPRGReader) Uint64() uint64

type CompressedState 

type CompressedState struct {
	Seed *PRGKey
}

func MakeCompressedState 

func MakeCompressedState(elem *PRGKey) CompressedState

type DBinfo 

type DBinfo struct {
	Num        uint64 // number of DB entries.
	Row_length uint64 // number of bits per DB entry.

	Packing uint64 // number of DB entries per Z_p elem, if log(p) > DB entry size.
	Ne      uint64 // number of Z_p elems per DB entry, if DB entry size > log(p).

	X uint64 // tunable param that governs communication,
	// must be in range [1, ne] and must be a divisor of ne;
	// represents the number of times the scheme is repeated.
	P    uint64 // plaintext modulus.
	Logq uint64 // (logarithm of) ciphertext modulus.

	// For in-memory DB compression
	Basis     uint64
	Squishing uint64
	Cols      uint64

	// bits of item in each entry, used in storing string type
	Item_bits uint64
}

type Database 

type Database struct {
	Info DBinfo
	Data *Matrix
}

func MakeDB 

func MakeDB(Num, row_length uint64, p *Params, vals []uint64) *Database

func MakeMyDB 

func MakeMyDB(Num, row_length uint64, p *Params, valslice [][]uint64) *Database

func MakeRandomDB 

func MakeRandomDB(Num, row_length uint64, p *Params) *Database

func MakeStrDB 

func MakeStrDB(Num, row_length uint64, p *Params, svals []string) *Database

func SetupDB 

func SetupDB(Num, row_length uint64, p *Params) *Database

func SetupStrDB 

func SetupStrDB(Num, row_length uint64, p *Params) *Database

func (*Database) GetElem 

func (DB *Database) GetElem(i uint64) uint64

get i-th entry in database

func (*Database) Squish 

func (DB *Database) Squish()

func (*Database) Unsquish 

func (DB *Database) Unsquish()

type DoublePIR 

type DoublePIR struct{}

func (*DoublePIR) Answer 

func (pi *DoublePIR) Answer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg

func (*DoublePIR) DecompressState 

func (pi *DoublePIR) DecompressState(info DBinfo, p Params, comp CompressedState) State

func (*DoublePIR) FakeSetup 

func (pi *DoublePIR) FakeSetup(DB *Database, p Params) (State, float64)

func (*DoublePIR) GetBW 

func (pi *DoublePIR) GetBW(info DBinfo, p Params)

func (*DoublePIR) Init 

func (pi *DoublePIR) Init(info DBinfo, p Params) State

func (*DoublePIR) InitCompressed 

func (pi *DoublePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)

func (*DoublePIR) InitCompressedSeeded 

func (pi *DoublePIR) InitCompressedSeeded(info DBinfo, p Params, seed *PRGKey) (State, CompressedState)

func (*DoublePIR) MyAnswer 

func (pi *DoublePIR) MyAnswer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg

func (*DoublePIR) MyInit 

func (pi *DoublePIR) MyInit(info DBinfo, p Params) State

func (*DoublePIR) MyQuery 

func (pi *DoublePIR) MyQuery(i []uint64, shared State, p Params, info DBinfo) (State, Msg)

func (*DoublePIR) MyRecover 

func (pi *DoublePIR) MyRecover(i []uint64, batch_index uint64, offline Msg, query Msg,
	answer Msg, shared State, client State, p Params, info DBinfo) []uint64

func (*DoublePIR) MySetup 

func (pi *DoublePIR) MySetup(DB *Database, shared State, p Params) (State, Msg)

func (*DoublePIR) Name 

func (pi *DoublePIR) Name() string

func (*DoublePIR) PickParams 

func (pi *DoublePIR) PickParams(N, d, n, logq uint64) Params

func (*DoublePIR) PickParamsGivenDimensions 

func (pi *DoublePIR) PickParamsGivenDimensions(l, m, n, logq uint64) Params

func (*DoublePIR) Query 

func (pi *DoublePIR) Query(i uint64, shared State, p Params, info DBinfo) (State, Msg)

func (*DoublePIR) Recover 

func (pi *DoublePIR) Recover(i uint64, batch_index uint64, offline Msg, query Msg,
	answer Msg, shared State, client State, p Params, info DBinfo) uint64

func (*DoublePIR) Reset 

func (pi *DoublePIR) Reset(DB *Database, p Params)

func (*DoublePIR) Setup 

func (pi *DoublePIR) Setup(DB *Database, shared State, p Params) (State, Msg)

type Matrix 

type Matrix struct {
	Rows uint64
	Cols uint64
	Data []C.Elem
}

func MatrixGaussian 

func MatrixGaussian(rows, cols uint64) *Matrix

func MatrixMul 

func MatrixMul(a *Matrix, b *Matrix) *Matrix

func MatrixMulTransposedPacked 

func MatrixMulTransposedPacked(a *Matrix, b *Matrix, basis, compression uint64) *Matrix

func MatrixMulVec 

func MatrixMulVec(a *Matrix, b *Matrix) *Matrix

func MatrixMulVecPacked 

func MatrixMulVecPacked(a *Matrix, b *Matrix, basis, compression uint64) *Matrix

func MatrixNew 

func MatrixNew(rows uint64, cols uint64) *Matrix

func MatrixNewNoAlloc 

func MatrixNewNoAlloc(rows uint64, cols uint64) *Matrix

func MatrixRand 

func MatrixRand(rows uint64, cols uint64, logmod uint64, mod uint64) *Matrix

func MatrixZeros 

func MatrixZeros(rows uint64, cols uint64) *Matrix

func MyMatrixMul 

func MyMatrixMul(a *Matrix, a_col_packing uint64, b *Matrix, b_row_packing uint64) *Matrix

func (*Matrix) Add 

func (a *Matrix) Add(val uint64)

func (*Matrix) AddAt 

func (a *Matrix) AddAt(val, i, j uint64)

func (*Matrix) AppendZeros 

func (m *Matrix) AppendZeros(n uint64)

func (*Matrix) Concat 

func (a *Matrix) Concat(b *Matrix)

func (*Matrix) ConcatCols 

func (m *Matrix) ConcatCols(n uint64)

func (*Matrix) Contract 

func (m *Matrix) Contract(mod uint64, delta uint64)

Computes the inverse operations of Expand(.)

func (*Matrix) Dim 

func (m *Matrix) Dim()

func (*Matrix) DropLastRows 

func (m *Matrix) DropLastRows(n uint64)

func (*Matrix) Expand 

func (m *Matrix) Expand(mod uint64, delta uint64)

Represent each element in the database with 'delta' elements in Z_'mod'. Then, map the database elements from [0, mod] to [-mod/2, mod/2].

func (*Matrix) Get 

func (m *Matrix) Get(i, j uint64) uint64

func (*Matrix) MatrixAdd 

func (a *Matrix) MatrixAdd(b *Matrix)

func (*Matrix) MatrixSub 

func (a *Matrix) MatrixSub(b *Matrix)

func (*Matrix) Print 

func (m *Matrix) Print()

func (*Matrix) PrintStart 

func (m *Matrix) PrintStart()

func (*Matrix) ReduceMod 

func (m *Matrix) ReduceMod(p uint64)

func (*Matrix) Round 

func (m *Matrix) Round(p Params)

func (*Matrix) RowsDeepCopy 

func (m *Matrix) RowsDeepCopy(offset, num_rows uint64) *Matrix

func (*Matrix) SelectColumn 

func (m *Matrix) SelectColumn(i uint64) *Matrix

func (*Matrix) SelectRows 

func (m *Matrix) SelectRows(offset, num_rows uint64) *Matrix

func (*Matrix) Set 

func (m *Matrix) Set(val, i, j uint64)

func (*Matrix) Size 

func (m *Matrix) Size() uint64

func (*Matrix) Squish 

func (m *Matrix) Squish(basis, delta uint64)

Compresses the matrix to store it in 'packed' form. Specifically, this method squishes the matrix by representing each group of 'delta' consecutive values as a single database element, where each value uses 'basis' bits.

func (*Matrix) Sub 

func (a *Matrix) Sub(val uint64)

func (*Matrix) Transpose 

func (m *Matrix) Transpose()

func (*Matrix) TransposeAndExpandAndConcatColsAndSquish 

func (m *Matrix) TransposeAndExpandAndConcatColsAndSquish(mod, delta, concat, basis, d uint64)

func (*Matrix) Unsquish 

func (m *Matrix) Unsquish(basis, delta, cols uint64)

Computes the inverse operation of Squish(.)

type Msg 

type Msg struct {
	Data []*Matrix
}

func MakeMsg 

func MakeMsg(elems ...*Matrix) Msg

func (*Msg) Size 

func (m *Msg) Size() uint64

type MsgSlice 

type MsgSlice struct {
	Data []Msg
}

func MakeMsgSlice 

func MakeMsgSlice(elems ...Msg) MsgSlice

func (*MsgSlice) Size 

func (m *MsgSlice) Size() uint64

type PIR 

type PIR interface {
	Name() string

	PickParams(N, d, n, logq uint64) Params
	PickParamsGivenDimensions(l, m, n, logq uint64) Params

	GetBW(info DBinfo, p Params)

	Init(info DBinfo, p Params) State
	MyInit(info DBinfo, p Params) State
	InitCompressed(info DBinfo, p Params) (State, CompressedState)
	DecompressState(info DBinfo, p Params, comp CompressedState) State

	Setup(DB *Database, shared State, p Params) (State, Msg)
	MySetup(DB *Database, shared State, p Params) (State, Msg)
	FakeSetup(DB *Database, p Params) (State, float64) // used for benchmarking online phase

	Query(i uint64, shared State, p Params, info DBinfo) (State, Msg)
	MyQuery(i []uint64, shared State, p Params, info DBinfo) (State, Msg)

	Answer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg
	MyAnswer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg

	Recover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg, shared State, client State,
		p Params, info DBinfo) uint64
	MyRecover(i []uint64, batch_index uint64, offline Msg, query Msg, answer Msg, shared State, client State,
		p Params, info DBinfo) []uint64

	Reset(DB *Database, p Params) // reset DB to its correct state, if modified during execution
}

Defines the interface for PIR with preprocessing schemes

type PRGKey 

type PRGKey [aes.BlockSize]byte

func RandomPRGKey 

func RandomPRGKey() *PRGKey

type PRGReader 

type PRGReader struct {
	Key PRGKey
	// contains filtered or unexported fields
}

We use the AES-CTR to generate pseudo-random numbers using a stream cipher. Go's native rand.Reader is extremely slow because it makes tons of system calls to generate a small number of pseudo-random bytes.

We pay the overhead of using a sync.Mutex to synchronize calls to AES-CTR, but this is relatively cheap.

func NewPRG 

func NewPRG(key *PRGKey) *PRGReader

func RandomPRG 

func RandomPRG() *PRGReader

func (*PRGReader) Read 

func (s *PRGReader) Read(p []byte) (int, error)

type Params 

type Params struct {
	N     uint64  // LWE secret dimension
	Sigma float64 // LWE error distribution stddev

	L uint64 // DB height
	M uint64 // DB width

	Logq uint64 // (logarithm of) ciphertext modulus
	P    uint64 // plaintext modulus
}

func (*Params) Delta 

func (p *Params) Delta() uint64

func (*Params) PickParams 

func (p *Params) PickParams(doublepir bool, samples ...uint64)

func (*Params) PrintParams 

func (p *Params) PrintParams()

func (*Params) Round 

func (p *Params) Round(x uint64) uint64

type SimplePIR 

type SimplePIR struct{}

func (*SimplePIR) Answer 

func (pi *SimplePIR) Answer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg

func (*SimplePIR) ConcatDBs 

func (pi *SimplePIR) ConcatDBs(DBs []*Database, p *Params) *Database

Works for SimplePIR because vertical concatenation doesn't increase the number of LWE samples (so don't need to change LWE params)

func (*SimplePIR) DecompressState 

func (pi *SimplePIR) DecompressState(info DBinfo, p Params, comp CompressedState) State

func (*SimplePIR) FakeSetup 

func (pi *SimplePIR) FakeSetup(DB *Database, p Params) (State, float64)

func (*SimplePIR) GetBW 

func (pi *SimplePIR) GetBW(info DBinfo, p Params)

func (*SimplePIR) Init 

func (pi *SimplePIR) Init(info DBinfo, p Params) State

func (*SimplePIR) InitCompressed 

func (pi *SimplePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)

func (*SimplePIR) InitCompressedSeeded 

func (pi *SimplePIR) InitCompressedSeeded(info DBinfo, p Params, seed *PRGKey) (State, CompressedState)

func (*SimplePIR) MyAnswer 

func (pi *SimplePIR) MyAnswer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg

func (*SimplePIR) MyInit 

func (pi *SimplePIR) MyInit(info DBinfo, p Params) State

func (*SimplePIR) MyQuery 

func (pi *SimplePIR) MyQuery(i []uint64, shared State, p Params, info DBinfo) (State, Msg)

func (*SimplePIR) MyRecover 

func (pi *SimplePIR) MyRecover(i []uint64, batch_index uint64, offline Msg, query Msg, answer Msg,
	shared State, client State, p Params, info DBinfo) []uint64

func (*SimplePIR) MySetup 

func (pi *SimplePIR) MySetup(DB *Database, shared State, p Params) (State, Msg)

func (*SimplePIR) Name 

func (pi *SimplePIR) Name() string

func (*SimplePIR) PackDB 

func (pi *SimplePIR) PackDB(DB *Database, p Params)

func (*SimplePIR) PickParams 

func (pi *SimplePIR) PickParams(N, d, n, logq uint64) Params

func (*SimplePIR) PickParamsGivenDimensions 

func (pi *SimplePIR) PickParamsGivenDimensions(l, m, n, logq uint64) Params

func (*SimplePIR) PickStrParams 

func (pi *SimplePIR) PickStrParams(N, d, n, logq uint64) Params

func (*SimplePIR) Query 

func (pi *SimplePIR) Query(i uint64, shared State, p Params, info DBinfo) (State, Msg)

func (*SimplePIR) Recover 

func (pi *SimplePIR) Recover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg,
	shared State, client State, p Params, info DBinfo) uint64

func (*SimplePIR) Reset 

func (pi *SimplePIR) Reset(DB *Database, p Params)

func (*SimplePIR) Setup 

func (pi *SimplePIR) Setup(DB *Database, shared State, p Params) (State, Msg)

func (*SimplePIR) SetupUnpackedDB 

func (pi *SimplePIR) SetupUnpackedDB(DB *Database, shared State, p Params) (State, Msg)

func (*SimplePIR) StrRecover 

func (pi *SimplePIR) StrRecover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg,
	shared State, client State, p Params, info DBinfo) string

type State 

type State struct {
	Data []*Matrix
}

func MakeState 

func MakeState(elems ...*Matrix) State

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.