IP Library › Granted Patent US 12,231,563
Granted Patent B2
US 12,231,563 · App. 18/297,339 · Granted Feb 18, 2025

Secure computation and communication

Inventors: Haohao Qian (Beijing, CN); Jian Du (Culver City, CA); Qiang Yan (Beijing, CN)
Assignee: Lemon Inc.
H04L9/3066G06F16/2456G06F16/258H04L2209/46
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,231,563
App. No.
18/297,339
Filed
Apr 7, 2023
Granted
Feb 18, 2025
Kind
B2
Art Unit
2436
USPC
713/193
Abstract

Methods and systems for secure computation and communication are provided. The method includes transforming identifications of a first dataset using a first transforming scheme, and transforming attributes of the first dataset using a second transforming scheme. The method also includes dispatching the transformed first dataset, receiving a second dataset, transforming identifications of the received second dataset, dispatching the identifications of the transformed received second dataset, and receiving a set of identifications. The method further includes generating a first intersection of the received set of identifications and the transformed received second dataset, generating a first share based on the first intersection, receiving a second share, and constructing a result based on the first share and the second share.

Claims (74)

1. A method for secure computation and communication, the method comprising:

transforming identifications of a first dataset using a first transforming scheme and then a third transforming scheme so that the identifications of the first dataset are transformed twice;

transforming attributes of the first dataset using a second transforming scheme

transforming identifications of a second dataset using the third transforming scheme and then the first transforming scheme so that the identifications of the second dataset are transformed twice;

generating a first intersection of the identifications of the transformed first dataset and the transformed second dataset;

after the first intersection being generated, generating a first share based on the generated first intersection by applying a masking scheme to attributes of the generated first intersection;

generating a second intersection of the identifications of the transformed second dataset and the transformed first dataset;

generating a second share based on the second intersection; and

constructing a first result based on the first share and the second share.

2. The method of claim 1 , further comprising:

before transforming the first dataset using the third transforming scheme, shuffling the transformed first dataset; and

before transforming the second dataset using the first transforming scheme, shuffling the transformed second dataset.

3. The method of claim 1 , wherein the generating of the first share based on the generated first intersection includes:

masking the attributes of the generated first intersection using the masking scheme;

dispatching the masked attributes of the generated first intersection;

generating a first portion of the first share using the masking scheme;

receiving a second portion of the first share;

transforming the second portion of the first share using the second transforming scheme used for transforming the attributes of the first dataset; and

generating the first share based on the first portion of the first share and the second portion of the first share.

4. The method of claim 1 , wherein a record of the generated first intersection includes an identification field and two or more attribute fields, the method further comprising:

expanding each of the two or more attribute fields to a predetermined size;

storing the expanded two or more attribute fields in two or more adjacent slots, respectively;

concatenating the two or more adjacent slots; and

masking the concatenated two or more adjacent slots using the masking scheme.

5. The method of claim 4 , wherein the masking of the concatenated two or more adjacent slots includes adding random values to the two or more adjacent slots, respectively.

6. The method of claim 1 , further comprising:

determining a random exponent for the first transforming scheme.

7. The method of claim 6 , wherein the transforming of the identifications of the first dataset using the first transforming scheme includes:

mapping the identifications of the first dataset to an elliptic curve, and

applying exponentiation on the mapped identifications using the random exponent.

8. The method of claim 1 , further comprising:

generating a public key for the second transforming scheme.

9. The method of claim 8 , wherein the transforming of the attributes of the first dataset using the second transforming scheme includes:

transforming the attributes of the first dataset using the public key.

10. The method of claim 1 , further comprising:

transforming attributes of the second dataset using a fourth transforming scheme;

receiving the first share; and

constructing a second result based on the first share and the second share.

11. The method of claim 10 , wherein the first result is the same as the second result.

12. The method of claim 10 , wherein identifications of the generated first intersection match identifications of the second intersection.

13. The method of claim 10 , further comprising:

before transforming the second dataset using the third transforming scheme, shuffling the second dataset; and

before transforming the first dataset using the first transforming scheme, shuffling the first dataset.

14. The method of claim 1 , further comprising:

before transforming the identifications of the first dataset using the third transforming scheme, dispatching the first dataset having the identifications of the first dataset being transformed using the first transforming scheme and the attributes of the first dataset being transformed using the second transforming scheme.

15. The method of claim 1 , further comprising:

shuffling the first dataset twice before generating the first intersection.

16. The method of claim 1 , wherein the attributes of the first intersection include attributes of the second dataset, but not the attributes of the first dataset.

17. A secure computation and communication system, the system comprising:

a memory to store a first dataset; and

a processor to:

transform identifications of the first dataset using a first transforming scheme and then a third transforming scheme so that the identifications of the first dataset are transformed twice;

transform attributes of the first dataset using a second transforming scheme

transform identifications of a second dataset using the third transforming scheme and then the first transforming scheme so that the identifications of the second dataset are transformed twice;

generate a first intersection of the identifications of the transformed first dataset and the transformed second dataset;

after the first intersection being generated, generate a first share based on the generated first intersection by applying a masking scheme to attributes of the generated first intersection;

generating a second intersection of the identifications of the transformed second dataset and the transformed first dataset;

generating a second share based on the second intersection; and

construct a first result based on the first share and the second share.

18. The system of claim 17 , wherein the processor is to further:

before transforming the first dataset using the third transforming scheme, shuffle the transformed first dataset; and

before transforming the second dataset using the first transforming scheme, shuffle the transformed second dataset.

19. A non-transitory computer-readable medium having computer-executable instructions stored thereon that, upon execution, cause one or more processors to perform operations comprising:

transforming identifications of a first dataset using a first transforming scheme and then a third transforming scheme so that the identifications of the first dataset are transformed twice;

transforming attributes of the first dataset using a second transforming scheme

transforming identifications of a second dataset using the third transforming scheme and then the first transforming scheme so that the identifications of the second dataset are transformed twice;

generating a first intersection of the identifications of the transformed first dataset and the transformed second dataset;

after the first intersection being generated, generating a first share based on the generated first intersection by applying a masking scheme to attributes of the generated first intersection;

generating a second intersection of the identifications of the transformed second dataset and the transformed first dataset;

generating a second share based on the second intersection; and

constructing a first result based on the first share and the second share.

20. The computer-readable medium of claim 19 , wherein the operations further comprise:

before transforming the first dataset using the third transforming scheme, shuffling the transformed first dataset; and

before transforming the second dataset using the first transforming scheme, shuffling the transformed second dataset.

Assignments (4)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 5, 2024
From: QIAN, HAOHAO
To: SHANGHAI SUIXUNTONG ELECTRONIC TECHNOLOGY CO., LTD.
Reel/Frame 066652/0741 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 5, 2024
From: DU, JIAN
To: TIKTOK INC.
Reel/Frame 066652/0747 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 5, 2024
From: YAN, QIANG
To: SHANGHAI SUIXUNTONG ELECTRONIC TECHNOLOGY CO., LTD.
Reel/Frame 066652/0752 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 5, 2024
From: SHANGHAI SUIXUNTONG ELECTRONIC TECHNOLOGY CO., LTD.; TIKTOK INC.
To: LEMON INC.
Reel/Frame 066652/0757 →
Continuity (1)
Related Publication 20240340178A1 · Oct 10, 2024
References Cited (66)
US 7058603B1 · Rhiando · 2006 [cited by applicant]
US 9652622B2 · Garfinkle et al. · 2017 [cited by applicant]
US 10289816B1 · Malassenet · 2019 [cited by applicant]
US 11522688B2 · Goodsitt et al. · 2022 [cited by applicant]
US 11593510B1 · Knox · 2023 [cited by applicant]
US 11704431B2 · Kraus · 2023 [cited by applicant]
US 20040179686A1 · Matsumura · 2004 [cited by examiner]
US 20100131764A1 · Goh · 2010 [cited by applicant]
US 20110202764A1 · Furukawa · 2011 [cited by applicant]
US 20120143922A1 · Rane · 2012 [cited by applicant]
US 20130212690A1 · Fawaz · 2013 [cited by applicant]
US 20160150047A1 · O'Hare · 2016 [cited by examiner]
US 20180101697A1 · Rane · 2018 [cited by applicant]
US 20190065775A1 · Klucar, Jr. · 2019 [cited by applicant]
US 20190244138A1 · Bhowmick · 2019 [cited by applicant]
US 20190361794A1 · Maksyutov · 2019 [cited by applicant]
US 20200250335A1 · Hockenbrocht · 2020 [cited by applicant]
US 20200401726A1 · Lim et al. · 2020 [cited by applicant]
US 20210073677A1 · Peterson · 2021 [cited by applicant]
US 20210173856A1 · Chitnis · 2021 [cited by applicant]
US 20210258149A1 · Kawaguchi · 2021 [cited by applicant]
US 20210303647A1 · Westmoreland · 2021 [cited by examiner]
US 20210328762A1 · Becher et al. · 2021 [cited by applicant]
US 20210336771A1 · Mukherjee · 2021 [cited by examiner]
US 20210360010A1 · Zaccak · 2021 [cited by applicant]
US 20210399874A1 · Polyakov · 2021 [cited by examiner]
US 20220100899A1 · Saillet · 2022 [cited by examiner]
US 20220138348A1 · Bernau · 2022 [cited by applicant]
US 20220244988A1 · Zhang · 2022 [cited by applicant]
US 20220277097A1 · Cabot · 2022 [cited by applicant]
US 20220335450A1 · Fenton · 2022 [cited by applicant]
US 20220405800A1 · Walcott · 2022 [cited by examiner]
US 20230045553A1 · Deshpande · 2023 [cited by applicant]
US 20230125887A1 · Habite · 2023 [cited by applicant]
US 20230146259A1 · Liktor · 2023 [cited by applicant]
US 20230017374A1 · Boehler · 2023 [cited by applicant]
US 20230214684A1 · Wang · 2023 [cited by applicant]
CN 102752794A · 2012 [cited by examiner]
CN 116049626A · 2023 [cited by applicant]
Buddhavarapu et al., “Private matching for compute”, Cryptology ePrint Archive, 2020, https://eprint.iacr.org/2020/599. [cited by applicant]
Guo et al., “Birds of a Feather Flock Together: How Set Bias Helps to Deanonymize You via Revealed Intersection Sizes”, 31st USENIX Security Symposium, Aug. 10-12, 2022, Boston, MA, USA, https://www.usenix.org/conferenc… [cited by applicant]
Ion et al., “On Deploying Secure Computing: Private Intersection-Sum-with-Cardinality”, 2020 IEEE European Symposium on Security and Privacy (EuroS&P), Date of Conference: Sep. 7-11, 2020, Date added to IEEE Xplore: Nov… [cited by applicant]
Chandran et al., “Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF”, Cryptology ePrint Archive, received Jan. 12, 2021, https://eprint.iacr.org/2021/034. [cited by applicant]
Pinkas et al., “SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension”, Cryptology ePrint Archive, received Jun. 3, 2019, https://eprint.iacr.org/2019/634. [cited by applicant]
Chase et al., “Secret Shared Shuffle”, Cryptology ePrint Archive, received Nov. 22, 2019, https://eprint.iacr.org/2019/1340. [cited by applicant]
Mohassel et al., “ How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation”, Cryptology ePrint Archive, received Mar. 9, 2013, https://eprint.iacr.org/2013/137. [cited by applicant]
Garimella et al., “Private Set Operations from Oblivious Switching”, Cryptology ePrint Archive, received Mar. 2, 2021, https://eprint.iacr.org/2021/243. [cited by applicant]
Dwork et al., “Differential Privacy and Robust Statistics”, Association for Computing Machinery, May 31, 2009, pp. 371-380, https://dl.acm.org/doi/10.1145/1536414.1536466. [cited by applicant]
Dwork et al., “Differential Privacy Under Continual Observation”, Association for Computing Machinery, Jun. 5, 2010, pp. 715-724, https://dl.acm.org/doi/10.1145/1806689.1806787. [cited by applicant]
Dwork et al. “Our Data, Ourselves: Privacy via Distributed Noise Generation”, Advances in Cryptology—EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. P… [cited by applicant]
Office Action dated Jun. 12, 2023 issued in the corresponding U.S. Appl. No. 18/297,376. [cited by applicant]
Case, Benjamin et al. “The Privacy-preserving Padding Problem: Non-negative Mechanisms for Conservative Answers with Differential Privacy.” 20 pages. Oct. 15, 2021. https://arxiv.org/abs/2110.08177. [cited by applicant]
Office Action dated Jul. 11, 2023 issued in the corresponding U.S. Appl. No. 18/297,389. [cited by applicant]
Office Action dated Jun. 14, 2023 issued in the corresponding U.S. Appl. No. 18/297,405. [cited by applicant]
Kairouz, Peter, Sweoong Oh, and Pramod Viswanath. “The composition theorem for differential privacy.” International Conference on machine learning. PMLR, 2015 (Year: 2015). [cited by applicant]
Office Action dated Jun. 20, 2023 issued in the corresponding U.S. Appl. No. 18/297,424. [cited by applicant]
Notice of Allowance dated Aug. 2, 2023 issued in the corresponding U.S. Appl. No. 18/297,424. [cited by applicant]
Office Action dated Jul. 12, 2023 issued in the corresponding U.S. Appl. No. 18/297,447. [cited by applicant]
Du et al. DP-PSI: Private and secure set intersection, Aug. 28, 2022, Cornel University, https://doi.org/10.48550/arXiv.2208.13249V1, p. 1-9. (Year: 2022). [cited by applicant]
Notice of Allowance dated Jul. 25, 2023 issued in the corresponding U.S. Appl. No. 18/297,530. [cited by applicant]
Notice of Allowance dated Aug. 2, 2023 issued in the corresponding U.S. Appl. No. 18/297,545. [cited by applicant]
Notice of Allowance dated Aug. 30, 2023 issued in the corresponding U.S. Appl. No. 18/297,376. [cited by applicant]
Notice of Allowance dated Aug. 30, 2023 issued in the corresponding U.S. Appl. No. 18/297,405. [cited by applicant]
International Search Report issued in PCT/SG2024/050217, dated May 18, 2024. [cited by applicant]
Secure Multiparty Computation (part 2). Sep. 29, 2016, Retrieved on May 10, 2024, from https://web.archive.org/web/20160929124624/https://research.cyber.ee/˜peeter/teaching/krprot09s/mpc2new.pdf, pp. 35-37. [cited by applicant]
Agrawal S. et al., Multi-Party Functional Encryption. Theory of Cryptography. TCC 2021, Nov. 4, 2021, vol. 13043, pp. 1-70, Retrieved on May 10, 2024. [cited by applicant]