Oblivious Linear Group Actions and Applications
Type
conference paper
Date Issued
2021-11
Author(s)
Attrapadung, Nuttapong
;
Hanaoaka, Goichiro
;
Matsuda, Takahiro
;
;
Ohara, Kazuma
;
Schuldt, Jacob C. N.
;
Teruya, Tadanori
;
Tozawa, Kazunari
Abstract
In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data
set. Our protocols capture various applications such as oblivious
shuffles, circular shifts, matrix multiplications, to name just a few. A
notable feature enjoyed by our protocols, is that they admit a roundoptimal (more precisely, one-round) online computation phase, once
an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal
online phase. The most efficient instantiations of our protocols are
obtained in the so-called client-aided client-server setting, where
the offline phase is run by a semi-honest input party (client) who
will then distribute the generated correlated randomness to the
computing parties (servers). When comparing the total running
time to the previous best two-party oblivious shuffle protocol by
Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided
setting is up to 105 times and 152 times faster, in the LAN and WAN
setting, respectively. We additionally show how the Chase et al.
protocol (which is a standard two-party protocol) can be modified
to leverage the advantages of the client-aided setting, but show
that, even doing so, our scheme is still two times faster in the online
phase and 1.34 times faster in total on average.
An additional feature of our protocols is that they allow to
re-invoke a previously generated group action, or its inverse, in
subsequent runs. This allows us to utilize randomize-then-reveal
techniques, which are crucial for constructing efficient protocols
in complex applications. As an application, we construct a new
oblivious sorting protocol implementing radix sort. Our protocol is
based on a similar approach to the three-party protocol by Chida et
al. (IACR ePrint 2019/965), but using our oblivious shuffle as a building block as well as various optimizations, we obtain a two-party
protocol (in the client-aided setting) with improved online running time and a reduced number of rounds. As other applications, we also obtain efficient protocols for oblivious selection, oblivious unit-vectorization, oblivious multiplexer, oblivious polynomial
evaluation, arithmetic-to-boolean share conversions, and more.
set. Our protocols capture various applications such as oblivious
shuffles, circular shifts, matrix multiplications, to name just a few. A
notable feature enjoyed by our protocols, is that they admit a roundoptimal (more precisely, one-round) online computation phase, once
an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal
online phase. The most efficient instantiations of our protocols are
obtained in the so-called client-aided client-server setting, where
the offline phase is run by a semi-honest input party (client) who
will then distribute the generated correlated randomness to the
computing parties (servers). When comparing the total running
time to the previous best two-party oblivious shuffle protocol by
Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided
setting is up to 105 times and 152 times faster, in the LAN and WAN
setting, respectively. We additionally show how the Chase et al.
protocol (which is a standard two-party protocol) can be modified
to leverage the advantages of the client-aided setting, but show
that, even doing so, our scheme is still two times faster in the online
phase and 1.34 times faster in total on average.
An additional feature of our protocols is that they allow to
re-invoke a previously generated group action, or its inverse, in
subsequent runs. This allows us to utilize randomize-then-reveal
techniques, which are crucial for constructing efficient protocols
in complex applications. As an application, we construct a new
oblivious sorting protocol implementing radix sort. Our protocol is
based on a similar approach to the three-party protocol by Chida et
al. (IACR ePrint 2019/965), but using our oblivious shuffle as a building block as well as various optimizations, we obtain a two-party
protocol (in the client-aided setting) with improved online running time and a reduced number of rounds. As other applications, we also obtain efficient protocols for oblivious selection, oblivious unit-vectorization, oblivious multiplexer, oblivious polynomial
evaluation, arithmetic-to-boolean share conversions, and more.
Language
English
HSG Classification
contribution to scientific community
Start page
630
End page
650
Pages
21
Event Title
ACM CCS 2021
Event Location
Virtual Event, Republic of Korea
Event Date
November 15–19, 2021
Subject(s)
Division(s)
Eprints ID
269451
File(s)![Thumbnail Image]()
Name
Oblivious Linear Group Actions and Applications.pdf
Size
1.56 MB
Format
Adobe PDF
Checksum (MD5)
f721d2c98ee893116d026d1163d2d794