文章目录[隐藏]
上了节Applied Cryptology的课。这老板和一切体系结构老师一样，非常push你做他想做的东西。大概密码学的研究，要不是一个全过程定义like CryptDB这样，或者弱化一个密码学的property优化性能，或者优化加密复杂度。一般都是找一个dummy implementation然后慢慢优化。
- More secure
- More Efficient
- More Expressive and functional
- Various query types (Boolean, point, range, join, group-by,...)
- Dynamic query workloads
- Specialized for various DB scenarios (relational, graph, array DBs, ...)
Cryptography Recap
Crypto Property
- One-time pad, the easiest one is ⊕
明文/密闻都是nbit，问题是传key太危险了。 - RSA
- Pseudo-Random Function
- Complies with the adversarial probability is negligible.
- Naor-Reingold
- Privacy-Preserving
- if (a==b) then Enc(a) = Enc(b) - Deterministic encryption
- if (a<=b) then Enc(a) <= Enc(b) - Order preserving encrytion
- CPA-security(Chosen-plaintext attack)
- The CPA Indistinguishability Experiment $PrivK^{cpa}_{A,\pi}$ < perfect
- Dynamic searchable encryption is CPA
- SDa
- High-level idea: Organize Nupdates in a collection of at most $log_2N$ independent encrypted indexes
Can Reduce from amortized to de-amortized by constructing dummy code and sorting and obliviously make it work.
-
Oblivious algorithm
- The algorithm of the 1sort does not hurt the obvious property like Bitonic Sort takes $Nlog^2N$ cost
- Oblivious sorted multimaps AVL Tree
-
MPC
-
TEE doesn't need every time download everything, but makes client inside the enclave and exchange data with outer devices. It can save transmission time.
-
ORAM makes the access pattern to the RAM not leaked by the attacker
-
Backward Privacy
CrytDB
用cyphertext对search scheme的(de)encrypt，可以想像就是死慢。有很多rebalance/重排操作优化
Searchable Encryption
怎么保证在search的过程中没有任何信息被leak，尤其是access pattern
我们可以对一个db操作的任何一个步骤都encrypt
Security 喜欢干的也是写模拟器。
需要保证的是一次search对ideal的访问操作的概率差在一个相关$\lambda$的可控范围内，有点像$\epsilon-N$定义。最naive的定义是PiBas模拟器来模拟SE。然后有个证明是用模拟器模拟和实际情况哦差别不大。
算法层面的定义key的encryption如上。
在模拟器里比较好测试算法的有效性。证明property like adaptive indistinguishability.
Whether construct all the key and pad to size of power of 2 will reduce the database result-size leakage?
What about adding random (key, value) pairs to $T$, so that the total number of elements is 2*N,
Optimal or Quasi-Optimal Search Time
Use ORAM Map + Backward privacy
I/O Efficient Searchable Encryption
Define Locality and Read Efficiency
Onechoice Allocation
Lower the Property that has a minor possibility of leaking the access pattern - Page Efficient SSE.
- Uniform random document/tuple id reassignment
- Compress the index
- Encrypt the compressed index
Private Range Queries
Key Idea is to transform the range queries into point queries.
Leakage Abuse Attacks
这部分就是看清哪里可以abuse的。
基本思想是在你的ORAM放一个aside ORAM，用一个散列函数分成俩$^n$倍。
Can leak the private join operation
ORAM introduction
A simple ORAM using Shuffling
This Oblivious Shuffling basically tell use the mapping will cost O(log N) for storage O(1), O(N) for storage O(log N) and O(N log N) for storage(N1)
1
shuffle有很多variant， double buffer amortized square root shuffle and cubic。安全证明是对$\sqrt N$的操作寻找整个data slot的期望是正好的。所以buffer可以到$\sqrt N$。
每次读，除了第一层都用PRF $K_i$ 拿到结果，然后put to first。第i层每$2^i$次操作reshuffle一次。
Existing ORAM database
ObliDB
一个标准的TEE保护数据。
OBlix
这个DB是Rust写的。想法是把client 放在SGX里面，做到双向Olivious，即ORAM clients make data-independent accesses to client memory (within enclave)，让server和client相互看不到access pattern。PATH ORAM的方法是把stash data的position map放在enclave client里，item放在不安全的binary tree上，通过trace拿到结果，这个操作是singly ORAM。
DORAM 说的是通过Block和fetched Block分离的方式读在server端的trace,
Read:get一次path替换dummy，添加block，添加dummy path到buckets里。
Write Back:
Snoopy
Opaque
Attacks cast on making ORAM non-malicious
这部分还是一个性能和安全的tradeoff
Reference
- https://people.eecs.berkeley.edu/~raluca/oblix.pdf
- https://arxiv.org/pdf/2106.09966.pdf
- https://www.cs.umd.edu/~jkatz/papers/sqoram.pdf
- https://cseweb.ucsd.edu//~cdcash/oram-slides.pdf
- https://keystone-enclave.org/open-source-enclaves-workshop/slides/OSEW19_RohitSinha_VisaResearch.pdf
Paper List
- RingORAM---Constants Count: Practical Improvements to Oblivious RAM
- Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue
- Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
- Fast Fully Oblivious Compaction and Shuffling
- Oblix: An Efficient Oblivious Search Index
- Snoopy: Surpassing the Scalability Bottleneck of Oblivious Storage
- Opaque: An Oblivious and Encrypted Distributed Analytics Platform
- Efficient Oblivious Database Joins
- Pancake: Frequency smoothing for encrypted data stores
- Snapshot-Oblivious RAMs: Sub-Logarithmic Efficiency for Short Transcripts
- SHORTSTACK: Distributed, Fault-tolerant, Oblivious Data Access
- Meltdown: Reading Kernel Memory from User Space
- Observing and Preventing Leakage in MapReduce ̊