Modular reduction with secret modulus

[b-kamphorst]

Hi @lschoe! I ran into an issue with integer division of secure integers. The following script fails for me when ran with at least three players (-M 3):

# test.py
from mpyc.runtime import mpc
secint = mpc.SecInt()

async def main():
    async with mpc:
        a = mpc.input(secint(3), senders=0)
        b = mpc.input(secint(2), senders=0)
        print(await mpc.output(a // b))  # similarly, mpc.output(mpc.mod(a, b))

if __name__ == "__main__":
    mpc.run(main())

$ python test.py -M3
2023-09-25 10:34:33,881 Start MPyC runtime v0.9
2023-09-25 10:34:34,189 All 3 parties connected.
2023-09-25 10:34:34,191 Unhandled exception in event loop
Traceback (most recent call last):
  File ".../.pyenv/versions/3.11.1/lib/python3.11/asyncio/events.py", line 80, in _run
    self._context.run(self._callback, *self._args)
  File ".../.venv/lib/python3.11/site-packages/mpyc/asyncoro.py", line 431, in <lambda>
    task.add_done_callback(lambda t: _reconcile(decl, t))
                                     ^^^^^^^^^^^^^^^^^^^
  File ".../.venv/lib/python3.11/site-packages/mpyc/asyncoro.py", line 355, in _reconcile
    givn = task.result()
           ^^^^^^^^^^^^^
  File ".../.venv/lib/python3.11/site-packages/mpyc/asyncoro.py", line 283, in _wrap_in_coro
    return await awaitable
           ^^^^^^^^^^^^^^^
  File ".../.venv/lib/python3.11/site-packages/mpyc/asyncoro.py", line 271, in __await__
    val = self.coro.send(None)
          ^^^^^^^^^^^^^^^^^^^^
  File ".../.venv/lib/python3.11/site-packages/mpyc/runtime.py", line 530, in output
    y = recombine(field, points)
        ^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../.venv/lib/python3.11/site-packages/mpyc/thresha.py", line 104, in recombine
    s = share_i[h]
        ~~~~~~~^^^
IndexError: list index out of range
Traceback (enclosing MPyC coroutine call):
  File ".../.venv/lib/python3.11/site-packages/mpyc/runtime.py", line 3206, in random_bits
    r2s = await self.output(r2s, threshold=2*t)
Traceback (most recent call last):
  File ".../test.py", line 14, in <module>
    mpc.run(main())
  File ".../.venv/lib/python3.11/site-packages/mpyc/runtime.py", line 181, in run
    return self._loop.run_until_complete(f)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../.pyenv/versions/3.11.1/lib/python3.11/asyncio/base_events.py", line 651, in run_until_complete
    raise RuntimeError('Event loop stopped before Future completed.')
RuntimeError: Event loop stopped before Future completed.

I am aware that the docstring of SecureNumber.__floordiv__ states public divisor. I wanted to work around this by using Runtime.mod, which seems to be designed to work explicitly with secure divisors as it starts with b = await self.gather(b). Since __floordiv__ actually calls mod under the hood, this yields the same error (but now the root of the issue is slightly narrowed down).

Should it indeed be possible to perform secure integer division/ modular reduction with public divisor/ modulus? If so, I am doing something wrong or this is a bug. If not, would you be willing to support (approximate) integer division?

Looking forward to your thoughts.

[lschoe]

Oh, yes, the line b = await self.gather(b) may put you on the wrong track, although the next lines go on to use b as a publicly known integer. The intent for future extension is that b will be allowed to be of a secure type, hence used as a secret-shared value.

For secure groups we already use integer division with a secure divisor. You can try to use this code by defining div as follows:

from mpyc.secgroups import _divmod
div = lambda a, b: _divmod(a, b)[0]

Maybe that helps you out, for now?

[b-kamphorst]

That indeed suffices for now, thank you for the quick reply (as always)!