Snapshot-Oblivious RAMs: Sub-Logarithmic Efficiency for Short Transcripts

Innovative research on Snapshot-Oblivious RAMs reveals sub-logarithmic efficiency for short transcripts, addressing database breach risks through bypassing inherent lower bounds with a focus on enhancing memory access security.

• - RAMs
• Security
• Database Breach
• Efficiency

boh_sch Follow

Uploaded on Feb 23, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Snapshot-Oblivious RAMs: Sub-Logarithmic Efficiency for Short Transcripts Yang Du1, Daniel Genkin2, Paul Grubbs1 1University of Michigan, 2Georgia Tech Aug 18, 2022 1

2. Database Breach . . . untrusted storage Access pattern attacks [IKK12, CGP+15, GMN+16, ZKP16, RM 17] 2

3. Oblivious RAM Read 1 Write 1 Read 2 Write 1 ORAM Write 2 untrusted storage Read 3 Write 3 3

4. Oblivious RAM Read 1 Write 1 Read 2 Write 1 ORAM Write 2 untrusted storage [GO90, SDS13, CLP14, WCS15, CS17, PRP+18, AKL18, PRP18] Read 3 Write 3 4

5. Problem: Oblivious RAM is neither asymptotically nor concretely efficient. An inherent (log N) lower bound [LN18, GO90] for all oblivious RAMs. Relaxation: DP-ORAM, offline ORAM. On each 4KB block, ObliviStore uses 79KB bandwidth; PathORAM uses 287 KB [BNP+15]. Round complexity, storage overhead, ... 5

6. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Key idea: Limit the adversary to an observing window! 6

7. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 Key idea: Limit the adversary to an observing window! 7

8. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 Window of size 3 Key idea: Limit the adversary to an observing window! 8

9. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 Window of size 3 Key idea: Limit the adversary to an observing window! 9

10. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 Window of size 3 Key idea: Limit the adversary to an observing window! 10

11. Bypassing the lower bound How can we sidestep the (log N) lower bound, while providing a meaningful security guarantee for memory access patterns? Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 Window of size 3 Key idea: Limit the adversary to an observing window! 11

12. Snapshot Attack Adversary access to system is often time-limited. Verizon Data Breach Incident Report: roughly 50% of detected security incidents were detected within a few days. Hackers from the Lapsus$ hacker group compromised Okta s systems, the access period was 25 minutes! 12

13. Bypassing the lower bound Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 ORAM ORAM ORAM Key idea: Limit the adversary to an observing window! 13

14. Our Contribution Introduce snapshot-oblivious RAM, define new security models. Construct & analyze three snapshot-oblivious RAM schemes. Bandwidth Overhead Concretely Efficient Client Storage OptORAMa O(1) O(log N) DP ORAM O(1) O(log N) = O(1) and 1/3 CQoram O(c) O(1) This Paper O(log2 c) PHQoram O(1) c = window size UHQoram O(1) O(log c) Prove the bandwidth overhead lower bound and show optimality 14

15. Our Contribution Introduce snapshot-oblivious RAM, define new security models. Construct & analyze three snapshot-oblivious RAM schemes. Bandwidth Overhead Concretely Efficient Client Storage OptORAMa O(1) O(log N) DP ORAM O(1) O(log N) = O(1) and 1/3 CQoram O(c) O(1) This Paper O(log2 c) PHQoram O(1) c = window size UHQoram O(1) O(log c) Prove the bandwidth overhead lower bound and show optimality 15

16. Our Contribution Introduce snapshot-oblivious RAM, define new security models. Construct & analyze three snapshot-oblivious RAM schemes. Bandwidth Overhead Concretely Efficient Client Storage OptORAMa O(1) O(log N) DP ORAM O(1) O(log N) = O(1) and 1/3 CQoram O(c) O(1) This Paper O(log2 c) PHQoram O(1) c = window size UHQoram O(1) O(log c) Prove the bandwidth overhead lower bound and show optimality. 16

17. Talk Outline Syntax and security of snapshot-oblivious RAM FSO: 1-snapshot oblivious scheme CQoram: Snapshot oblivious scheme for general window size New data structure to achieve optimal bandwidth overhead https://eprint.iacr.org/2022/858.pdf 17

18. Talk Outline Syntax and security of snapshot-oblivious RAM FSO: 1-snapshot oblivious scheme CQoram: Snapshot oblivious scheme for general window size New data structure to achieve optimal bandwidth overhead https://eprint.iacr.org/2022/858.pdf 18

19. The c- Snapshot Oblivious RAM Write 1 Write 2 Write 3 Read 1 Read 2 Write 1 Read 4 Write 3 DB1, T1 = (c) Write 3 Write 2 Write 1 Read 2 Read 1 Write 4 Read 3 Write 1 DB2, T2 = . Init(c, DB1) ORAM . Init(c, DB2) ORAM . Exec(T1) ORAM . . Exec(T2) ORAM . Read 1 Write 1 Read 2 Write 2 Read 3 Write 3 Read 4 Write 4 19

20. Talk Outline Syntax and security of snapshot-oblivious RAM FSO: 1-snapshot oblivious scheme CQoram: Snapshot oblivious scheme for general window size New data structure to achieve optimal bandwidth overhead https://eprint.iacr.org/2022/858.pdf 20

21. FSO: 1-Snapshot ORAM . Init: 1. ORAM shuffle the memory using a PRP. 2. . Exec(x): ORAM read the memory location PRP(x), and write it back. 21

22. FSO: 1-Snapshot ORAM Write 1 Write 3 Theorem: FSO is 1-snapshot secure. ORAM ORAM Read PRP(3) Read PRP(1) Write PRP(1) Write PRP(3) 22

23. Attack for ? ? Write 3 Write 3 PRP reveals repetition in transcript! ORAM ORAM Read PRP(3) Read PRP(3) Write PRP(3) Write PRP(3) 23

24. Talk Outline Syntax and security of snapshot-oblivious RAM FSO: 1-snapshot oblivious scheme CQoram: Snapshot oblivious scheme for general window size New data structure to achieve optimal bandwidth overhead https://eprint.iacr.org/2022/858.pdf 24

25. Insecure c-Snapshot ORAM c = window size . Init: 1. ORAM shuffle the memory (size N) and 2c fillers using a PRP; initialize an empty queue. 2. . Exec(x): ORAM x not in queue: read the shuffled memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 25

26. Insecure c-Snapshot ORAM c = window size . Init: 1. ORAM shuffle the memory (size N) and 2c fillers using a PRP; initialize an empty queue. 2. . Exec(x): ORAM x not in queue: read the shuffled memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 26

27. Insecure c-Snapshot ORAM c = window size . Init: 1. ORAM shuffle the memory (size N) and 2c fillers using a PRP; initialize an empty queue. 2. . Exec(x): ORAM x not in queue: read the shuffled memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 27

28. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler Queue: 7 Filler ORAM 1 8 Filler Read PRP(1) . Exec(x): ORAM x not in queue: Write PRP(5) read the memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 28

29. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler Queue: 7 Filler ORAM 1 8 Filler Read PRP(6) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(7) read the memory location PRP(x); 29

30. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler Queue: 7 Filler ORAM 2 1 8 Filler Read PRP(2) . Exec(x): ORAM x not in queue: Write PRP(8) read the memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 30

31. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler Queue: 7 Filler ORAM 3 2 1 8 Filler Read PRP(3) . Exec(x): ORAM x not in queue: Write PRP(1) read the memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 31 31

32. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler Queue: 7 Filler ORAM 4 3 2 8 Filler Read PRP(4) . Exec(x): ORAM x not in queue: Write PRP(2) read the memory location PRP(x); otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. 32 32

33. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(4) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); 33 33

34. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(4) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); 34 34

35. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(4) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); 35 35

36. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(4) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); 36 36

37. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 4 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(4) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); 37 37

38. Insecure c-Snapshot ORAM Index Value c = window size 1 . . . 2 Write 1 Write 1 Read 2 Read 3 Write 1 3 4 5 Filler 6 Filler 7 Filler ORAM ORAM ORAM ORAM ORAM 8 Filler Read PRP(5) Read PRP(2) Read PRP(3) Read PRP(1) Read PRP(1) . Exec(x): ORAM x not in queue: otherwise: read a filler. queue is full: write last queue element back; otherwise: write a filler. Write PRP(6) Write PRP(7) Write PRP(1) Write PRP(2) Write PRP(4) read the memory location PRP(x); Fetch-after-write-back hazard 38 38

39. CQoram: c-Snapshot ORAM c = window size Add a second queue to the insecure version; Remember the written-back value for c more operations; Move contents from the second queue back to the first queue if accessed again; Main point: Fetch the memory content from queues whenever possible. 39

40. CQoram: c-Snapshot ORAM c = window size x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. 40

41. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 1 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 41 41 41

42. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 1 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 42 42 42 42

43. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 1 2 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 43 43 43 43

44. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 2 3 1 1 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 44 44 44 44

45. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 1 3 1 2 2 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 45 45 45 45

46. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 1 3 3 1 4 2 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 46 46 46 46

47. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler 8 Filler Read Queue: Write Queue: Client: 2 3 1 1 4 3 write queue is full? Write last element back. Otherwise: Write a filler. read queue is full? Discard the last element. x is in write queue? Read filler; x is in read queue? Fetch x and read filler; Otherwise: Read x. . Exec(x): ORAM 47 47 47 47

48. CQoram: c-Snapshot ORAM Index Value c = window size 1 . . . 2 3 Write 1 Write 1 Read 2 Read 3 Write 1 Read 4 Read 3 4 5 Filler 6 Filler 7 Filler Index Index Index Index Index Index Index 8 Filler 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 48

49. Talk Outline Syntax and security of snapshot-oblivious RAM FSO: 1-snapshot oblivious scheme CQoram: Snapshot oblivious scheme for general window size New data structure to achieve optimal bandwidth overhead https://eprint.iacr.org/2022/858.pdf 49

50. Outsource the Client Storage Maintain a first-in-first-out queue structure. Efficiently check membership in the queue. Obliviousness. New data structure: HashQueue PHQoram: circular array + oblivious map UHQoram: circular array + cuckoo hashing Check the paper!! ia.cr/2022/858 50

Load More ...