"...the composer may conceive the germ of the Idea for his composition in 'a flash' (Mozart's Gleich alIes zusammen) but his task then is to bring this outside time experience into the reality of time and give it substance and duration, allowing it to achieve its inherent shape and balance."

(Daphne #Oram, "An Individual Note")

S. Mathialagan and N. Vafa, "MacORAMa: Optimal Oblivious RAM with Integrity"¹

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of
Ω(log N) in the number of RAM queries is necessary assuming
O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with O(log⁡ N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the
Ω(log N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

#ResearchPapers #IACR #OblivousRAM #ORAM #MemoryChecking

__
¹ https://eprint.iacr.org/2023/083

A. Vadapalli et al., "Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation"¹

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with n addressable locations, Duoram can perform a sequence of m arbitrarily interleaved reads and writes using just O(m lg n) words of communication, compared with Floram's O(m n) words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just O (m) words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

#IACR #ResearchPapers #ORAM #ObliviousRAM
__
¹ https://eprint.iacr.org/2022/1747

„Sisters with Transistors“ hat nicht nur einen coolen Titel. Es ist auch eine sehenswerte Doku über die großteils vergessenen Pionierinnen der elektronischen Musik. (Ja genau, sie wurden vergessen wie die ersten Programmiererinnen und die ersten Regisseurinnen.)
https://www.arte.tv/de/videos/104017-000-A/sisters-with-transistors-die-verkannten-heldinnen-der-elektronischen-musik/

Wer – wie ich – nach der Doku ausgewählte Stücke der Komponistinnen in Gänze hören möchte, wird mit diesem Podcast bedient: https://www.uncannyvalley.de/articles/sisters-with-transistors-special

Die Komponistinnen sind Clara #Rockmore, Daphne #Oram, Bebe #Barron, Delia #Derbyshire, Maryanne #Amacher, Pauline #Oliveros, Wendy #Carlos, Eliane #Radigue, Suzanne #Ciani und Laurie #Spiegel.

#electronicmusik #elektronischemusik #theremin #moog #buchla #ark #synthesizer #musik #music

bunybunybunybuny  

#oram