Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On Invertible Sampling and Adaptive Security

Yuval Ishai, Abishek Kumarasubramanian, Claudio Orlandi, Amit Sahai

Published Jan 1, 2010• 15 citations
Publisher
DOI
10.1007/978-3-642-17373-8_27

Related papers

The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults

Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay +3 more

Copyright © 2015 ACM. The vast majority of works on secure multi-party computation (MPC) assume a full communication pattern: every party exchanges messages with all the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data. Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of communication locality, namely, the total number of pointto- point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any n-party function, with communication locality O(logc n) and round complexity O(logc' n), for appropriate constants c and c'. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to t < (1/3 - ε)n parties for any given constant 0 < ε < 1/3. These results leave open the following questions: (1) Can we achieve low communication locality and round complexity while tolerating adaptive adversaries? (2) Can we achieve low communication locality with optimal resiliency t < n/2? In this work we answer both questions affirmatively. We consider the Boyle et al. model, where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity polylog(n) (similarly to Boyle et al.) which tolerates up to t < n/2 adaptive corruptions, under a standard intractability assumption for adaptively secure protocols, namely, the existence of trapdoor permutations whose domain has invertible sampling. This is done by using the SKI to derive a sequence of random hidden communication graphs among players. A central new technique shows how to use these graphs to emulate a complete network in polylog(n) rounds while preserving polylog(n) locality. We also show how to remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of √n.

•Jan 1, 2015•0 citations

On Adaptively Secure Protocols

Muthuramakrishnan Venkitasubramaniam

Lecture notes in computer science•Jan 1, 2014•13 citations

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

Lecture notes in computer science•Jan 1, 2015•19 citations

Simpler Proofs of Quantumness

Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani +1 more

A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor's algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

arXiv:2005.04826•Leibniz international proceedings in informatics•Jan 1, 2020•25 citations

Self-Adaptive Gate Control for Efficient Escape From Local Minimum Energy on Invertible Logic

Naoya Onizawa, Koji Yano, Seiichi Shin +2 more

Invertible logic can realize bidirectional operations of a function represented by a Hamiltonian (energy) with noise and can be applied for integer factorization and training neural networks. However, the computation error is not negligible due to becoming trapped at the local minimum energy when the Hamiltonian is large. This paper introduces self-adaptive gate control (SAGC) for high convergence rates to the global minimum energy on invertible logic. From our analysis based on simulating small-scale invertible logic circuits, it is supposed that becoming stuck is caused by invalid states of invertible gates. The proposed SAGC autonomously detects invalid gates by checking the truth tables and adds large noise to them for efficient escape from the local minimum energy. As a typical example of invertible logic, invertible adders, multipliers and multiplexers are designed and evaluated. The simulation results show that the convergence probabilities to the global minimum based on SAGC are a few times higher than those based on a conventional method that equally adds noise to all the gates.

IEEE Access•Jan 1, 2023•0 citations

Adaptive Security with Quasi-Optimal Rate

Brett Hemenway, Rafail Ostrovsky, Silas Richelson +1 more

Lecture notes in computer science•Dec 18, 2015•10 citations
Copyright © 2015 ACM. The vast majority of works on secure multi-party computation (MPC) assume a full communication pattern: every party exchanges messages with all the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data. Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of communication locality, namely, the total number of pointto- point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any n-party function, with communication locality O(logc n) and round complexity O(logc' n), for appropriate constants c and c'. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to t < (1/3 - ε)n parties for any given constant 0 < ε < 1/3. These results leave open the following questions: (1) Can we achieve low communication locality and round complexity while tolerating adaptive adversaries? (2) Can we achieve low communication locality with optimal resiliency t < n/2? In this work we answer both questions affirmatively. We consider the Boyle et al. model, where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity polylog(n) (similarly to Boyle et al.) which tolerates up to t < n/2 adaptive corruptions, under a standard intractability assumption for adaptively secure protocols, namely, the existence of trapdoor permutations whose domain has invertible sampling. This is done by using the SKI to derive a sequence of random hidden communication graphs among players. A central new technique shows how to use these graphs to emulate a complete network in polylog(n) rounds while preserving polylog(n) locality. We also show how to remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of √n.
A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor's algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.
Invertible logic can realize bidirectional operations of a function represented by a Hamiltonian (energy) with noise and can be applied for integer factorization and training neural networks. However, the computation error is not negligible due to becoming trapped at the local minimum energy when the Hamiltonian is large. This paper introduces self-adaptive gate control (SAGC) for high convergence rates to the global minimum energy on invertible logic. From our analysis based on simulating small-scale invertible logic circuits, it is supposed that becoming stuck is caused by invalid states of invertible gates. The proposed SAGC autonomously detects invalid gates by checking the truth tables and adds large noise to them for efficient escape from the local minimum energy. As a typical example of invertible logic, invertible adders, multipliers and multiplexers are designed and evaluated. The simulation results show that the convergence probabilities to the global minimum based on SAGC are a few times higher than those based on a conventional method that equally adds noise to all the gates.