11 ms·
Solving the Dating Problem with the SENPAI Protocol [pdf]
- zardeh 10y agoI'm curious what happened to paper number 6
- zentiggr 10y ago"There is no paper number six!"
- peteretep 10y agoTangential: can somebody explain to me how same-sex speed-dating is sequenced? Two-sex is easy as one sex remains static while the other rotates around, but I can't figure out a solution for single-sex. Update: a solution that satisfies being practical to organise and that lets you talk to all participants Update2: http://math.stackexchange.com/questions/55439/gay-speed-dating-problem http://math.stackexchange.com/questions/55439/gay-speed-dati...
- smallnamespace 10y agoYou divide the people into two groups arbitrarily.
- peteretep 10y agoWhile I suspect that this is true in practice, this is the disadvantage that you don't talk to everyone, even though you can see them.
- Grishnakh 10y agoI have a solution: divide everyone into two groups arbitrarily. Then, tell everyone to look at everyone in their group, and inform them they won't be able to talk to any of those people. Then offer anyone who's unhappy with this (because they see someone in their group they'd like to chat with) the option of switching sides. Do it one at a time, until everyone's happy with the arrangement (however long this takes), then if one group is too large, arbitrarily move some people to the smaller group and repeat. When time runs out (because you've booked the venue for X hours), then send everyone home even though they never actually got to do the speed-dating at all.
- waqf 10y agoI don't know how they actually do it, but this would work: https://en.wikipedia.org/wiki/Graph_factorization#Complete_graphs https://en.wikipedia.org/wiki/Graph_factorization#Complete_g...
- peteretep 10y agoThis way you see everyone, but have a logistical nightmare.
- deleted 10y ago[deleted]
- wiml 10y agoAll you need to do is set it to music, so that at the end of the set each 1-factor of the factorization has been represented for a verse. You'd probably need a distinct song and pattern for each group size. If your dancers are some mixture of male/female/het/homo/bi such that you don't have a complete graph or other easy problem then you may need to have a computer-augmented dance caller.
- Pxl_Buzzard 10y agoA solution: everyone is sequentially numbered. Evens rotate left one round, odds rotate right the next round. That way everyone has to move the same amount (assuming an even number of participants).
- JacksonGariety 10y agoThere is a dating problem?
- wyred 10y agoWhat is this dating thing everyone seems to be talking about?
- woliveirajr 10y agoI thought Tinder had it solved...
- dripton 10y agoTinder is Trent in this protocol. As long as both Alice and Bob trust Trent, that works. But Trent can cheat.
- twokwy 10y agoYeah, Tinder achieves exactly the objective described of both parties only finding out if both parties' responses are 1. (And suffers from the issue they discuss where 'detectable cheating' - in this case, swiping right regardless to maximise information gain - is difficult to prevent). But, as others have mentioned, it relies on the trusted third party, that is to say Tinder, being trustworthy and not performing what the paper amusingly refers to as a 'Matchmaker In The Middle' attack.
- Kalium 10y ago> In his presentation of the original protocol, Aaronson suggests that zero-knowledge proofs can be used to prevent cheating. However, we find this approach unsatisfying, partly because zero-knowledge proofs would make the protocol much more unwieldy and time-consuming, and partly because we have no clue how to actually implement ZKP in this context I am in love with the honesty in this.
- mrob 10y agoZKP is also useless in this case because there's no way to enforce dating if the ZKP finds a match. Anybody who wants to detect a crush can simply lie about having one themself.
- gizmo686 10y agoExcept the presented protocol already does not prevent this attack (which they acknowledge in the paper). ZKP still provides the property that cheating will be detected, which is all that is required to satisfy the papers security definition.
- jeremysalwen 10y agoGarbled circuits can be used for the ZKP protocol, and in this case the circuit would just be a single AND gate. https://www.math.ucla.edu/~tdokos/notes_files/garbledCircuits.pdf https://www.math.ucla.edu/~tdokos/notes_files/garbledCircuit...
- rakoo 10y ago> An unavoidable issue with group SENPAI exchanges is the problem of love triangles [...] The authors’ recom- mended solution is polyamory [...] We remark that this situation is just generally shitty, and seri- ously, what do you expect us to even do here? I love this
- whatismybrowser 10y ago"Notice me SENPAI!"
- Ar-Curunir 10y agoIf you want to use heavy handed crypto you can utilise multiparty computation protocols that are secure against malicious parties. For the 2PC case this problem was solved way back in the 1980s Andrew Yao.
- yongjik 10y ago> The Just Man Up And Ask Protocol (JMAP) is often proposed as a naive solution to the Dating Problem... Man, this paper is golden!
- NeutronBoy 10y ago> Unfortunately, this protocol is completely dependent on the trustworthiness of Trent, as they receive all of Alice and Bob’s information and are entirely free to manipulate the results of the protocol. If Trent has been compromised, perhaps by a nation-state adversary, Alice and Bob’s love life will be completely in the hands of a malicious attacker Beautifully done.
- peterburkimsher 10y ago"nation-state adversary" and "logical AND" both cracked me up. It is surprising to see common themes with my own research on this topic: "thinking too much".
- mickdj 10y ago[10] is the best
- GuiA 10y agoFor those not getting the reference, "senpai" is a Japanese honorific used to address one's upper classman in school. A common trope in Japanese medium is that a character will have a crush on a senpai (equivalent to a prefect or hall monitor in that context), only for them to be utterly oblivious to it. http://tvtropes.org/pmwiki/pmwiki.php/Main/SempaiKohai http://tvtropes.org/pmwiki/pmwiki.php/Main/SempaiKohai This is a witty paper, as other commenters are noting.
- ekianjo 10y ago> For those not getting the reference, "senpai" is a Japanese honorific used to address one's upper classman in school. Not just in school. In work situations as well. Note that this is no real equivalent for the opposite (there is Kouhai but it's not used at all in the same way).
- smhost 10y agoHow is "kouhai" used? Is it not the same as hoobae (Korean)?
- Kretiini 10y agoI don't know any Korean, but the difference in Japanese is that you (generally) don't address people with kōhai. The younger one usually says '<name>-senpai' or 'senpai', the elder just '<name>'. They're really not that different.
- thaumasiotes 10y ago> The younger one usually says '<name>-senpai' or 'senpai', the elder just '<name>'. Really? I thought use of a bare name was only for intimate relationships.
- jrockway 10y ago<name> here is the family name, which in a language without idiomatic spoken pronouns, is how you talk about people.
- dlgeek 10y agoThe entire site hosting this is hilarious - it appears to be an April Fools parody of an academic tech conference and it's very well executed. "Submissions are double blind and author names must be removed. On the published copy, authors must be ordered by descending number of vowels."
- YeGoblynQueenne 10y agoThanks- I initially thought this was hosted on arxiv (it's on a MIT server). This paper from the same conference also looks good: http://sigtbd.csail.mit.edu/pubs/veryconference-paper5.pdf http://sigtbd.csail.mit.edu/pubs/veryconference-paper5.pdf "Locally Bijective, Non-Noetherian, Ultra-Liouville Random Variables and Parabolic Lie Theory" "Good" as in "it was probably generated by an LSTM RNN". Full papers listing here: http://sigtbd.csail.mit.edu/pubs/ http://sigtbd.csail.mit.edu/pubs/ And main conference page: http://sigtbd.csail.mit.edu/ http://sigtbd.csail.mit.edu/ For the benefit of other July fools like me :0 P.S. This one is of special interest to me: Evident Logic, a logic programming language based on a new logic, made special by "not the rules that it has, but the rules it lacks, so we wish the reader good luck in figuring that out": http://sigtbd.csail.mit.edu/pubs/veryconference-paper8.pdf http://sigtbd.csail.mit.edu/pubs/veryconference-paper8.pdf
- codeulike 10y agoAny interpersonal conflicts of interest must be declared in the form of a passive aggressive email sent to the PC chair. In the event an interpersonal conflict of interest is declared, the validity of the interpersonal conflict of interest will be determined by the PC. The best conflict of interest emails will be anonymized and includeed in the conference proceedings. If you are using LaTeX to typeset your paper, then we strongly suggest that you use this LaTeX class file (with the ‘sigtbd’ class option) and template. If you are using Microsoft Word, we recommend you give up on following any of the formatting requirements and submit in whatever format you please.
- s_m_t 10y agoThis already exists, it is called flirting. Given two socially well adjusted participants it allows either party to back down without hurting the other parties feelings and allows everyone to save face. The person escalating the flirtation doesn't feel bad because they aren't outright denied and the respondee isn't put in the awkward situation of having to deny someone. It also has the added benefit of allowing each person to get to know each other better and figure out if they actually have real 'chemistry' to begin with. Furthermore, attraction isn't binary, you might initially start chatting with someone with the intention of escalating the flirting process but figure out, hey, I just want to be friends with this person! With the SENPAI protocol you might just end up in an ill fated relationship with your would be friend
- fdsaaf 10y ago> Given two socially well adjusted participants So non-socially-well-adjusted, raised-on-the-internet types shouldn't get to date? Your comment is tautological and merely says that people who are good at dating are good at dating.
- waqf 10y agoYou might as well argue that the SENPAI paper implies that people who aren't comfortable with homomorphic encryption shouldn't get to date.
- GrumpyNl 10y agoWhile reading i had to scratch my head and ask myself, is this serious or is someone pulling my leg.
- obi1kenobi 10y agoThe paper was submitted to SIGTBD 2016. From the website (http://sigtbd.csail.mit.edu/ http://sigtbd.csail.mit.edu/): SIGTBD's emphases includes innovative, elegant (to the point of simplicity) and creative approaches for solving problems that are not traditionally served by the academic community. These problem spaces may be obsolete or unrealistic even by academic standards and are often of debatable research taste.
- GrumpyNl 10y agodlgeek 7 hours ago [-] The entire site hosting this is hilarious - it appears to be an April Fools parody of an academic tech conference and it's very well executed. "Submissions are double blind and author names must be removed. On the published copy, authors must be ordered by descending number of vowels." reply
- kazinator 10y ago先輩のが多きくて硬い。 カッコいい！
- qwertyuiop924 10y agoFirst the underwear sorting hat, and now this. MIT, never change.
- akanet 10y agoThis whole paper was great. It starts heavy on the humor but then also delivers just enough actual cryptographic protocol to make the lead-up worth it. This bit at the end was my favorite: As is noted in [1], if Alice simply suggests to Bob that they carry out a SENPAI exchange, this in and of itself is indicative of interest on Alice’s part. Thus, the only nonawkward way to actually use the SENPAI protocol is to assemble large groups of people, and have every pair of people carry out the protocol.
- iraphael 10y agoI'm interested in the consequences of, instead of "everyone" carrying out SENPAI, having a more efficient STB Matching System (Spin The Bottle). Sure, it could backfire: interested parties may fall victims of the universe's Random Number Generator, but it makes for some interesting Game Theory dynamics, which I call the Tinder Card Stack Dilemma. Any one party could be more willing to express interest in any of the other parties (assigned by STB), if they believe there is a low chance of them being matched with someone else they are more interested in. On the other hand, they could become more picky, and only express interest in parties they are very interested in, rejecting others because they believe there is a high chance of them being matched with greater interests. There is a definite trade off between efficiency and overall population happiness when choosing between STB and the solution described in the paper. Because STB is more efficient, it ends up being way more scale-able. But bigger populations greatly intensify the TCSD.
- deleted 10y ago[deleted]
- peterburkimsher 10y agoThe paper is very helpful for the arbitration of a "simple, binary phenomenon". Section 4.1 correctly investigates ternary responses. However, logic may only be used if a common GND is accepted. If Alice does not believe in absolute truth, there is no way that trust can be established. Analogue systems may not approach 1, only digital logic can provide "TRUE" love. Moral relativism is commonly professed. However, I theorise that an absolute 0 point can be readily established. "Is cheating in relationships always wrong?" If a common GND cannot be established this way, then the crush may be ended without wasting more time running the simulation.
- usmannk 10y agoIs the protocol described in Aaronson's algorithm actually sound? I can't seem to make sense of it myself. An example sequence would help.
- rhyzomatic 10y agoSuper fun paper. It seems like their modification to Aaronson's algorithm would also work for Yao's garbled circuits, i.e. 1. Alice generates a long random bitstring s, and publishes hash(s) 2. Alice crafts a garbled circuit with just one AND gate, where the false output is 0+s, and the true output is 1. Alice sends the circuit and her input to Bob. 3. Bob gets his input from Alice using oblivious transfer. He evaluates the circuit, publishing the result. 4. If the result starts with 0, Bob verifies that hash of the rest of the string matches the hash published by Alice. Alice also checks to make sure the rest of the string matches her original s.
- abetusk 10y agoTLDR; (fta) Alice and Bob should each learn the logical AND of their responses, and nobody should learn any other information The SENPAI protocol is proposing a way to do this with cryptography. There's a historical review of other proposed protocols (AMP, JMAP, MFP, SOAP, YGMP, SLP) along with their deficiencies. A SENPAI-MTT protocol is also considered that allows for non-binary interest (MTT=More Than Two). They propose foiling protocol cracking by quantum factoring by basing future SENPAI protocols on lattice based cryptographic methods.
- IshKebab 10y agoThis has already existed for ages using trusted third parties. A while ago on Facebook there were things were you could say which of your friends you fancy, and if you match it sends you both a message. The problem is there's no real disincentive just to say 'yes' to everyone, just to see who said yes back. Kind of like always swiping right on Tinder (although I'm sure they punish you for that in some way).
- samfisher83 10y agoWho is the Author of the paper? Usually people put that at the top.
- michaelmior 10y agoThis is a preprint from a conference with a double blind submission process, which is why the author names are not present. According to the agenda the authors are S. Dukhovni, J. Weisblat, and I. Chung.
- samfisher83 10y agoI can't find these people using google.
- oceliker 10y agoThey are undergraduates at the EECS department.
- nialv7 10y agoUhm, how do one compute the cubic root of x^3 modulo N?