Documentation
¶
Index ¶
- Constants
- func ApproxDatabaseDims(N, row_length, p, lower_bound_m uint64) (uint64, uint64)
- func ApproxSquareDatabaseDims(N, row_length, p uint64) (uint64, uint64)
- func ApproxSquareStrDatabaseDims(N, row_length, p uint64, Item_bits uint64) (uint64, uint64)
- func Base_p(p, m, i uint64) uint64
- func Compute_num_entries_base_p(p, log_q uint64) uint64
- func Compute_num_str_entries_base_p(p, log_q uint64, Item_bits uint64) uint64
- func FindLongestElement(slice []string) string
- func GaussSample() int64
- func LoadFile(filepath, col_name string) []string
- func MathRand() *mrand.Rand
- func Num_DB_entries(N, row_length, p uint64) (uint64, uint64, uint64)
- func Num_StrDB_entries(N, row_length, p uint64, Item_bits uint64) (uint64, uint64, uint64)
- func PrintTime(start time.Time) time.Duration
- func RandInt(mod *big.Int) *big.Int
- func ReconstructElem(vals []uint64, index uint64, info DBinfo) uint64
- func Reconstruct_from_base_p(p uint64, vals []uint64) uint64
- func RunFakePIR(pi PIR, DB *Database, p Params, i []uint64, f *os.File, profile bool) (float64, float64, float64, float64)
- func RunMyPIR(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)
- func RunPIR(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)
- func RunPIRCompressed(pi PIR, DB *Database, p Params, i []uint64) (float64, float64)
- type BufPRGReader
- type CompressedState
- type DBinfo
- type Database
- func MakeDB(Num, row_length uint64, p *Params, vals []uint64) *Database
- func MakeMyDB(Num, row_length uint64, p *Params, valslice [][]uint64) *Database
- func MakeRandomDB(Num, row_length uint64, p *Params) *Database
- func MakeStrDB(Num, row_length uint64, p *Params, svals []string) *Database
- func SetupDB(Num, row_length uint64, p *Params) *Database
- func SetupStrDB(Num, row_length uint64, p *Params) *Database
- type DoublePIR
- func (pi *DoublePIR) Answer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg
- func (pi *DoublePIR) DecompressState(info DBinfo, p Params, comp CompressedState) State
- func (pi *DoublePIR) FakeSetup(DB *Database, p Params) (State, float64)
- func (pi *DoublePIR) GetBW(info DBinfo, p Params)
- func (pi *DoublePIR) Init(info DBinfo, p Params) State
- func (pi *DoublePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)
- func (pi *DoublePIR) InitCompressedSeeded(info DBinfo, p Params, seed *PRGKey) (State, CompressedState)
- func (pi *DoublePIR) MyAnswer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg
- func (pi *DoublePIR) MyInit(info DBinfo, p Params) State
- func (pi *DoublePIR) MyQuery(i []uint64, shared State, p Params, info DBinfo) (State, Msg)
- func (pi *DoublePIR) MyRecover(i []uint64, batch_index uint64, offline Msg, query Msg, answer Msg, ...) []uint64
- func (pi *DoublePIR) MySetup(DB *Database, shared State, p Params) (State, Msg)
- func (pi *DoublePIR) Name() string
- func (pi *DoublePIR) PickParams(N, d, n, logq uint64) Params
- func (pi *DoublePIR) PickParamsGivenDimensions(l, m, n, logq uint64) Params
- func (pi *DoublePIR) Query(i uint64, shared State, p Params, info DBinfo) (State, Msg)
- func (pi *DoublePIR) Recover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg, shared State, ...) uint64
- func (pi *DoublePIR) Reset(DB *Database, p Params)
- func (pi *DoublePIR) Setup(DB *Database, shared State, p Params) (State, Msg)
- type Matrix
- func MatrixGaussian(rows, cols uint64) *Matrix
- func MatrixMul(a *Matrix, b *Matrix) *Matrix
- func MatrixMulTransposedPacked(a *Matrix, b *Matrix, basis, compression uint64) *Matrix
- func MatrixMulVec(a *Matrix, b *Matrix) *Matrix
- func MatrixMulVecPacked(a *Matrix, b *Matrix, basis, compression uint64) *Matrix
- func MatrixNew(rows uint64, cols uint64) *Matrix
- func MatrixNewNoAlloc(rows uint64, cols uint64) *Matrix
- func MatrixRand(rows uint64, cols uint64, logmod uint64, mod uint64) *Matrix
- func MatrixZeros(rows uint64, cols uint64) *Matrix
- func MyMatrixMul(a *Matrix, a_col_packing uint64, b *Matrix, b_row_packing uint64) *Matrix
- func (a *Matrix) Add(val uint64)
- func (a *Matrix) AddAt(val, i, j uint64)
- func (m *Matrix) AppendZeros(n uint64)
- func (a *Matrix) Concat(b *Matrix)
- func (m *Matrix) ConcatCols(n uint64)
- func (m *Matrix) Contract(mod uint64, delta uint64)
- func (m *Matrix) Dim()
- func (m *Matrix) DropLastRows(n uint64)
- func (m *Matrix) Expand(mod uint64, delta uint64)
- func (m *Matrix) Get(i, j uint64) uint64
- func (a *Matrix) MatrixAdd(b *Matrix)
- func (a *Matrix) MatrixSub(b *Matrix)
- func (m *Matrix) Print()
- func (m *Matrix) PrintStart()
- func (m *Matrix) ReduceMod(p uint64)
- func (m *Matrix) Round(p Params)
- func (m *Matrix) RowsDeepCopy(offset, num_rows uint64) *Matrix
- func (m *Matrix) SelectColumn(i uint64) *Matrix
- func (m *Matrix) SelectRows(offset, num_rows uint64) *Matrix
- func (m *Matrix) Set(val, i, j uint64)
- func (m *Matrix) Size() uint64
- func (m *Matrix) Squish(basis, delta uint64)
- func (a *Matrix) Sub(val uint64)
- func (m *Matrix) Transpose()
- func (m *Matrix) TransposeAndExpandAndConcatColsAndSquish(mod, delta, concat, basis, d uint64)
- func (m *Matrix) Unsquish(basis, delta, cols uint64)
- type Msg
- type MsgSlice
- type PIR
- type PRGKey
- type PRGReader
- type Params
- type SimplePIR
- func (pi *SimplePIR) Answer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg
- func (pi *SimplePIR) ConcatDBs(DBs []*Database, p *Params) *Database
- func (pi *SimplePIR) DecompressState(info DBinfo, p Params, comp CompressedState) State
- func (pi *SimplePIR) FakeSetup(DB *Database, p Params) (State, float64)
- func (pi *SimplePIR) GetBW(info DBinfo, p Params)
- func (pi *SimplePIR) Init(info DBinfo, p Params) State
- func (pi *SimplePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)
- func (pi *SimplePIR) InitCompressedSeeded(info DBinfo, p Params, seed *PRGKey) (State, CompressedState)
- func (pi *SimplePIR) MyAnswer(DB *Database, query MsgSlice, server State, shared State, p Params) Msg
- func (pi *SimplePIR) MyInit(info DBinfo, p Params) State
- func (pi *SimplePIR) MyQuery(i []uint64, shared State, p Params, info DBinfo) (State, Msg)
- func (pi *SimplePIR) MyRecover(i []uint64, batch_index uint64, offline Msg, query Msg, answer Msg, ...) []uint64
- func (pi *SimplePIR) MySetup(DB *Database, shared State, p Params) (State, Msg)
- func (pi *SimplePIR) Name() string
- func (pi *SimplePIR) PackDB(DB *Database, p Params)
- func (pi *SimplePIR) PickParams(N, d, n, logq uint64) Params
- func (pi *SimplePIR) PickParamsGivenDimensions(l, m, n, logq uint64) Params
- func (pi *SimplePIR) PickStrParams(N, d, n, logq uint64) Params
- func (pi *SimplePIR) Query(i uint64, shared State, p Params, info DBinfo) (State, Msg)
- func (pi *SimplePIR) Recover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg, shared State, ...) uint64
- func (pi *SimplePIR) Reset(DB *Database, p Params)
- func (pi *SimplePIR) Setup(DB *Database, shared State, p Params) (State, Msg)
- func (pi *SimplePIR) SetupUnpackedDB(DB *Database, shared State, p Params) (State, Msg)
- func (pi *SimplePIR) StrRecover(i uint64, batch_index uint64, offline Msg, query Msg, answer Msg, shared State, ...) string
- type State
Constants ¶
const COMP_RATIO = uint64(64)
Ratio between first-level DB and second-level DB
Variables ¶
This section is empty.
Functions ¶
func ApproxDatabaseDims ¶
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 ¶
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 Compute_num_entries_base_p ¶
Returns how many entries in Z_p are needed to represent an element in Z_q
func Compute_num_str_entries_base_p ¶
Returns how many entries in Z_p are needed to represent an element in Z_q
func FindLongestElement ¶
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 Num_DB_entries ¶
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 ReconstructElem ¶
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 ¶
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.
Types ¶
type BufPRGReader ¶
func NewBufPRG ¶
func NewBufPRG(prg *PRGReader) *BufPRGReader
func (*BufPRGReader) Int63 ¶
func (b *BufPRGReader) Int63() int64
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 DoublePIR ¶
type DoublePIR struct{}
func (*DoublePIR) DecompressState ¶
func (pi *DoublePIR) DecompressState(info DBinfo, p Params, comp CompressedState) State
func (*DoublePIR) InitCompressed ¶
func (pi *DoublePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)
func (*DoublePIR) InitCompressedSeeded ¶
func (*DoublePIR) PickParams ¶
func (*DoublePIR) PickParamsGivenDimensions ¶
type Matrix ¶
func MatrixGaussian ¶
func MatrixMulVec ¶
func MatrixMulVecPacked ¶
func MatrixNewNoAlloc ¶
func MatrixZeros ¶
func MyMatrixMul ¶
func (*Matrix) AppendZeros ¶
func (*Matrix) ConcatCols ¶
func (*Matrix) DropLastRows ¶
func (*Matrix) Expand ¶
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) PrintStart ¶
func (m *Matrix) PrintStart()
func (*Matrix) RowsDeepCopy ¶
func (*Matrix) SelectColumn ¶
func (*Matrix) SelectRows ¶
func (*Matrix) Squish ¶
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) TransposeAndExpandAndConcatColsAndSquish ¶
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 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.
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) PickParams ¶
func (*Params) PrintParams ¶
func (p *Params) PrintParams()
type SimplePIR ¶
type SimplePIR struct{}
func (*SimplePIR) ConcatDBs ¶
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) InitCompressed ¶
func (pi *SimplePIR) InitCompressed(info DBinfo, p Params) (State, CompressedState)